LC 406. 根据身高重建队列

class Solution {
    int[][] people;
    boolean[] flag;
    List<int[]> path = new ArrayList();
    List<int[]> result;
    public int[][] reconstructQueue(int[][] people) {
        this.people = people;
        this.flag = new boolean[people.length];
        backtrack(0, 0);
        return result.toArray(new int[people.length][]);
    }
    // 当前是第 stage 阶段
    // 当前阶段的决策为让下标为 index 的人站到队列 stage 下标的位置
    public void backtrack(int stage, int index) {
        if (path.size() == people.length) {
            result = new ArrayList(path);
            return;
        }
        for (int i = 0; i < people.length && result == null; i++) {
            if (flag[i] == false && judge(i)) {
                int[] ints = {people[i][0], people[i][1]};
                path.add(ints);
                flag[i] = true;
                backtrack(stage + 1, i);
                flag[i] = false;
                path.remove(stage);
            }
        }
    }
    // 判断 下标为 index 的人 站在此时的队列后面是否满足要求
    public boolean judge(int i) {
        int size = 0;
        for (int j = 0; j < path.size(); j++) {
            int[] ints = path.get(j);
            if (ints[0] >= people[i][0]) {
                size++;
            }
        }
        if (size == people[i][1]) {
            return true;
        } else {
            return false;
        }
    }
}

LC 435. 无重叠区间

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    int[][] intervals;
    int result = Integer.MAX_VALUE;
    // 备忘录
    int[][] memo;
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        this.intervals = intervals;
        memo = new int[intervals.length + 1][100000];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }
        // maxValue 初始化赋为 -5 * 10000 的原因:start 的取值范围为 -5 * 104 <= start
        backtracking(0, 0, -5 * 10000);
        return result;
    }
    // index 为：当前阶段为决策下标为 index 的区间
    // num 为：截止到目前需要移除的区间数量
    // maxValue 为：最大右边界
    public void backtracking(int index, int num, int maxValue) {
        // 由于 maxValue 有可能为负数, 因此需要偏移
        if (memo[index][maxValue + 5 * 10000] != -1 && num >= memo[index][maxValue + 5 * 10000]) {
            return;
        }
        if (index >= intervals.length) {
            result = Math.min(result, num);
            return;
        }
        memo[index][maxValue + 5 * 10000] = num;
        // 决策一：移除下标为 index 的区间
        backtracking(index + 1, num + 1, maxValue);
        // 决策二：不移除（需要满足不重叠的条件）
        if (intervals[index][0] >= maxValue) {
            backtracking(index + 1, num, Math.max(maxValue, intervals[index][1]));
        }
    }
}

LC 455. 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // g 是孩子的胃口
        Arrays.sort(g);
        // s 是饼干的尺寸
        Arrays.sort(s);
        int result = 0;
        // index 是饼干数组的下标
        int index = s.length - 1;
        for (int i = g.length - 1; i >= 0; i--) {
            if (index >= 0 && s[index] >= g[i]) {
                result++;
                index--;
            }
        }
        return result;
    }
}

LC 491. 递增子序列

本题求自增子序列，是不能对原数组进行排序的。所以不能使用之前的使用 used[] 去重逻辑

class Solution {
    {
        /*
        输入[1,1,1]
        输出[[1,1],[1,1,1],[1,1],[1,1]]
        预期结果[[1,1],[1,1,1]]
         */
    }
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    int[] nums;
    public List<List<Integer>> findSubsequences(int[] nums) {
        this.nums = nums;
        this.used = new boolean[nums.length];
        backtracking(0, -1);
        return result;
    }
    // 集合的区间范围 [startIndex, nums.length - 1]
    public void backtracking(int startIndex, int frontFloorIndex) {
        if (startIndex > 0) {
            if (path.size() > 1) {
                result.add(new ArrayList<>(path));
            }
        }
        if (startIndex >= nums.length) {
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (frontFloorIndex >= 0) {
                boolean judge = judge(frontFloorIndex, i - 1, nums[i]);
                if (judge) {
                    continue;
                }
            }
            if (path.size() > 0 && nums[i] < path.get(path.size() - 1)) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtracking(i + 1, i);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
    // 如果树层重复,返回 true; 否则返回 false
    public boolean judge(int l, int r, int value) {
        int index = judgeExist(l, r, value);
        if (index != -1) {
            return !used[index];
        }
        return false;
    }
    // 判断数组的 [l, r] 区间范围内, 是否有值为 value 的元素
    // 如果有, 返回元素的下标; 如果没有, 返回 - 1;
    public int judgeExist(int l, int r, int value) {
        for (int i = l; i <= r; i++) {
            if (value == nums[i]) {
                return i;
            }
        }
        return -1;
    }
}