61. Serialize binary tree*

Please implement two functions to serialize and deserialize binary tree

The serialization of binary tree means that a binary tree is saved as a string in a certain format according to the result of a certain traversal way, so that the binary tree established in memory can be saved for a long time. Serialization can be modified based on the binary tree traversal mode of sequence first, middle, last and sequence. The result of serialization is a string. When serializing, a symbol is used to represent an empty node (ා). In order to! Represents the end (value!) of a node value.

The deserialization of binary tree refers to the reconstruction of binary tree according to the result str of serialization string obtained in a certain traversal order.

thinking

Can't understand the meaning of the question

But looking back, it's quite simple, but he's "so! What is the end (value!) of a node value?

Links: https://www.nowcoder.com/questionTerminal/cf7e25aa97c04cc1a68c8f040e71fb84?f=discussion
//Source: niuke.com

/*
    Algorithm idea: complete the serialization and deserialization according to the pre order traversal rules. The so-called serialization refers to traversing a binary tree into a string; the so-called deserialization refers to reconstructing a binary tree from a string.
    The binary tree is serialized according to the preorder traversal sequence, because the preorder traversal sequence starts from the root node. When Null pointers are encountered while traversing a binary tree, they are serialized into a special character "ා".
    In addition, the values between nodes are separated by commas.
*/
public class Solution {
    int index = -1;   //Enumeration variables
  
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null){
            sb.append("#,");
            return sb.toString();
        }
        //Preorder traversal
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
  }
    TreeNode Deserialize(String str) {
        index++;
        //int len = str.length();
        //if(index >= len){
        //    return null;
       // }
        String[] strr = str.split(",");
        TreeNode node = null;
        if(!strr[index].equals("#")){
            node = new TreeNode(Integer.valueOf(strr[index]));
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }
        return node;
  }
}

62. The k-th node of binary search tree

The middle order traversal ends at k, and returns null if k is 0 or k is greater than the number of nodes

import java.util.*;

public class Solution {
	static ArrayList<TreeNode> nodes;
	static int count;
	static int k;

	public void midOrder(TreeNode root) {
		if (count == k) return;
		if (root == null) return;
		if (root.left != null) {
			midOrder(root.left);

		}
		nodes.add(root);
		count++;
		if (root.right != null) {
			midOrder(root.right);

		}
		return;
	}

	TreeNode KthNode(TreeNode pRoot, int k) {
		count = 0;
		nodes = new ArrayList<TreeNode>();
		if (k == 0) return null;
		this.k = k;
		midOrder(pRoot);
		if (k > count) return null;
		return nodes.get(k - 1);

	}
}

63. Median in data flow

How to get the median in a data stream? If an odd number is read from the data stream, the median is the number in the middle after all the numbers are sorted. If even numbers are read from the data stream, the median is the average of the middle two numbers after all the numbers are sorted. We use the Insert() method to read the data stream and the getmedia () method to get the median of the currently read data

My violent writing

import java.util.*;
public class Solution {
   static ArrayList<Integer> nums=new ArrayList<Integer>();
    public void Insert(Integer num) {
        nums.add(num);
    }

    public Double GetMedian() {
        int len= nums.size();
      //The median of each query needs to be sorted first. According to this feature, the virtual priority queue can be tested
        Collections.sort(nums);
        if(len%2==0){
            return (Double.valueOf(nums.get(len/2))+Double.valueOf(nums.get(len/2-1)))/2;
        }
        else{
            return Double.valueOf(nums.get(len/2));
        }
        
    }

}

Reference resources

private int cnt = 0;
private PriorityQueue<Integer> low = new PriorityQueue<>();
// Default maintenance small top heap
private PriorityQueue<Integer> high = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});
 
public void Insert(Integer num) {
    // Quantity + +
    cnt++;
    // If it's an odd number
    if ((cnt & 1) == 1) {
        // Due to the odd number, it needs to be stored on the large top pile
        // But now you don't know about num and the little top heap
        // The small top pile stores the large number of the second half
        // If the current value is greater than the number on the small top heap
        if (!low.isEmpty() && num > low.peek()) {
            // Deposit in
            low.offer(num);
            // And then spit out the smallest one
            num = low.poll();
        } // The smallest is in the big top because it stores the first half
        high.offer(num);
    } else {
        // Even numbers need to store small numbers at this time
        // Note that whether it is a large top pile or a small top pile, the precondition for spitting out quantity is to have a certain number
        if (!high.isEmpty() && num < high.peek()) {
            high.offer(num);
            num = high.poll();
        } // Large numbers are spit out, small tops are inserted
        low.offer(num);
    }
 
}
 
public Double GetMedian() {// Indicates an even number
    double res = 0;
    // Odd number
    if ((cnt & 1) == 1) {
        res = high.peek();
    } else {
        res = (high.peek() + low.peek()) / 2.0;
    }
    return res;
}

64. Maximum sliding window

Given the size of an array and sliding window, find out the maximum value of the values in all sliding windows. {2,3,4, [2,6,2], 5,1}, {2,3,4,2, [6,2,5], 1}, {2,3,4,2,6, [2,5, 1]}.

My code is still violent

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {  ArrayList<Integer> res=new ArrayList<Integer>();
        if(size<=0||size>num.length){
        return res;
    }
        int len = num.length;
      int start=0;
     int end=size-1;
     int flag=0;
    
     while(end<len){
              int max=num[start];
         for(int i=start;i<=end;i++){
             if(num[i]>max){
                 max=num[i];
             }
         }
             res.add(max);
         start++;
         end++;   
     }
     return res;
        
    }
}

import java.util.*;
//Idea: use a large top heap to save the data in the current sliding window. Each time the sliding window moves one grid, it will count the front one out of the heap and the back one into the heap.
public class Solution {
    public PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>((o1,o2)->o2-o1);//Big top pile
    public ArrayList<Integer> result = new ArrayList<Integer>();//Save results
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        if(num==null || num.length<=0 || size<=0 || size>num.length){
            return result;
        }
        int count=0;
        for(;count<size;count++){//Initialize sliding window
            maxQueue.offer(num[count]);
        }
        while(count<num.length){//For each operation, find the maximum value (using the large top heap of the priority queue), and then slide backward (one out of the heap, one in the heap)
            result.add(maxQueue.peek());
            maxQueue.remove(num[count-size]);
            maxQueue.add(num[count]);
            count++;
        }
        result.add(maxQueue.peek());//The results are not saved after the last time in the heap. You can do one extra time here
 
        return result;
    }
}

65. Matrix path

Please design a function to determine whether there is a path containing all characters of a string in a matrix. The path can start from any lattice in the matrix, and each step can move one lattice left, right, up and down in the matrix. If a path passes through a lattice in the matrix, the path can no longer enter the lattice.

My code, only over 30%, is similar to the reference, but I just don't know what's wrong

public class Solution {
    static  int flag;
    static int row;
    static  int col;
    static  boolean[][] vis;
    public  static void dfs(char[] matrix,int x,int y ,char[] str, int cur){
        int len=str.length;
        if(cur==len){
            flag=1;
            return;
        }
        if(flag==1){
            return;
            }
        if((x>=0&&x<row)&&(y<col&&y>=0)){
            if(!vis[x][y]&&matrix[x*col+y]==str[cur]){
                vis[x][y]=true;
                int[] x_index={0,0,-1,1};
                int[] y_index={1,-1,0,0};
                for(int i=0;i<4;i++){
                    dfs(matrix,x+x_index[i],y+y_index[i],str,cur+1);
                }
            }
        }
        return;
    }
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        flag=0;
        row=rows;
        col=cols;
        vis=new boolean[row][col];
        for (int i = 0; i <rows ; i++) {
            for (int j = 0; j <cols ; j++) {
                if(flag==1){
                    return  true;
                }
                if(matrix[i*cols+j]==str[0]){
                    dfs(matrix,i,j,str,0);
                }

            }
        }
        return  false;
    }
}

Reference resources

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        //Flag bit, initialized to false
        boolean[] flag = new boolean[matrix.length];
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                 //Loop through the two-dimensional array, find the value of the starting point equal to the first element of str, and then recursively determine whether there is a qualified around -- backtracking method
                 if(judge(matrix,i,j,rows,cols,flag,str,0)){
                     return true;
                 }
            }
        }
        return false;
    }
     
    //Judge (initial matrix, index row coordinate i, index vertical coordinate j, number of matrix rows, number of matrix columns, string to be judged, string index initial 0 is the first bit of the string to be judged first)
    private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
        //First, calculate the position of the first matched element into one-dimensional array according to i and j
        int index = i*cols+j;
        //Recursive termination condition
        if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k] || flag[index] == true)
            return false;
        //If k has reached the end of str, it means that the previous ones have been matched successfully. Just return true directly
        if(k == str.length-1)
            return true;
        //The first position to go is set to true, indicating that it has passed
        flag[index] = true;
         
        //Backtracking, recursive search. Add one to k every time you find it. Can't find it. Restore
        if(judge(matrix,i-1,j,rows,cols,flag,str,k+1) ||
           judge(matrix,i+1,j,rows,cols,flag,str,k+1) ||
           judge(matrix,i,j-1,rows,cols,flag,str,k+1) ||
           judge(matrix,i,j+1,rows,cols,flag,str,k+1)  )
        {
            return true;
        }
        //Go here, it means that this road is blocked. Restore, and try another path
        flag[index] = false;
        return false;
        }}

66. Range of motion of robot

There is a grid of m rows and n columns on the ground. A robot starts to move from the grid of coordinates 0,0. Each time, it can only move one grid to the left, right, up and down directions, but it can't enter the grid where the sum of the row coordinates and the column coordinates is greater than k. For example, when k is 18, the robot can enter the grid (35, 37), because 3 + 5 + 3 + 7 = 18. However, it cannot enter the grid (35,38) because 3 + 5 + 3 + 8 = 19. How many squares can the robot reach?

//Classic dfs, on the contrary, has stepped on many holes in the details, drunk
public class Solution {
    static int count;
    static boolean[][] vis;
    static int row;
    static int col;

    public boolean judge(int x, int y, int threshold) {
        String s1 = String.valueOf(x);
        String s2 = String.valueOf(y);
        char[] c = (s1 + s2).toCharArray();
        int sum = 0;
        for (int i = 0; i < c.length; i++) {
            sum += Integer.parseInt(String.valueOf(c[i]));
        }

        if (sum > threshold) {
            return false;
        } else {
            return true;
        }
    }

    public void dfs(int x, int y, int threshold) {
        int[] x_index = {0, 0, -1, 1};
        int[] y_index = {-1, 1, 0, 0};
        if ((x >= 0 && x < row) && (y >= 0 && y < col)) {
            if (judge(x, y, threshold) && !vis[x][y]) {
                vis[x][y] = true;
                count++;
                for (int i = 0; i <4 ; i++) {
                    dfs(x+x_index[i],y+y_index[i],threshold);
                }
            }
        }
        return;
    }
    public int movingCount(int threshold, int rows, int cols) {
        row = rows;
        count=0;
        col = cols;
        vis = new boolean[rows][cols];
        dfs(0, 0, threshold);
        return count;
    }}

67. Cut the rope*

To give you a rope of length N, please cut the rope into integral length m segments (m, n are integers, n > 1 and M > 1). The length of each segment of rope is recorded as k[0],k[1] k[m]. Excuse me, k[0]xk[1]x What is the possible maximum product of xk[m]? For example, when the length of a rope is 8, we cut it into three sections with the length of 2, 3 and 3, and the maximum product is 18.

public class Solution {
    public int cutRope(int n) {
       // When n < = 3, M > 1 must be segmented, for example: 3 must be divided into 1, 2; 1, 1, 1, n=3 the maximum segmented product is 2,
        if(n==2)
            return 1;
        if(n==3)
            return 2;
        int[] dp = new int[n+1];
        /*
        The following three lines are n > = 4. Unlike n < = 3, 4 can be divided into many segments, such as 1 and 3,
        There is no need to subdivide the 3 here, because the maximum of the 3 segments is only 2, and the indiscriminate is 3. Record the largest.
         */
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        int res=0;//Record the largest
        for (int i = 4; i <= n; i++) {
            for (int j = 1; j <=i/2 ; j++) {
                res=Math.max(res,dp[j]*dp[i-j]);
            }
            dp[i]=res;
        }
        return dp[n];
    }
}