leetcode199场周赛
leetcode199场周赛
这几天一直在忙面试的事，一直拖到现在才写…
先上成绩吧
这周时阿里云赞助的，前300名给内推，这可能是我里阿里最近的一次了吧，福报是享受不到了..
T1：重新排列字符串
给你一个字符串 s 和一个 长度相同 的整数数组 indices 。
请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。
返回重新排列后的字符串。
示例 1：
输入：s = "codeleet", indices = [4,5,6,7,0,2,1,3]
输出："leetcode"
解释：如图所示，"codeleet" 重新排列后变为 "leetcode" 。
示例 2：
输入：s = "abc", indices = [0,1,2]
输出："abc"
解释：重新排列后，每个字符都还留在原来的位置上。
示例 3：
输入：s = "aiohn", indices = [3,1,4,2,0]
输出："nihao"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shuffle-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。很简单，新开辟一个数组直接按规则一位一位复制过去即可。
class Solution {
public String restoreString(String s, int[] indices) {
char[] arr = s.toCharArray();
for(int i = 0; i < indices.length; i++){
arr[indices[i]] = s.charAt(i);
}
return String.valueOf(arr);
}
}T2:灯泡开关 IV
房间中有 n 个灯泡，编号从 0 到 n-1 ，自左向右排成一行。最开始的时候，所有的灯泡都是 关 着的。
请你设法使得灯泡的开关状态和 target 描述的状态一致，其中 target[i] 等于 1 第 i 个灯泡是开着的，等于 0 意味着第 i 个灯是关着的。
有一个开关可以用于翻转灯泡的状态，翻转操作定义如下：
- 选择当前配置下的任意一个灯泡（下标为
i） - 翻转下标从
i到n-1的每个灯泡
翻转时，如果灯泡的状态为 0 就变为 1，为 1 就变为 0 。
返回达成 target 描述的状态所需的 最少 翻转次数。
示例 1：
输入：target = "10111"
输出：3
解释：初始配置 "00000".
从第 3 个灯泡（下标为 2）开始翻转 "00000" -> "00111"
从第 1 个灯泡（下标为 0）开始翻转 "00111" -> "11000"
从第 2 个灯泡（下标为 1）开始翻转 "11000" -> "10111"
至少需要翻转 3 次才能达成 target 描述的状态
示例 2：
输入：target = "101"
输出：3
解释："000" -> "111" -> "100" -> "101".
示例 3：
输入：target = "00000"
输出：0
示例 4：
输入：target = "001011101"
输出：5
提示：
1 <= target.length <= 10^5
target[i] == '0' 或者 target[i] == '1'解决方案
有题意知每次操作是将当前位置到其结尾位置依次反转，将全0串变为目标串的一种很容易想到的思路是从最左端开始遍历，依次将所有的位都置相同。由于每次都要将当前位置到最后的所有元素都逆制，因此时间复杂度为O（N^2），而N的数据范围为1e5，明显是来卡N^2来的。
我们发现只有变化的只有两个状态，因此不需要每次都反转其之后的所有元素，只需要使用一个反转标志，若该标志位true，则之后的元素结果与真实值相反，为false则相同，遍历过程中每次只需控制该标志位即可，因此可将时间复杂度降为O（N）。
代码如下：
class Solution {
public int minFlips(String target) {
boolean reverseFlag = false;// 该值为反转标志位
int ans = 0;
for(int i = 0; i < target.length(); i++){
if(!reverseFlag){
if(target.charAt(i) == '1'){
reverseFlag = true;
ans++;
}
}else{
if(target.charAt(i) == '0'){
reverseFlag = false;
ans++;
}
}
}
return ans;
}
}T3:好叶子节点对的数量
给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
示例 1：
输入：root = [1,2,3,null,4], distance = 3
输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。
示例 2：
输入：root = [1,2,3,4,5,6,7], distance = 3
输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。
示例 3：
输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
输出：1
解释：唯一的好叶子节点对是 [2,5] 。
示例 4：
输入：root = [100], distance = 1
输出：0
提示：
tree 的节点数在 [1, 2^10] 范围内。
每个节点的值都在 [1, 100] 之间。
1 <= distance <= 10解决方案
很明显这是一道二叉树的数据搜集题目。
对于给定结点cur，数据为cur下面的叶子结点到cur的距离。当其获得左右孩子收集的信息分别记做leftInfo，rightInfo，这两个list中的距离一一见面，统计出小于等于给定长度的数目，最后将leftInfo和rightInfo中长度加1并合并返回给其的上一层。
代码如下：
class Solution {
int ans = 0;
public int countPairs(TreeNode root, int distance) {
ans = 0;
process(root, distance);
return ans;
}
public List<Integer> process(TreeNode root, int distance){
if(root.left == null && root.right == null){ // 叶子结点
List<Integer> temp = new ArrayList<>();
temp.add(1);
return temp;
}
if(root.left == null || root.right == null){ // 某个子树为null
TreeNode next = null;
if(root.left == null){
next = root.right;
}else{
next = root.left;
}
List<Integer> info = process(next, distance);
for(int i = 0; i < info.size(); i++){
int cur = info.get(i);
info.set(i, cur + 1);
}
return info;
}
List<Integer> leftInfo = process(root.left, distance);
List<Integer> rightInfo = process(root.right, distance);
for(int num1 : leftInfo){
for(int num2 : rightInfo){
if(num1 + num2 <= distance){
ans++;
}
}
}
List<Integer> info = new ArrayList<>();
for(int num : leftInfo){
info.add(num + 1);
}
for(int num : rightInfo){
info.add(num + 1);
}
return info;
}
}为啥没T4呢？问就是不会
腾讯云开发者
