IVN
0%

DFS(2)

Posted on Edited on In
Symbols count in article: 24k Reading time ≈ 22 mins.

DFS选编（2）

472. Concatenated Words

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
Set<String> set=new HashSet<>();
public List<String> findAllConcatenatedWordsInADict(String[] words) {
    List<String> res=new ArrayList<>();
    for (String word : words) {
        set.add(word);
    }
    for (String word : words) {
        for (int i = 0; i < word.length()-1; i++) {
            //[0,i]
            if(set.contains(word.substring(0,i+1))
                    && dfs(word,i+1)){
                res.add(word);
                break;
            }
        }
    }
    return res;
}

boolean dfs(String s, int start){
    if(start==s.length()){
        return true;
    }
    for (int i = start; i < s.length(); i++) {
        if(set.contains(s.substring(start,i+1)) && dfs(s,i+1)){
            return true;
        }
    }
    return false;
}

508. Most Frequent Subtree Sum

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
Map<Integer,Integer> map=new HashMap<>();
  int max=Integer.MIN_VALUE;
public int[] findFrequentTreeSum(TreeNode root) {
    dfs(root);
    List<Integer> list=new ArrayList<>();
    for (Integer i : map.keySet()) {
        if(map.get(i)==max){
            list.add(i);
        }
    }
    int[] res=new int[list.size()];
    for (int i = 0; i < res.length; i++) {
        res[i]=list.get(i);
    }
    return res;
}

int dfs(TreeNode node){
    if(node==null){
        return 0;
    }
    int l=dfs(node.left);
    int r=dfs(node.right);
    int sum=l+r+node.val;
    map.put(sum,map.getOrDefault(sum,0)+1);
    int freq=map.get(sum);
    max=Math.max(max,freq);
    return sum;
}

529. Minesweeper

注意adjacent的定义：

  • 'B' represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals)

DFS:

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
    int row;
    int col;
    char[][] board;
    public char[][] updateBoard(char[][] board, int[] click) {
        row=board.length;
        col=board[0].length;
        this.board=board;
        int i=click[0];
        int j=click[1];
        if(board[i][j]=='M'){
            board[i][j]='X';
        }else{
            dfs(i,j);
        }
        return board;
    }

    /* [["E","E","E","E","E","E","E","E"],
        ["E","E","E","E","E","E","E","M"],
        ["E","E","M","E","E","E","E","E"],
        ["M","E","E","E","E","E","E","E"],
        ["E","E","E","E","E","E","E","E"],
        ["E","E","E","E","E","E","E","E"],
        ["E","E","E","E","E","E","E","E"],
        ["E","E","M","M","E","E","E","E"]]
[0,0]*/

    void dfs(int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || board[i][j]!='E'){
            return;
        }
        int count=0;
        for(int x=i-1; x<=i+1; x++){
            for(int y=j-1; y<=j+1; y++){
                if(x>=0 && x<row && y>=0 && y<col && board[x][y]=='M'){
                    count++;
                }
            }
        }
        if(count==0){
            board[i][j]='B';
            dfs(i-1,j-1);
            dfs(i-1,j);
            dfs(i-1,j+1);
            dfs(i,j-1);
            dfs(i,j+1);
            dfs(i+1,j-1);
            dfs(i+1,j);
            dfs(i+1,j+1);
        }else{
            board[i][j]=(char)('0'+count);
        }
    }

BFS:

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 char[][] updateBoard(char[][] board, int[] click) {
    int row=board.length;
    int col=board[0].length;
    Deque<int[]> q=new LinkedList<>();
    if(board[click[0]][click[1]]=='M'){
        board[click[0]][click[1]]='X';
    }else{
        q.offer(click);
        while(!q.isEmpty()){
            int[] cur=q.poll();
            int i=cur[0];
            int j=cur[1];
            if(board[i][j]!='E'){
                continue;
            }
            int count=0;
            for(int x=i-1; x<=i+1; x++){
                for(int y=j-1; y<=j+1; y++){
                    if(x>=0 && x<row && y>=0 && y<col
                            && board[x][y]=='M'){
                        count++;
                    }
                }
            }
            if(count==0){
                board[i][j]='B';
                for(int x=i-1; x<=i+1; x++){
                    for(int y=j-1; y<=j+1; y++){
                        if(x>=0 && x<row && y>=0 && y<col
                                && board[x][y]=='E'){
                            q.offer(new int[]{x,y});
                        }
                    }
                }
            }else{
                board[i][j]=(char)('0'+count);
            }
        }
    }
    return board;
}

545. Boundary of 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
List<Integer> res=new LinkedList<>();
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
    res.add(root.val);
    leftBoundary(root.left);
    leaf(root.left);
    leaf(root.right);
    rightBoundary(root.right);
    return res;
}

void leaf(TreeNode node){
    if(node==null){
        return;
    }
    if(node.left==null && node.right==null){
        res.add(node.val);
        return;
    }
    leaf(node.left);
    leaf(node.right);
}

void leftBoundary(TreeNode node){
    if(node==null || node.left==null && node.right==null){
        return;
    }
    res.add(node.val);
    if(node.left!=null){
        leftBoundary(node.left);
    }else{
        leftBoundary(node.right);
    }
}

void rightBoundary(TreeNode node){
    if(node==null || node.left==null && node.right==null){
        return;
    }
    if(node.right!=null){
        rightBoundary(node.right);
    }else{
        rightBoundary(node.left);
    }
    res.add(node.val);
}

549. Binary Tree Longest Consecutive Sequence II

好题！需要返回两个值怎么办？

  • 返回arr
  • arr[0] 为increasing consecutive sequence的长度
  • arr[1] 为decreasing consecutive sequence的长度
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
int max=1;
  //[icr,dcr]
public int longestConsecutive(TreeNode root) {
    dfs(root);
    return max;
}

int[] dfs(TreeNode node){
    if(node==null){
        return new int[]{0,0};
    }
    int icr=1;
    int dcr=1;
    if(node.left!=null){
        int[] l=dfs(node.left);
        if(node.val==node.left.val+1){
            icr+=l[0];
        }
        if(node.val==node.left.val-1){
            dcr+=l[1];
        }
    }
    if(node.right!=null){
        int[] r=dfs(node.right);
        if(node.val==node.right.val+1){
            icr=Math.max(icr,1+r[0]);
        }
        if(node.val==node.right.val-1){
            dcr=Math.max(dcr,1+r[1]);
        }
    }
    max=Math.max(max,icr+dcr-1);
    return new int[]{icr,dcr};
}

563. Binary Tree Tilt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 int res=0;
 public int findTilt(TreeNode root) {
     sum(root);
     return res;
 }

int sum(TreeNode node){
     if(node==null){
         return 0;
     }
   
     if(node.left==null && node.right==null){
           int val=node.val;
           node.val=0;
           return val;
     }
     int l=sum(node.left);
     int r=sum(node.right);
     int val=node.val;
     node.val=Math.abs(l-r);
     res+=node.val;
     return l+r+val;
}

565. Array Nesting

Time Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int max=0;
public int arrayNesting(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        dfs(nums,nums[i],new boolean[nums.length],0);
    }
    return max;
}

void dfs(int[] nums, int cur, boolean[] visited, int l){
    if(visited[cur]){
        max=Math.max(max,l);
        return;
    }
    visited[cur]=true;
    dfs(nums,nums[cur],visited,l+1);
}

无需重复考虑元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    int max=0;
public int arrayNesting(int[] nums) {
    HashSet<Integer> set=new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        dfs(nums,nums[i],set,0);
    }
    return max;
}

void dfs(int[] nums, int cur, Set<Integer> visited, int l){
    if(visited.contains(cur)){
        max=Math.max(max,l);
        return;
    }
    visited.add(cur);
    dfs(nums,nums[cur],visited,l+1);
}

572. Subtree of Another Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
      if(root==null){
          return false;
      }
    if(isEqual(root,subRoot)){
        return true;
    }
    return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}

boolean isEqual(TreeNode root, TreeNode subRoot) {
    if(root==null && subRoot==null){
        return true;
    }
    if(root==null || subRoot==null || root.val!=subRoot.val){
        return false;
    }
    return isEqual(root.left,subRoot.left) && isEqual(root.right,subRoot.right);
}

589. N-ary Tree Preorder Traversal

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 List<Integer> preorder(Node root) {
    List<Integer> res=new ArrayList<>();
    if(root==null){
        return res;
    }
    Deque<Node> stack=new LinkedList<>();
    stack.push(root);
    while(!stack.isEmpty()){
        //root, 0,1,2
        //2,1,0, root
        Node node=stack.pop();
        if(node!=null){
            for (int i = node.children.size() - 1; i >= 0; i--) {
                stack.push(node.children.get(i));
            }
            stack.push(node);
            stack.push(null);
        }else{
            node=stack.poll();
            res.add(node.val);
        }
    }
    return res;
}

590. N-ary Tree Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<Integer> postorder(Node root) {
    List<Integer> res=new ArrayList<>();
    if(root==null){
        return res;
    }
    Deque<Node> stack=new LinkedList<>();
    stack.offer(root);
    while(!stack.isEmpty()){
        Node cur=stack.pop();
        if(cur!=null){
            //out: left right root
            //in:  root right left
            stack.push(cur);
            stack.push(null);
            for (int i = cur.children.size() - 1; i >= 0; i--) {
                stack.push(cur.children.get(i));
            }
        }else{
            res.add(stack.pop().val);
        }
    }
    return res;
}

652. Find Duplicate Subtrees

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
List<TreeNode> res=new ArrayList<>();
Map<String,Integer> map=new HashMap<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    dfs(root);
    return res;
}

String dfs(TreeNode node){
    if(node==null){
        return "#";
    }
    String l=dfs(node.left);
    String r=dfs(node.right);
    String cur=node.val+","+l+","+r;
    map.put(cur,map.getOrDefault(cur,0)+1);
    if(map.get(cur)==2){
        res.add(node);
    }
    return cur;
}

663. Equal Tree Partition

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
Map<TreeNode,Long> map=new HashMap<>();
public boolean checkEqualTree(TreeNode root) {
      if(root==null){
          return false;
      }
    long l=sum(root.left);
    long r=sum(root.right);
    if(root.right!=null && l+root.val==r || root.left!=null && r+root.val==l){
        return true;
    }
    if(root.left!=null){
        root.left.val+=root.val+r;
    }
    if(root.right!=null){
        root.right.val+=root.val+l;
    }
    return checkEqualTree(root.left) || checkEqualTree(root.right);
}

long sum(TreeNode node){
      if(node==null){
          return 0;
      }
      if(map.containsKey(node)){
          return map.get(node);
      }
      long res=sum(node.left)+sum(node.right)+node.val;
      map.put(node,res);
      return res;
}

690. Employee Importance

DFS:

1
2
3
4
5
6
7
8
9
10
int res=0;
for (Employee employee : employees) {
    if(employee.id==id){
        res+=employee.importance;
        for (Integer next : employee.subordinates) {
            res+=getImportance(employees,next);
        }
    }
}
return res;

BFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int getImportance(List<Employee> employees, int id) {
    Map<Integer,Employee> map=new HashMap<>();
    for (Employee employee : employees) {
        map.put(employee.id,employee);
    }
    Deque<Integer> q=new LinkedList<>();
    q.offer(id);
    int res=0;
    while(!q.isEmpty()){
        Employee cur=map.get(q.poll());
        res+=cur.importance;
        for (Integer next : cur.subordinates) {
            q.offer(next);
        }
    }
    return res;
}

687. Longest Univalue 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
28
29
30
int max=0;
public int longestUnivaluePath(TreeNode root) {
    dfs(root);
    return max;
}

int[] dfs(TreeNode node){
     if(node==null){
         return null;
     }
     //[val,len]
     int[] l=dfs(node.left);
     int[] r=dfs(node.right);
     int len=1;
     if(l!=null && l[0]==node.val){
         len+=l[1];
     }
    if(r!=null && r[0]==node.val){
        len+=r[1];
    }
    max=Math.max(max,len-1);
    int path=1;
    if(l!=null && l[0]==node.val){
        path+=l[1];
    }
    if(r!=null && r[0]==node.val){
        path=Math.max(path,1+r[1]);
    }
    return new int[]{node.val,path};
}

785. Is Graph Bipartite?

https://leetcode.com/problems/is-graph-bipartite/discuss/115487/Java-Clean-DFS-solution-with-Explanation

Our goal is trying to use two colors to color the graph and see if there are any adjacent nodes having the same color.
Initialize a color[] array for each node. Here are three states for colors[] array:
0: Haven't been colored yet.
1: Blue.
-1: Red.
For each node,

  1. If it hasn’t been colored, use a color to color it. Then use the other color to color all its adjacent nodes (DFS).
  2. If it has been colored, check if the current color is the same as the color that is going to be used to color it. (Please forgive my english… Hope you can understand it.)

DFS Solution:

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 boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n];			
				
        for (int i = 0; i < n; i++) {              //This graph might be a disconnected graph. So check each unvisited node.
            if (colors[i] == 0 && !validColor(graph, colors, 1, i)) {
                return false;
            }
        }
        return true;
    }
    
    public boolean validColor(int[][] graph, int[] colors, int color, int node) {
        if (colors[node] != 0) {
            return colors[node] == color;
        }       
        colors[node] = color;       
        for (int next : graph[node]) {
            if (!validColor(graph, colors, -color, next)) {
                return false;
            }
        }
        return true;
    }
}

841. Keys and Rooms

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 LeetCode841 {
    List<List<Integer>> rooms;
    int n;
    Set<Integer> set=new HashSet<>();
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        this.rooms=rooms;
        this.n=rooms.size();
        return dfs(0);
    }

    boolean dfs(int cur){
        set.add(cur);
        if(set.size()==n){
            return true;
        }
        boolean res=false;
        for (Integer next : rooms.get(cur)) {
            if(set.contains(next)){
                continue;
            }
            if(dfs(next)){
                res=true;
                break;
            }
        }
        return res;
    }
}

397. Integer Replacement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Map<Long,Integer> map=new HashMap<>();
public int integerReplacement(int n) {
    return dfs(n);
}

int dfs(long n){
    if(n==1){
        return 0;
    }
    if(map.containsKey(n)){
        return map.get(n);
    }
    int res=0;
    if(n%2==0){
        res=1+dfs(n/2);
    }else{
        res=1+Math.min(dfs(n+1),dfs(n-1));
    }
    map.put((long)n,res);
    return res;
}

473. Matchsticks to Square

NP problem: best solution is exponential

https://leetcode.com/problems/matchsticks-to-square/discuss/95744/cpp-6ms-solution-with-DFS

3 optimizations:

  1. bigger nums added first, if any side > target, return false
  2. if 2 sides have the same length, avoid repetitions
  3. check in advance if sum%4==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
37
38
39
40
41
42
long[] sides=new long[4];
long target;
public boolean makesquare(int[] matchsticks) {
    long sum=0;
    int n=matchsticks.length;
    Arrays.sort(matchsticks);
    for (int matchstick : matchsticks) {
        sum+=matchstick;
    }
    if(sum%4!=0){
        return false;
    }
    target=sum/4;
    return dfs(matchsticks,n-1);
}

boolean dfs(int[] nums, int i){
    if(i==-1){
        if(sides[0]==sides[1] && sides[1]==sides[2] && sides[2]==sides[3]){
            return true;
        }
        return false;
    }
    for (int j = 0; j < 4; j++) {
        boolean skip=false;
        for(int p=0; p<j; p++){
            if(sides[p]==sides[j]){
                skip=true;
                break;
            }
        }
        if(skip || sides[j]+nums[i]>target){
            continue;
        }
        sides[j]+=nums[i];
        if(dfs(nums,i-1)){
            return true;
        }
        sides[j]-=nums[i];
    }
    return false;
}

988. Smallest String Starting From Leaf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
String res;
public String smallestFromLeaf(TreeNode root) {
    dfs(root, new StringBuilder());
    return res;
}

void dfs(TreeNode node, StringBuilder sb){
    if(node==null){
        return;
    }
    sb.append((char)('a'+node.val));
    if(node.left==null && node.right==null){
        sb.reverse();
        String s=sb.toString();
        if(res==null || s.compareTo(res)<0){
            res=s;
        }
        sb.reverse();
    }
    dfs(node.left,sb);
    dfs(node.right,sb);
    sb.deleteCharAt(sb.length()-1);
}

979. Distribute Coins in Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int res=0;
public int distributeCoins(TreeNode root) {
    dfs(root);
    return res;
}

int dfs(TreeNode node){
    if(node==null){
        return 0;
    }
    if(node.left==null && node.right==null){
        res+=Math.abs(node.val-1);
        return node.val-1;
    }
    int l=dfs(node.left);
    int r=dfs(node.right);
    res+=Math.abs(l+r+node.val-1);
    return l+r+node.val-1;
}

967. Numbers With Same Consecutive Differences

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
List<Integer> list=new ArrayList<>();
public int[] numsSameConsecDiff(int n, int k) {
    if(n==0){
        return new int[]{};
    }
    char[] chars=new char[n];
    for (char i = '0'; i <= '9'; i++) {
        chars[0]=i;
        dfs(chars,n,k,1);
    }
    int[] res=new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        res[i]=list.get(i);
    }
    return res;
}

void dfs(char[] chars, int n, int k, int cur){
    if(cur==n){
        String s=new String(chars);
        if(s.length()==1 || s.charAt(0)!='0'){
            int num=Integer.valueOf(s);
            list.add(num);
        }
        return;
    }
    char last=chars[cur-1];
    if(last=='0'){
        return;
    }
    char c=(char)(last+k);
    if(Character.isDigit(c)){
        chars[cur]=c;
        dfs(chars,n,k,cur+1);
    }
    if(k!=0){
        c=(char)(last-k);
        if(Character.isDigit(c)){
            chars[cur]=c;
            dfs(chars,n,k,cur+1);
        }
    }
}

1026. Maximum Difference Between Node and Ancestor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int res;
public int maxAncestorDiff(TreeNode root) {
    dfs(root,root.val,root.val);
    return res;
}

void dfs(TreeNode node, int max, int min){
    if(node==null){
        return;
    }
    int v=node.val;
    res=Math.max(res,Math.max(Math.abs(max-v),Math.abs(min-v)));
    max=Math.max(max,v);
    min=Math.min(min,v);
    dfs(node.left,max,min);
    dfs(node.right,max,min);
}

698. Partition to K Equal Sum Subsets

经典NP穷举，同472

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
int[] sets;
public boolean canPartitionKSubsets(int[] nums, int k) {
    if(k==1){
        return true;
    }
    int n=nums.length;
    Arrays.sort(nums);
    int sum=0;
    for (int num : nums) {
        sum+=num;
    }
    if(sum%k!=0){
        return false;
    }
    int target=sum/k;
    sets=new int[k];
    return dfs(nums,n-1,target,k);
}

boolean dfs(int[] nums, int cur, int target, int k){
    if(cur==-1){
        for (int i = 0; i < k; i++) {
            if(sets[i]!=target){
                return false;
            }
        }
        return true;
    }
    boolean res=false;
    for (int i = 0; i < k; i++) {
        boolean skip=false;
        for(int j=0; j<i; j++){
            if(sets[j]==sets[i]){
                skip=true;
                break;
            }
        }
        if(!skip && sets[i]+nums[cur]<=target){
            sets[i]+=nums[cur];
            if(dfs(nums,cur-1,target,k)){
                return true;
            }
            sets[i]-=nums[cur];
        }
    }
    return false;
}

1522. Diameter of N-Ary 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
int max=0;
public int diameter(Node root) {
    //return Math.max(max,depth(root)-1); wrong!
    int depth=depth(root);
    return Math.max(max,depth-1);
}

int depth(Node node){
    if(node==null){
        return 0;
    }
    int max1=0;
    int max2=0;//max1>=max2
    for (Node child : node.children) {
        int depth=depth(child);
        if(depth>max1){
            max2=max1;
            max1=depth;
        }else if(depth>max2){
            max2=depth;
        }
    }
    max=Math.max(max,max1+max2);
    return max1+1;
}

1485. Clone Binary Tree With Random Pointer

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 LeetCode1485 {
      class Node {
      int val;
      Node left;
      Node right;
      Node random;
      Node() {}
      Node(int val) { this.val = val; }
      Node(int val, Node left, Node right, Node random) {
          this.val = val;
          this.left = left;
          this.right = right;
          this.random = random;
      }
    }

    class NodeCopy {
        int val;
        NodeCopy left;
        NodeCopy right;
        NodeCopy random;
        NodeCopy() {}
        NodeCopy(int val) { this.val = val; }
        NodeCopy(int val, NodeCopy left, NodeCopy right, NodeCopy random) {
            this.val = val;
            this.left = left;
            this.right = right;
            this.random = random;
        }
    }

    Map<Node,NodeCopy> map=new HashMap<>();
    public NodeCopy copyRandomBinaryTree(Node root) {
        copy(root);
        return map.get(root);
    }

    private NodeCopy copy(Node node){
          if(node==null){
              return null;
          }
          if(map.containsKey(node)){
              return map.get(node);
          }
          NodeCopy copy=new NodeCopy(node.val);
          map.put(node,copy);
          copy.left=copy(node.left);
          copy.right=copy(node.right);
          copy.random=copy(node.random);
          return copy;
    }
}

1372. Longest ZigZag Path in a Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int max=-1;
public int longestZigZag(TreeNode root) {
    dfs(root);
    return max;
}

private int[] dfs(TreeNode node){
    if(node==null){
        return new int[]{-1,-1};
    }
    //[l,r]
    int[] l=dfs(node.left);
    int[] r=dfs(node.right);
    int curL=1+l[1];
    int curR=1+r[0];
    max=Math.max(max,Math.max(curL,curR));
    return new int[]{curL,curR};
}

2767. Partition String Into Minimum Beautiful Substrings

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 int minimumBeautifulSubstrings(String s) {
    int n=s.length();
    int res=Integer.MAX_VALUE;
    if(s.charAt(0)=='0'){
        return -1;
    }
    for (int i = 0; i < n; i++) {
        //[0,i]
        if(valid(Long.parseLong(s.substring(0,i+1),2))){
            int sub=i+1>=n ? 0 : minimumBeautifulSubstrings(s.substring(i+1));
            if(sub!=-1){
                res=Math.min(res,1+sub);
            }
        }
    }
    return res==Integer.MAX_VALUE ? -1 : res;
}

private boolean valid(long num){
    while(num>=5){
        if(num%5!=0){
            return false;
        }
        num/=5;
    }
    return num==1;
}

2305. Fair Distribution of Cookies

经典剪枝：

  1. sort
  2. avoid repetition
  3. avoid meaningless search
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
int n;
int k;
int res;
int[] children;
public int distributeCookies(int[] cookies, int k) {
    Arrays.sort(cookies);
    n=cookies.length;
    this.k=k;
    children=new int[k];
    res=Integer.MAX_VALUE;
    dfs(cookies,n-1,0);
    return res;
}

private void dfs(int[] cookies, int i, int curMax){
    if(curMax>=res){
        return;
    }
    if(i==-1){
        res=Math.min(res,curMax);
        return;
    }
    for (int j = 0; j < k; j++) {
        for (int p = 0; p < j; p++) {
            if(children[p]==children[j]){
                continue;
            }
        }
        children[j]+=cookies[i];
        dfs(cookies,i-1,Math.max(curMax,children[j]));
        children[j]-=cookies[i];
    }
}

673. Number of Longest Increasing Subsequence

Bottom Up

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 int findNumberOfLIS(int[] nums) {
    int n=nums.length;
    int[][] dp=new int[n][2];//maxLen,maxCount ending with i
    for (int i = 0; i < n; i++) {
        int len=1;
        int count=1;
        for (int j = 0; j < i; j++) {
            if(nums[i]>nums[j]){
                if(len==dp[j][0]+1){
                    count+=dp[j][1];
                }else if(len<dp[j][0]+1){
                    len=dp[j][0]+1;
                    count=dp[j][1];
                }
            }
        }
        dp[i][0]=len;
        dp[i][1]=count;
    }
    int max=0;
    for (int i = 0; i < n; i++) {
        max=Math.max(max,dp[i][0]);
    }
    int res=0;
    for (int i = 0; i < n; i++) {
        if(dp[i][0]==max){
            res+=dp[i][1];
        }
    }
    return res;
}

Top Down

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
int[][] dp;
public int findNumberOfLIS(int[] nums) {
    int n=nums.length;
    //top down明显慢于bottom up
    dp=new int[n][2]; //maxLen, maxCount
    int max=0;
    int count=0;
    for (int i = 0; i < n; i++) {
        int[] cur=lis(nums,i);
        if(cur[0]>max){
            max=cur[0];
            count=cur[1];
        }else if(cur[0]==max){
            count+=cur[1];
        }
    }
    return count;
}

private int[] lis(int[] nums,int i){
    if(dp[i][0]!=0){
        return dp[i];
    }
    int max=1;
    int maxCount=1;

    for (int j = i+1; j < nums.length; j++) {
        if(nums[j]>nums[i]){
            int[] next=lis(nums,j);
            int cur=1+next[0];
            if(cur>max){
                max=cur;
                maxCount=next[1];
            }else if(cur==max){
                maxCount+=next[1];
            }
        }
    }
    dp[i][0]=max;
    dp[i][1]=maxCount;
    return dp[i];
}

427. Construct Quad 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class LeetCode427 {
// Definition for a QuadTree node.
private class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;


    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};

    class Solution {
        int[][] grid;
        int n;
        public Node construct(int[][] grid) {
            this.grid=grid;
            n=grid.length;
            return dfs(0,0,n);
        }

        private Node dfs(int rowStart, int colStart, int len){
            int val=grid[rowStart][colStart];
            boolean isLeaf=true;
            for(int i=rowStart; i<rowStart+len; i++){
                for(int j=colStart; j<colStart+len; j++){
                    if(grid[i][j]!=val){
                        isLeaf=false;
                        break;
                    }
                }
            }
            if(isLeaf){
                return new Node(val==1,true);
            }
            Node node=new Node(false,false);
            node.topLeft=dfs(rowStart,colStart,len/2);
            node.topRight=dfs(rowStart,colStart+len/2,len/2);
            node.bottomLeft=dfs(rowStart+len/2,colStart,len/2);
            node.bottomRight=dfs(rowStart+len/2,colStart+len/2,len/2);
            return node;
        }
    }
}