Posted Updated LeetCode / Medium / 复习a minute read (About 181 words)

46. Permutations

问题
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

回溯，建立搜索树。
每次遍历nums中的元素。
如果未遍历过该元素，则向链表及set中添加。
向下递归，链表长度达到nums的长度时返回。
然后从set和链表中移除上一个值，回溯到上一个节点。

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
class Solution {
    List<List<Integer>> ans;
    HashSet<Integer> set;
    public List<List<Integer>> permute(int[] nums) {
        ans = new ArrayList();
        set = new HashSet();
        backTrack(new LinkedList(), nums, nums.length, nums.length);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list,int[] nums, int n, int k){
        if(k == 0){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i = 0; i < n ; i++){
            if(!set.contains(nums[i])){
                list.add(nums[i]);
                set.add(nums[i]);
                backTrack(list, nums , n, k-1);
                set.remove(nums[i]);
                list.removeLast();
            }
        }
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 183 words)

102. Binary Tree Level Order Traversal

Question

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Solution

BFS搜索，层序遍历，记录每个层级的节点数量size。
在遍历时挤出size个节点，并将其子节点加入队列。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        int size = 1;
        while(!q.isEmpty()){
            List<Integer> list = new ArrayList<>();
            TreeNode curr = null;
            for(int i = 0; i < size; i++){
                curr = q.poll();
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
                list.add(curr.val);
            }
            ret.add(list);
            size = q.size();
        }
        return ret;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 228 words)

77. Combinations

问题
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

回溯，构建搜索树。
子节点取出的数值应大于父节点中取出的数值。
直到树高度达到k后返回。

返回时，要new一个List，将原有list传入。
否则添加到ans的值只是list的内存地址。
ArrayList换成LinkedList可以优化一些速度，因为可以直接removeLast。（22ms -> 16ms）
i的范围限制在start到n-k+1，后面的限制容易被忽略，可以大幅度减枝，优化速度。（16ms -> 1ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<>();
        backTrack(new LinkedList(),1,n,k);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list, int start, int n, int k){
        if (k == 0){
            ans.add(new ArrayList(list));
            return;
        }

        for (int i = start; i <= n-k+1; i++){
            list.add(i);
            backTrack(list, i+1, n, k-1);
            list.removeLast();
        }
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 361 words)

116. Populating Next Right Pointers in Each Node

问题
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1
2
3
4
5
6
 struct Node {
 int val;
 Node *left;
 Node *right;
 Node *next;
>}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

递归，当root为null时返回。
如果root有右节点，则左节点next指向右节点。
如果root有右节点同时next已经指向了一个节点，则将其右节点next指向该节点的左子节点。
递归左右子节点，并返回root。

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
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root==null){return root;}
        if (root.right!=null){
            root.left.next = root.right;
            if (root.next!=null){
                root.right.next = root.next.left;
            }
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

BFS搜索每一个节点，将节点指向队列中next下一个节点。
当计数器达到2的指数时，将节点指向null。

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
class Solution {
    public Node connect(Node root) {
        if (root == null){
            return root;
        }
        
        int count = 1;
        Queue<Node> q = new LinkedList();
        q.offer(root);
        while (!q.isEmpty()){
            count++;
            Node curr = q.poll();
            if ( isPow(count) ){
                curr.next = null;
            }
            else{
                curr.next = q.peek();
            }
            if(curr.left!=null){
                q.add(curr.left);
            }
            if(curr.right!=null){
                q.add(curr.right);
            }

        }
        return root;
    }
    
    private boolean isPow(int val){
        if(val == 0 || val == 1){
            return false;
        }
        while ( val % 2 == 0 ){
            val = val / 2;
        }
        if (val == 1){
            return true;
        }
        return false;
    }
}
695. Max Area of Island
Posted Updated LeetCode / Medium / 复习2 minutes read (About 292 words)

695. Max Area of Island

Question

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Solution

DFS搜索, 维护一个变量count，为连续执行DFS搜索的次数。
遍历地图上所有为1的位置。

运行BFS时每次将全局变量count增加1。
执行完毕后BFS时将全局变量count清零。

遍历每个等于1的地图块。
递归周围四个地图块，当超越数组范围，或者当前位置不为1时返回。
进行搜索时将搜索过的地图块标记为0，不再重复搜索。

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
class Solution {
    int[][] visited, directions;
    int count;
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int x = 0; x < grid.length; x++){
            for(int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 1){
                    count = 0;
                    dfs(grid, x, y);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
    
    private void dfs(int[][] grid, int x, int y){
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return;
        grid[x][y] = 0;
        count++;
        for(int[] direction : directions){
            int i = x + direction[0];
            int j = y + direction[1];
            dfs(grid, i, j);
        }
    }
}
3. Longest Substring Without Repeating Characters
Posted Updated LeetCode / Medium / 复习2 minutes read (About 355 words)

3. Longest Substring Without Repeating Characters

Question

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

Solution 1

滑动窗口加数组统计。
用一个数组bin[]记录各个字符的访问情况。（数组尺寸由字符串的总数决定）

当指针j第一次遍历到一个字符时，如果该字符对应的位置为0，则将其设置为1。
否则对前面的i指针进行遍历，并将i经过的位置重新设置为0。如果i的字符与当前j字符相等，则将bin[index]设置为0，计算当前的长度j-i并更新最大值best。

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0, i = 0, j = 0;
        char[] word = s.toCharArray();
        int[] bin = new int[128];
        while(j < s.length()){
            int index = word[j] - ' ';
            if(bin[index] == 0){
                bin[index] = 1;
                j++;
            }
            else{
                while(i < j){
                    int temp = word[i] - ' ';
                    if(temp == index && bin[index] == 1){
                        bin[index] = 0;
                        best = Math.max(best, j - i);
                        i++;
                        break;
                    }
                    bin[temp] = 0;
                    i++;
                }
            }
            best = Math.max(best, j - i);
        }
        return best;
    }
}

Solution 2

滑动窗口，哈希表记录访问过的字符的元素。
如果重复，则放弃前一个重复的字符，更新左指针。
注意：只有在新指针大于现有指针时才更新！

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0;
        int i = 0;
        int j = 0;
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        while ( j < s.length() ){
            char curChar = s.charAt(j);
            if ( !map.containsKey(curChar) ){
                map.put( curChar, j );
            }
            else{
                if ( map.get(curChar) + 1 > i){
                    i = map.get(curChar) + 1;
                }

                map.put( curChar, j );
            }
            
            if ((j - i + 1) > best){
                best = (j - i + 1);
            }
            j++;
        }
        return best;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 264 words)

923. 3Sum With Multiplicity

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 109 + 7.

首先遍历元素，根据元素的值和出现次数建立哈希表。
然后再哈希表中选择三个元素，如果和等于target，则计算三个元素出现次数的乘积。
最后除以重复计算的次数。
由于数值较大，因此中途计算应该采用长整型long。

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
class Solution {
    public int threeSumMulti(int[] arr, int target) {
        //enumberate every element and put them into the map
        HashMap<Integer, Long> map = new HashMap<Integer, Long>();
        long count = 0;
        
        for ( int num : arr ){
            if (!map.containsKey(num)){
                map.put(num, (long)1);
            }
            else{
                map.put(num, map.get(num)+1);
            }
        }
        
        //traverse whole elements and select three numbers
        
        for ( int a : map.keySet() ){
            long totalA = map.get(a);
            for (int b : map.keySet()){
                long totalB = map.get(b);
                if ( a == b ){
                    if (totalB < 2){
                        continue;
                    }
                    totalB = totalB - 1;
                }

                int c = target - a - b;
                if ( map.containsKey(c) ){
                    long totalC = map.get(c);
                    long total = 0;
                    if ( a == b && b == c ){
                        total = totalA * totalB * ( totalC - 2 ) ;
                    }
                    else if ( b == c || a == c ){
                        total = totalA * totalB * ( totalC - 1 ) ;
                    }
                    else{
                        total = totalA * totalB * totalC;
                    }
                    if ( total > 0 ){
                        count += total;
                    }

                }
            }
        }
        count/=6;
        int ans = (int) (count % 1000000007);
            
        return ans;
    }
}

Posted Updated LeetCode / Medium / 复习2 minutes read (About 346 words)

11. Container With Most Water

问题
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

双指针在首尾，二者容量取决于两者中较小的一个。
贪心算法，保留两个指针上较大的元素，移动较小一边的指针。
由于指针移动时距离只会减小，因此当新的元素比上一个更大时才有可能比之前的容量更大。
遍历一次找到最大容量。
时间复杂度：O(n)

感觉这个移动有点博弈论的味了，每次都移动自己最差的一边，虽然可能变得更差，但是总比不动（或者减小）强，动最差的部分可能找到更好的结果，但是动另一边总会更差或者不变，兄弟们，这不是题，这是人生，逃离舒适圈！！（这解释我觉得无敌了，哈哈哈）

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
class Solution {
    public int maxArea(int[] height) {
        int best = 0;
        
        int i = 0;
        int j = height.length - 1;
        
        while ( i < j ){
            int product = 0;
            if (height[i] < height[j]){
                product = height[i] * ( j -i );
                i++;
            }
            else{
                product = height[j] * ( j -i );
                j--;
            }
            if ( product > best){
                best = product;
            }
        }
        return best;
    }
}

Posted Updated LeetCode / Medium / 复习3 minutes read (About 388 words)

31. Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

从数组末尾开始遍历第i个元素。
如果后一项小于前一项，则排序关系正确。
反之则将i与遍历过的部分中比i大的第一个数字交换。
然后对已遍历的部分排序。

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 {
    public void nextPermutation(int[] nums) {
        int flag = 0;   //标记，如果没有下一个排列时，排序数组。
        if (nums.length != 1){
            int i = nums.length -2;
            while (i >= 0){
                if (nums[i + 1] <= nums[i]) {   //从尾部开始，比较元素是否是大到小
                    i--;
                    continue;
                }
                else {  //排序关系不正确时
                    for (int j = nums.length-1;j>i;j--){
                        if (nums[j] <= nums[i]){
                            continue;
                        }
                        int temp = nums[j]; //将i元素和遍历过的元素中第一个比nums[i]大的交换。
                        nums[j] = nums[i];
                        nums[i] = temp;
                        Arrays.sort(nums,i+1,nums.length);  //排序i之后的数组。
                        flag = 1;
                        break;
                    }
                    break;
                }
            }
            if (flag == 0 ){    //如果全部从大到小，则排序整个数组。
                Arrays.sort(nums);
            }  
        }
    }
}

Posted Updated LeetCode / Medium / 复习a minute read (About 146 words)

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

环型替换，先求出数列长度和轮转次数的最大公约数m。
然后依次替换数列中的每个值。

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
//Rotate Array

class Solution {
    public void rotate(int[] nums, int k) {
        if (k != 0){
            int m = gcd(nums.length,k);
        
            for (int n = 0; n < m; n++ ) {
                int i = n + k;
                i %= nums.length;

                int temp = nums[n];
                while( true ){
                    int tempI = nums[i];
                    nums[i] = temp;
                    temp = tempI;
                
                    i += k;
                    i %= nums.length;
                
                    if (i == n){
                        nums[n] = temp;
                        break;
                    }
                }
            }
        }
    }
    
    private int gcd(int a, int b){
        int max = a;
        int min = b;
        if (max == min){
            return min;
        }
        
        if ( a < b ){
            max = b;
            min = a;
        }
        
        return gcd(max - min, min);
    }
}

Follow

Recents

Archives

Links

×