每日一些题

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

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

标题

思路

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

题解

1. public List<List<Integer>> subsetsWithDup(int[] nums) {
2.         List<List<Integer>> res = new ArrayList<>();
3.         Arrays.sort(nums);
4.         fun(nums,0,new ArrayList<Integer>(),res);
5.         return res;
6.     }
8.     private void fun(int[] nums, int start, ArrayList<Integer> cur, List<List<Integer>> res) {
9.         res.add(new ArrayList<Integer>(cur));
10.         for (int i = start; i < nums.length; i++) {
11.             if(i>start&&nums[i]==nums[i-1]){
12.                 continue;
13.             }
14.             cur.add(nums[i]);
15.             fun(nums,i+1,cur,res);
16.             cur.remove(cur.size()-1);
17.         }
18.     }

复制代码

外貌数列

标题

思路

直接模擬試驗
题解

1. public String countAndSay(int n) {
2.         List<Integer> list = new ArrayList<Integer>();
3.         list.add(1);
4.         list = fun(1, n, list);
5.         StringBuilder sb = new StringBuilder();
6.         for (Integer integer : list) {
7.             sb.append(integer);
8.         }
9.         return sb.toString();
10.     }
12.     public List<Integer> fun(int k, int n, List<Integer> list) {
13.         if (k == n) {
14.             return list;
15.         }
16.         List<Integer> result = new ArrayList<>();
17.         int forn = 0, num = 0;
18.         for (Integer integer : list) {
19.             if (forn == 0) {
20.                 forn = integer;
21.                 num = 1;
22.             } else if (integer == forn) {
23.                 num++;
24.             } else {
25.                 result.add(num);
26.                 result.add(forn);
27.                 num = 1;
28.                 forn = integer;
29.             }
30.         }
31.         result.add(num);
32.         result.add(forn);
33.         return fun(k + 1, n, result);
34.     }

复制代码

两数相除

标题

思路

用位移运算（<<，即左移）可以快速实现“乘法”操作，从而加速除法过程。
具体来说，不断将 divisor 左移（即乘以 2）直到它大于被除数 dividend，然后从高位开始减去符合的倍数。这样可以将复杂度从 O(dividend) 降低到 O(log(dividend))。
代码

1. public int divide(int dividend, int divisor) {
2.         if (dividend == Integer.MIN_VALUE && divisor == -1) {
3.             return Integer.MAX_VALUE;
4.         }
5.         if (dividend == Integer.MIN_VALUE && divisor == 1) {
6.             return Integer.MIN_VALUE;
7.         }
9.         int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
10.         long absDividend = Math.abs((long) dividend);
11.         long absDivisor = Math.abs((long) divisor);
13.         long sum = 0;
14.         while (absDividend >= absDivisor) {
15.             long temp = absDivisor, multiple = 1;
16.             while (absDividend >= (temp << 1)) {
17.                 temp <<= 1;
18.                 multiple <<= 1;
19.             }
20.             absDividend -= temp;
21.             sum += multiple;
22.         }
23.         sum = sign == 1 ? sum : -sum;
24.         if (sum > Integer.MAX_VALUE) {
25.             return Integer.MAX_VALUE;
26.         }
27.         if (sum < Integer.MIN_VALUE) {
28.             return Integer.MIN_VALUE;
29.         }
30.         return (int) sum;
31.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。