Java实现LeetCode第199场周赛(题号5472,5473,5474,5462)

aanndd 2020-07-26

一看就会,一做就废??

5472. 重新排列字符串

给你一个字符串 s 和一个 长度相同 的整数数组 indices 。

请你重新排列字符串 s ,其中第 i 个字符需要移动到 indices[i] 指示的位置。

返回重新排列后的字符串。

示例 1:

 
输入:s = "codeleet", indices = [4,5,6,7,0,2,1,3]
输出:"leetcode"
解释:如图所示,"codeleet" 重新排列后变为 "leetcode" 。

Java实现LeetCode第199场周赛(题号5472,5473,5474,5462)

示例 2:

输入:s = "abc", indices = [0,1,2]
输出:"abc"
解释:重新排列后,每个字符都还留在原来的位置上。
示例 3:

输入:s = "aiohn", indices = [3,1,4,2,0]
输出:"nihao"
示例 4:

输入:s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
输出:"arigatou"
示例 5:

输入:s = "art", indices = [1,0,2]
输出:"rat"

提示:

s.length == indices.length == n
1 <= n <= 100
s 仅包含小写英文字母。
0 <= indices[i] < n
indices 的所有的值都是唯一的(也就是说,indices 是整数 0 到 n - 1 形成的一组排列)。
class Solution {
    //新建一个数组,直接按照下标把当前的字符放进去
    public String restoreString(String s, int[] indices) {
        char[] ss = s.toCharArray();
        char[] res =new char[s.length()];
        for(int i=0;i<s.length();i++){
            res[indices[i]]=ss[i];
        }
        return new String(res);
    }
}

5473. 灯泡开关 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‘
class Solution {
    /*
        按照从前向后开始模拟
        如果当前位置的目标为1看一下是不是开关灯的次数是不是偶数,如果是偶数,证明当前不能变成1,因为默认值都是0,所以要在改变一次
        相反,当前位置为0,看一下开关灯次数如果是奇数,那么就要在改变一次
    
    */
    public int minFlips(String target) {
        char[] num = target.toCharArray();
        int count = 0;
        for (char c : num){
            if(c==‘0‘ && count%2==1){
                ++count;
            } else if(c==‘1‘&& count%2==0){
                ++count;
            }
        }
        return count;
    }
}

5474. 好叶子节点对的数量 (DFS搜索树)

给你二叉树的根节点 root 和一个整数 distance 。

如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ,那它们就可以构成一组 好叶子节点对 。

返回树中 好叶子节点对的数量 。

示例 1:
Java实现LeetCode第199场周赛(题号5472,5473,5474,5462)

输入:root = [1,2,3,null,4], distance = 3
输出:1
解释:树的叶节点是 3 和 4 ,它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。

示例 2:

Java实现LeetCode第199场周赛(题号5472,5473,5474,5462)

输入: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

示例 5:

输入:root = [1,1,1], distance = 2
输出:1

提示:

tree 的节点数在 [1, 2^10] 范围内。
每个节点的值都在 [1, 100] 之间。
1 <= distance <= 10
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  private int distance = 0;
    
    private int res = 0;
        
    public int countPairs(TreeNode root, int distance) {
        this.distance = distance;
        dfs(root);
        return res;
    }
    
    private int[] dfs(TreeNode node){
        if(node == null){
            return new int[distance + 1];
        }
        int[] dis = new int[distance + 1];
        if(node.left == null && node.right == null){
            dis[1] = 1;
            return dis;
        }
        //左右的数量
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        for(int i = 1; i < distance; i++){
            //这里left是左面,right的是要减去左面的的步数的所以范围要-i
            for(int j = 1; j <= distance - i; j++){
                //左右相乘就是方案数
                res += left[i] * right[j];
            }
        }
        //dis是第几个的位置,就是left,right上一位的
        //dis[2]二点的位置,要一点位置的左右两个
        //就是dis【i】就代表,距离为i的数量
        for(int i = 2; i <= distance; i++){
            dis[i] = left[i - 1] + right[i - 1];
        }
        return dis;
    }
    
}

5462. 压缩字符串 II (DFS搜索)

行程长度编码 是一种常用的字符串压缩方法,它将连续的相同字符(重复 2 次或更多次)替换为字符和表示字符计数的数字(行程长度)。例如,用此方法压缩字符串 “aabccc” ,将 “aa” 替换为 “a2” ,“ccc” 替换为` “c3” 。因此压缩后的字符串变为 “a2bc3” 。

注意,本问题中,压缩时没有在单个字符后附加计数 ‘1’ 。

给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符,以使 s 的行程长度编码长度最小。

请你返回删除最多 k 个字符后,s 行程长度编码的最小长度 。

示例 1:

输入:s = "aaabcccd", k = 2
输出:4
解释:在不删除任何内容的情况下,压缩后的字符串是 "a3bc3d" ,长度为 6 。最优的方案是删除 ‘b‘ 和 ‘d‘,这样一来,压缩后的字符串为 "a3c3" ,长度是 4 。

示例 2:

输入:s = "aabbaa", k = 2
输出:2
解释:如果删去两个 ‘b‘ 字符,那么压缩后的字符串是长度为 2 的 "a4" 。

示例 3:

输入:s = "aaaaaaaaaaa", k = 0
输出:3
解释:由于 k 等于 0 ,不能删去任何字符。压缩后的字符串是 "a11" ,长度为 3 。

提示:

1 <= s.length <= 100
0 <= k <= s.length
s 仅包含小写英文字母
class Solution {
     public int getLengthOfOptimalCompression(String s, int k) {
    int n = s.length();
    Integer[][][][] dp = new Integer[n + 1][26][n + 1][k + 1];
    return dfs(dp, s, 0, s.charAt(0), 0, k);
  }
                                   //题目字符串  当前位置    当前位置的字符  当前字符前面有多少相同的      剩余可删除的字符 
  private int dfs(Integer[][][][] dp, String s, int cur,    char c,        int num,                     int k){
    int n = s.length();
    if(cur >= n){
        //最后一位如果是一位的字母或者小于1位,就用这个数,如果是多个数字,大于等于10就是两位,小于10就是一位
      return num <= 1 ? num: 1 + (num >= 10 ? 2: 1);
    }
      //如果当前这一位计算过,那么就可以直接返回了,剪枝
    if(dp[cur][c - ‘a‘][num][k] != null){
      return dp[cur][c - ‘a‘][num][k];
    }
      //如果和上一位不一样
    if(s.charAt(cur) != c){
        //看看前面的那个数字有多少相同的,然后加上后面便利的
      dp[cur][c - ‘a‘][num][k] = (num <= 1 ? num: 1 + (num >= 10 ? 2: 1)) + dfs(dp, s, cur + 1, s.charAt(cur), 1, k);
    } else {
        //如果相等,继续往后面扩展
      dp[cur][c - ‘a‘][num][k] = dfs(dp, s, cur + 1, c, num + 1, k);
    }
    if(k > 0){
        //如果还能减的话,就尝试一下吧当前的这个剪掉
      dp[cur][c - ‘a‘][num][k] = Math.min(dp[cur][c - ‘a‘][num][k], dfs(dp, s, cur + 1, c, num, k - 1));
    }
      //返回
    return dp[cur][c - ‘a‘][num][k];
  }
}

相关推荐