Day 39

969 pancake sorting

Give you an integer array arr, please use pancake flip to sort the array.

The execution process of a pancake flip is as follows:

• Select an integer k, 1 < = k < = arr.length

• Inverse rotor array arr[0...k-1] (subscript starts from 0)

For example, arr = [3,2,1,4], select k = 3 to flip the pancake once, reverse the rotor array [3,2,1], and get arr = [**1**,**2**,**3**,4].

Return the k-value sequence corresponding to the pancake flipping operation that can make arr orderly in the form of array. Any valid answer that sorts the array and flips the array within 10 * arr.length will be judged to be correct.

method

According to the definition of pancake sorting, we can consider arranging each number from small to large according to the following rules:

• Find the subscript k of the ith number from the original array, and then we flip the whole array by K
• After the above operation, we flip the i-th number to the head of the array, and then flip the cnt according to the number of elements that have been arranged. In this way, we put the above elements in the position

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < arr.length; ++i) {
            int index = findIndex(arr, i + 1);
            flip(arr ,index);
            res.add(index + 1);
            if (check(arr)) return res;
            flip(arr, index - i);
            res.add(index - i + 1);
            if (check(arr)) return res;
            flip(arr, index);
            res.add(index + 1);
            if (check(arr)) return res;
        }
        return res;
    }

    public boolean check(int[] arr) {
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] != i + 1) return false;
        }
        return true;
    }

    public int findIndex(int[] arr, int target) {
        for (int i = 0; i < arr.length; ++i) if (arr[i] == target) return i;
        return 0;
    }

    public void flip(int[] arr, int index){
        int s = 0, e = index;
        int temp = 0;
        while (s < e){
            temp = arr[s];
            arr[s] = arr[e];
            arr[e] = temp;
            s++;
            e--;
        }
    }
}

1104 binary tree routing

In an infinite binary tree, each node has two child nodes, and the nodes in the tree are marked in zigzag line by line.

As shown in the figure below, mark the odd rows (i.e. the first row, the third row, the fifth row...) in the order from left to right;

In even rows (i.e., the second row, the fourth row, the sixth row...), they are marked from right to left.

Give you the label label of a node in the tree. Please return the path from the root node to the label node. The path is composed of the label of the passing node.

method

For a given label, we consider what its parent element is.

Since the binary tree is arranged in a zigzag shape, we can first consider that if the elements are arranged from right to right, it is easy to know that the parent element of label is label / 2 (integer division here). Due to the addition of the rule of zigzag arrangement, the value of its parent element should be the value corresponding to the reciprocal position of the values arranged in the original order in the position of the corresponding layer. For example, the elements of the third layer are 4,5,6,7. Let label=15. If the binary tree is not arranged in a zigzag shape, its parent element is 7 and its position in the third layer is the last element, so its actual position should be the first element of the layer. That is, the last element corresponds to the first element, and the first element corresponds to the last element.

According to the above conclusion, we can easily know that the parent element of label is: cnt + cnt - 1 - (label / 2 - cnt)

Label / 2 represents the position of the original parent element, label / 2 - cnt represents the first element of the parent layer, cnt - 1 - (label / 2 - cnt) represents the penultimate element of its corresponding parent layer, and cnt + cnt - 1 - (label / 2 - cnt) represents its actual value.

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        int cnt = 0;
        int temp = label;
        int[] powTwo = new int[32];
        int base = 1;
        for (int i = 1; i < 25; ++i){
            powTwo[i] = base;
            base *= 2;
        }
        while (temp > 0) {
            cnt++;
            temp >>= 1;
        }

        List<Integer> res = new ArrayList<>();
        while (cnt > 0){
            res.add(label);
            label =powTwo[cnt - 1] + powTwo[cnt - 1] - 1 - (label / 2 - powTwo[cnt - 1]);
            cnt--;
        }
        Collections.reverse(res);
        return res;
    }
}

717 1-bit and 2-bit characters

There are two special characters:

• The first character can be represented by one bit 0

• The second character can be represented by two bits (10 or 11)

Give you a binary array bits ending with 0. If the last character must be a one bit character, return true.

method

We decode the input string from beginning to end. If we encounter the second type of characters, let the flag be false, otherwise it is true. Since the flag records the type of characters decoded last time, we only need to return the flag.

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        boolean flag = false;
        int index = 0;
        while (index < bits.length){
            if (bits[index] == 0) flag = true;
            else {
                index++;
                flag = false;
            }
            index++;
        }
        return flag;
    }
}

838 push domino

Arrange n dominoes in a row and erect each dominoes vertically. At the beginning, push some dominoes to the left or right at the same time.

Every second, the dominoes that fall to the left push the adjacent dominoes to the left. Similarly, a domino upside down to the right will push the adjacent domino standing on its right.

If there are dominoes falling down on both sides of a vertically erected dominoes, the dominoes will remain unchanged due to the balance of forces.

As far as this is concerned, we will think that a falling domino will not exert additional force on other falling or fallen dominoes.

Give you a string dominoes to represent the initial state of this row of dominoes, where:

• dominoes[i] = 'L', indicating that the i-th domino is pushed to the left,

• dominoes[i] = 'R', indicating that the i-th domino is pushed to the right,

• dominoes[i] = '.'， Indicates that the i-th domino was not promoted.

Returns a string representing the final state.

method

We use breadth first search to deal with this problem. First, we write down the positions of all L and R and put them into the queue. Because when there is an odd number of motionless dominoes between R and L, the middle one has to remain motionless. Therefore, at the same time, we need to count the distance between this r character and the next L character when encountering r character, If the distance is odd, we will mark the state of the middle element so that it will not be wrongly marked as L or R in the process of breadth first search.

class Solution {
    public String pushDominoes(String dominoes) {
        StringBuilder res = new StringBuilder();
        Queue<Integer> queue = new LinkedList<>();
        int[] status = new int[dominoes.length()];
        for (int i = 0; i < dominoes.length(); ++i){
            if (dominoes.charAt(i) == 'R') {
                queue.add(i + 1);//Due to the existence of subscript 0, we offset the position by a position symbol, which represents the direction. The right is positive and the left is negative
                status[i] = 1;
                int index = i + 1;
                while (index < dominoes.length()) {
                    if (dominoes.charAt(index) == 'L') {//Record the special position marked as 3
                        if ((index - i) % 2 == 0) status[(index + i) >> 1] = 3;
                        break;
                    }
                    if (dominoes.charAt(index) == 'R') break;
                    index++;
                }
            }
            else if (dominoes.charAt(i) == 'L') {
                queue.add(-i - 1);
                status[i] = -1;
            }
        }
        while (!queue.isEmpty()) {
            int dir = queue.peek() > 0 ? 1 : -1;
            int index = Math.abs(queue.poll()) - 1;
            if (index + dir >= 0 && index + dir < dominoes.length()) {
                if (status[index + dir] == 0) {
                    status[index + dir] = dir;
                    queue.add(dir * (index + dir + 1));
                }
            }
        }
        for (int i : status) {
            if (i == 1) res.append('R');
            else if (i == -1) res.append('L');
            else res.append('.');
        }
        return res.toString();
    }
}