string probs

keon · keon · commit ee490c18152c · 2016-12-08T15:55:23.000-05:00
diff --git a/array/plus_one.py b/array/plus_one.py
@@ -4,25 +4,25 @@
 # The digits are stored such that the most significant
 # digit is at the head of the list.
 
-# def plusOne(digits):
-    # """
-    # :type digits: List[int]
-    # :rtype: List[int]
-    # """
-    # digits[-1] = digits[-1] + 1
-    # res = []
-    # ten = 0
-    # i = len(digits)-1
-    # while i >= 0 or ten == 1:
-        # sum = 0
-        # if i >= 0:
-            # sum += digits[i]
-        # if ten:
-            # sum += 1
-        # res.append(sum % 10)
-        # ten = sum / 10
-        # i -= 1
-    # return res[::-1]
+def plusOne(digits):
+    """
+    :type digits: List[int]
+    :rtype: List[int]
+    """
+    digits[-1] = digits[-1] + 1
+    res = []
+    ten = 0
+    i = len(digits)-1
+    while i >= 0 or ten == 1:
+        sum = 0
+        if i >= 0:
+            sum += digits[i]
+        if ten:
+            sum += 1
+        res.append(sum % 10)
+        ten = sum / 10
+        i -= 1
+    return res[::-1]
 
 
 def plus_one(digits):
diff --git a/matrix/pacific_atlantic.py b/matrix/pacific_atlantic.py
@@ -0,0 +1,65 @@
+# Given an m x n matrix of non-negative integers representing
+# the height of each unit cell in a continent,
+# the "Pacific ocean" touches the left and top edges of the matrix
+# and the "Atlantic ocean" touches the right and bottom edges.
+
+# Water can only flow in four directions (up, down, left, or right)
+# from a cell to another one with height equal or lower.
+
+# Find the list of grid coordinates where water can flow to both the
+# Pacific and Atlantic ocean.
+
+# Note:
+# The order of returned grid coordinates does not matter.
+# Both m and n are less than 150.
+# Example:
+
+# Given the following 5x5 matrix:
+
+  # Pacific ~   ~   ~   ~   ~
+       # ~  1   2   2   3  (5) *
+       # ~  3   2   3  (4) (4) *
+       # ~  2   4  (5)  3   1  *
+       # ~ (6) (7)  1   4   5  *
+       # ~ (5)  1   1   2   4  *
+          # *   *   *   *   * Atlantic
+
+# Return:
+
+# [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
+# (positions with parentheses in above matrix).
+
+def pacific_atlantic(matrix):
+    """
+    :type matrix: List[List[int]]
+    :rtype: List[List[int]]
+    """
+    n = len(matrix)
+    if not n: return []
+    m = len(matrix[0])
+    if not m: return []
+    res = []
+    atlantic = [[False for _ in range (n)] for _ in range(m)]
+    pacific =  [[False for _ in range (n)] for _ in range(m)]
+    for i in range(n):
+        DFS(pacific, matrix, float("-inf"), i, 0)
+        DFS(atlantic, matrix, float("-inf"), i, m-1)
+    for i in range(m):
+        DFS(pacific, matrix, float("-inf"), 0, i)
+        DFS(atlantic, matrix, float("-inf"), n-1, i)
+    for i in range(n):
+        for j in range(m):
+            if pacific[i][j] and atlantic[i][j]:
+                res.append([i, j])
+    return res
+
+def DFS(grid, matrix, height, i, j):
+    if i < 0 or i >= len(matrix) or j < 0 or  j >= len(matrix[0]):
+        return
+    if grid[i][j] or matrix[i][j] < height:
+        return
+    grid[i][j] = True
+    DFS(grid, matrix, matrix[i][j], i-1, j)
+    DFS(grid, matrix, matrix[i][j], i+1, j)
+    DFS(grid, matrix, matrix[i][j], i, j-1)
+    DFS(grid, matrix, matrix[i][j], i, j+1)
diff --git a/queue/reconstruct_queue.py b/queue/reconstruct_queue.py
@@ -0,0 +1,29 @@
+# Suppose you have a random list of people standing in a queue.
+# Each person is described by a pair of integers (h, k),
+# where h is the height of the person and k is the number of people
+# in front of this person who have a height greater than or equal to h.
+# Write an algorithm to reconstruct the queue.
+
+# Note:
+# The number of people is less than 1,100.
+
+# Example
+
+# Input:
+# [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
+
+# Output:
+# [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
+
+def reconstruct_queue(people):
+    """
+    :type people: List[List[int]]
+    :rtype: List[List[int]]
+    """
+    queue = []
+    people.sort(key=lambda x: (-x[0], x[1]))
+    for h, k in people:
+        queue.insert(k, (h, k))
+    return queue
+
+
diff --git a/string/reverse_vowel.py b/string/reverse_vowel.py
@@ -1,8 +1,17 @@
 
-def isVowel(c):
-    pass
-
-def reverseVowel(s):
-    i, j = 0, len(s)
+def reverse_vowel(s):
+    vowels = "AEIOUaeiou"
+    i, j = 0, len(s)-1
+    s = list(s)
     while i < j:
+        while i < j and s[i] not in vowels:
+            i += 1
+        while i < j and s[j] not in vowels:
+            j -= 1
+        s[i], s[j] = s[j], s[i]
+        i, j = i + 1, j - 1
+    return "".join(s)
 
+test = "hello"
+print(test)
+print(reverse_vowel(test))
diff --git a/string/reverse_words.py b/string/reverse_words.py
@@ -1,14 +1,33 @@
 
-
-
-def reverse(array):
-    i, j = 0, len(array)
+def reverse(array, i, j):
     while i < j:
         array[i], array[j] = array[j], array[i]
         i += 1
         j -= 1
 
-def reverseWords(array):
-    reverse(array)
+def reverse_words(string):
+    arr = list(string)
+    n = len(arr)
+    reverse(arr, 0, n-1)
+
+    start = None
+    for i in range(n-1):
+        if arr[i] == " ":
+           if start:
+                reverse(arr, start, i-1)
+                start = None
+        elif i == n-1:
+            if start:
+                reverse(arr, start, i)
+        else:
+            if not start:
+                start = i
+    return "".join(arr)
+
+test = "I am keon kim and I like pizza"
+print(test)
+print(reverse_words(test))
+
+
 
 
diff --git a/tree/is_subtree.py b/tree/is_subtree.py
@@ -0,0 +1,69 @@
+# Given two binary trees s and t, check if t is a subtree of s.
+# A subtree of a tree t is a tree consisting of a node in t and
+# all of its descendants in t.
+
+# Example 1:
+
+# Given s:
+
+     # 3
+    # / \
+   # 4   5
+  # / \
+ # 1   2
+
+# Given t:
+
+   # 4
+  # / \
+ # 1   2
+# Return true, because t is a subtree of s.
+
+# Example 2:
+
+# Given s:
+
+     # 3
+    # / \
+   # 4   5
+  # / \
+ # 1   2
+    # /
+   # 0
+
+# Given t:
+
+     # 3
+    # /
+   # 4
+  # / \
+ # 1   2
+# Return false, because even though t is part of s,
+# it does not contain all descendants of t.
+
+# Follow up:
+# What if one tree is significantly lager than the other?
+
+
+def is_subtree(big, small):
+    flag = False
+    queue = collections.deque()
+    queue.append(big)
+    while queue:
+        node = queue.popleft()
+        if node.val == small.val:
+            flag = comp(node, small)
+            break
+        else:
+            queue.append(node.left)
+            queue.append(node.right)
+    return flag
+
+def comp(p, q):
+    if not p and not q:
+        return True
+    if p and q:
+        return p.val == q.val and comp(p.left,q.left) and comp(p.right, q.right)
+    return False
+
+
