剑指 Offer 14- I. 剪绳子

image.png

  • 使用一个数组dp来代表长度为i时候，乘积的最大值
  • 对于当前i，遍历最后一个长度，加入最后一段长度是j
    • 那么对于i-j来说，有两个取值
      • 取（i-j）剪开情况的最大值j * dp[i - j]
      • （i-j）长度不剪开j * (i - j)

  • dp[i] = max(dp[i], max(j (i - j), j dp[i - j]))

    1. class Solution {
    2.   public int cuttingRope(int n) {
    3.       int[] dp = new int[n+1];
    4.       // for(int i = 0;i<=n;i++) {
    5.       //     dp[i][1] = i;
    6.       // }
    7.       dp[1]=1;
    8.       dp[2]=1;
    9.       for(int i = 3; i <= n;i++) {
    10.           for(int j = 1; j < i ; j++) {
    11.               dp[i] = Math.max(dp[i-j]*j,dp[i]);
    12.               dp[i] = Math.max((i-j)*j,dp[i]);
    13.           }
    14.       }
    15.       // System.out.println(Arrays.toString(dp));
    16.       return dp[n];
    17.   }
    18. }

    剑指 Offer 15. 二进制中1的个数

    image.png

    1. public class Solution {
    2.   // you need to treat n as an unsigned value
    3.   public int hammingWeight(int n) {
    4.       int mask = 1;
    5.       int num = 0;
    6.       int max = 1<<31;
    7.       while((mask&max)==0) {
    8.           if((mask&n)!=0) { // 不要!=1,因为最低位才是1，其余位比较不为1
    9.               num++;
    10.           }
    11.           mask<<=1;
    12.       }
    13.       // (mask&max)!=0的情况，即maks=1<<31的时候
    14.       if((mask&n)!=0) {
    15.           num++;
    16.       }
    17.       return num;
    18.   }
    19. }

    剑指 Offer 16. 数值的整数次方

    image.png

  • 注意负数

  • 注意min没有整数对应

    1. class Solution {
    3.   public double myPow(double x, int n) { 
    4.       // 注意-2147483648的情况，没有对应的正数值
    5.       if(n<0) {
    6.           int t = n/2;
    7.           if(n%2==0) {
    8.               double res = myPow(x,-t);
    9.               return 1.0/(res*res);
    10.           } else {
    11.               double res = myPow(x,-t);
    12.               return 1.0/(res*res*x);
    13.           }
    14.       }
    16.       if(n==1)
    17.           return x;
    18.       if(n==0)
    19.           return 1;
    20.       if(n%2==0) {
    21.           double res = myPow(x,n/2);
    22.           return res*res;
    23.       } else {
    24.           double res = myPow(x,n/2);
    25.           return res*res*x;
    26.       }
    27.   }
    28. }

    剑指 Offer 17. 打印从1到最大的n位数

    image.png

    1. class Solution {
    2.   public int[] printNumbers(int n) {
    3.       StringBuilder builder = new StringBuilder();
    4.       List<Integer> list= new ArrayList();
    5.       dfs(n,0,builder,list);
    6.       int[] res = new int[list.size()];
    7.       for(int i = 0 ; i < res.length;i++)
    8.           res[i] = list.get(i);
    9.       return res;
    10.   }
    12.   void dfs(int n,int index,StringBuilder builder,List<Integer> list) {
    13.       if(n==index) {
    14.           String s = builder.toString();
    15.           int i = 0;
    16.           // 越过前面的0
    17.           while(i<s.length() && s.charAt(i)=='0') i++;
    18.           if(i!=builder.length()) // 不为0则添加
    19.               list.add(Integer.parseInt(s.substring(i)));
    20.           return;
    21.       }
    23.       for(int i = 0 ; i <= 9 ; i++) {
    24.           builder.append(i);
    25.           dfs(n,index+1,builder,list);
    26.           builder.deleteCharAt(builder.length()-1);
    27.       }
    28.   }
    29. }

    剑指 Offer 36. 二叉搜索树与双向链表

    image.png

  • 递归左子树

    • 返回左子树最右边的节点t
    • 让root的left指向t，t的右子树指向root
  • 递归右子树
    • 返回右子树的最左边的节点t
    • 让root的right指向t，t的左子树指向root
  1. class Solution {
  2.     public Node treeToDoublyList(Node root) {
  3.         if(root==null)
  4.             return null;
  5.         // 处理根节点
  6.         if(root.left!=null) {
  7.             Node l = tree(root.left,true);
  8.             root.left = l;
  9.             l.right = root;
  10.         }
  11.         // 跟的右子树
  12.         if(root.right!=null) {
  13.             Node r = tree(root.right,false);
  14.             r.left = root;
  15.             root.right = r;
  16.         }
  18.         Node tail = root;
  19.         while(tail.right!=null)
  20.             tail = tail.right;
  21.         Node head = root;
  22.         while(head.left!=null)
  23.             head = head.left;
  24.         head.left = tail;
  25.         tail.right = head;
  27.         return head;
  28.     }
  31.     public Node tree(Node root,boolean left) {
  32.         Node l = null;
  33.         Node r = null;
  34.         if(root.left!=null) {
  35.             l = tree(root.left,true);
  36.         }
  37.         if(root.right!=null) {
  38.             r = tree(root.right,false);
  39.         }
  40.         if(l!=null) {
  41.             l.right = root;
  42.             root.left = l;
  43.         }
  44.         if(r!=null){
  45.             r.left = root;
  46.             root.right = r;
  47.         }
  49.         Node now = root;
  50.         if(left) {
  51.             while(now.right!=null)
  52.                 now = now.right;
  53.             return now;
  54.         } else {
  55.             while(now.left!=null)
  56.                 now = now.left;
  57.             return now;
  58.         }
  59.     }
  60. }

229. 求众数 II

难度中等353
image.png
moore投票法，O(N)时间，O(1)空间。本质上是利用两个变量cm, cn记录频率最高的两个元素m, n的频率，遇到m,n自增对应的频率，遇到非m,非n，自减cm,cn。最后再重置cm,cn为0，再遍历一遍数组查看获取的最高频率的m，n的频率是否大于1/3的总元素个数。因为有可能最高频率的元素并不大于1/3的总元素个数(比如[1,1,2,2,3,4,5,6,7,8,9])

  1. class Solution {
  2.     public List<Integer> majorityElement(int[] nums) {
  3.         int a1 = nums[0];
  4.         int b1 = 0;
  5.         int a2 = nums[0];
  6.         int b2 = 0;
  7.         for(int num:nums) {
  8.             if(a1==num) {
  9.                 b1++;
  10.                 continue;
  11.             }
  12.             if(a2==num) {
  13.                 b2++;
  14.                 continue;
  15.             }
  16.             if(b1==0){
  17.                 a1 = num;
  18.                 b1=1;
  19.                 continue;
  20.             } 
  21.             if(b2==0) {
  22.                 a2 = num;
  23.                 b2=1;
  24.                 continue;
  25.             }
  26.             b1--;
  27.             b2--;
  28.         }
  29.         b1=0;
  30.         b2=0;
  31.         for(int n:nums){
  32.             if(n==a1) {
  33.                 b1++;
  34.             } else if(n==a2){
  35.                 b2++;
  36.             }
  37.         }
  38.         List<Integer> list = new ArrayList();
  40.         if(b1*3>nums.length)
  41.             list.add(a1);
  42.         if(b2*3>nums.length)
  43.             list.add(a2);
  44.         return list;
  45.     }
  46. }

剑指 Offer 35. 复杂链表的复制

image.png
剑指offer - 图9

  1. class Solution {
  2.     public Node copyRandomList(Node head) {
  4.         Node now = head;
  5.         // 复制新节点，将其放入原节点的后面
  6.         while(now != null) {
  7.             Node copyNode = new Node(now.val);
  8.             copyNode.next = now.next;
  9.             now.next = copyNode;
  10.             now = now.next.next;
  11.         }
  13.         now = head;
  14.         // 设置新结点的random
  15.         while(now!=null) {
  16.             if(now.random!=null) {
  17.                 now.next.random = now.random.next;
  18.             }
  19.             now = now.next.next;
  20.         }
  21.         // now = head;
  22.         // while(now!=null){
  23.         //     System.out.print(now.val+" ");
  24.         //     now = now.next;
  25.         // }
  26.         Node dummy = new Node(-1);
  27.         Node pre = dummy;
  28.         now = head;
  29.         // 拆分节点
  30.         while(now!=null) {
  31.             pre.next = now.next;
  32.             now.next = now.next.next;
  33.             pre = pre.next;
  34.             pre.next=null;
  35.             now = now.next;
  36.         }
  37.         return dummy.next;
  38.     }
  39. }

剑指 Offer 40. 最小的k个数

image.png

  • 快排

    1. class Solution {
    3.   public int[] getLeastNumbers(int[] arr, int k) {
    4.       find(arr,0,arr.length-1,k-1);
    5.       int[] res = new int[k];
    6.       for(int i = 0 ; i < k ; i++)
    7.           res[i] = arr[i];
    8.       return res;
    9.   } 
    11.   void find(int[] arr,int l,int r,int k) {
    12.       if(l>=r)
    13.           return;
    14.       int pivot = arr[l];
    15.       int left = l;
    16.       int right = r;
    17.       while(left<right) {
    18.           while(left<right && arr[right]>=pivot)
    19.               right--;
    20.           while(left<right && arr[left]<=pivot)
    21.               left++;
    22.           if(left<right) {
    23.               int t = arr[left];
    24.               arr[left] = arr[right];
    25.               arr[right] = t;
    26.           }
    27.       }
    28.       arr[l] = arr[left];
    29.       arr[left] = pivot;
    31.       if(left<k) {
    32.           find(arr,left+1,r,k);
    33.       } else if(left>k) {
    34.           find(arr,l,left-1,k);
    35.       }
    36.   }
    37. }

    剑指 Offer 33. 二叉搜索树的后序遍历序列

    image.png
    image.png ```java class Solution { public boolean verifyPostorder(int[] postorder) {

    1.   return find(postorder,0,postorder.length-1);

    }

  1. boolean find(int[] postorder,int l,int r) {
  2.     if(l>=r)
  3.         return true;
  5.     int p = l;
  6.     while(postorder[p]<postorder[r]) p++;  // 左子树
  7.     int m = p; // m记录的是第一个右子树的节点
  8.     while(postorder[p]>postorder[r]) p++;  // 右子树
  9.     // p==r的意义是：
  10.     /*
  11.         5
  12.        /
  13.       3
  14.        \
  15.         6
  17.         这样6，3，5:6和3符合规则，3和5符合规则，但是5，6不符合规则;
  18.         是为了防止非直接父节点的冲突
  19.     */
  20.     return p==r && find(postorder,l,m-1) && find(postorder,m,r-1);
  21. }

}

  1. <a name="eihXN"></a>
  2. #### [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/)
  3. ```c
  4. class Solution {
  5.     public int maxSubArray(int[] nums) {
  6.         int max = nums[0];
  7.         int res = nums[0];
  8.         for(int i = 1 ; i < nums.length;i++) {
  9.             if(res<0) { // 放弃之前的子序和
  10.                 res = 0;
  11.             }
  12.             res+= nums[i];
  13.             max = Math.max(res,max);
  14.         }
  15.         return max;
  16.     }
  17. }

剑指 Offer 46. 把数字翻译成字符串

image.png

  1. class Solution {
  2.     public int translateNum(int num) {
  3.         int a = 1; // -1 index  初试化
  4.         int b = 1; //  0 index  初始化
  5.         char[] ch = (num+"").toCharArray();
  6.         for(int i = 1;i<ch.length;i++) {
  7.             int t = 0;
  8.             if(check(ch[i-1],ch[i])) {
  9.                 t+=a;
  10.             }
  11.             t+=b;
  12.             a = b;
  13.             b = t;
  14.         }
  15.         return b;
  16.     }
  18.     boolean check(char a,char b) {
  19.         if(a=='0') // 十位不能为0
  20.             return false;
  21.         int res = 0;
  22.         res += (a-'0');
  23.         res = res * 10 + (b-'0');
  24.         if(res>0 && res <= 25) {
  25.             return true;
  26.         }
  27.         return false;
  28.     }
  29. }

剑指 Offer 45. 把数组排成最小的数

image.png
image.png

  1. class Solution {
  2.     public String minNumber(int[] nums) {
  3.         PriorityQueue<String> queue = new PriorityQueue<String>(new Comparator<String>(){
  4.             public int compare(String s1,String s2) {
  5.                 return (s1+s2).compareTo(s2+s1);
  6.             }
  7.         });
  8.         for(int num:nums) {
  9.             queue.add(num+"");
  10.         }
  11.         StringBuilder builder = new StringBuilder();
  12.         while(queue.size()!=0) {
  13.             builder.append(queue.poll());
  14.         }
  15.         return builder.toString();
  16.     }
  17. }
  20. ==== 标准答案
  21. class Solution {
  22.     public String minNumber(int[] nums) {
  23.         String[] strs = new String[nums.length];
  24.         for(int i = 0 ;i < strs.length;i++) {
  25.             strs[i] = String.valueOf(nums[i]);
  26.         }
  27.         Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
  28.         StringBuilder builder = new StringBuilder();
  29.         for(int i = 0 ;i < strs.length;i++) {
  30.             builder.append(strs[i]);
  31.         }
  32.         return builder.toString();
  33.     }
  34. }

剑指 Offer 44. 数字序列中某一位的数字

image.png

  1. class Solution {
  2.     public int findNthDigit(int n) {
  3.         int digit = 1;
  4.         long start = 1;
  5.         long count = 9;
  6.         while (n > count) { // 1.
  7.             n -= count;
  8.             digit += 1;
  9.             start *= 10;
  10.             count = digit * start * 9;
  11.         }
  12.         long num = start + (n - 1) / digit; // 2.
  13.         return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
  14.     }
  15. }
  17. 作者：jyd
  18. 链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/
  19. 来源：力扣（LeetCode）
  20. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

剑指 Offer 49. 丑数

image.png
image.png

  1. class Solution {
  2.     public int nthUglyNumber(int n) {
  3.         int a2 = 0;
  4.         int a3 = 0;
  5.         int a5 = 0;
  6.         int[] arr = new int[n];
  7.         arr[0] = 1;
  8.         for(int i = 1; i < n ; i++) {
  9.             int n2 = 2*arr[a2];
  10.             int n3 = 3*arr[a3];
  11.             int n5 = 5*arr[a5];
  12.             int m = Math.min(n2,Math.min(n3,n5));
  13.             arr[i] =m;
  14.             if(m==n2)   a2++;//对于6来说,2*3=6;3*2=6;所以a2和a3要同时增加1
  15.             if(m==n3)   a3++;
  16.             if(m==n5)   a5++;
  17.         }
  19.         return arr[n-1];
  20.     }
  21. }

剑指 Offer 41. 数据流中的中位数

image.png

  1. class MedianFinder {
  3.     PriorityQueue<Integer> q1 = null;
  4.     PriorityQueue<Integer> q2 = null;
  6.     /** initialize your data structure here. */
  7.     public MedianFinder() {
  8.         q1 = new PriorityQueue(new Comparator<Integer>(){
  9.             public int compare(Integer i1,Integer i2) {
  10.                 return i2-i1;
  11.             }
  12.         });
  13.         q2 = new PriorityQueue(new Comparator<Integer>(){
  14.             public int compare(Integer i1,Integer i2) {
  15.                 return i1-i2;
  16.             }
  17.         });
  18.     }
  20.     public void addNum(int num) {
  22.         int s1 = q1.size();
  23.         int s2 = q2.size();
  24.         if(s1==0) { // 初始化的状态
  25.             q1.add(num);
  26.         } else if(s1==s2) { // 两者大小相同的时候,需要挑一个元素放到前半个中
  27.             if(num < q2.peek()) { // 当前元素比较小,可以直接放入前一半
  28.                 q1.add(num);
  29.             } else { // 当前元素大于后半段的第一个,需要将后半段的第一个加入前半段
  30.                 q1.add(q2.poll());
  31.                 q2.add(num);
  32.             }
  33.         } else {
  34.             if(q1.peek()>num) {
  35.                 q2.add(q1.poll());
  36.                 q1.add(num);
  37.             } else {
  38.                 q2.add(num);
  39.             }
  40.         }
  41.     }
  43.     public double findMedian() {
  44.         int s1 = q1.size();
  45.         int s2 = q2.size();
  46.         if(s1==s2) {
  47.             return (q1.peek()+q2.peek())/2.0;
  48.         }
  49.         return q1.peek()/1.0;
  50.     }
  51. }

剑指 Offer 56 - II. 数组中数字出现的次数 II

image.png

  • 对数组的每个数
    • 记录当前数的每一位的数量,如果第i位为1,那么count[i]+=1;
  • 现在已经得到所有数的第i位的个数
  • count[i]%=3;

  • 根据count计算结果

    1. class Solution {
    2.   public int singleNumber(int[] nums) {
    3.       int[] count = new int[32];
    4.       for(int i = 0 ; i < nums.length; i++) {
    5.           int now = nums[i];
    6.           for(int j = 0 ; j < 32 ; j++) {
    7.               if(now==0)
    8.                   break;
    9.               count[j] += 1&now;  // 记录当前数的第j位
    10.               now = now>>>1;
    11.           }
    12.       }
    13.       for(int i = 0 ;  i< 32;i++) {
    14.           count[i] %= 3;
    15.       }
    16.       int res = 0;
    17.       for(int i = 0 ; i < 32;i++) {
    18.           res += (count[i]<<i);
    19.       }
    20.       return res;
    21.   }
    22. }

    剑指 Offer 56 - I. 数组中数字出现的次数

    image.png
    全部异或一边,得到两个只出现一次的x,y的值得z=x^y,找出z二进制表示里面为1的一位,这边是对于这个位来说,可以把x,y分成不一样的组,所以就可以求出来了.

    1. class Solution {
    2.   public int[] singleNumbers(int[] nums) {
    3.       int flag = 0;
    4.       for(int i = 0 ; i < nums.length; i++) {
    5.           flag^=nums[i];
    6.       }
    7.       int j = 0;
    8.       while(true) {
    9.           if((flag&1)==1) {
    10.               break;
    11.           }
    12.           j++;
    13.           flag>>>=1;
    14.       }
    15.       int f1 = 0;
    16.       int f2 = 0;
    17.       for(int i = 0 ; i < nums.length; i++) {
    18.           if(((nums[i]>>j)&1)==1) {
    19.               f1 ^= nums[i];
    20.           } else {
    21.               f2 ^= nums[i];
    22.           }
    23.       }
    24.       return new int[]{f1,f2};
    25.   }
    26. }

    剑指 Offer 51. 数组中的逆序对

    image.png
    image.pngimage.png ```java class Solution {

    int result = 0; public int reversePairs(int[] nums) {

    1.   divid(nums,0,nums.length-1);
    2.   return result;

    }

  1. void divid(int[] nums,int l,int r) {
  2.     if(l>=r)
  3.         return;
  5.     int m = l+r>>1;
  6.     divid(nums,l,m);
  7.     divid(nums,m+1,r);
  9.     if(nums[m]<=nums[m+1])
  10.         return;
  12.     merge(nums,l,m,r);
  14. }
  16. void merge(int[] nums,int l,int m,int r) {
  17.     int[] arr = new int[r-l+1];
  18.     int index = 0;
  19.     int len = arr.length;
  20.     int l1 = l;
  21.     int l2 = m+1;
  22.     int res = 0;
  23.     while(index<len) {
  24.         if(l1==m+1) {
  25.             arr[index] = nums[l2++];
  26.         } else if(l2==r+1) {
  27.             arr[index] = nums[l1++];
  28.             res += (l2-m-1);
  29.         } else {
  30.             if(nums[l1]<=nums[l2]) {
  31.                 arr[index] = nums[l1++]; // 如果两个开始位置相等,则前面的一个先移动
  32.                 res += (l2-m-1);
  33.             } else {
  34.                 arr[index] = nums[l2++];
  35.             }
  36.         }
  37.         index++;
  38.     }
  39.     for(int i = l;i<=r;i++) {
  40.         nums[i] = arr[i-l];
  41.     }
  42.     result+=res;
  43.     // System.out.println(result);
  44.     // System.out.println(Arrays.toString(nums));
  45. }

}

  1. <a name="A46gI"></a>
  2. #### [剑指 Offer 57 - II. 和为s的连续正数序列](https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/)
  3. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/8429887/1618239440084-5639d9eb-8255-4878-b242-0079e28ca20f.png#align=left&display=inline&height=421&margin=%5Bobject%20Object%5D&name=image.png&originHeight=421&originWidth=576&size=21323&status=done&style=none&width=576)
  5. - 两个指针l=1,r=2;
  6. - 计算这个区间中数的大小
  7. - 如果数小于,则r++
  8. - 大于,则l++
  9. - 等于,则r++
  10. ```java
  11. class Solution {
  12.     public int[][] findContinuousSequence(int target) {
  13.         List<int[]> list = new ArrayList();
  14.         for(int l = 1,r = 2;l<r;) {
  15.             int sum = (l+r)*(r-l+1);
  16.             if(target*2==sum) {
  17.                 int[] nums = new int[r-l+1];
  18.                 for(int i = l;i<=r;i++) {
  19.                     nums[i-l] = i;
  20.                 }
  21.                 list.add(nums);
  22.                 r++;
  23.             } else if (target*2<sum) {
  24.                 l++;
  25.             } else {
  26.                 r++;
  27.             }
  28.         }
  29.         int[][] arr = new int[list.size()][];
  30.         for(int i = 0 ; i < arr.length;i++) {
  31.             arr[i] = list.get(i);
  32.         }
  33.         return arr;
  34.     }
  35. }

剑指 Offer 59 - I. 滑动窗口的最大值

image.png

  • 单调队列
    • 判断队头是不是失效了
    • 将小于等于当前元素的数据全部出列
      1. class Solution {
      2. public int[] maxSlidingWindow(int[] nums, int k) {
      3.    if(nums.length==0)
      4.        return new int[]{};
      5.    LinkedList<Integer> queue = new LinkedList();
      6.    for(int i = 0; i < k ; i++) {  // 初始化链表
      7.        while(!queue.isEmpty() && nums[queue.getLast()] < nums[i]) {
      8.            queue.removeLast();
      9.        }
      10.        queue.add(i);
      11.    }
      12.    int[] res = new int[nums.length-k+1];
      13.    int index = 0;
      14.    res[index++] = nums[queue.peek()];
      15.    // 遍历剩下的元素
      16.    for(int i = k ; i < nums.length; i++) {
      17.        if(queue.peek() == i-k) {
      18.            queue.poll();
      19.        }
      20.        while(!queue.isEmpty() && nums[queue.getLast()] <= nums[i]) {
      21.            queue.removeLast();
      22.        }
      23.        queue.add(i);
      24.        res[index++] = nums[queue.peek()];
      25.    }
      26.    return res;
      27. }
      28. }