发表于 | 分类于

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
1
 \
  2
 /
3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

解法1：Iterative version 用stack

递归的就不写了，实在太简单。
用stack的方法的关键点在于，每一条路劲在探寻最左元素的时候，要把所有的parent node都push到stack中。
如果当前的路径到头了之后，从stack里pop出上一个parent，然后移步到右边。
注意终止条件是需要node！= null同时stack不为空。
C++

1

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            // push all left nodes into stack
            while (current != null) {
                res.add(current.val);
                stack.push(current);
                current = current.left;
            }
            if (!stack.isEmpty()) {
                TreeNode temp = stack.pop();
                current = temp.right;   // move to the right cell
            }
        }
        return res;
    }
}

发表于 | 分类于

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1
2
3
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1
1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

解法1：

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        // 找规律发现是一个fibb sequence
        int curr = 0, sum = 0;
        for (int i = 2; i < A.length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                curr += 1;
                sum += curr;
            } else {
                curr = 0;
            }
        }
        return sum;
    }
}

发表于 | 分类于

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

Example 1:
s = “abc”, t = “ahbgdc”

Return true.

Example 2:
s = “axc”, t = “ahbgdc”

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

解法1：O(N) 解法

用两个指针一前一后的分别指向string的位置。如果两个字符相等就同前进，如果不相等，那么只前进target的指针，因为subsequence可以要求是不连续的。
然后判断一下s的指针时候到尾巴了就可以了。如果t到尾巴了还没有结果，则说明答案是false。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean isSubsequence(String s, String t) {
        if ((s == null && t == null) || (s.length() == 0)) {
            return true;
        }
        if (s.length() > t.length()) {
            return false;
        }
        int i = 0, j = 0;
        while (j < t.length()) {
            if (t.charAt(j) == s.charAt(i)) {
                i++;
                if (i == s.length()) return true;
            }
            j++;
        }
        return false;
    }
}

发表于 | 分类于

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

1
2
3
4
5
6
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.

Example 2:

1
2
3
4
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Note:

1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

解法1：

是同时维护两个dp而相互update的一类题目。
用max，min分别表示对于[i,j]范围的一组数，先手的player能取到的最大和最小值。
要注意： min对于[i,i]就为0
max对于[i,j]的递推公式是，如果取尾巴，那么再取下一步一定是取[i, j -1]的最小值。
如果取头部，那么再取一定是取[i - 1, j]的最小值。
min对于[i, j]的递推公式是，当对手取了[i]或者[j]之后，剩下的矩阵取一个最大值.
要注意更新矩阵的时候是按对角线更新。

C++

1

Java

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
public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int n = nums.length;
        // max and min points if the array is [i, j]
        int[][] max = new int[n][n];
        int[][] min = new int[n][n];
        for (int i = 0; i < n; i++) {
            max[i][i] = nums[i];
            min[i][i] = 0;  // min is player gets nothing
        }
        // Need to fill the dp matrix diagonally
        for (int diff = 1; diff < n; diff++) {
            for (int start = 0; start < n - diff; start++) {
                int end = start + diff;
                max[start][end] = Math.max(nums[end] + min[start][end - 1], nums[start] + min[start + 1][end]);
                min[start][end] = Math.min(max[start][end - 1], max[start + 1][end]);
            }
        }
        // Check which player gets higher score
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return max[0][n - 1] >= sum - max[0][n - 1];
    }
}

发表于 | 分类于

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:

1
2
3
4
5
6
7
8
9
10
11
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.

Note:

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

解法1：

用dfs + memo的想法来解决。
用一个map来记录对于一个子数组和一个相对应的和，有多少种方法可以计算出相对应的和。
然后进行dfs遍历，对于每一个元素，有+和-两种办法加和到总和之中，然后再进行下一步遍历。
直到遍历到数组的最后一个，只需要判断最后一个元素是否是所剩和的+/-就可。
C++

1

Java

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
public class Solution {
    // key will be pos and targetSum
    HashMap<List<Integer>, Integer> map = new HashMap<>();
    public int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return dfs(nums, 0, S);
    }
    private int dfs(int[] nums, int pos, int S) {
        List<Integer> key = new ArrayList<Integer>(Arrays.asList(pos, S));
        if (map.containsKey(key)) {
            return map.get(key);
        }
        if (pos == nums.length - 1) {
            int res = 0;
            if (nums[pos] == S) {
                res++;
            }
            if (nums[pos] == S * (-1)) {
                res++;
            }
            return res;
        }
        int res = 0;
        res += dfs(nums, pos + 1, S - nums[pos]);
        res += dfs(nums, pos + 1, S + nums[pos]);
        map.put(key, res);  
        return res;
    }
}

发表于 | 分类于

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

1
2
3
Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

1
2
3
Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

The length of the array won’t exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

解法1：O(N^2)

Subarray Sum的题目考虑用prefix sum解决，先计算每一个prefix sum，然后再遍历每一个subarray来寻找满足条件的最大答案。
C++

1

Java

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
public class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        // prefix sum
        int[] dp = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        // check if there is a sum - prefix that is n * k
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j < i - 1; j++) {
                int temp = dp[i] - dp[j];
                if (k == 0 && temp == 0) {
                    return true;
                } else if (k != 0 && temp % k == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

发表于 | 分类于

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:

1
2
3
4
5
6
7
Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

1
2
3
4
5
6
7
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.

解法1：

用了一个DFS + memo的做法，基本思路是去尝试每一个deal，当needs全都满足的时候更新一下最小的cost。
要注意的是用一个memo table去记录已经探寻过的一种needs对应的cost。
同时对每一个needs要考虑是否不用任何一个deal，就是说对于每个商品单独相加花费更少。
C++

1

Java

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class Solution {
    Map<List<Integer>, Integer> map = new HashMap<>();
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int res = dfs(price, special, needs);
        return res;
    }
    private int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        if (map.containsKey(needs)) {
            return map.get(needs);
        }
        int fulfilledStatus = fulfilled(needs);
        if (fulfilledStatus == 1) {
            return 0;
        }
        if (fulfilledStatus == -1) {
            // Invalid Move;
            return Integer.MAX_VALUE;
        }
        int min = Integer.MAX_VALUE;
        for (List<Integer> deal : special) {
            List<Integer> updatedNeeds = useDeal(needs, deal);
            if (updatedNeeds != null) {
                int temp = dfs(price, special, updatedNeeds);
                min = Math.min(min, temp + deal.get(deal.size() - 1));
            }
        }
        // check if needs can be fulfilled with single purchases
        min = Math.min(min, useNoDeal(price, needs));
        map.put(needs, min);
        return min;        
    }
    private int useNoDeal(List<Integer> price, List<Integer> needs) {
        int sum = 0;
        for (int i = 0; i < price.size(); i++) {
            sum += price.get(i) * needs.get(i);
        }
        return sum;
    }
    private List<Integer> useDeal(List<Integer> needs, List<Integer> deal) {
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < needs.size(); i++) {
            int left = needs.get(i) - deal.get(i);
            if (left < 0) {
                return null;
            }
            res.add(left);
        }
        return res;
    }
    private int fulfilled(List<Integer> needs) {
        for (int need : needs) {
            if (need > 0) {
                return 0;
            } else if (need < 0) {
                return -1;
            }
        }
        return 1;
    }
}

发表于 | 分类于

Given a 2D grid, each cell is either a wall ‘W’, an enemy ‘E’ or empty ‘0’ (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.

Example:

1
2
3
4
5
6
7
For the given grid
0 E 0 0
E 0 W E
0 E 0 0
return 3. (Placing a bomb at (1,1) kills 3 enemies)

解法1：

C++

1

Java

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 {
    public int maxKilledEnemies(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int rowCount = 0;
        int[] colCount = new int[n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0 || grid[i][j - 1] == 'W') {
                    rowCount = 0;
                    for (int k = j; k < n && grid[i][k] != 'W';k++) {
                        rowCount += grid[i][k] == 'E' ? 1 : 0;
                    }
                }
                if (i == 0 || grid[i - 1][j] == 'W') {
                    colCount[j] = 0;
                    for (int k = i; k < m && grid[k][j] != 'W'; k++) {
                        colCount[j] += (grid[k][j] == 'E' ? 1 : 0);
                    }
                }
                if (grid[i][j] == '0') {
                    res = Math.max(res, rowCount + colCount[j]);
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext.

The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

next() - if the original string still has uncompressed characters, return the next letter; Otherwise return a white space.
hasNext() - Judge whether there is any letter needs to be uncompressed.

Note:
Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details.

Example:

StringIterator iterator = new StringIterator(“L1e2t1C1o1d1e1”);

iterator.next(); // return ‘L’
iterator.next(); // return ‘e’
iterator.next(); // return ‘e’
iterator.next(); // return ‘t’
iterator.next(); // return ‘C’
iterator.next(); // return ‘o’
iterator.next(); // return ‘d’
iterator.hasNext(); // return true
iterator.next(); // return ‘e’
iterator.hasNext(); // return false
iterator.next(); // return ‘ ‘

解法1：

思路比较好想。用一个count记录当前字符还剩下的个数，另一个用pos记录在compressedString里面扫描到的位置。
要注意的是在判断hasNext的时候要check count！=0
C++

1

Java

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
public class StringIterator {
    int pos = 0;
    char prev = ' ';
    int count = 0;
    String data = null;
    public StringIterator(String compressedString) {
        this.data = compressedString;
    }
    public char next() {
        if (!hasNext()) {
            return ' ';
        }
        if (count == 0) {
            prev = data.charAt(pos++);
            int tempCount = 0;
            while (pos < data.length() && Character.isDigit(data.charAt(pos))) {
                tempCount = tempCount * 10 + data.charAt(pos) - '0';
                pos++;
            }
            count = tempCount;
        }
        count--;
        return prev;        
    }
    public boolean hasNext() {
        return pos < data.length() || count != 0;
    }
}
/**
 * Your StringIterator object will be instantiated and called as such:
 * StringIterator obj = new StringIterator(compressedString);
 * char param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

发表于 | 分类于

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

1
2
3
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

解法1：

对于subsequence的题目，经常会用到two pointer，一种是从两头像中间靠拢，另一种是前后两个指针按照条件和数字的变化不停的移动。这题就属于后者。
C++

1

Java

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
public class Solution {
    public int findLHS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int res = 0;
        int left = 0, right = 1;
        while (right < nums.length) {
            if (nums[right] - nums[left] > 1) {
                left++;
            } else if (nums[right] - nums[left] < 1) {
                right++;
            } else {
                right++;
                // update the max length of the subarray
                res = Math.max(res, right - left);
            }
        }
        return res;
    }
}