lcpBi97

分割数组中数字的数位

方法一：双端队列

class Solution {
    public int[] separateDigits(int[] nums) {
        Deque<Integer> deque = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        for (int x : nums) {
            while (x != 0) {
                deque.offerFirst(x % 10);
                x /= 10;
            }
            while (!deque.isEmpty())
                list.add(deque.pollFirst());
        }
        return list.stream().mapToInt(i->i).toArray();
    }
}

从一个范围内选择最多整数 I

方法一：HashSet

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        Set<Integer> set = new HashSet<>();
        for (int x : banned)
            set.add(x);
        int sum = 0, res = 0;
        for (int i = 1; i <= n; ++i) {
            if (set.contains(i))
                continue;
            if (sum + i <= maxSum) {
                sum += i;
                ++res;
            }
        }
        return res;
    }
}

两个线段获得的最多奖品

方法一：同向双指针

class Solution {
    public int maximizeWin(int[] pos, int k) {
        int n = pos.length, res = 0, l = 0;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            while (pos[i] - pos[l] > k)
                ++l;
            res = Math.max(res, pre[l] + i - l + 1);
            pre[i + 1] = Math.max(pre[i], i - l + 1);
        }
        return res;
    }
}

二进制矩阵中翻转最多一次使路径不连通

方法一：两次DFS

class Solution {
    public boolean isPossibleToCutPath(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        return !dfs(0, 0) || !dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        if (i == m - 1 && j == n - 1)
            return true;
        grid[i][j] = 0;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && grid[row][col] == 1 && dfs(row, col))
                return true;
        }
        return false;
    }


    int m, n;
    int[][] dirs = new int[][]{{1, 0}, {0, 1}}, grid;

    private boolean isValid(int i, int j) {
        return i < m && j < n;
    }
}