发表于 | 分类于

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

解法1：

用两个指针指向需要reverse的部分，再分别reverse。把string转化成char array之后比较好操作。
char array到string可以用new string(a)来转化。
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
public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        int start = 0, end = 0;
        char[] ch = s.toCharArray();
        while (end < ch.length) {
            if (ch[end] != ' ') {
                end++;
            } else {
                // reverse substring from start to end
                reverse(ch, start, end - 1);
                while (end < ch.length && ch[end] == ' ') {
                    end++;
                }
                start = end;
            }
        }
        reverse(ch, start, end - 1);
        return new String(ch);
    }
    private void reverse(char[] ch, int start, int end) {
        while (start < end) {
            char temp = ch[start];
            ch[start] = ch[end];
            ch[end] = temp;
            start++;
            end--;
        }
        return;
    }
}

发表于 | 分类于

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:
 Tree 1                     Tree 2                  
         1                         2                             
        / \                       / \                            
       3   2                     1   3                        
      /                           \   \                      
     5                             4   7                  
Output:
Merged tree:
      3
     / \
    4   5
   / \   \
  5   4   7

Note: The merging process must start from the root nodes of both trees.

解法1：

Tree最常见的divide & conquer思想，分成左右树。然后分别递归。
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
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        TreeNode node = null;
        if (t2 == null) {
            node = new TreeNode(t1.val);
            node.left = mergeTrees(t1.left, null);
            node.right = mergeTrees(t1.right, null);
        } else if (t1 == null) {
            node = new TreeNode(t2.val);
            node.left = mergeTrees(t2.left, null);
            node.right = mergeTrees(t2.right, null);
        } else {
            node = new TreeNode(t1.val + t2.val);
            node.left = mergeTrees(t1.left, t2.left);
            node.right = mergeTrees(t1.right, t2.right);
        }
        return node;
    }
}

发表于 | 分类于

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

解法1：

还是双指针。用一个慢指针p来记录下一个需要插入的位置。一开始快慢指针都在一起。然后比较快指针p所对应的元素与p-2所对应的元素。
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
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length <= 2) {
            return nums.length;
        }
        int p = 2, i = 2;
        while (i < nums.length) {
            if (nums[i] != nums[p - 2]) {
                nums[p++] = nums[i];
            }
            i++;
        }
        return p;
    }
}

发表于 | 分类于

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up:

Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

解法1：

这题的关键点在于要想到用状态机来存储过去的历史。如果一位上仅用0,1表示的话，那么只能表示两个状态。如果我们用2 bits（也就是0,1,2,3）来表示的话可以表示4个状态。
这里我们有
0 -> 0 : 0
1 -> 1 : 1
1 -> 0 : 2
0 -> 1 : 3
然后逐个扫描，根据规则update每一个元素。要注意的是判断live cell的时候要check两个数值，一个是1，一个是2。这个地方很容易错。
最后我们对结果数组对2取对数就可以了。
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
public class Solution {
    public void gameOfLife(int[][] board) {
        if (board.length == 0 || board[0].length == 0) {
            return;
        }
        int m = board.length, n = board[0].length;
        // define directions
        int[][] directions = new int[][]{{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cnt = 0;
                for (int k = 0; k < directions.length; k++) {
                    int row = i + directions[k][0];
                    int col = j + directions[k][1];
                    if (row >= 0 && row < m && col >= 0 && col < n && (board[row][col] == 1 || board[row][col] == 2)) {
                        cnt++;
                    }
                }
                if (board[i][j] == 1 && (cnt < 2 || cnt > 3)) {
                    board[i][j] = 2;
                } else if (board[i][j] == 0 && cnt == 3) {
                    board[i][j] = 3;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] %= 2;
            }
        }
        return;
    }
}

发表于 | 分类于

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

解法1：

Moore Voting 算法的延伸。 和Majority Element I类似，这里用两个变量来维护当前出现次数较大的数字。
对于第二个元素n2初始化为0是没关系的，因为他的计数器初始化为0。如果有数字和他一样的话计数器再加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
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int n1 = nums[0], n2 = 0, c1 = 0, c2 = 0;
        for (int num : nums) {
            if (num == n1) {
                c1++;
            } else if (num == n2) {
                c2++;
            } else if (c1 == 0) {
                n1 = num;
                c1 = 1;
            } else if (c2 == 0) {
                n2 = num;
                c2 = 1;
            } else {
                c1--;
                c2--;
            }
        }
        c1 = 0;
        c2 = 0;
        for (int num : nums) {
            if (num == n1) {
                c1++;
            } else if (num == n2) {
                c2++;
            }
        }
        if (c1 > nums.length / 3) {
            res.add(n1);
        }
        if (c2 > nums.length / 3) {
            res.add(n2);
        }
        return res;
    }
}

发表于 | 分类于

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

解法1：O(NlogN)

这题是一个binary search的变形。题目给的条件显示能套用的常用算法应该只剩下binary search了。
难点是怎么舍弃一半的空间。这里巧妙的用了这个特性：1 - n的数字的mid是（1+n)/2, 那么如果比mid小的数较多，说明重复的数在小半区。这样我们可以缩小范围。
如果比mid小的数较少，那么重复的数就在大半区。
计算出一个mid之后统计和mid大小的时候要遍历。
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 int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // loop through nums
            int cnt = 0;
            for (int num : nums) {
                if (num <= mid) {
                    cnt++;
                }
            }
            if (cnt > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

解法2：O(N)

龟兔赛跑的算法，和找闭环的入口的思路一样。这里用的是一个扩展了的算法。
核心就是对于slow指针apply function一次，而对于fast指针apply function两次。
具体的解释可以参考这个
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 findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }
        fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast) {
                break;
            }
        }
        return slow;
    }
}

发表于 | 分类于

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

解法1：

Binary Search的经典题。主要是要考虑怎么扔掉一半。
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 int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[start] == nums[mid]) {
                return mid;
            }
            if (nums[start] < nums[mid]) {
                if (target < nums[mid] && target >= nums[start]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (nums[end] == target) {
            return end;
        }
        if (nums[start] == target) {
            return start;
        }
        return -1;
    }
}

发表于 | 分类于

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2”,”4->5”,”7”].

解法1：

这题思路很简单，双指针。就是要写好写的没有bug不容易。
用一个j记录end的距离，然后在push到结果的时候检查j是否为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
public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<String>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int j = 1;
            while (i + j < n && nums[i + j] - nums[i] == j) {
                j++;
            }
            String range = j == 1 ? Integer.toString(nums[i]) : Integer.toString(nums[i]) + "->" + Integer.toString(nums[i + j - 1]);
            res.add(range);
            i += j;
        }
        return res;
    }
}

重写了一个清楚点的版本

lang: 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
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int start = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1] + 1) {
                res.add(getRange(nums[start], nums[i - 1]));
                start = i;
            }
        }
        res.add(getRange(nums[start], nums[nums.length - 1]));
        return res;
    }
    private String getRange(int start, int end) {
        if (start == end) {
            return Integer.toString(start);
        }
        return Integer.toString(start) + "->" + Integer.toString(end);
    }
}

发表于 | 分类于

Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.

Example 1:

1
2
3
4
5
6
7
Input:
[[1,2,3],
[4,5],
[1,2,3]]
Output: 4
Explanation:
One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Note:

Each given array will have at least 1 number. There will be at least two non-empty arrays.
The total number of the integers in all the m arrays will be in the range of [2, 10000].
The integers in the m arrays will be in the range of [-10000, 10000].

解法1： O(NM)

Maintain global min and max calculated from previous arrays and compare current min, max wrt to the global ones.
Results should be in Max(res, abs(global_min - current_max)) and Max(res, abs(global_max - current_min))
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
public class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int res = Integer.MIN_VALUE;
        int amin = Integer.MAX_VALUE;
        int amax = Integer.MIN_VALUE;
        for (int i = 0; i < arrays.get(0).size(); i++) {
            amin = Math.min(amin, arrays.get(0).get(i));
            amax = Math.max(amax, arrays.get(0).get(i));
        }
        for (int i = 1; i < arrays.size(); i++) {
            // get min and max from each array
            int cmin = Integer.MAX_VALUE;
            int cmax = Integer.MIN_VALUE;
            for (int j = 0; j < arrays.get(i).size(); j++) {
                cmin = Math.min(cmin, arrays.get(i).get(j));
                cmax = Math.max(cmax, arrays.get(i).get(j));
                res = Math.max(res, Math.abs(amin - cmax));
                res = Math.max(res, Math.abs(amax - cmin));
            }
            amin = Math.min(cmin, amin);
            amax = Math.max(cmax, amax);
        }
        return res;
    }
}

发表于 | 分类于

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

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

用一个HashMap来存储每一个number出现的位置。然后对于所有出现过两次以上的数字计算是否有满足的答案。
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 containsNearbyDuplicate(int[] nums, int k) {
        
        if (nums == null || nums.length == 0) {
            return false;
        }
        
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i]).add(i);
            } else {
                map.put(nums[i], new ArrayList<Integer>());
                map.get(nums[i]).add(i);
            }
        }
        
        // traverse the HashMap
        for (int num : map.keySet()) {
            if (map.get(num).size() >= 2) {
                List<Integer> indices = map.get(num);
                // traverse the list
                for (int i = 0; i < indices.size() - 1; ++i) {
                    if (indices.get(i + 1) - indices.get(i) <= k) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
}