A look will, a do on the waste 😔

Rearrange the strings

It gives you a string s and an array of integers of the same length as indices.

Rearrange the string s so that the ith character needs to be moved to the location indicated by the indices[I].

Returns the rearranged string.

The sample1: Enter: s ="codeleet", indices = [4.5.6.7.0.2.1.3] output:"leetcode"Explanation: As shown in the figure,"codeleet"After rearranging, it becomes"leetcode" 。
Copy the code

The sample2: Enter: s ="abc", indices = [0.1.2] output:"abc"Explanation: After the rearrangement, each character remains in its original position. The sample3: Enter: s ="aiohn", indices = [3.1.4.2.0] output:"nihao"The sample4: Enter: s ="aaiougrt", indices = [4.0.2.6.7.3.1.5] output:"arigatou"The sample5: Enter: s ="art", indices = [1.0.2] output:"rat"
 
Copy the code

Tip:

s.length == indices.length == n
1 <= n <= 100S contains only lowercase letters.0<= indices[I] < n Indices all values are unique (that is, indices is an integer0The n -1A group of permutations formed).Copy the code
class Solution {
    // Create a new array and put the current characters directly in the array
    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 newString(res); }}Copy the code

Light bulb Switch IV (analog traversal)

There are n light bulbs in the room, numbered from 0 to N-1, in a row from left to right. In the beginning, all the lights were off.

Please try to make the light bulb on/off state consistent with the state described by target, where target[I] is equal to 1 and the ith light bulb is on, equal to 0 means that the ith light bulb is off.

There is a switch that can be used to flip the state of the bulb. The flip operation is defined as follows:

Select any light bulb in the current configuration (subscript I). Flip each light bulb with subscripts from I to N-1. If the state of the light bulb is 0, it becomes 1, and if it is 1, it becomes 0.

Returns the minimum number of flips required to achieve the state described by target.

The sample1: Enter: target ="10111"Output:3Description: Initial configuration"00000"From the first.3One light bulb (submarked2) begins to flip"00000" -> "00111"From the first1One light bulb (submarked0) begins to flip"00111" -> "11000"From the first2One light bulb (submarked1) begins to flip"11000" -> "10111"At least you need to flip3Times to achieve the status example described by target2: Enter: target ="101"Output:3Explanation:"000" -> "111" -> "100" -> "101"Example.3: Enter: target ="00000"Output:0The sample4: Enter: target ="001011101"Output:5
 
Copy the code

Tip:

1 <= target.length <= 10^5
target[i] == '0'Or target = = [I]'1'
Copy the code
class Solution {
    / * according to start from the front to rear If the current position of the target for 1 look at the number of open to turn off the lights is even, if it is even, prove the current couldn't become 1, because the default value is 0, so to change once, on the other hand, the current position is 0, look at the open to turn off the lights if it is an odd number of times, then changing a * /
    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; }}returncount; }}Copy the code

Number of good leaf pairs (DFS search tree)

You are given the root node of the binary tree root and an integer distance.

If the shortest path length between two leaf nodes in a binary tree is less than or equal to distance, then they can form a good pair of leaf nodes.

Returns the number of pairs of good leaves in the tree.

Example 1:

Enter: root = [1.2.3.null.4], distance = 3Output:1Explanation: The leaves of a tree are3 和 4, the length of the shortest path between them is3. This is the only good leaf node pair.Copy the code

Example 2:

Enter: root = [1.2.3.4.5.6.7], distance = 3Output:2Explanation: A good leaf node pair is [4.5] and [6.7], the shortest path length is2. But leaf node pairs [4.6] does not meet the requirement because the shortest path length between them is4 。
Copy the code

Example 3:

Enter: root = [7.1.4.6.null.5.3.null.null.null.null.null.2], distance = 3Output:1Explanation: The only good leaf node pair is [2.5].Copy the code

Example 4:

Enter: root = [100], distance = 1Output:0
Copy the code

Example 5:

Enter: root = [1.1.1], distance = 2Output:1
Copy the code

Tip:

The number of nodes in a tree is [1.2^10]. The value of each node is in [1.100Between].1 <= distance <= 10
Copy the code
/** * 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;
        }
        // About the number of
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        for(int i = 1; i < distance; i++){
            // Where left is the left, right is the number of steps to subtract from the left, so the range is -i
            for(int j = 1; j <= distance - i; j++){
                // The number of schemes is multiplied by the left and rightres += left[i] * right[j]; }}//dis is the number of digits above left and right
        //dis[2] //dis[2
        // dis [I] represents the number of distance I
        for(int i = 2; i <= distance; i++){
            dis[i] = left[i - 1] + right[i - 1];
        }
        returndis; }}Copy the code

Compressed String II (DFS search)

Stroke length encoding is a common method of string compression that replaces consecutive identical characters (repeated two or more times) with characters and numbers representing the count of characters (stroke length). For example, use this method to compress the string “aabccc” by replacing “aa” with “a2” and “CCC” with ‘c3″. So the compressed string becomes “a2bc3”.

Note that in this case, the compression did not append the count ‘1’ to a single character.

I give you a string s and an integer k. You need to remove up to k characters from the string S to minimize the travel length encoding length of S.

Please return the minimum length of the S stroke length encoding after deleting a maximum of K characters.

Example 1:

Enter: s ="aaabcccd", k = 2Output:4Explanation: Without deleting anything, the compressed string is"a3bc3d", the length of6. The best solution is to delete'b' 和 'd'In this way, the compressed string is"a3c3", the length is4 。
Copy the code

Example 2:

Enter: s ="aabbaa", k = 2Output:2Explanation: If delete two'b'Character, then the compressed string is of length2 的 "a4" 。
Copy the code

Example 3:

Enter: s ="aaaaaaaaaaa", k = 0Output:3Explanation: since k is equal to0Cannot delete any characters. The compressed string is"a11", the length of3 。
 
Copy the code

Tip:

1 <= s.length <= 100
0<= k <= s. long th s Contains only lowercase lettersCopy the code
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);
  }
                                   // The current position of the title string. The character at the current position. How many identical remaining deletable characters before the current character
  private int dfs(Integer[][][][] dp, String s, int cur,    char c,        int num,                     int k){
    int n = s.length();
    if(cur >= n){
        // If the last digit is a one-digit letter or less than one digit, use this number. If there are multiple digits, two digits are greater than or equal to 10, and one digit is less than 10
      return num <= 1 ? num: 1 + (num >= 10 ? 2: 1);
    }
      // If the current bit is calculated, then it can be returned directly, pruning
    if(dp[cur][c - 'a'][num][k] ! =null) {return dp[cur][c - 'a'][num][k];
    }
      // If it is different from the previous digit
    if(s.charAt(cur) ! = c){// See how many of the previous numbers are the same, and then add the next convenience
      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 {
        // If so, continue to expand
      dp[cur][c - 'a'][num][k] = dfs(dp, s, cur + 1, c, num + 1, k);
    }
    if(k > 0) {// If you can, try cutting the current one
      dp[cur][c - 'a'][num][k] = Math.min(dp[cur][c - 'a'][num][k], dfs(dp, s, cur + 1, c, num, k - 1));
    }
      / / return
    return dp[cur][c - 'a'][num][k]; }}Copy the code