Tme2022 campus recruitment background development / operation development / business operation and maintenance / application development written examination (I) a little self analysis of programming q

Fill the array

Catalog

Fill the array 【 More difficult +DP】

subject ：

Ideas ：

Code ：

Maximum 【 Although write , But not flexible 】

subject ：

Ideas ：

Code ：

【 Must be 】 Trim the leaves 【 Simple + Two fork tree pruning 】

subject ：

Ideas ：

Code ：

---

Fill the array 【 More difficult +DP】

subject ：

Niu Mei gave Niu Niu a length of  n  Subscript from 0 The starting positive integer array  a , Careless Niuniu accidentally deleted some of the figures .

If ai​ Been deleted , be ai​=0. For all deleted numbers , Niuniu must select a positive integer to fill . Now Niuniu wants to know how many filling schemes make ：

a0​≤a1​≤...≤an−1​  And for all 0≤i≤n−1 Satisfy 1≤ai​≤k .

Function passes in a subscript from 0 Starting array  a  And a positive integer  k , Please return the legal number of filling scheme pairs  10^9+7 The value of the die , The number of schemes guaranteed to be nonexistent is 0 The data of .

Example 1

Input

[0,4,5],6

Output

4

explain

All legal filling schemes are ：[1,4,5],[2,4,5],[3,4,5],[4,4,5], common 4 Kind of .  

Example 2

Input

[1,0,0],3

Output

6

explain

All legal filling schemes are ：[1,1,1],[1,1,2],[1,2,2],[1,2,3],[1,3,3],[1,1,3] common 6 Kind of   

Example 3

Input

[0,0,0,0,0,67,0,0],100

Output

746845806

remarks :

1≤n,k≤1000

Array a Satisfy 0≤ai​≤k

Ideas ：

• For each segment in the input array 0 Can be abstracted as a sub problem ：
  • fill i Number , The value range is j Number , Find the number of filling schemes
• The answer to the final question is every paragraph 0 Multiply the number of schemes and then take the module .
• set up dp[i][j] For filling i Number 、 The value range is j Number of filling schemes ：
  • fill 0 The number of schemes is 0,dp[0][j] = 0
  • The value range is 0 The number of schemes is 0,dp[i][0] = 0
  • fill 1 The number of schemes is equal to the number of value ranges ,dp[1][j] = j
  • fill i The number can be converted into filling i-1 Number , For the last number, there is j Three filling schemes , Choosing different numbers will affect the remaining i-1 The value range of the number , namely  dp[i][j]=∑k=1jdp[i−1][k]dp[i][j] , That is to say dp[i] by dp[i-1] And , It can be simplified as  dp[i][j]=dp[i][j−1]+dp[i−1][j];
• Self analysis ： This is Niuke's highly praised answer , At that time, I found the law for a long time and didn't find it , The result is DP, Still inflexible, I ;
• Reference resources ： Fill the array __ Cattle from

Code ：

import java.util.*;
 
//  Niuke praises the solution , Dynamic programming 
public class Solution {
	int MOD=1000000007;
	long[][] dp=new long[1005][1005];//dp[i][j] Indicates filling i Number , The number of values is j Number of alternatives 
	public int FillArray(int[] a, int k) {
		long res=1;
		int n=a.length;
		// initialization 
		for(int i=1;i<=k;i++){
			dp[1][i]=i;
		}
		for(int i=2;i<=n;i++){
			for(int j=1;j<=k;j++){
				dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;// State transition equation 
			}
		}
		 
		int i=0;
		while(i<n){// Calculate the number of schemes in each section , Multiplicative multiplication 
			while(i<n&&a[i]!=0){
				i++;
			}
			if(i==n) break;
			int l=i;// Left interval 
			int x=i>0?a[i-1]:1;
			while(i<n&&a[i]==0){
				i++;
			}
			int r=i;// The right range 
			int y=i<n?a[i]:k;
			res=(res*dp[r-l][y-x+1])%MOD;// Multiplicative multiplication 
		}
		return (int)res;
	}
}

Maximum 【 Although write , But not flexible 】

subject ：

There is a character only '1' To '9' The length of the composition is  n  String  s , Now you can intercept one of them with a length of  k  And treat the substring as a positive decimal integer , For example, for substring "123", Its corresponding decimal number is 123 .

If you want this positive integer to be as large as possible , Ask the maximum number of positive integers .

The function passes in a length of  n  String  s  And a positive integer  k , Please return to the answer .

Example 1

Input

"321",2

Output

32

explain

All lengths are  2  The substring of is ："32" and "21", obviously 32 It's the biggest .  

Example 2

Input

"1234",4

Output

1234

explain

All lengths are  4  The substring of has only itself , So the answer is  1234 .  

remarks :

1≤n≤105,1≤k≤min(n,8)

Ideas ：

• The interception length of sliding window is k The string of , And compare when intercepting String convert to int After the size of , Record return ;

Code ：

import java.util.*;

public class Solution {
	public int maxValue (String s, int k) {
		// write code here
		if(k==s.length())return string2int(s);
		int maxRes=0;
		for(int i=0;i<s.length()-k+1;i++){
			int a = string2int(s.substring(i,i+k));
			maxRes=Math.max(a,maxRes);
		}
		return maxRes;
	}
	public int string2int(String s){
		int index=0;
		int res =0;
		while(index<s.length()){
			res*=10;
			res+=(s.charAt(index)-'0');
			index++;
		}
		return res;
	}
}

【 Must be 】 Trim the leaves 【 Simple + Two fork tree pruning 】

subject ：

There is a tree with n A binary tree of nodes , Its root node is root. The pruning rules are as follows :

1. Trim the leaf nodes of the current binary tree , However, leaf nodes cannot be deleted directly

2. Only the parent nodes of leaf nodes can be trimmed , After trimming the parent node , Leaf nodes will also be deleted

3. If you want to leave as many nodes as possible , Trim off all leaf nodes . Please return to the pruned binary tree .

There is the following binary tree :

1 2 3 4 5

o    / \   o   o  / \  / \ o  o o   o

After pruning, only the root node will be left .

Example 1

Input

{1,1,1,1,1,1,1}

Output

{1}

explain

The leaf node is the lowest 4 individual 1 node , But you can't trim it directly , Only trim the middle 2 individual 1, After pruning , Only the root node

Example 2

Input

{1,#,1,#,1,#,1,#,1}

Output

{1,#,1,#,1}

explain

Degenerated into a chain , Delete the last two nodes .

remarks :

2≤n≤105, When deleting the root node, the return is null .

Ideas ：

• It is obviously a root left and right preorder traversal ;
• The topic requires that only parent nodes can be built , Therefore, it is necessary to ensure that the child nodes of the current node exist , And it can be deleted only when the two child nodes of the child node do not exist ;
  • Note: delete the parent node directly ！ Instead of disconnecting the parent node from the child node ！
• There are three cases of recursive functions ：
  • Recursive functions do not need to return values ;
    • Search the whole tree , But don't deal with recursive return values , Such as three simple traversal methods 、 Path summation problems ;
    • At this time, there is no need to assign values to child nodes , Just make recursive calls ;
    • dfs1(root.left,targetSum);
    • dfs1(root.right,targetSum);
  • If the recursive function has a return value , How to distinguish an edge to search , Or search the whole tree ？
    • This return value refers to the undertaking relationship inside and outside recursion , The outside needs to use the inside value , Of course, you have to assign values ！
    • Search for One side Writing ：
      • if ( Recursive function (root.left)) return ;
      • if ( Recursive function (root.right)) return ;
    • Search for The whole tree How to write it ：
      • left = Recursive function (root.left);
      • right = Recursive function (root.right);
      • left And right Logical processing of ;
    • When a recursive function has a return value ： If you want to search for an edge , When the return value of recursive function is not empty , Go back to , If you search the whole tree , Just use a variable left、right Catch the return value , This left、right There is also the need for logic processing in the post order , That is to say, the logic to deal with intermediate nodes in post order traversal （ It's also retrospective ）;
• The logic of deleting nodes in binary tree ：
  • When there is a return value , Find the node to delete , return null Just delete ;
  • If there is no return value , You need to manually disconnect root.left=null Connection with child nodes ;
• Mainly, some people may have XOR on the return value and whether to assign a value ;

Code ：

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
	public TreeNode pruneLeaves (TreeNode root) {
		if(root==null)return root;
		
		if(root.left!=null && root.left.left==null && root.left.right==null){
			return null;
		}
		if(root.right!=null && root.right.left==null && root.right.right==null){
			return null;
		}
		
		if(root.left!=null)root.left = pruneLeaves(root.left);
		if(root.right!=null)root.right = pruneLeaves(root.right);
		return root;
	}
}