LeetCode 68. 文本左右对齐 / 1894. 找到需要补充粉笔的学生编号 / 600. 不含连续1的非负整数（数位dp，好好学）

68. 文本左右对齐

2021.9.9 每日一题

题目描述

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。

示例:

输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
["This    is    an","example  of text","justification.  "
]

示例 2:

输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
["What   must   be","acknowledgment  ","shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",因为最后一行应为左对齐，而不是左右两端对齐。       第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:
words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
["Science  is  what we","understand      well","enough to explain to","a  computer.  Art is","everything  else  we","do                  "
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/text-justification
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

硬生生模拟的，100%
看了一下题解，计算空格的思路是一样的

class Solution {public List<String> fullJustify(String[] words, int maxWidth) {//思路应该就是模拟int l = words.length;List<String> res = new ArrayList<>();int idx = 0;while(idx < l){int len = 0;    //长度，包括一个空格int curr = idx; //本次到达的下标while(curr < l){String s = words[curr];len += s.length() + 1;if(len - 1 > maxWidth){break;}curr++;}//走到这，说明能放idx 到 curr - 1 的字符串if(curr != l){int num = curr - idx;//System.out.println(num);//计算长度，剩下的就是要空格补充的len -= (words[curr].length() + 1 + 1);//System.out.println(len);int black = maxWidth - len;int per = 0;int count = 0;if(num != 1){per = black / (num - 1);    //每个空里要插入多少个空格count = black % (num - 1);  //左边比右边多，所以剩下的空格插到左边}StringBuffer sb = new StringBuffer();if(num == 1){sb.append(words[idx]);for(int i = 0; i < black; i++){sb.append(" ");}                    }else{for(int i = idx; i < curr; i++){sb.append(words[i]);if(i != curr - 1){sb.append(" ");for(int j = 1; j <= per; j++){sb.append(" ");}if(count-- > 0)sb.append(" ");}}}res.add(sb.toString());//如果是最后一行}else{int num = curr - idx;StringBuffer sb = new StringBuffer();for(int i = idx; i < curr; i++){sb.append(words[i]);if(i != curr - 1)sb.append(" ");}while(sb.length() < maxWidth){sb.append(" ");}res.add(sb.toString());}idx = curr;            }return res;}
}

1894. 找到需要补充粉笔的学生编号

2021.9.10 每日一题

题目描述

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充 粉笔。

请你返回需要 补充 粉笔的学生 编号 。

示例 1：

输入：chalk = [5,1,5], k = 22
输出：0
解释：学生消耗粉笔情况如下：

• 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
• 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
• 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
• 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
• 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
• 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
  编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。

示例 2：

输入：chalk = [3,4,1,2], k = 25
输出：1
解释：学生消耗粉笔情况如下：

• 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。
• 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。
• 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。
• 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。
• 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。
• 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。
• 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。
• 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。
• 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。
  编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。

提示：
chalk.length == n
1 <= n <= 10^5
1 <= chalk[i] <= 10^5
1 <= k <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

注意sum会超过int范围

class Solution {public int chalkReplacer(int[] chalk, int k) {int l = chalk.length;long sum = 0;for(int i = 0; i < l; i++){sum += chalk[i];}long t = (long)k;t = t % sum;int idx = 0;while(t >= 0){t -= chalk[idx++];}return idx - 1;}
}

或者看这里，直接k %= total 这样写的话，就可以不需要类型转换

class Solution {public int chalkReplacer(int[] chalk, int k) {int n = chalk.length;long total = 0;for (int num : chalk) {total += num;}k %= total;int res = -1;for (int i = 0; i < n; ++i) {if (chalk[i] > k) {res = i;break;}k -= chalk[i];}return res;}
}

600. 不含连续1的非负整数

2021.9.11 每日一题

题目描述

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例 1:

输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: 1 <= n <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个有点难了…
第一时间想到的是打家劫舍的动规，但是如何确定是小于等于n呢

整理一下官解的思路：
首先把小于等于n的非负整数的二进制形式想像成一个字典树，例如官解给的这个图

然后可以发现，这颗树是由满二叉树和完全二叉树组成的；如果一个节点有两个子节点，那么左以左子结点为根的树是满二叉树，右子节点为根的树是完全二叉树；如果只有一个子节点，那么就是左子结点，是一个完全二叉树
那么如何计算一个完全二叉树中，不包含连续1的从根到叶子节点的路径数量
可以发现，完全二叉树的左子结点是高度减1的完全二叉树，而右子节点是1，所以只有右子节点的左子结点可以满足要求，也就是高度减2的完全二叉树，而右边的子树因为肯定包含两个连续的1所以不成立
所以可以看到这是一个动态规划：
定义dp[n]为高度为n，根节点为0的满二叉树中满足条件的路径数量
所以dp[n] = dp[n - 1] + dp[n - 2]

那么如何拆分成满二叉树和完全二叉树呢，从根节点出发，如果有两个子节点，那么左边是满二叉树，右边是完全二叉树，如果只有一个节点，那么继续对这个节点处理

说实话，明白了这个思路，也不知道怎么写代码，想想

首先，根节点为0的时候，定义dp[0] = 1（方便计算）；高度为1的时候，根节点是0，所以dp[1] = 1;
在静态代码块中，预先处理dp的值

然后从高到低判断每一位，如果当前位是1，那么就可以分为左右子树，左边是根节点为0的满二叉树，右边是根节点为1的完全二叉树；如果当前位是0，那么就跳过，继续往下拆分；

另外，还有一个比较关键的地方就是：如果有连续两个1，就不用继续处理了，这句话应该怎么理解呢？
例如求14，就是1110，那么第一次肯定是1000，也就是 i 等于3的时候，这时，处理了高度为4的，根节点为0的树；而接下来，是100，也就是 i 等于2的时候，这时，处理高度为3的，根节点为0的树；
此时，想像那颗二叉树，从根部分成左右两个子树，左边部分已经被处理了；右边部分又被分成两个部分left，right，而left也被处理了，那么只剩下right部分，而right部分前提是前面两位都是1，这肯定是不满足要求的，所以就停止了

最后，如果能走到底，例如101，会计算dp[3] + dp[1]，但是会漏掉一种情况，101，就是整棵树最右边的一条路径，所以需要另外加上
官解中说的是“叶结点没有子结点，需要作为特殊情况单独处理”，不太能理解

class Solution {//高度为n的，以0为根节点的满二叉树中符合条件的路径的数量static int[] dp = new int[31];static{dp[0] = 1;dp[1] = 1;for(int i = 2; i < 31; i++){dp[i] = dp[i - 1] + dp[i - 2];}        }public int findIntegers(int n) {//我第一时间想到的也是打家劫舍，就相当于相邻位置不能偷呗//但是怎么保证是小于等于n的呢int pre = 0;int res = 0;for(int i = 29; i >= 0; i--){int val = 1 << i;//如果当前位是1，比如6if((n & val) != 0){//减去当前值，减去4n -= val;//加上根节点为0的满二叉树的值，例如4的高度就是3res += dp[i + 1];//如果之前一位是1，那么结束if(pre == 1)break;pre = 1;}else{pre = 0;}if(i == 0)res++;}return res;}
}

三叶姐的方法说实话看不太懂，看到一个很巧妙的方法，就是不断在一个数后面补0或者1

class Solution {int res;int n;public int findIntegers(int n) {this.n = n;res = 1;    //为0的情况dfs(1);return res;}public void dfs(int cur){//如果当前值大于n，那么结束if(cur > n)return;res++;//如果当前值末尾是1，那么后面只能补0if((cur & 1) == 1){dfs(cur << 1);//如果末尾是0，那么后面1和0都可以}else{dfs(cur << 1);dfs((cur << 1) + 1);}}
}

数位dp的一个模板解法，我觉得讲的挺不错的，最起码让我明白了数位dp的一般思路：
https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/solution/shu-wei-dpmo-ban-ji-jie-fa-by-initness-let3/

首先，明确数位dp是按每一位进行计算的，
看这个题解中所给的这个图，将每一位可以分为最大值，也就是当前能取到的值，例如第一位是5；和比5小的值0-4；而以0-4开头的所有情况，都可以取到
后面每一位都是这样

所以需要预处理，也就是当前位为某个数时，所有能够满足条件的情况，方便后面的计算

先计算小于当前位最大值的情况；对于等于当前位置最大值的情况，需要继续向后计算，如图中就是0-4直接取预处理中的值，而5的情况，因为和后面的数字有关，所以继续向后处理

class Solution {//定义dp为长度为n的二进制数字，最高位为j的情况下，满足条件的数的个数static int[][] dp = new int[32][2];static{dp[1][0] = 1;   //长度为1，且最高位为0，只有0dp[1][1] = 1;   //长度为1，最高位为1，只有1for(int i = 2; i < 32; i++){//最高位为0，可以由0和1转移而来dp[i][0] = dp[i - 1][0] + dp[i - 1][1];//最高位为1，低一位只能取0，来确保没有连续的一dp[i][1] = dp[i - 1][0];}}public int findIntegers(int n) {//数位dp，根据理解来写一下//将n转换为二进制的形式List<Integer> list = new ArrayList<>();while(n > 0){list.add(n & 1);n >>= 1;}int res = 0;int pre = 0;//然后从最高位开始dpfor(int i = list.size() - 1; i >= 0; i--){//当前位int temp = list.get(i);//遍历当前位能选的值（除了最高位），这里就是是否可以选0//对于最高位为当前值temp的情况，继续向下处理for(int j = 0; j < temp; j++){//在当前位枚举到自己本身的值之前，它所包含的合法数字数量就对应了之前预处理出的dp值//这里就是：如果可以选0，那么长度为i + 1的最高位为0的所有情况都可以选res += dp[i + 1][j];}//如果已经有连续两个位置是1了，那么后面所有情况都不满足条件了，所以跳出if(temp == 1 && pre == 1)break;pre = temp;//如果已经遍历到最低一位的本身的值，需要加上这个合法数字，对应的是图中右下方的方案if(i == 0)res++;}return res;}}