lcp351

美丽下标对的数目

class Solution {
    public int countBeautifulPairs(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; ++i)
            for (int j = i + 1; j < nums.length; ++j)
                if (check(i, j, nums))
                    ++res;
        return res;
    }

    private boolean check(int i, int j, int[] nums) {
        int num1 = nums[i], num2 = nums[j];
        char ch1 = String.valueOf(num1).charAt(0);
        String str = String.valueOf(num2);
        char ch2 = str.charAt(str.length() - 1);
        int l = Integer.parseInt(String.valueOf(ch1)), r = Integer.parseInt(String.valueOf(ch2));
        int small = l < r ? l : r;
        int great = l > r ? l : r;
        if (small == 1)
            return true;
        for (int k = 2; k <= small; ++k) {
            if (small % k == 0 && great % k == 0)
                return false;
        }
        return true;
    }
}

得到整数零需要执行的最少操作数

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        /**
         * 1. 从小到大枚举答案
         * 2. 假设操作次数为 k
         * 则问题变为：x = num1 - k * num2 能不能是k个2^i之和
         * 能的话就立即返回结果
         * 3. 如果x.bitCount <= k，那么一定可以是k个2^i之和
         * 对于循环退出条件，那么如果num2 < 0, 那么当 x < k，再增大k只会让x越来越小，此时肯定要结束循环
         * 若num2 < 0，因为num2只能是-1 -2 -3...这样，也就是说若k + 1，则x 会增加 -num2，也就是说至少也会+1
         * 则k永远无法追上x，此时也要结束循环
         */
        for (long k = 1; k <= num1 - k * num2; k++) {
            if (k >= Long.bitCount(num1 - k * num2)) return (int)k;
        }
        return -1;
    }
}

将数组划分成若干好子数组的方式

class Solution {
    public int numberOfGoodSubarraySplits(int[] nums) {
        // {0,1,|0,0,1|,0,0,1,0}
        // {0,1,|0,0,1,0|,0,1,0}
        // {0,1,|0,0,1,0,0|,1,0}

        // {0,1,0,|0,1|,0,0,1,0}
        // {0,1,0,|0,1,0|,0,1,0}
        // {0,1,0,|0,1,0,0|,1,0}

        // {0,1,0,0,|1,|0,0,1,0}
        // {0,1,0,0,|1,0,|0,1,0}
        // {0,1,0,0,|1,0,0,|1,0}
        final long MOD = (long) 1e9 + 7;
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < nums.length; ++i)
            if (nums[i] == 1)
                list.add(i);
        int[] interval = list.stream().mapToInt(i -> i).toArray();
        if (interval.length == 0)
            return 0;
        long res = 1;
        for (int i = 1; i < interval.length; ++i)
            res = (res * (interval[i] - interval[i - 1])) % MOD;
        return (int) res;
    }
}

机器人碰撞

方法一：栈模拟

类似于735. 行星碰撞

class Solution {
    public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
        int n = positions.length;
        Map<Integer, Integer> posToIdx = new HashMap<>(), posToHealth = new HashMap<>();
        Map<Integer, Character> posToDir = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            posToIdx.put(positions[i], i);
            posToHealth.put(positions[i], healths[i]);
            posToDir.put(positions[i], directions.charAt(i));
        }
        Arrays.sort(positions);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; ++i) {
            boolean alive = true;
            char dir = posToDir.get(positions[i]);
            while (alive && !stack.isEmpty() && dir == 'L' && posToDir.get(stack.peek()) == 'R' ) {
                int topPos = stack.peek();
                int topHealth = posToHealth.get(topPos);
                if (posToHealth.get(positions[i]) > topHealth) {
                    stack.pop();
                    posToHealth.put(positions[i], posToHealth.get(positions[i]) - 1);
                }
                else if (posToHealth.get(positions[i]) < topHealth) {
                    alive = false;
                    posToHealth.put(topPos, posToHealth.get(topPos) - 1);
                }
                else { //==
                    alive = false;
                    stack.pop();
                }
            }
            if (alive)
                stack.push(positions[i]);
        }
        int[] newHealths = new int[n];
        while (!stack.isEmpty()) {
            int pos = stack.pop();
            int index = posToIdx.get(pos), health = posToHealth.get(pos);
            newHealths[index] = health;
        }
        List<Integer> survivor = new LinkedList<>();
        for (int x : newHealths)
            if (x != 0)
                survivor.add(x);
        return survivor;
    }
}

​