Java实现LeetCode第199场周赛（题号5472，5473，5474，5462）

class Solution {
    //新建一个数组，直接按照下标把当前的字符放进去
    public String restoreString(String s, int[] indices) {
        char[] ss = s.toCharArray();
        char[] res =new char[s.length()];
        for(int i=0;i){
            res[indices[i]]=ss[i];
        }
        return new String(res);
    }
}

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

/**
 * 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 ){
            //这里left是左面，right的是要减去左面的的步数的所以范围要-i
            for(int j = 1; j ){
                //左右相乘就是方案数
                res += left[i] * right[j];
            }
        }
        //dis是第几个的位置，就是left，right上一位的
        //dis[2]二点的位置，要一点位置的左右两个
        //就是dis【i】就代表，距离为i的数量
        for(int i = 2; i ){
            dis[i] = left[i - 1] + right[i - 1];
        }
        return dis;
    }
    
}

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 = 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 = 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];
  }
}