发表于 | 分类于

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.

Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn’t have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.

The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.

The right-most node is also defined by the same way with left and right exchanged.

Example 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input:
  1
   \
    2
   / \
  3   4
Ouput:
[1, 3, 4, 2]
Explanation:
The root doesn't have left subtree, so the root itself is left boundary.
The leaves are node 3 and 4.
The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
So order them in anti-clockwise without duplicates and we have [1,3,4,2].

Example 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input:
    ____1_____
   /          \
  2            3
 / \          / 
4   5        6   
   / \      / \
  7   8    9  10  
       
Ouput:
[1,2,4,7,8,9,10,6,3]
Explanation:
The left boundary are node 1,2,4. (4 is the left-most node according to definition)
The leaves are node 4,7,8,9,10.
The right boundary are node 1,3,6,10. (10 is the right-most node).
So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

解法1：

参考了这篇的解法。
对于leaf我们可以用dfs来解决。似乎还需要两个function分别来存储left path和right path。那么在找寻left path的过程中，我们一直向左，如果碰到左面的节点就属于left path，如果还有右节点那么就用dfs搜索leaf。
对于right path也是一个原理。
对于rightPath函数的写法，要注意对于每一个节点，要先得出leaf node，再得出right node。因为题目要求是逆时针
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
/**
 * 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> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        res.add(root.val);
        leftPath(root.left, res);
        rightPath(root.right, res);
        
        return res;
    }
    
    private void leftPath(TreeNode root, List<Integer> res) {
        if (root != null) {
            res.add(root.val);
            if (root.left != null) {
                leftPath(root.left, res);
                dfs(root.right,res);
            } else {
                leftPath(root.right, res);
            }
        }
    }
    
    private void rightPath(TreeNode root, List<Integer> res) {
        
        if (root != null) {
            if (root.right != null) {
                dfs(root.left, res);	// 这里的顺序要注意
                rightPath(root.right, res);
            } else {
                rightPath(root.left, res);
            }
            res.add(root.val);
        }
    }
    
    private void dfs(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        
        if (root.left == null && root.right == null) {
            res.add(root.val);
            return;
        }
        dfs(root.left, res);
        dfs(root.right, res);
    }
}

发表于 | 分类于

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

alt text
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

解法1: 两遍扫描 O(N) Time O(N) Space

这题和Product of Array except itself有点类似。对于每一个bar，顶端是否能储水取决于左面和右面是否有比它高的bar，假设有而且较低的bar的高度是h，那么对于现在这个bar能储水的量就是h-height。
由此我们可以得出一个思路：对于每一个bar，计算出左边和右边的最高的bar。
在计算右面的bar的时候，我们不必要维护一个新的数组，而是用一个变量就可以了。
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 {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] heights) {
        // write your code here
        
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        int n = heights.length;
        
        if (n < 3) {
            return 0;
        }
        
        
        int[] leftHeight = new int[heights.length];
        
        for (int i =1; i < n; i++) {
            leftHeight[i] = Math.max(leftHeight[i - 1], heights[i - 1]);
        }
        
        int rightHeight = 0;
        
        int sum = 0;
        for (int i = n - 2; i >= 0; i--) {
            rightHeight = Math.max(rightHeight, heights[i + 1]);
            sum += Math.max(0, Math.min(leftHeight[i], rightHeight) - heights[i]);
        }
        
        return sum;
        
    }
}

解法2：Stack, O(N) Time O(N) Space

这题也可以用stack来做。但感觉stack比较容易错。
stack的思路是，要存水必须有一个凹槽。那么我们用stack维护一个递减的数列，遇到比现在的top的数更大的时候就知道有水可以存储了。
当前的top即是凹槽的底，弹出top之后如果还不是空，则继续比较top和当前的bar的高度，如果当前bar还高，那么存储的水就是top - bottom 乘上距离。
这里有一个地方容易错就是，如果当前的height不比top高，那么这个时候也要存储结果。
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
public class Solution {
    public int trap(int[] height) {
        
        if (height == null || height.length == 0) {
            return 0;
        }
        
        if (height.length < 3) {
            return 0;
        }
        
        // Stack stores the index of a element in the array
        Stack<Integer> stack = new Stack<Integer>();
        
        stack.push(0);
        
        int res = 0;
        for (int i = 1; i < height.length; ++i) {
            if (height[i] > height[stack.peek()]) {
                int bottom = height[stack.peek()];
                stack.pop();
                while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                    res += (height[stack.peek()] - bottom) * (i - stack.peek() - 1);
                    bottom = height[stack.pop()];
                }
                if (!stack.isEmpty()) {
                    res += (height[i] - bottom) * ( i - stack.peek() - 1);	//这地方容易漏掉
                }
            }
            stack.push(i);
        }
        return res;
    }
}

发表于 | 分类于

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);
// Returns false as 2 does not exist in the set.
randomSet.remove(2);
// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);
// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();
// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);
// 2 was already in the set, so return false.
randomSet.insert(2);
// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

解法1：Two HashMaps

这题如果没有getRandom的话用一个set就可以解决了。因为加上了getRandom，那么需要用一些方法来存储每一个数字对应的index。由此就想到用两个hashmap来存储数字和他位置的对应关系。insert比较好解决，就是把对应关系加入两个map中。remove稍微复杂一点，首先将对应的数字pair从两个map中移除。
如果说移除的是最后一个元素或者是唯一一个元素，移除之后不需要对map额外处理。如果是移除的当中的某个元素。那么移除之后他们的index就不是连续的了。这个时候就要额外的来处理一下。因为要把最后一位的元素对应的位置-1， 那么我们可以把最后一位元素对应的位置放到刚才删除的元素的位置上。然后更新存储位置的hashmap就可以了。
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
public class RandomizedSet {
    private Map<Integer, Integer> valueIndex;
    private Map<Integer, Integer> indexValue;
    private Random rand;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        valueIndex = new HashMap<Integer, Integer>();
        indexValue = new HashMap<Integer, Integer>();
        rand = new Random(System.currentTimeMillis());
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (valueIndex.containsKey(val)) {
            return false;
        } else {
            int index = valueIndex.size();
            valueIndex.put(val, index);
            indexValue.put(index, val);
            return true;
        }
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (valueIndex.containsKey(val)) {
            int index = valueIndex.get(val);
            valueIndex.remove(val);
            indexValue.remove(index);
            
            if (valueIndex.isEmpty() || index == valueIndex.size()) {
                return true;
            }
            
            // if delete from the middle,
            // put the last element into the middle
            int last = indexValue.get(indexValue.size());
            valueIndex.put(last, index);
            indexValue.remove(indexValue.size());
            indexValue.put(index, last);
            return true;
        } else {
            return false;
        }
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        if (valueIndex.isEmpty()) {
            return -1;
        } else if (valueIndex.size() == 1) {
            return indexValue.get(0);
        } else {
            int index = rand.nextInt(valueIndex.size());
            return indexValue.get(index);    
        }
    }
}
/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

发表于 | 分类于

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

解法1：O(N) Time + O(1) Space

把题目分成两个小问题来解决。except self换句话说就是左面的和右面的乘积。
那么从左面扫一遍得到一组数，从右面扫一遍得到一组数。然后把左右两组数相乘便是答案。
一个小要求是需要O(1)的space。在从右面扫描的时候我们不用维护一个数组，而是用一个变量product来记录现在的乘积。
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
public class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        if (nums == null || nums.length == 0) {
            return nums;
        }
        
        int[] res = new int[nums.length];
        // from left to right
        res[0] = 1;
        for (int i = 1; i < nums.length; ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        
        int product = 1;
        
        // from right to left
        for (int i = nums.length - 1; i >= 0; --i) {
            res[i] = res[i] * product;
            product = product * nums[i];
        }
        
        return res;
    }
}

发表于 | 分类于

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

1
2
3
4
5
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example:

1
2
3
Input: "cbbd"
Output: "bb"

解法1：DP: O(N^2)

字符串的问题，如果牵涉到substring(i,j)的，要是往dp方向上考虑就需要用二维的。这题也不例外。
dp[i][j]表示的是，(i,j)这个字符串是否是palindrome。
有三种情况可以考虑，一个是i == j, 一个是相邻，还有一个是距离大于2。
每次找到一个palindrome的时候都更新下max，同时也更新一下res的string。
要注意的是我们要求矩阵从下往上搜索，并且j >= i, 所以我们只搜索了上半部的矩阵。
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
public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] state = new boolean[n][n];
        int maxlen = Integer.MIN_VALUE;
        String res = "";
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    state[i][j] = true;
                } else if (j == i + 1) {
                    state[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    state[i][j] = s.charAt(i) == s.charAt(j) && state[i + 1][j - 1];
                }
                if (state[i][j]) {
                    int len = j - i + 1;
                    if (len > maxlen) {
                        maxlen = len;
                        res = s.substring(i, j + 1);
                    }
                }
            }
        }
        return res;
    }
}

解法2：O(n^2) Time, O(1) Space

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
class Solution {
    public String longestPalindrome(String s) {
        if (s == null) {
            return s;
        }
        // loop through each possible expanding center
        int start = 0, end = 0;
        int maxLen = Integer.MIN_VALUE;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    private int expand(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

发表于 | 分类于

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解法1：

这个答案对我的启发比较大，主要可以用于一类题目。
思路是用一个hashtable维护出现过的字母的位置，只存储上一次出现过的位置。
那么如果遇到还未出现过的字符则直接向前进，如果遇到出现过的字符那么需要比较当前的substring的长度和max。
同时，需要移动left指针，因为从left开始到right部分已经不符合要求了。left需要移动到上一次出现的位置+1.
注意这里有个坑：因为可能出现上一次的位置比现在left的位置还好往后，要保证left只进不退，只能用left = Math.max(left, last_pos)来保证。
还有一个坑，就是在最后一步还需要判断max和当前right - left的大小的比较。
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 int lengthOfLongestSubstring(String s) {
        
        int[] table = new int[256];
        Arrays.fill(table, -1);
        
        int left = 0, right = 0;
        int max = 0;
        while (right < s.length()) {
            int current_char = (int)s.charAt(right);
            int last_pos = table[current_char];
            if (last_pos != -1) {
                max = Math.max(right - left, max);
                // move left pointer
                left = Math.max(left, table[current_char] + 1);
                table[current_char] = right;
            } else {
                table[current_char] = right;
            }
            ++right;
        }
        
        return Math.max(max, right - left);
        
    }
}

发表于 | 分类于

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Show Company Tags
Show Tags

解法1：特殊解法　

如果是out-of-place的解法，就用
temp[j][n - 1 - j] = matrix[i][j]

如果要inplace的解法：可以有这么几种：

  • 先按逆对角线翻转一次，然后按ｘ轴中线翻转一次。
  • 或者呢也可以先transpose，然后把每一行翻转。
    个人感觉第二种解法比较好记也比较好写。不容易出错

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
public class Solution {
    public void rotate(int[][] matrix) {
        
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        
        int n = matrix.length;
        // flip along /
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < n - 1 - i; ++j) {
               swap(matrix, i, j, n - 1 - j, n - 1 - i);
            }
        }
        
        // flip between 
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix, i, j, n - 1 - i, j);
            }
        }
        
        return;
    }
    
    private void swap(int[][] matrix, int ix, int iy, int jx, int jy) {
        int temp = matrix[ix][iy];
        matrix[ix][iy] = matrix[jx][jy];
        matrix[jx][jy] = temp;
        return;
    }
}

发表于 | 分类于

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given

1
2
s = "leetcode",
dict = ["leet", "code"].

Return true because “leetcode” can be segmented as “leet code”.

解法1：DP O(N^2)

经典的用DP的问题，用一个dp数组来记录。dp[i]表示前i个字符是否可能分词。
所以对于每一个dp[i], dp[i] = true if word(0,i) in dict, or dp[k] = true && word(k, i) in dict
这题的坑在于java的substring比较坑，string.substring(j,k)表示从第j个字符到第k-1个字符所组成的substring。
我们这里需要用word(k,i)表示的是第k+1个字符到第i-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
public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        
        if (s == null || s.isEmpty() || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        
        // convert to set
        Set<String> set = new HashSet<String>();
        for (String word: wordDict) {
            set.add(word);
        }
        
        
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            if (set.contains(s.substring(0,i))) {
                dp[i] = true;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (dp[j] && set.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        
        return dp[s.length()];
        
    }
}

发表于 | 分类于

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

解法1：PriorityQueue, O(NlogK), Space O(K)

一种解法是很直观的用heap来解决，维护一个大小为k的堆。因为每次insert的操作的时间复杂度是O(logK), 一共要遍历N个元素。
最后取出顶元素即可。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k);
        
        for (int num: nums) {
            queue.offer(num);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        
        return queue.poll();
    }
}

解法2：比较优解 Quick Select, Average O(N), worst O(N^2), Space O(1)

主要是用到了Quick Select中一次partition就可以知道pivot在array中的具体位置，假设是X。
那么如果X == k, 我们要求的就求道了。假设是X < k, 那么我们只需要在右半边找，反之就在左半边找。
要掌握partition函数的写法。
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
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        if (k <= 0) {
            return 0;
        }
        
        return helper(nums, nums.length - k + 1, 0, nums.length - 1);
        
    }
    
    private int helper(int[] nums, int k, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        
        int p = partition(nums, start, end);
        if (p + 1 == k) {
            return nums[p];
        } else if (p + 1 < k) {
            return helper(nums, k, p + 1, end);
        } else {
            return helper(nums, k, start, p - 1);
        }
    }
    
    private int partition(int[] nums, int start, int end) {
        int pivot = nums[end];
        int index = start;
        for (int i = start; i < end; ++i) {
            if (nums[i] < pivot) {
                swap(nums, index, i);
                ++index;
            }
        }
        swap(nums, end, index);
        return index;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

发表于 | 分类于

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解法1：O(N + M) Time + O(1) Space

这题的坑是leetocde的OJ可能会TLE，要用tail.next = new ListNode(temp)就可以过了。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        int carry = 0;
        
        while (l1 != null && l2 != null) {
            int val = l1.val + l2.val + carry;
            int digit = val % 10;
            carry = val / 10;
            ListNode temp = new ListNode(digit);
            tail.next = temp;
            tail = tail.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        
        while (l1 != null) {
            int val = l1.val + carry;
            int digit = val  % 10;
            carry = val / 10;
            tail.next = new ListNode(digit);
            tail = tail.next;
            l1 = l1.next;
        }
        
        while (l2 != null) {
            int val = l2.val + carry;
            int digit = val % 10;
            carry = val / 10;
            tail.next = new ListNode(digit);
            tail = tail.next;
            l2 = l2.next;
        }
        
        if (carry != 0) {
            tail.next = new ListNode(carry);
        }
        return dummy.next;
        
    }
}