Posted on | In

494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Idea

counting problems, max min problems are always involved with DP.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        # cache[(i, s)] the number of combination sum up to s from nums[i] to nums[n - 1]
        def findTarget(i, s):
            if (i, s) not in cache:
                r = 0
                if i == len(nums): # base case
                    if s == 0: # the top of the figure, where number of solutions is 1.
                        r = 1
                else:
                    r = findTarget(i+1, s-nums[i]) + findTarget(i+1, s+nums[i])
                cache[(i, s)] = r
            return cache[(i, s)]
        cache = {}
        return findTarget(0, S)

Posted on | In

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

Idea

classical dfs problem

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res = []
        if not nums:
            return self.res
        self.dfs([], 0, nums)
        return self.res
        
    # return all the subset while start from pos in nums
    def dfs(self, subset, pos, nums):
        if pos > len(nums):
            return
        
        self.res.append(list(subset))
        for i in range(pos, len(nums)):
            subset.append(nums[i])
            self.dfs(subset, i+1, nums)
            subset.pop()

Posted on | In

211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord(“bad”)
addWord(“dad”)
addWord(“mad”)
search(“pad”) -> false
search(“bad”) -> true
search(“.ad”) -> true
search(“b..”) -> true

Idea

Trie (for add) + Dfs (for search)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class TrieNode():
    def __init__(self):
        self.children = {}
        self.isWord = False

class WordDictionary(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        
    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.isWord = True

    def search(self, word):
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        self.ans = False
        self.dfs(0, word, self.root)
        return self.ans

    def dfs(self, pos, word, root):
        if pos >= len(word):
            if root.isWord:
                self.ans = True
            return
        
        if word[pos] == '.':
            for c in root.children:
                self.dfs(pos+1, word, root.children[c])
        else:
            if word[pos] in root.children:
                self.dfs(pos+1, word, root.children[word[pos]])

Posted on | In

277. Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

Idea:

In fact, through api knows(a, b), one candidate can be screened. If knows(a, b) is true, a is not the celebrity, otherwise, b is not celebrity. The key idea here, is to make best use of the judgment from knows(a, b)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):

class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        for i in range(1, n):
            if knows(ans, i):
                ans = i
        print ans
                
        for i in range(0, n):
            if i == ans:
                continue
            if not knows(i, ans):
                return -1
            if knows(ans, i):
                return -1
            
        return ans

Posted on | In

683. K Empty Slots

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:
Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.
Example 2:
Input:
flowers: [1,2,3]
k: 1
Output: -1
Note:
The given array will be in the range [1, 20000].

Idea

Through treeset, we may find the ceiling and floor of the new pos, and we can check whether the new pos is k slots away from its ceiling or floor. If so, it’s the answer.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < flowers.length; i++) {
            int pos = flowers[i];
            Integer left = set.floor(pos - 1);
            Integer right = set.ceiling(pos + 1);
            if (left != null && left == pos - k - 1) {
                return i + 1;
            }
            if (right != null && pos == right - k - 1) {
                return i + 1;
            }
            set.add(pos);
        }
        return -1;
    }
}

Java

The ceiling(E e) method is used to return the least element in this set greater than or equal to the given element, or null if there is no such element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package com.tutorialspoint;

import java.util.Iterator;
import java.util.TreeSet;

public class TreeSetDemo {
   public static void main(String[] args) {

      // creating a TreeSet 
      TreeSet <Integer>treeadd = new TreeSet<Integer>();

      // adding in the tree set
      treeadd.add(12);
      treeadd.add(11);
      treeadd.add(16);
      treeadd.add(15);

      // getting ceiling value for 13
      System.out.println("Ceiling value for 13: "+treeadd.ceiling(13));   
   }     
}
# print: Ceiling value for 13: 15

The floor(E e) method is used to return the greatest element in this set less than or equal to the given element, or null if there is no such element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.tutorialspoint;

import java.util.TreeSet;

public class TreeSetDemo {
   public static void main(String[] args) {

      // creating a TreeSet 
      TreeSet <Integer>treeadd = new TreeSet<Integer>();

      // adding in the tree set
      treeadd.add(12);
      treeadd.add(11);
      treeadd.add(16);
      treeadd.add(15);

      // getting the floor value for 13
      System.out.println("Floor value for 13: "+treeadd.floor(13));   
   }    
} 
# print: Floor value for 13: 12

Posted on | In

314. Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

3
/\
/ \
9 20
/\
/ \
15 7

Output:

[
[9],
[3,15],
[20],
[7]
]
Examples 2:

Input: [3,9,8,4,0,1,7]

 3
/\

/ \
9 8
/\ /\
/ \/ \
4 01 7

Output:

[
[4],
[9],
[3,0,1],
[8],
[7]
]

Idea

the order:
Say, in example2,
[3, 0, 1], include the order from layer-layer and left-right in the same layer, which the bfs may achieve the requirement. Since, we may need the order vertical, we can perform bfs on a col que as well as nodes.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        que_node = [root]
        que_col = [0]
        dic_ = collections.defaultdict(list)
        dic_[0].append(root.val)
        
        while que_node:
            h = que_node.pop(0)
            c = que_col.pop(0)
            
            if h.left:
                que_node.append(h.left)
                que_col.append(c - 1)
                dic_[c - 1].append(h.left.val)
                
            if h.right:
                que_node.append(h.right)
                que_col.append(c + 1)
                dic_[c + 1].append(h.right.val)
        res = []
        for i in sorted(dic_.keys()):
            res.append(dic_[i])
            
        return res

Posted on | In

200. Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1
Example 2:

Input:
11000
11000
00100
00011

Output: 3

Idea

the template for bfs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// T 指代任何你希望存储的类型
Queue<T> queue = new LinkedList<>();
Set<T> set = new HashSet<>();

set.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
    T head = queue.poll();
    for (T neighbor : head.neighbors) {
        if (!set.contains(neighbor)) {
            set.add(neighbor);
            queue.offer(neighbor);
        }
    }
}

上述代码中：
neighbor 表示从某个点 head 出发，可以走到的下一层的节点。
set 存储已经访问过的节点（已经丢到 queue 里去过的节点）
queue 存储等待被拓展到下一层的节点
set 与 queue 是一对好基友，无时无刻都一起出现，往 queue 里新增一个节点，就要同时丢到 set 里。

The que stores the nodes of the previous level and then add the nodes of the next layer again and again til the end.
In the code below the visited matrix is the same as the set.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or len(grid) == 0:
            return 0
        
        self.grid = grid
        self.n, self.m = len(grid), len(grid[0])
        self.visited = [[False] * self.m for _ in range(self.n)]
        
        ans = 0
        for i in range(self.n):
            for j in range(self.m):
                if grid[i][j] == '1' and not self.visited[i][j]:
                    ans += 1
                    self.visited[i][j] = True
                    self.bfs(i, j)
        return ans
    
    def bfs(self, x, y):
        dzs = zip([1, 0, -1, 0], [0, 1, 0, -1])
        que = [(x, y)]
        while que:
            h = que.pop(0)
            for dz in dzs:
                x_, y_ = h[0] + dz[0], h[1] + dz[1]
                if self.isValid(x_, y_) and not self.visited[x_][y_]:
                    self.visited[x_][y_] = True
                    que.append((x_, y_))
                    
    def isValid(self, x, y):
        if x >= 0 and x <= self.n - 1 and \
            y >= 0 and y <= self.m - 1 and \
            self.grid[x][y] == '1':
                return True
        return False

Posted on | In

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: “A man, a plan, a canal: Panama”
Output: true
Example 2:

Input: “race a car”
Output:

Idea

the python string operations:
string1.join([….])
string2.lower()

Code

Mine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and (not (s[l].isalpha() or s[l].isdigit())):
                l += 1
            while l < r and (not (s[r].isalpha() or s[r].isdigit())):
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

more concise

1
2
3
4
5
6
7
8
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = ''.join([x for x in s if x.isalpha() or x.isdigit()]).lower()
        return s == s[::-1]

Posted on | In

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

Idea

  • two pointer
    firstly perform the sort operation

    1
    2
    3
    4
    5
    6
    7
    l, r = init1, init2
    if s(l, r) < target:
        l += 1
    elif s(l, r) > target:
        r -= 1
    else:
        ...

  • find next different number:

    1
    2
    3
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]: # find next different num1
            continue

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        nums = sorted(nums)
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]: # find next different num1
                continue
            # two pointers operations
            l, r = i + 1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    ans.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l + 1]: # find last same number as num2
                        l += 1
                    while l < r and nums[r] == nums[r - 1]: # find last same number as num3
                        r -= 1
                    l += 1 # find next different number
                    r -= 1 # find next different number
        return ans

Posted on | In

278. First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

Idea: binary search

template:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0, end = nums.length - 1;
        // 要点1: start + 1 < end
        while (start + 1 < end) {
	    // 要点2：start + (end - start) / 2
            int mid = start + (end - start) / 2;
            // 要点3：=, <, > 分开讨论，mid 不+1也不-1
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        // 要点4: 循环结束后，单独处理start和end
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        start, end = 1, n
        while start + 1 < end:
            mid = start + (end - start) / 2
            if isBadVersion(mid):
                end = mid
            else:
                start = mid
        if isBadVersion(start):
            return start
        return end