填充数组

目录

填充数组【较难+DP】

题目：

思路：

代码：

最大值【虽写出，但不灵活】

题目：

思路：

代码：

【必会】修剪叶子【简单+二叉树剪枝】

题目：

思路：

代码：

---

填充数组【较难+DP】

题目：

牛妹给了牛牛一个长度为 n 的下标从0开始的正整型数组 a ，粗心的牛牛不小心把其中的一些数字删除了。

假如ai​被删除了，则ai​=0。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得：

a0​≤a1​≤...≤an−1​ 且对于所有的0≤i≤n−1满足1≤ai​≤k 。

函数传入一个下标从0开始的数组 a 和一个正整数 k ，请返回合法的填充方案数对 10^9+7取模的值,保证不存在方案数为0的数据。

示例1

输入

[0,4,5],6

输出

4

说明

所有的合法填充方案是：[1,4,5],[2,4,5],[3,4,5],[4,4,5]，共4种。  

示例2

输入

[1,0,0],3

输出

6

说明

所有的合法填充方案是：[1,1,1],[1,1,2],[1,2,2],[1,2,3],[1,3,3],[1,1,3]共6种  

示例3

输入

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

输出

746845806

备注:

1≤n,k≤1000

数组a满足0≤ai​≤k

思路：

• 对于输入数组中的每一段 0 都可以抽象为一个子问题：
  • 填充 i 个数，取值范围有 j 个数，求填充方案数
• 最终问题的答案就是每一段 0 的方案数相乘再取模。
• 设 dp[i][j] 为填充 i 个数、取值范围有 j 个数的填充方案数：
  • 填充 0 个数的方案数为 0，dp[0][j] = 0
  • 取值范围为 0 的方案数也为 0，dp[i][0] = 0
  • 填充 1 个数的方案数等于取值范围的个数，dp[1][j] = j
  • 填充 i 个数可以转化为填充 i-1 个数，对于最后一个数有 j 种填充方案，选择不同的数会影响剩余 i-1 个数的取值范围，即 dp[i][j]=∑k=1jdp[i−1][k]dp[i][j] ，也就是 dp[i] 为 dp[i-1] 的前缀和，可以简化为 dp[i][j]=dp[i][j−1]+dp[i−1][j]；
• 自我分析：这个是牛客的高赞回答，当时找了半天规律并没有找出来，结果是DP，还是不灵活啊我；
• 参考：填充数组__牛客网

代码：

import java.util.*;
 
// 牛客高赞题解，动态规划
public class Solution {
	int MOD=1000000007;
	long[][] dp=new long[1005][1005];//dp[i][j]表示填充i个数，取值个数是j的方案数
	public int FillArray(int[] a, int k) {
		long res=1;
		int n=a.length;
		//初始化
		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;//状态转移方程
			}
		}
		 
		int i=0;
		while(i//计算每一段的方案数，累乘
			while(i0){
				i++;
			}
			if(i==n) break;
			int l=i;//左区间
			int x=i>0?a[i-1]:1;
			while(i0){
				i++;
			}
			int r=i;//右区间
			int y=i
			res=(res*dp[r-l][y-x+1])%MOD;//累乘
		}
		return (int)res;
	}
}

最大值【虽写出，但不灵活】

题目：

有一个只由字符'1'到'9'组成的长度为 n 的字符串 s ，现在可以截取其中一段长度为 k 的子串并且将该子串当作十进制的正整数，如对于子串"123"，其对应的十进制数字就是123 。

如果想让这个正整数尽可能的大的话，问该正整数最大能是多少。

函数传入一个长度为 n 的字符串 s 和一个正整数 k ，请你返回答案。

示例1

输入

"321",2

输出

32

说明

所有长度为 2 的子串为："32"和"21"，显然32是最大的。  

示例2

输入

"1234",4

输出

1234

说明

所有长度为 4 的子串只有它自己本身，因此答案为 1234 。  

备注:

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

思路：

• 滑动窗口截取长度为k的子串，并在截取的时候比较String转换成int之后的大小，记录返回；

代码：

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;i1;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
			res*=10;
			res+=(s.charAt(index)-'0');
			index++;
		}
		return res;
	}
}

【必会】修剪叶子【简单+二叉树剪枝】

题目：

有一棵有n个节点的二叉树，其根节点为root。修剪规则如下:

1.修剪掉当前二叉树的叶子节点，但是不能直接删除叶子节点

2.只能修剪叶子节点的父节点，修剪了父节点之后，叶子节点也会对应删掉

3.如果想在留下尽可能多的节点前提下，修剪掉所有的叶子节点。请你返回修剪后的二叉树。

有如下二叉树:

修剪过后仅会留下根节点。

示例1

输入

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

输出

{1}

说明

叶子节点为最下面的4个1节点，但是不能直接修剪，只能修剪中间的2个1，修剪掉之后，只有根节点了

示例2

输入

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

输出

{1,#,1,#,1}

说明

退化为一条链了，将最后两个节点删除。

备注:

2≤n≤105，删除根节点时返回为空。

思路：

• 显然是根左右前序遍历；
• 题目要求只能修建父节点，所以需要保证当前节点的子节点存在时，且子节点的两个子节点不存在的时候才能进行删除；
  • 注意是直接删除父节点！而不是断开父节点与子节点之间的联系！
• 递归函数有三种情况：
  • 递归函数不需要返回值；
    • 搜索整棵树，但是不用处理递归返回值，如三种单纯的遍历方式、路径总和类题目；
    • 这时不用赋值给子节点，只是进行递归调用即可；
    • dfs1(root.left,targetSum);
    • dfs1(root.right,targetSum);
  • 如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？
    • 这个有返回值指的是递归内外的承接关系，外面需要用到里面的值，当然必须得赋值了！
    • 搜索一条边的写法：
      • if (递归函数(root.left)) return ;
      • if (递归函数(root.right)) return ;
    • 搜索整个树写法：
      • left = 递归函数(root.left);
      • right = 递归函数(root.right);
      • left与right的逻辑处理;
    • 在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）；
• 二叉树删除节点的逻辑：
  • 有返回值的情况，找到要删除的节点，返回null就是删除了；
  • 如果没有返回值，则需要手动断开root.left=null与子节点的联系；
• 主要是有的人会对返回值和是否赋值可能存在异或；

代码：

/*
 * 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;
	}
}