IVN
0%

Meta高频

Posted on Edited on In
Symbols count in article: 46k Reading time ≈ 41 mins.

Meta高频题

1249. Minimum Remove to Make Valid Parentheses

Meta高频题No. 1

看见括号匹配，想到用栈

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
public class LeetCode1249 {
    public String minRemoveToMakeValid(String s) {
        int n=s.length();
        char[] chars = s.toCharArray();
        Deque<Integer> stack=new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char c=chars[i];
            if(c==')' && !stack.isEmpty() && chars[stack.peek()]=='('){
                stack.pop();
            }else if(c=='(' || c==')'){
                stack.push(i);
            }
        }
        int[] arr=new int[n];
        while(!stack.isEmpty()){
            arr[stack.pop()]=1;
        }
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < n; i++) {
            if(arr[i]==1){
                continue;
            }else{
                sb.append(chars[i]);
            }
        }
        return sb.toString();
    }
}

680. Valid Palindrome II

常规longest palindrome subsequence的DP解法超时！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean validPalindrome(String s) {
    //longest palindrome subsequence
    int n=s.length();
    int[][] dp=new int[n][n];
    for (int i = n-1; i >= 0; i--) {
        dp[i][i]=1;
        for(int j=i+1; j<n; j++){
            if(s.charAt(i)==s.charAt(j)){
                dp[i][j]=dp[i+1][j-1]+2;
            }else{
                dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1]>=n-1;
}

考虑Greedy Algorithm:

  1. 双指针，若两头相等，则继续内缩，直到两头不等
  2. 不等后，判断 [i+1,j] 和 [i, j-1] 是否有一个是palindrome
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 boolean validPalindrome(String s) {
    int left=0;
    int right=s.length()-1;
    while(left<right){
        if(s.charAt(left)!=s.charAt(right)){
            return isValid(s,left+1,right) || isValid(s,left,right-1);
        }
        left++;
        right--;
    }
    return true;
}

boolean isValid(String s, int start, int end){
    int left=start;
    int right=end;
    while(left<right){
        if(s.charAt(left)!=s.charAt(right)){
            return false;
        }
        left++;
        right--;
    }
    return true;
}

560. Subarray Sum Equals K

法一：brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode560 {
    public int subarraySum(int[] nums, int k) {
        int count=0;
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            int sum=0;
            for(int j=i; j<n; j++){
                sum+=nums[j];
                if(sum==k){
                    count++;
                }
            }
        }
        return count;
    }
}

法二：prefix sum + HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int subarraySum(int[] nums, int k) {
    Map<Integer,Integer> map=new HashMap<>();
    map.put(0,1);   //前缀和为0的subarray个数初始为1
    int n=nums.length;
    int sum=0;
    int count=0;
    for (int i = 0; i < n; i++) {
        sum+=nums[i];
        if(map.containsKey(sum-k)){
            count+=map.get(sum-k);
        }
        map.put(sum,map.getOrDefault(sum,0)+1);
    }
    return count;
}

938. Range Sum of BST

法一：recursively

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 LeetCode938 {
    boolean finished;
    int low;
    int high;
    int sum;
    public int rangeSumBST(TreeNode root, int low, int high) {
        this.low=low;
        this.high=high;
        this.sum=0;
        dfs(root);
        return sum;
    }

    void dfs(TreeNode root){
        if(root==null || finished){
            return;
        }
        dfs(root.left);
        if(root.val>=low && root.val<=high){
            sum+=root.val;
        }
        if(root.val>high){
            finished=true;
        }
        dfs(root.right);
    }
}

法二：non recursively

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
public int rangeSumBST(TreeNode root, int low, int high) {
    int sum=0;
    boolean finished=false;
    Deque<TreeNode> stack=new LinkedList<>();
    stack.push(root);
    while(!stack.isEmpty() && !finished){
        TreeNode node=stack.pop();
        if(node!=null){
            //left root right
            //right root left
            if(node.right!=null){
                stack.push(node.right);
            }
            stack.push(node);
            stack.push(null);
            if(node.left!=null){
                stack.push(node.left);
            }
        }else{
            node =stack.pop();
            if(node.val>=low && node.val<=high){
                sum+=node.val;
            }
            if(node.val>high){
                finished=true;
            }
        }
    }
    return sum;
}

236. Lowest Common Ancestor of a Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root, p.val, q.val);
    }

    TreeNode find(TreeNode root, int p, int q){
        if(root==null || root.val==p || root.val==q){
            return root;
        }
        TreeNode findLeft=find(root.left,p,q);
        TreeNode findRight=find(root.right,p,q);
        if(findLeft!=null && findRight!=null){
            return root;
        }
        return findLeft==null ? findRight : findLeft;
    }
}

215. Kth Largest Element in an Array

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
class Solution {
    int[] nums;
    public int findKthLargest(int[] nums, int k) {
        this.nums=nums;
        int n=nums.length;
        int lo=0;
        int hi=nums.length-1;
        while(lo<=hi){
            int j=partition(lo,hi);
            if(j>n-k){
                hi=j-1;
            }else if(j<n-k){
                lo=j+1;
            }else{
                return nums[j];
            }
        }
        return -1;
    }

    int partition(int start, int end){
        int pivot=nums[start];
        int i=start+1;
        int j=end;
        while(i<=j){
            while(i<=end && nums[i]<=pivot){ //注意：由于最后swap(start,j)，所以要保证j不越界，但i可以越界
                i++;
            }
            while(j>=start && nums[j]>pivot){
                j--;
            }
            if(i>=j){
                break;
            }
            swap(i,j);
        }
        swap(start,j);
        return j;
    }

    void swap(int i, int j){
        if(i==j){
            return;
        }
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

314. Binary Tree Vertical Order Traversal

好题，好题！

注意：

  1. TreeMap

    采用 TreeMap<Integer, List>来存储每列答案，

    返回时直接return new ArrayList<>(res.values()), 可以保证结果按key升序

  2. res.computeIfAbsent(i, k -> new ArrayList<>()), 若不存在这个key，则插入新的键值对

    • getOrDefault：仅仅是返回值，如果不存在返回指定的默认值，不修改map的结构
    • putIfAbsent：key不存在时，塞一个值，不应该关心返回值
    • computeIfAbsent：获取key对应的value，不存在时塞一个并返回
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
// 主要思想是层级遍历
// 因为是垂直输出结果，所以假设根节点的初始位置是 0，那么左边向下逐层减 1，右边向下逐层加 1
public List<List<Integer>> verticalOrder1(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    // 存放当前位置(key)的结果集(value)
    Map<Integer, List<Integer>> res = new TreeMap<>();

    // 存放当前节点（TreeNode）的位置
    Map<TreeNode, Integer> nodeMap = new HashMap<>();
    nodeMap.put(root, 0);

    // 层序遍历
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        int i = nodeMap.get(node);
        // 如果当前位置还没有存储元素的结果集，则初始化 value，并添加元素
        res.computeIfAbsent(i, k -> new ArrayList<>()).add(node.val);
        // 左边向下逐层减 1
        if (node.left != null) {
            queue.add(node.left);
            nodeMap.put(node.left, i - 1);
        }
        // 右边向下逐层加 1
        if (node.right != null) {
            queue.add(node.right);
            nodeMap.put(node.right, i + 1);
        }
    }
    return new ArrayList<>(res.values());
}

50. Pow(x, n)

注意 int 范围： [ -2147483648, 2147483647]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode50 {
    public double myPow(double x, int n) {
        long i=n;
        if(i<0){
            i=-i;
            x=1/x;
        }
        double res=1;
        while(i>0){
            if(i%2==1){
                res*=x;
            }
            i/=2;
            x*=x;
        }
        return res;
    }
}

1762. Buildings With an Ocean View

As long as it has no next greater element, it is valid

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 LeetCode1762 {
    public int[] findBuildings(int[] heights) {
        Deque<Integer> stack=new LinkedList<>();
        int n=heights.length;
        int[] next=new int[n];
        for (int i = n-1; i >= 0; i--) {
            while(!stack.isEmpty() && heights[stack.peek()]<heights[i]){
                stack.pop();
            }
            next[i]=stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        List<Integer> list=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if(next[i]==-1){
                list.add(i);
            }
        }
        int[] res=new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i]=list.get(i);
        }
        return res;
    }
}

973. K Closest Points to Origin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode973 {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> pq=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int s1=o1[0]*o1[0]+o1[1]*o1[1];
                int s2=o2[0]*o2[0]+o2[1]*o2[1];
                return s1-s2;
            }
        });
        for (int[] point : points) {
            pq.offer(point);
        }
        int[][] res=new int[k][2];
        for (int i = 0; i < k; i++) {
            int[] head = pq.poll();
            res[i][0]=head[0];
            res[i][1]=head[1];
        }
        return res;
    }
}

1570. Dot Product of Two Sparse Vectors

只要存放系数不为0的位置及其对应系数即可，求乘积时优先遍历长度较小的向量，可以缩短很多时间

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 LeetCode1570 {
    class SparseVector {

        Map<Integer,Integer> map;
        SparseVector(int[] nums) {
            this.map=new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                if(nums[i]!=0){
                    map.put(i,nums[i]);
                }
            }
        }

        // Return the dotProduct of two sparse vectors
        public int dotProduct(SparseVector vec) {
            int size1 = this.map.size();
            int size2 = vec.map.size();
            Map<Integer,Integer> map1;
            Map<Integer,Integer> map2;
            if(size1<size2){
                map1=this.map;
                map2=vec.map;
            }else{
                map1=vec.map;
                map2=this.map;
            }
            int res=0;
            for (Integer i : map1.keySet()) {
                if(map2.containsKey(i)){
                    res+=map1.get(i)*map2.get(i);
                }
            }
            return res;
        }
    }
}

1650. Lowest Common Ancestor of a Binary Tree III

从下向上，用HashSet来记录所有见过的结点

第一个出现的结点必然就是LCA

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
public class LeetCode1650 {
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node parent;
    };


    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> set=new HashSet<>();
        while(p!=null || q!=null){
            if(p!=null){
                if(set.contains(p)){
                    return p;
                }
                set.add(p);
                p=p.parent;
            }
            if(q!=null){
                if(set.contains(q)){
                    return q;
                }
                set.add(q);
                q=q.parent;
            }
        }
        return null;
    }
}

528. Random Pick with Weight

前缀和数组 + 二分查找

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 {

    int[] preSum;
    int n;
    int total;
    public Solution(int[] w) {
        n=w.length;
        preSum=new int[n];
        preSum[0]=w[0];
        for (int i = 1; i < n; i++) {
            preSum[i]=preSum[i-1]+w[i];
        }
        total= Arrays.stream(w).sum();
    }

    public int pickIndex() {
        int x=(int)(Math.random()*total)+1;
        return binarySearch(x);
    }

    int binarySearch(int target){
        int left=0;
        int right=n;
        while(left<right){
            int mid=left+(right-left)/2;
            if(preSum[mid]<target){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return left;
    }
}

124. Binary Tree Maximum Path Sum

好题，注意：

  1. dfs返回值和所求结果不同时，应该想到引入成员变量来记录所求结果

  2. 遍历所有节点，并考虑经过每个节点的maximum path

  3. 求经过某个节点的maximum path只需要经过其左右子节点的单侧最大分支，即dfs函数的返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode124 {
    int max;
    public int maxPathSum(TreeNode root) {
        this.max=Integer.MIN_VALUE;
        dfs(root);
        return max;
    }

    int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftMax=Math.max(dfs(root.left),0);
        int rightMax=Math.max(dfs(root.right),0);
        max=Math.max(max,leftMax+root.val+rightMax);
        return Math.max(leftMax,rightMax)+root.val;
    }
}

31. Next Permutation

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

思路：

  1. 先倒序遍历数组, 找到第一个 (前一个数比后一个数小的位置) (即nums[i] < nums[i+1]);
  2. 这个时候我们不能直接把后一个数nums[i+1] 跟前一个数nums[i]交换就完事了; 还应该从nums[i+1]–>数组末尾这一段的数据中 找出最优的那个值( 如何最优? 即比nums[i]稍微大那么一丢丢的数, 也就是 nums[i+1]之后, 比nums[i]大的数中最小的那个值)
  3. 找到之后, 跟num[i]交换, 这还不算是下一个排列, num[i]后面的数值还不够小, 所以还应当进升序排列

例如:

nums = [1,2,7,4,3,1],

  1. 第一步: 倒序遍历数组, 找出第一组: 前一个数比后一个数小的两个数, 即[2, 7]
  2. 2所处的这个位置就是需要找出比它稍微大的数的位置;
  3. 我们从[7,4,3,1]中找出比2大的数中的最小值, 也就是3, 找到后跟2交换即可;; 当然了, 如果没找到的话, 直接跳到第5步, 直接升序排列输出.
  4. 目前nums=[1,3,7,4,2,1], 不用我说你们也看出来还不算下一个排列
  5. 对3后面的数, 升序排列, 即最终结果: nums = [1,3,1,2,4,7]
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 LeetCode31 {
    public void nextPermutation(int[] nums) {
        int n=nums.length;
        int i;
        for (i = n - 2; i >= 0; i--) {
            if(nums[i]<nums[i+1]){
                break;
            }
        }
        if(i>=0){
            int next=i+1;
            for(int j=i+1; j<n; j++){
                if(nums[j]>nums[i] && nums[j]<nums[next]){
                    next=j;
                }
            }
            int temp=nums[i];
            nums[i]=nums[next];
            nums[next]=temp;
        }
        Arrays.sort(nums,i+1,n);
    }
}

56. Merge Intervals

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 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                return o1[0]!=o2[0] ? o1[0]-o2[0] : o1[1]-o2[1]; 
            }
        });

        List<int[]> list=new ArrayList<>();
        int n=intervals.length;
        int start=intervals[0][0];
        int end=intervals[0][1];
        for(int i=1; i<n; i++){
            int left=intervals[i][0];
            int right=intervals[i][1];
            if(left>end){
                list.add(new int[]{start,end});
                start=left;
                end=right;
            }else if(right>end){
                end=right;
            }
        }
        list.add(new int[]{start,end});
        return list.toArray(new int[list.size()][]);
    }
}

921. Minimum Add to Make Parentheses Valid

法一：用栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LeetCode921 {
    public int minAddToMakeValid(String s) {
        Deque<Character> stack=new LinkedList<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if(c==')' && !stack.isEmpty() && stack.peek()=='('){
                stack.pop();
            }else{
                stack.push(c);
            }
        }
        return stack.size();
    }
}

法二：不用栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minAddToMakeValid(String s) {
        char[] chars = s.toCharArray();
        int left=0;
        int right=0;
        for (char c : chars) {
            if(c=='('){
                left++;
            }
            if(c==')'){
                right++;
                if(left>0){
                    left--;
                    right--;
                }
            }
        }
        return left+right;
    }
}

199. Binary Tree Right Side View

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 {
    public List<Integer> rightSideView(TreeNode root) {
        if(root==null){
            return new ArrayList();
        }
        List<Integer> res=new ArrayList<>();
        Deque<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            while(size-->0){
                TreeNode node=queue.poll();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                if(size==0){
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

347. Top K Frequent Elements

一个基于优先级堆的无界优先级[队列]。优先级队列的元素按照其[自然顺序]进行排序，或者根据构造队列时提供的 [Comparator] 进行排序，具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）。

此队列的头 是按指定排序方式确定的最小 元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列获取操作 poll、remove、peek 和 element 访问处于队列头的元素。

实现注意事项：此实现为排队和出队方法（offer、poll、remove() 和 add）提供 O(log(n)) 时间；为 remove(Object) 和 contains(Object) 方法提供线性时间；为获取方法（peek、element 和 size）提供固定时间。

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 {
    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<int[]> pq=new PriorityQueue(new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                return o2[1]-o1[1];
            }
        });
        int n=nums.length;
        Arrays.sort(nums);
        int count=0;
        for(int i=0; i<n; i++){
            if(i>0 && nums[i]!=nums[i-1]){
                pq.offer(new int[]{nums[i-1],count});
                count=0;
            }
            count++;
        }
        pq.offer(new int[]{nums[n-1],count});
        int[] res=new int[k];
        for(int i=0; i<k; i++){
            res[i]=pq.poll()[0];
        }
        return res;
    }
}

543. Diameter of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int max;
    public int diameterOfBinaryTree(TreeNode root) {
        max=Integer.MIN_VALUE;
        dfs(root);
        return max;
    }

    int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftDepth=dfs(root.left);
        int rightDepth=dfs(root.right);
        max=Math.max(leftDepth+rightDepth,max);
        return Math.max(leftDepth,rightDepth)+1;
    }
}

227. Basic Calculator II

基础版：原中缀表达式中所有运算数都是个位数

但本题中操作数可以为任意int

由于没有括号且操作数全部非负，无需使用逆波兰式通法:

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
class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new LinkedList<Integer>();
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    default:
                        stack.push(stack.pop() / num);
                }
                preSign = s.charAt(i);
                num = 0;
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.pop();
        }
        return ans;
    }
}

逆波兰式通法：

  • 从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；

  • 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈元素依次出栈并输出，并将当前符号进栈

    • 注意：左括号直接进栈，右括号则需要一直出栈到左括号（包括左括号）

  • 一直到最终输出后缀表达式为止。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public class LeetCode227 {
    public int calculate(String s) {
        String s1 = s.trim();
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i)!=' '){
                sb.append(s1.charAt(i));
            }
        }
        s1=sb.toString();
        List<String> in=new ArrayList<>();
        int start=0;
        for (int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i)-'0'>=0 && s1.charAt(i)-'0'<=9){
                continue;
            }else{
                in.add(s1.substring(start,i));
                in.add(s1.substring(i,i+1));
                start=i+1;
            }
        }
        in.add(s1.substring(start));
        int n=in.size();


        Deque<String> post=new LinkedList<>();
        Deque<String> stack=new LinkedList<>();
        for (int i = 0; i < n; i++) {
            String str=in.get(i);
            if(str.length()==1 && (str.charAt(0)=='+' ||str.charAt(0)=='-' ||
            str.charAt(0)=='*' || str.charAt(0)=='/')){
                while(!stack.isEmpty()){	//注意：循环：若操作符栈顶元素优先级大于等于当前符号，则出栈并入队
                    if(prior(str,stack.peek())<=0){
                        post.offer(stack.pop());
                    }else{
                        break;
                    }
                }
                stack.push(str);
            }else{
                post.offer(str);
            }
        }
        while(!stack.isEmpty()){
            post.offer(stack.pop());
        }

        Deque<Integer> postStack=new LinkedList<>();
        int size=post.size();
        for (int i = 0; i < size; i++) {
            String str=post.poll();
            if(str.length()==1 && (str.charAt(0)=='+' ||str.charAt(0)=='-' ||
                    str.charAt(0)=='*' || str.charAt(0)=='/')){
                int o1=postStack.pop();
                int o2=postStack.pop();
                int res=0;
                char c=str.charAt(0);
                if(c=='+'){
                    res=o2+o1;
                }
                if(c=='-'){
                    res=o2-o1;
                }
                if(c=='*'){
                    res=o2*o1;
                }
                if(c=='/'){
                    res=o2/o1;
                }
                postStack.push(res);
            }else{
                postStack.push(Integer.valueOf(str));
            }
        }
        return postStack.peek();
    }

    int prior(String s1, String s2){
        char c1=s1.charAt(0);
        char c2=s2.charAt(0);
        if(c1=='*' || c1=='/'){
            if(c2=='+' || c2=='-'){
                return 1;
            }else{
                return 0;
            }
        }else if(c2=='+' || c2=='-'){
            return 0;
        }else{
            return -1;
        }
    }
}

71. Simplify Path

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 LeetCode71 {
    public String simplifyPath(String path) {
        String[] split = path.split("/");
        LinkedList<String> list=new LinkedList<>();

        for (String s : split) {
            if(s.length()==0 || s.equals(".")){
                continue;
            }
            if(s.equals("..")){
                if(!list.isEmpty()){
                    list.removeLast();
                }
            }else{
                list.add(s);
            }
        }
        StringBuilder sb=new StringBuilder();
        int size=list.size();
        for (int i = 0; i < size; i++) {
            sb.append("/");
            sb.append(list.get(i));
        }
        String s=sb.toString();
        return s.length()==0 ? "/" : s;
    }
}

88. Merge Sorted Array

双指针，从后向前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode88 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1;
        int j=n-1;
        int p=m+n-1;
        while(i>=0 && j>=0){
            if(nums1[i]>=nums2[j]){
                nums1[p--]=nums1[i--];
            }else{
                nums1[p--]=nums2[j--];
            }
        }
        while(j>=0){
            nums1[p--]=nums2[j--];
        }
    }
}

339. Nested List Weight Sum

每层求和时，需要当前的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        return dSum(nestedList,1);
    }

    int dSum(List<NestedInteger> nestedList, int d){
        int sum=0;
        for(NestedInteger nest: nestedList){
            if(nest.isInteger()){
                sum+=nest.getInteger()*d;
            }else{
                sum+=dSum(nest.getList(),d+1);
            }
        }
        return sum;
    }
}

162. Find Peak Element

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
public class LeetCode162 {
    public int findPeakElement(int[] nums) {
        //nums[i-1]<nums[i]>nums[i+1]
        //nums[i-1]>nums[i]<nums[i+1], i=i+1
        //nums[i-1]>nums[i]>nums[i+1], i=i-1
        //nums[i-1]<nums[i]<nums[i+1], i=i+1
        int n=nums.length;
        int left=0;
        int right=n-1;
        int res=0;
        while(left<=right){
            int mid=left+(right-left)/2;
            int c=compare(nums,mid-1,mid,mid+1);
            if(c==0){
                res=mid;
                break;
            }else if(c>0){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return res;
    }

    int compare(int[] nums, int pre, int cur, int post){
        int preVal= pre==-1 ? Integer.MIN_VALUE : nums[pre];
        int postVal= post==nums.length ? Integer.MIN_VALUE : nums[post];
        int curVal=nums[cur];
        if(curVal>preVal && curVal>postVal){
            return 0;
        }
        if(curVal<preVal && curVal>postVal){
            return -1;
        }
        return 1;
    }
}

125. Valid Palindrome

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 LeetCode125 {
    public boolean isPalindrome(String s) {
        s=s.trim().toLowerCase();
        StringBuilder sb=new StringBuilder();
        int n=s.length();
        for (int i = 0; i < n; i++) {
            char c=s.charAt(i);
            if(Character.isLetterOrDigit(c)){
                sb.append(c);
            }
        }
        n=sb.length();
        int left=0;
        int right=n-1;
        while(left<right){
            if(sb.charAt(left)!=sb.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

426. Convert Binary Search Tree to Sorted Doubly Linked List

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list.

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
Node pre;
Node head;
public Node treeToDoublyList(Node root) {
    if(root==null){
        return null;
    }
    pre=null;
    head=null;
    dfs(root);
    pre.right=head;
    head.left=pre;
    return head;
}

void dfs(Node root){
    if(root==null){
        return;
    }
    dfs(root.left);
    if(pre==null){
        head=root;
    }
    if(pre!=null){
        root.left=pre;
        pre.right=root;
    }
    pre=root;
    dfs(root.right);
}

987. Vertical Order Traversal of a Binary Tree

注意：同一层同一位置元素必须升序进入结果集

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
public class LeetCode987 {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Deque<TreeNode> queue=new LinkedList<>();
        TreeMap<Integer,LinkedList<Integer>> res=new TreeMap<>();
        Map<TreeNode,Integer> map=new HashMap<>();
        queue.offer(root);
        map.put(root,0);
        while(!queue.isEmpty()){
            int size=queue.size();
            TreeMap<Integer,LinkedList<Integer>> level=new TreeMap<>();
            while(size-->0){
                TreeNode node=queue.poll();
                int i=map.get(node);
                if(!level.containsKey(i)){
                    level.put(i,new LinkedList<>());
                    level.get(i).add(node.val);
                }else{
                    int l=level.get(i).size();
                    boolean added=false;
                    for (int j = 0; j < l; j++) {
                        if(level.get(i).get(j)>node.val){
                            level.get(i).add(j,node.val);
                            added=true;
                            break;
                        }
                    }
                    if(!added){
                        level.get(i).add(node.val);
                    }
                }
                if(node.left!=null){
                    queue.offer(node.left);
                    map.put(node.left,i-1);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                    map.put(node.right,i+1);
                }
            }
            for (Integer i : level.keySet()) {
                if(!res.containsKey(i)){
                    res.put(i,new LinkedList<>());
                }
                int l=level.get(i).size();
                for (int j = 0; j < l; j++) {
                    res.get(i).add(level.get(i).get(j));
                }
            }
        }
        return new ArrayList<>(res.values());
    }
}

官方解法：根据坐标对节点整体排序，依次加入结果集

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
class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<int[]>();
        dfs(root, 0, 0, nodes);
        Collections.sort(nodes, new Comparator<int[]>() {
            public int compare(int[] tuple1, int[] tuple2) {
                if (tuple1[0] != tuple2[0]) {
                    return tuple1[0] - tuple2[0];
                } else if (tuple1[1] != tuple2[1]) {
                    return tuple1[1] - tuple2[1];
                } else {
                    return tuple1[2] - tuple2[2];
                }
            }
        });
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int size = 0;
        int lastcol = Integer.MIN_VALUE;
        for (int[] tuple : nodes) {
            int col = tuple[0], row = tuple[1], value = tuple[2];
            if (col != lastcol) {
                lastcol = col;
                ans.add(new ArrayList<Integer>());
                size++;
            }
            ans.get(size - 1).add(value);
        }
        return ans;
    }

    public void dfs(TreeNode node, int row, int col, List<int[]> nodes) {
        if (node == null) {
            return;
        }
        nodes.add(new int[]{col, row, node.val});
        dfs(node.left, row + 1, col - 1, nodes);
        dfs(node.right, row + 1, col + 1, nodes);
    }
}

408. Valid Word Abbreviation

replacing any number of non-adjacent, non-empty substrings with their lengths

优先判断都是字母的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i=0,j=0;
        while(j<abbr.length()&&i<word.length()){
            if(Character.isLetter(abbr.charAt(j))){
                if(abbr.charAt(j)!=word.charAt(i)){return false;}
                i++;
                j++;
            }
            else{
                if(abbr.charAt(j)=='0'){return false;}
                int sum=0;
                while(j<abbr.length()&&Character.isDigit(abbr.charAt(j))){
                    sum=10*sum+abbr.charAt(j)-'0';
                    j++;
                }
                i+=sum;
            }
        }
        return j==abbr.length()&&i==word.length();
    }
}

138. Copy List with Random Pointer

好题！

法一：迭代法

如何去复制一个带随机指针的链表？

1、在每个节点的后面加上它的复制，并将原链表和复制链表连在一起。

2、 从前往后遍历每一个原链表节点，对于有 random 指针的节点 p，我们让它的 p->next->random = p->random->next，这样我们就完成了对原链表 random 指针的复刻。

3、最后我们把原链表和复制链表拆分出来，并将原链表复原。

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 Node copyRandomList(Node head) {
    if(head==null){
        return null;
    }
    //在每个原节点后复制一个新节点
    Node p=head;
    while(p!=null){
        Node next=p.next;
        Node node=new Node(p.val);
        p.next=node;
        node.next=next;
        p=next;
    }

    //修改新节点的random，指向对应的新节点
    p=head;
    while(p!=null ){
        Node next=p.next.next;
        if(p.random!=null){
            p.next.random=p.random.next;
        }
        p=next;
    }

    //借助dummy结点，将新旧链表拆开
    p=head;
    Node dummy=new Node(-1);
    dummy.next=p.next;
    while(p!=null){
        Node next=p.next.next;
        p.next.next= next==null ? null : next.next;
        p.next=next;
        p=next;
    }

    return dummy.next;
}

法二：哈希+递归

建立源节点到复制节点的映射，避免重复复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Map<Node,Node> map;
public Node copyRandomList(Node head) {
    map=new HashMap<>();
    return dfs(head);
}

Node dfs(Node node){
    if(node==null){
        return null;
    }
    if(map.containsKey(node)){
        return map.get(node);
    }
    Node clone=new Node(node.val);
    map.put(node,clone);
    clone.next=dfs(node.next);
    clone.random=dfs(node.random);
    return clone;
}

146. LRU Cache

LinkedHashMap

注意makeRecently，保证头旧尾新（LinkedHashMap是尾插）

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
class LRUCache {

    LinkedHashMap<Integer,Integer> cache;
    int cap;
    public LRUCache(int capacity) {
        cache=new LinkedHashMap<>();
        cap=capacity;
    }

    public int get(int key) {
        int val=cache.getOrDefault(key,-1);
        if(val!=-1){
            makeRecently(key);
        }
        return val;
    }

    public void put(int key, int value) {
        if(cache.containsKey(key)){
            cache.put(key,value);
            makeRecently(key);
        }else{
            cache.put(key,value);
        }
        if(cache.size()>cap){
            int first = cache.keySet().iterator().next();
            cache.remove(first);
        }
    }

    void makeRecently(int key){
        int val=cache.get(key);
        cache.remove(key);
        cache.put(key,val);
    }
}

23. Merge k Sorted Lists

divide and conquer

递归 后序遍历 先child后root

把前半部分和后半部分都merge成一个，再合并这两部分

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
public ListNode mergeKLists(ListNode[] lists) {
      if(lists.length==0){
          return null;
      }
      int n=lists.length;
      return mergeK(lists,0,n-1);
}

ListNode mergeK(ListNode[] lists, int start, int end){
      if(start==end){
          return lists[start];
      }
      int mid=start+(end-start)/2;
      ListNode headA=mergeK(lists,start,mid);
      ListNode headB=mergeK(lists,mid+1,end);
      return mergeTwoLists(headA,headB);
}

ListNode mergeTwoLists(ListNode headA, ListNode headB){
    ListNode a=headA;
    ListNode b=headB;
    ListNode dummy=new ListNode(-1);
    ListNode pre=dummy;
    while(a!=null && b!=null){
        if(a.val<b.val){
            pre.next=a;
            pre=a;
            a=a.next;
        }else{
            pre.next=b;
            pre=b;
            b=b.next;
        }
    }
    if(a!=null){
        pre.next=a;
    }else{
        pre.next=b;
    }
    return dummy.next;
}

415. Add Strings

大整数加法，借助StringBuilder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String addStrings(String num1, String num2) {
    int i=num1.length()-1;
    int j=num2.length()-1;
    int add=0;
    StringBuilder sb=new StringBuilder();
    while(i>=0 || j>=0 || add>0){
        int a=i>=0 ? num1.charAt(i)-'0' : 0;
        int b=j>=0 ? num2.charAt(j)-'0' : 0;
        i--;
        j--;
        int res=a+b+add;
        sb.append(res%10);
        add=res/10;
    }
    return sb.reverse().toString();
}

42. Trapping Rain Water

对于一根柱子而言，它能不能蓄水、能蓄多少水取决于它左侧和右侧的最高柱子中的较低者的高度和它本身的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int trap(int[] height) {
    int n=height.length;
    int[] leftMax=new int[n];
    int[] rightMax=new int[n];
    leftMax[0]=Integer.MIN_VALUE;
    rightMax[n-1]=Integer.MIN_VALUE;
    for(int i=1; i<n; i++){
        leftMax[i]=Math.max(leftMax[i-1],height[i-1]);
    }
    for(int i=n-2; i>=0; i--){
        rightMax[i]=Math.max(rightMax[i+1],height[i+1]);
    }
    int res=0;
    for(int i=1; i<n-1; i++){
        int h=Math.min(leftMax[i],rightMax[i]);
        res+= h-height[i]>0 ? h-height[i] : 0;
    }
    return res;
}

1091. Shortest Path in Binary Matrix

BFS好题！

8-directionally connected

解题思路
典型的BFS最短路径问题，用DFS也可以求解，但是容易超时。

在二维矩阵中搜索，什么时候用BFS，什么时候用DFS？

  1. 如果只是要找到某一个结果是否存在，那么DFS会更高效。因为DFS会首先把一种可能的情况尝试到底，才会回溯去尝试下一种情况，只要找到一种情况，就可以返回了。但是BFS必须所有可能的情况同时尝试，在找到一种满足条件的结果的同时，也尝试了很多不必要的路径；
  2. 如果是要找所有可能结果中最短的，那么BFS回更高效。因为DFS是一种一种的尝试，在把所有可能情况尝试完之前，无法确定哪个是最短，所以DFS必须把所有情况都找一遍，才能确定最终答案（DFS的优化就是剪枝，不剪枝很容易超时）。而BFS从一开始就是尝试所有情况，所以只要找到第一个达到的那个点，那就是最短的路径，可以直接返回了，其他情况都可以省略了，所以这种情况下，BFS更高效。

BFS解法中的visited为什么可以全局使用？
BFS是在尝试所有的可能路径，哪个最快到达终点，哪个就是最短。那么每一条路径走过的路不同，visited（也就是这条路径上走过的点）也应该不同，那么为什么visited可以全局使用呢？
因为我们要找的是最短路径，那么如果在此之前某个点已经在visited中，也就是说有其他路径在小于或等于当前步数的情况下，到达过这个点，证明到达这个点的最短路径已经被找到。那么显然这个点没必要再尝试了，因为即便去尝试了，最终的结果也不会是最短路径了，所以直接放弃这个点即可。

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
//BSF由近到远的特性，天然适配shortest path问题
public int shortestPathBinaryMatrix(int[][] grid) {
    int[][] delta={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    int count=1;
    int n=grid.length;
    if(grid[0][0]==1){
        return -1;
    }
    if(n==1){
        return 1;
    }
    boolean[][] visited=new boolean[n][n];
    Deque<int[]> queue=new LinkedList<>();
    queue.offer(new int[]{0,0});
    while(!queue.isEmpty()){
        int size=queue.size();
        count++;
        while(size-->0){
            int[] poll = queue.poll();
            int i=poll[0];
            int j=poll[1];
            for(int d=0; d<8; d++){
                int nextI=i+delta[d][0];
                int nextJ=j+delta[d][1];
                if(nextI<0 || nextI>=n || nextJ<0 || nextJ>=n
                        || grid[nextI][nextJ]==1 || visited[nextI][nextJ]){
                    continue;
                }
                if(nextI==n-1 && nextJ==n-1){
                    return count;   //BFS特性，第一次遇到某个点时必定是到该点的最短路径
                }
                queue.offer(new int[]{nextI,nextJ});
                visited[nextI][nextJ]=true;
            }
        }
    }
    return -1;
}

791. Custom Sort String

法一：直接法，借助优先队列、自定义Comparator

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 String customSortString(String order, String s) {
    Map<Character,Integer> map=new HashMap<>();
    int n1=order.length();
    char[] chars = order.toCharArray();
    for (int i = 0; i < n1; i++) {
        map.put(chars[i],n1-i);
    }
    char[] arr = s.toCharArray();
    PriorityQueue<Character> pq=new PriorityQueue<>(new Comparator<Character>() {
        @Override
        public int compare(Character o1, Character o2) {
            int a=map.getOrDefault(o1,0);
            int b=map.getOrDefault(o2,0);
            return b-a;
        }
    });
    for (int i = 0; i < arr.length; i++) {
        pq.offer(arr[i]);
    }
    StringBuilder sb=new StringBuilder();
    while(!pq.isEmpty()){
        sb.append(pq.poll());
    }
    return sb.toString();
}

法二：间接法，计数

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 customSortString(String S, String T) {
        // count[char] = the number of occurrences of 'char' in T.
        // This is offset so that count[0] = occurrences of 'a', etc.
        // 'count' represents the current state of characters
        // (with multiplicity) we need to write to our answer.
        int[] count = new int[26];
        for (char c: T.toCharArray())
            count[c - 'a']++;

        // ans will be our final answer.  We use StringBuilder to join
        // the answer so that we more efficiently calculate a
        // concatenation of strings.
        StringBuilder ans = new StringBuilder();

        // Write all characters that occur in S, in the order of S.
        for (char c: S.toCharArray()) {
            for (int i = 0; i < count[c - 'a']; ++i)
                ans.append(c);
            // Setting count[char] to zero to denote that we do
            // not need to write 'char' into our answer anymore.
            count[c - 'a'] = 0;
        }

        // Write all remaining characters that don't occur in S.
        // That information is specified by 'count'.
        for (char c = 'a'; c <= 'z'; ++c)
            for (int i = 0; i < count[c - 'a']; ++i)
                ans.append(c);

        return ans.toString();
    }
}

65. Valid Number

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 LeetCode65 {
    public boolean isNumber(String s) {
        boolean seenDigit=false;
        boolean seenDot=false;
        boolean seenE=false;
        boolean seenSign=false;
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if(c=='+' || c=='-'){
                if(seenSign || seenDigit){
                    return false;
                }
                seenSign=true;	
            }else if(c=='.'){
                if(seenDot || seenE){
                    return false;
                }
                seenDot=true;
                seenSign=true;		//出现.后不可以再出现+-号
            }else if(c=='e' || c=='E'){
                if(seenE || !seenDigit){
                    return false;
                }
                seenE=true;
                seenSign=false;		//出现e后可以再次出现+-号
                seenDigit=false;	//出现e后必须出现数字
            }else if(Character.isDigit(c)){
                if(!seenDigit){
                    seenDigit=true;		
                }
            }else{
                return false;
            }
        }
        return seenDigit;
    }
}

827. Making A Large Island

allowed to change at most one 0 to be 1

难！

最值问题考虑用DFS穷举，但必须考虑去重

也可以用UnionFind

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
public class LeetCode827 {
    int row;
    int col;
    int idx;
    int[][] grid;
    int[] area;
    int[] dx;
    int[] dy;
    public int largestIsland(int[][] grid) {
        row=grid.length;
        col=grid[0].length;
        this.grid=grid;
        idx=2;
        dx=new int[]{0,0,1,-1};
        dy=new int[]{1,-1,0,0};
        area=new int[row*col+2];    //存储每个岛屿的面积，岛屿下标从2开始

        int max=Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==1){
                    area[idx]=dfs(i,j);
                    max=Math.max(max,area[idx]);
                    idx++;
                }
            }
        }


        //注意去重，同一个岛屿只加一次
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j]==0){
                    set.clear();
                    int s=1;
                    for (int k = 0; k < 4; k++) {
                        int x=i+dx[k];
                        int y=j+dy[k];
                        if(x<0 || x>=row || y<0 || y>=col || grid[x][y]==0){
                            continue;
                        }
                        if(set.contains(grid[x][y])){
                            continue;
                        }
                        s+=area[grid[x][y]];
                        set.add(grid[x][y]);    //此时grid中存储的已经是岛屿的编号
                    }
                    max=Math.max(max,s);
                }
            }
        }
        return max;
    }

    //计算每个岛屿的面积，并给岛屿编号，同一岛屿编号相同
    int dfs(int i, int j){
        int res=1;
        grid[i][j]=idx;
        for (int k = 0; k < 4; k++) {
            int x=i+dx[k];
            int y=j+dy[k];
            if(x<0 || x>=row || y<0 || y>=col || grid[x][y]!=1){
                continue;
            }
            //等于0说明是水，大于等于2说明已经作为岛屿(的一部分)被计算过了
            res+=dfs(x,y);
        }
        return res;
    }
}

523. Continuous Subarray Sum

prefix sum array + hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,-1);
        int sum=0;
        int n=nums.length;
        for(int i=0; i<n; i++){
            sum+=nums[i];
            int mod=sum%k>=0 ? sum%k : sum%k+k;
            if(map.containsKey(mod)){
                if(i-map.get(mod)>=2){
                    return true;
                }
                continue;
            }
            map.put(mod,i);
        }
        return false;
    }
}

670. Maximum Swap

swap two digits at most once

greedy

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
public class LeetCode670 {
    public int maximumSwap(int num) {
        String s = String.valueOf(num);
        char[] chars = s.toCharArray();
        int[] last=new int[10];
        for (int i = 0; i < chars.length; i++) {
            last[chars[i]-'0']=i;	//记录每个digit的最后一次出现的位置; 针对1993,用最后一个9去换1
        }

        boolean done=false;
        for (int i = 0; i < chars.length; i++) {
            if(done){
                break;
            }
            int digit=chars[i]-'0';
            for(int d=9; d>digit; d--){	//只用考虑比当前digit大的数字
                if(last[d]>i){	//若后面有比当前digit大的数字，交换
                    char temp=chars[last[d]];
                    chars[last[d]]=chars[i];
                    chars[i]=temp;
                    done=true;
                    break;
                }
            }
        }
        return Integer.valueOf(new String(chars));
    }
}

721. Accounts Merge

并查集

以email为帮派，根据属于同一account来合并帮派

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class LeetCode721 {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        //email union
        //email,account map 用于返回结果时对应account和email集
        //email,index map   用于合并同一个account的所有email
        Map<String,String> email_account=new HashMap<>();
        Map<String,Integer> email_index=new HashMap<>();

        int emailCount=0;
        for (int i = 0; i < accounts.size(); i++) {
            List<String> account=accounts.get(i);
            String name=account.get(0);
            for(int j=1; j<account.size(); j++){
                String email=account.get(j);
                if(!email_account.containsKey(email)){//注意：每个email只记录第一次
                    email_account.put(email,name);
                    email_index.put(email,emailCount++);
                }
            }
        }

        UnionFind u=new UnionFind(emailCount);

        //合并同一用户的email
        for (int i = 0; i < accounts.size(); i++) {
            List<String> account=accounts.get(i);
            String head=account.get(1);
            int a=email_index.get(head);
            for(int j=2; j<account.size(); j++){
                String next=account.get(j);
                int b=email_index.get(next);
                u.union(a,b);
            }
        }

        Map<Integer,List<String>> map=new HashMap<>();
        for (String email : email_index.keySet()) {
            int i=u.find(email_index.get(email));   //每个email属于哪个帮派
            if(!map.containsKey(i)){
                map.put(i,new ArrayList<>());
            }
            map.get(i).add(email);
        }

        List<List<String>> res=new ArrayList<>();
        for (List<String> value : map.values()) {
            String name=email_account.get(value.get(0));
            Collections.sort(value);
            List<String> list=new ArrayList<>();
            list.add(name);
            list.addAll(value);
            res.add(list);
        }
        return res;
    }

    class UnionFind{

        int[] parents;
        int[] sizes;
        int total;

        UnionFind(int n){
            parents=new int[n];
            sizes=new int[n];
            for (int i = 0; i < n; i++) {
                parents[i]=i;
                sizes[i]=1;
            }
            total=n;
        }

        int find(int i){
            while(parents[i]!=i){
                i=parents[i];
            }
            return i;
        }

        void union(int a, int b){
            int rootA=find(a);
            int rootB=find(b);
            if(rootA==rootB){
                return;
            }
            if(sizes[rootA]<sizes[rootB]){
                parents[rootA]=rootB;
            }else{
                parents[rootB]=rootA;
            }
            total--;
        }
    }
}

636. Exclusive Time of Functions

the exclusive time for a given function

注意：

  1. 既然用模拟法，就老老实实模拟，不要想当然！
  2. String长度可能大于1，直接String转Integer，不要通过char
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 LeetCode636 {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] res=new int[n];
        Deque<Integer> stack=new LinkedList<>();
        String first=logs.get(0);
        String[] f = first.split(":");
        stack.push(Integer.valueOf(f[0]));
        int lastStart=Integer.valueOf(f[2]);
        for (int i=1; i<logs.size(); i++) {
            String[] split = logs.get(i).split(":");
            int cur=Integer.valueOf(split[0]);
            int time=Integer.valueOf(split[2]);
            if(split[1].charAt(0)=='s'){
                //start
                if(!stack.isEmpty()){
                    res[stack.peek()]+=time-lastStart;
                }
                stack.push(cur);
                lastStart=time;
            }else{
                //end
                res[stack.peek()]+=time-lastStart+1;
                stack.pop();
                lastStart=time+1;
            }

        }

        return res;
    }
}

498. Diagonal Traverse

找规律：遍历方向由层数决定，层数为横纵坐标之和，偶数向左上，奇数向右下

注意边界处理：

  • 向左上遇到最后一列或第一行
  • 向右下遇到最后一行或第一列
  • 同时遇到边界，优先处理越最后一列和最后一行
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 LeetCode498 {
    public int[] findDiagonalOrder(int[][] mat) {
        int row=mat.length;
        int col=mat[0].length;
        int[] res=new int[row*col];
        int i=0;
        int j=0;
        for (int k = 0; k < res.length; k++) {
            res[k]=mat[i][j];
            if(((i+j)&1)==0){//偶数层
                if(j==col-1){//不能调换判断顺序
                    i++;
                }else if(i==0){
                    j++;
                }else{
                    i--;
                    j++;
                }
            }else{//奇数层
                if(i==row-1){//不能调换判断顺序
                    j++;
                }else if(j==0){
                    i++;
                }else{
                    i++;
                    j--;
                }
            }
        }
        return res;
    }
}

173. Binary Search Tree Iterator

原来这种土方法还有洋名：扁平化

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 BSTIterator {

        LinkedList<Integer> list;
        public BSTIterator(TreeNode root) {
            list=new LinkedList<>();
            dfs(root);
        }

        public int next() {
            return list.pollFirst();
        }

        public boolean hasNext() {
            return !list.isEmpty();
        }

        private void dfs(TreeNode root){
            if(root==null){
                return;
            }
            dfs(root.left);
            list.add(root.val);
            dfs(root.right);
        }
}

1047. Remove All Adjacent Duplicates In String

看到匹配想到Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String removeDuplicates(String s) {
        int n=s.length();
        Deque<Character> stack=new LinkedList<>();
        for(int i=0; i<n; i++){
            if(!stack.isEmpty() && stack.peek()==s.charAt(i)){
                stack.pop();
            }else{
                stack.push(s.charAt(i));
            }
            
        }
        StringBuilder sb=new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}

249. Group Shifted Strings

看到分组想到Map

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
public class LeetCode249 {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String,List<String>> map=new HashMap<>();
        for (String s : strings) {
            String r=s;
            if(s.charAt(0)!='a'){
                r=reg(s);
            }
            if(!map.containsKey(r)){
                map.put(r,new ArrayList<>());
            }
            map.get(r).add(s);
        }
        return new ArrayList<>(map.values());
    }

    String reg(String s){
        char[] chars = s.toCharArray();
        int shift=chars[0]-'a';
        for (int i = 0; i < chars.length; i++) {
            chars[i]-=shift;
            if(chars[i]<'a'){	//注意"ba"的情况，需要调整成"az"
                chars[i]+=26;
            }
        }
        return new String(chars);
    }
}

139. Word Break

好题，一题三解！

法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> set=new HashSet<>(wordDict);
    int n=s.length();
    boolean[] dp=new boolean[n+1];//dp[i]表示 s[0,i-1]合法
    dp[0]=true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if(dp[j] && set.contains(s.substring(j,i))){
                dp[i]=true;
                break;
            }
        }
    }
    return dp[n];
}

法二：DFS

法三：BFS

8. String to Integer (atoi)

提早判断（越界时即判断并返回int结果）

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 LeetCode8 {
    public int myAtoi(String s) {
        s=s.trim();
        long res=0;
        boolean negative=false;
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if(c=='+' || c=='-'){
                if(i!=0){
                    break;
                }
                if(c=='-'){
                    negative=true;
                }
            }else if(Character.isDigit(c)){
                res*=10;
                res+=c-'0';
                if(res>Integer.MAX_VALUE){
                    return negative? Integer.MIN_VALUE :Integer.MAX_VALUE;
                }
            }else{
                break;
            }
        }
        return negative? (int)-res : (int)res;
    }
}

301. Remove Invalid Parentheses

好题！

法一：backtracking：

  1. 先算出misplaced left和misplaced right的数量
  2. 遇到每个括号都考虑删去或保留
  3. 根据misplaced left和misplaced right剪枝
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
74
public class LeetCode301 {
    Set<String> res;
    public List<String> removeInvalidParentheses(String s) {
        res = new HashSet<>();
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            }
            if (c == ')') {
                if (left > 0) {
                    left--;
                } else {
                    right++;
                }
            }
        }
        backtracking(left,right,new StringBuilder(),s,0);
        return new ArrayList<>(res);
    }

    private void backtracking(int left, int right, StringBuilder sb, String s, int i){
        if(i==s.length()){
            if(left!=0 || right!=0){
                return;
            }
            if(valid(sb.toString())){
                res.add(sb.toString());
            }
            return;
        }
        if(left<0 || right<0){
            return;
        }
        char c=s.charAt(i);
        if(Character.isLetter(c)){
            sb.append(c);
            backtracking(left,right,sb,s,i+1);
            sb.deleteCharAt(sb.length()-1);
        }else if(c=='('){
            sb.append(c);
            backtracking(left,right,sb,s,i+1);
            sb.deleteCharAt(sb.length()-1);
            backtracking(left-1,right,sb,s,i+1);
        }else{
            sb.append(c);
            backtracking(left,right,sb,s,i+1);
            sb.deleteCharAt(sb.length()-1);
            backtracking(left,right-1,sb,s,i+1);
        }
    }

    private boolean valid(String s){
        Deque<Character> stack=new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if(Character.isLetter(c)){
                continue;
            }
            if(c=='('){
                stack.push(c);
            }else{
                if(!stack.isEmpty()){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty() ? true : false;
    }
}

法二：BFS

注意到题目中要求最少删除，这样的描述正是广度优先搜索算法应用的场景，并且题目也要求我们输出所有的结果。我们在进行广度优先搜索时每一轮删除字符串中的 11 个括号，直到出现合法匹配的字符串为止，此时进行轮转的次数即为最少需要删除括号的个数。

我们进行广度优先搜索时，每次保存上一轮搜索的结果，然后对上一轮已经保存的结果中的每一个字符串尝试所有可能的删除一个括号的方法，然后将保存的结果进行下一轮搜索。在保存结果时，我们可以利用哈希表对上一轮生成的结果去重，从而提高效率。

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
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<String>();
        Set<String> currSet = new HashSet<String>();

        currSet.add(s);
        while (true) {
            for (String str : currSet) {
                if (isValid(str)) {
                    ans.add(str);
                }
            }
            if (ans.size() > 0) {
                return ans;
            }
            Set<String> nextSet = new HashSet<String>();
            for (String str : currSet) {
                for (int i = 0; i < str.length(); i ++) {
                    if (i > 0 && str.charAt(i) == str.charAt(i - 1)) {
                        continue;
                    }
                    if (str.charAt(i) == '(' || str.charAt(i) == ')') {
                        nextSet.add(str.substring(0, i) + str.substring(i + 1));
                    }
                }
            }
            currSet = nextSet;
        }
    }

    private boolean isValid(String str) {
        char[] ss = str.toCharArray();
        int count = 0;

        for (char c : ss) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
                if (count < 0) {
                    return false;
                }
            }
        }

        return count == 0;
    }
}

317. Shortest Distance from All Buildings

140. Word Break II

经典backtracking

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 LeetCode140 {
    List<String> res;
    Set<String> set;
    public List<String> wordBreak(String s, List<String> wordDict) {
        res=new ArrayList<>();
        set=new HashSet<>();
        for (String word : wordDict) {
            set.add(word);
        }
        backtracking(s,new ArrayList<>(),0);
        return res;
    }

    void backtracking(String s, List<String> list, int i){
        if(i==s.length()){
            StringBuilder sb=new StringBuilder();
            for (String sub : list) {
                sb.append(sub);
                sb.append(" ");
            }
            sb.deleteCharAt(sb.length()-1);
            res.add(sb.toString());
            return;
        }
        for (int j = i; j < s.length(); j++) {
            String sub=s.substring(i,j+1);
            if(set.contains(sub)){
                list.add(sub);
                backtracking(s,list,j+1);
                list.remove(list.size()-1);
            }
        }
    }
}