数组题解二

爬楼梯#70（简单）

https://leetcode-cn.com/problems/climbing-stairs/

class Solution {
    public int climbStairs(int n) {
        //法一:递归,时间复杂度O(2^n),空间复杂度O(2^n)
        if (n <= 2) {
            return n;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
}
//====================================================================
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public int climbStairs(int n) {
        //法二:递归+记忆化,时间复杂度O(n),空间复杂度O(n)
        //因为有大量的中间结果进行了重复计算，所以可以把这些重复结果存起来。
        if (n < 3) {
            return n;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int sum = climbStairs(n-1) + climbStairs(n-2);
        map.put(n, sum);
        return sum;
    }
}
//=======================================================================
class Solution {
    public int climbStairs(int n) {
        //法三:迭代,时间复杂度O(n),空间复杂度O(1)
        if (n < 3) {
            return n;
        }
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}
//=======================================================================
class Solution {
    public int climbStairs(int n) {
        //法四:动态规划,时间复杂度O(n),空间复杂度O(1)
        int a = 0, b = 0, c = 1;
        for (int i = 1; i <= n; i++) {
            //这里要从1开始，保证只循环n次
            a = b;
            b = c;
            c = a + b;
        }
        //这里就只能return c
        return c;
    }
}
//========================================================================
//矩阵快速幂还是看官方题解吧。

颜色分类#75（中等）

https://leetcode.cn/problems/sort-colors/

class Solution {
    public void sortColors(int[] nums) {
        //法一:两次遍历，统计个数然后填充回去。时间复杂度O(n),空间复杂度O(1)
        int countOfZero = 0, countOfOne = 0, countOfTwo = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                countOfZero++;
            } else if (nums[i] == 1) {
                countOfOne++;
            } else {
                countOfTwo++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i < countOfZero) {
                nums[i] = 0;
            } else if (i < countOfOne + countOfZero) {
                nums[i] = 1;
            } else {
                nums[i] = 2;
            }
        }
    }
}
//======================================================================
class Solution {
    public void sortColors(int[] nums) {
        //法二:单指针两次遍历。时间复杂度O(n),空间复杂度O(1)
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                swap(nums, i, ptr);
                ptr++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                swap(nums, i, ptr);
                ptr++;
            }
        }
    }
    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
//=====================================================================
class Solution {
    public void sortColors(int[] nums) {
        //法三：liweiwei的循环不变量做法。
        int len = nums.length;
        if (len < 2) {
            return;
        }
        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in (two, len - 1] = 2
        // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
        // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
        // 所以下面遍历到 0 的时候，先交换，再加
        int zero = 0;
        // 为了保证初始化的时候 (two, len - 1] 为空，设置 two = len-1
        // 所以下面遍历到 2 的时候，先交换，再减
        int two = len - 1;
        int i = 0;
        // 当 i == two 上面的三个子区间正好覆盖了全部数组
        // 因此，循环可以继续的条件是 i < two
        while (i <= two) {
            if (nums[i] == 0) {
                swap(nums, i, zero);
                zero++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                swap(nums, i, two);
                two--;
            }
        }
    }
    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

子集#78（中等）

https://leetcode.cn/problems/subsets/

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        //法一:回溯.时间复杂度O(n*(2^n)),空间复杂度O(n)
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> temp = new LinkedList<>();
        dfs(0, nums, ans, temp);
        return ans;
    }

    private void dfs(int index, int[] nums, List<List<Integer>> ans, List<Integer> temp) {
        if (index == nums.length) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        temp.add(nums[index]);
        dfs(index + 1, nums, ans, temp);
        temp.remove(temp.size() - 1);
        dfs(index + 1, nums, ans, temp);
    }
}
//===========================================================================
class Solution {
    //官方题解，用二进制掩码的方式选取。
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

柱状图中最大的矩形#84（困难）

https://leetcode.cn/problems/largest-rectangle-in-histogram/

合并两个有序数组#88（简单）

https://leetcode.cn/problems/merge-sorted-array/

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //法一:先添加，后排序,时间复杂度O((m+n)log(m+n)),空间复杂度O((m+n)log(m+n))
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}
//==========================================================================
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //法二:中间数组+双指针.时间复杂度O(m+n),空间复杂度O(m+n)
        int[] temp = new int[m+n];
        int p1 = 0, p2 = 0;
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            temp[p1+p2-1] = cur;
        }
        for (int i = 0; i < m + n; i++) {
            nums1[i] = temp[i];
        }
    }
}
//========================================================================
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //法三:双指针后入，不需要多余数组.时间复杂度O(m+n),空间复杂度O(1)
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 > -1 || p2 > -1) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums2[p2--];
            } else {
                cur = nums1[p1--];
            }
            nums1[tail--] = cur;
        }
    }
}

子集Ⅱ#90（中等）

https://leetcode.cn/problems/subsets-ii/

class Solution {
    Set<List<Integer>> res = new HashSet<>();
    List<Integer> temp = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //排序+set回溯,时间复杂度O(n*(2^n)),空间复杂度O(n)
        Arrays.sort(nums);
        dfs(0, nums);
        return new ArrayList<>(res);
    }

    public void dfs(int index, int[] nums) {
        if (index == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        temp.add(nums[index]);
        dfs(index + 1, nums);
        temp.remove(temp.size() - 1);
        dfs(index + 1, nums);
    }
}
//官方题解===============================================================
class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(false, 0, nums);
        return ans;
    }

    public void dfs(boolean choosePre, int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        dfs(false, cur + 1, nums);
        if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
            return;
        }
        t.add(nums[cur]);
        dfs(true, cur + 1, nums);
        t.remove(t.size() - 1);
    }
}
//三叶姐的题解，另一个思路，感觉比官解合理一点=======================
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(nums, 0, cur, ans);
        return ans;
    }

    /**
     * @param nums 原输入数组
     * @param u 当前决策到原输入数组中的哪一位
     * @param cur 当前方案
     * @param ans 最终结果集
     */
    void dfs(int[] nums, int u, List<Integer> cur, List<List<Integer>> ans) {
        // 所有位置都决策完成，将当前方案放入结果集
        int n = nums.length;
        if (n == u) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        // 记录当前位置是什么数值（令数值为 t），并找出数值为 t 的连续一段
        int t = nums[u];
        int last = u;
        while (last < n && nums[last] == nums[u]) last++;

        // 不选当前位置的元素，直接跳到 last 往下决策
        dfs(nums, last, cur, ans);

        // 决策选择不同个数的 t 的情况：选择 1 个、2 个、3 个 ... k 个
        for (int i = u; i < last; i++) {
            cur.add(nums[i]);
            dfs(nums, last, cur, ans);
        }

        // 回溯对数值 t 的选择
        for (int i = u; i < last; i++) {
            cur.remove(cur.size() - 1);
        }
    }
}

作者：AC_OIer
链接：https://leetcode.cn/problems/subsets-ii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hui-s-g77q/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。