每日一些题

题解开始之前，给大家安利一个上班偷偷学习的好搭档，idea中的插件有一个叫 LeetCode with labuladong，可以在idea中直接刷力扣的题目。

 朋友们上班没事的时候，可以偷偷摸几题。看八股的话，可以用面试鸭，也是idae插件，比较隐蔽。

子集Ⅱ

题目

思路

• 排序： 首先对 nums 数组进行排序，排序有助于后续判断重复元素。在递归过程中，我们只会在每个位置选择当前数字，并且如果当前数字和前一个数字相同，我们只会在前一个数字被选择的情况下才选择当前数字。这是避免重复的关键。
• 回溯算法： 从数组的起始位置开始，每个元素有两种选择：要么选择它，要么不选择它。我们不断递归地进行决策，同时收集所有的子集。
• 避免重复： 在递归中，处理重复元素时，只有在当前元素与前一个元素相等，并且前一个元素已经被选择的情况下，才可以选择当前元素。这样就避免了重复子集的产生。

题解

 public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        fun(nums,0,new ArrayList<Integer>(),res);
        return res;
    }

    private void fun(int[] nums, int start, ArrayList<Integer> cur, List<List<Integer>> res) {
        res.add(new ArrayList<Integer>(cur));
        for (int i = start; i < nums.length; i++) {
            if(i>start&&nums[i]==nums[i-1]){
                continue;
            }
            cur.add(nums[i]);
            fun(nums,i+1,cur,res);
            cur.remove(cur.size()-1);
        }
    }

外观数列

题目

思路

直接模擬試驗

题解

 public String countAndSay(int n) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list = fun(1, n, list);
        StringBuilder sb = new StringBuilder();
        for (Integer integer : list) {
            sb.append(integer);
        }
        return sb.toString();
    }

    public List<Integer> fun(int k, int n, List<Integer> list) {
        if (k == n) {
            return list;
        }
        List<Integer> result = new ArrayList<>();
        int forn = 0, num = 0;
        for (Integer integer : list) {
            if (forn == 0) {
                forn = integer;
                num = 1;
            } else if (integer == forn) {
                num++;
            } else {
                result.add(num);
                result.add(forn);
                num = 1;
                forn = integer;
            }
        }
        result.add(num);
        result.add(forn);
        return fun(k + 1, n, result);
    }

两数相除

题目

思路

用位移运算（<<，即左移）可以快速实现“乘法”操作，从而加速除法过程。

具体来说，不断将 divisor 左移（即乘以 2）直到它大于被除数 dividend，然后从高位开始减去合适的倍数。这样可以将复杂度从 O(dividend) 降低到 O(log(dividend))。

代码

public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        if (dividend == Integer.MIN_VALUE && divisor == 1) {
            return Integer.MIN_VALUE;
        }

        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);

        long sum = 0;
        while (absDividend >= absDivisor) {
            long temp = absDivisor, multiple = 1;
            while (absDividend >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            absDividend -= temp;
            sum += multiple;
        }
        sum = sign == 1 ? sum : -sum;
        if (sum > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (sum < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int) sum;
    }