2023-05-17 刷题

标签：pre 遍历 return 17 05 int omitIdx ++ 刷题

算法题目1：【Mid】47. 全排列 II

思路分析：

将原问题转换成子问题，先不考虑重复元素，例如 P{1,2,3} = {"1" + P{2,3}, "2" + P{1,3}， "3" + P{1,2}}。之后再考虑重复元素。
怎么枚举？枚举每个位置可以填哪些数。【这种枚举方式能保证字典序，除此外，还有一种，枚举每个数可以放到哪个位置上，这题不适合】
怎么去重？首先对输入的数组进行排序，目的是在当前位置枚举可以使用哪些元素时，可以将相同的元素规定一个顺序。对于1 1 1 2 2 这种，重复的数，规定只能从前往后使用。visit[]数组标记每个数是否使用了。对于三个1，要使用第二个1，只有当visit[0] = true。同理，要使用第三个1，只能当visit[1] = true。这样就能保证相同元素在所有的全排列结果中的相对顺序是唯一的。

复杂度分析：

时间：O(nlogn + n! * n). 对输入数组进行排序，O(nlogn), dfs递归调用，实际是枚举每个位置，反应在参数pos (也等于path.size(), 这里没有省略pos，是因为显示写出pos更易懂一点) 。因此，总共有n个位置，每个位置遍历n个元素，依次将没有使用过的元素，放在该位置上，然后进行递归调用，最后枚举到的结果，需要copy一遍到结果数组中，所以这步的时间复杂度就是：O(n! * n).
空间：O(n). 如果不考虑结果数组的话，中间用到的visited数组以及递归的栈最大深度n, 因此空间是O(n).

本题难点：去重。

class Solution {
    public List<List<Integer>> permuteUnique(int[] A) { // time: O(nlogn + n!*n), space: O(n)
        ans = new ArrayList<>();
        visited = new boolean[A.length];

        Arrays.sort(A);
        dfs(A, 0, new ArrayList<>());

        return ans;
    }

    List<List<Integer>> ans;
    boolean[] visited;

    void dfs(int[] A, int pos, List<Integer> path) {
        if (pos == A.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 枚举当前pos位置，能填哪些数
        for(int i = 0; i < A.length; i++) {
            if (visited[i] || 
                i > 0 && A[i] == A[i-1] && !visited[i - 1]
            ) {
                continue;
            }
            // 否则说明A[i]这个数可以使用
            visited[i] = true;
            path.add(A[i]);

            dfs(A, pos + 1, path);

            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

【easy】1909. 删除一个元素使数组严格递增

思路：遍历找到第一个逆序对，然后尝试删除其中一个，看剩下来是否严格递增。思路很简单，代码实现刚开始可能有点绕，后来想清楚了就简单了。

  public boolean canBeIncreasing(int[] A) { // time: O(n), space: O(1)
        int n = A.length;
        for(int i = 1; i < n; i++) {
            if (A[i-1] >= A[i]) { // 找到一个逆序对
                return isIncreasing(A, i - 1) // try to delete A[i-1]
                    || isIncreasing(A, i);    // try to delete A[i]
            }
        }
        return true;
    }

    boolean isIncreasing(int[] A, int omitIdx) {
        int pre = -1;
        for(int i = 0; i < A.length; i++) { // 因为omitIdx有可能是0，所以这里要从0开始遍历，不能假定A[0]始终都存在
            if (i == omitIdx) {
                continue;
            }
            if (pre > -1 && A[pre] >= A[i]) {
                return false;
            }
            pre = i;
        }
        return true;
    }

复杂度分析：

时间：O(n)，找到第一个逆序对遍历一遍，然后判断删除元素之后，是否递增，最多遍历两遍。所以时间复杂度是O(n)
空间：O(1)

细节上可以做一些优化，isIncreasing函数没必要从头开始，从omitIdx的下一个开始也可以。

  boolean isIncreasing(int[] A, int omitIdx) { // 优化之后，最多遍历两遍
        int pre = omitIdx - 1;
        for(int i = omitIdx + 1; i < A.length; i++) {            
            if (pre > -1 && A[pre] >= A[i]) {
                return false;
            }
            pre = i;
        }
        return true;
    }

还可以再优化一下，只遍历一遍，代码如下

  public boolean canBeIncreasing(int[] A) { // time: O(n), space: O(1)
        int n = A.length;
        int count = 0;
        for(int i = 1; i < n; i++) {
            if (A[i-1] >= A[i]) {
                count++;
                if (i > 1 && A[i-2] >= A[i]) { // can't delete A[i-1]
                    // so try to delete A[i]
                    A[i] = A[i-1];
                } // else delete A[i-1], 优先删除A[i-1]因为它比A[i]大，删除它之后，递增的概率大一点？
            }
        }
        return count <= 1;
    }

算法题目2：【easy】1909. 删除一个元素使数组严格递增