剑指 Offer 03. 数组中重复的数字

image.png

  • 如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture

    1. class Solution {
    2.   public int findRepeatNumber(int[] nums) {
    3.       int len = nums.length;
    4.       for(int i = 0; i < len;i++) {
    5.           while(nums[i]!=i) {
    6.               if(nums[nums[i]]==nums[i])
    7.                   return nums[i];
    8.               else  // 交换nums[i] 与 nums[nums[i]]
    9.                   swap(nums,nums[i],i);
    10.           }
    11.       }
    12.       return -1;
    13.   }
    15.   void swap(int[] nums,int a,int b){
    16.       int t = nums[a];
    17.       nums[a] = nums[b];
    18.       nums[b] = t;
    19.   }
    20. }

    51. N 皇后

    image.png

    1. class Solution {
    3.   List<List<String>> res = new ArrayList();
    4.   List<String> list = new ArrayList();
    6.   public List<List<String>> solveNQueens(int n) {
    7.       int[] len = new int[n];
    8.       dfs(len,0);
    9.       return res;
    10.   }
    12.   void dfs(int[] arr,int start){
    13.       // 找到位置，转变成字符串
    14.       if(start==arr.length){
    15.           for(int c:arr) {
    16.               char[] ch = new char[arr.length];
    17.               Arrays.fill(ch,'.');
    18.               int i = 0;
    19.               while((c&(1<<i))==0) {
    20.                   i++;
    21.               }
    22.               ch[ch.length-i-1]='Q';
    23.               list.add(new String(ch));
    24.           }
    25.           res.add(new ArrayList(list));
    26.           list.clear();
    27.           return;
    28.       }
    30.       // 当前行的棋盘分布
    31.       int now = arr[start];
    33.       // 依次实验该行所有的位置放置queen
    34.       while(now<=(1<<(arr.length-1))){
    35.           if(now==0) {
    36.               now=1;
    37.               arr[start] = 1;
    38.           } else {
    39.               arr[start] = now;
    40.           }
    41.           // 判断
    42.           if(check(arr,start)) {
    43.               dfs(arr,start+1);
    44.           }
    45.           now=now<<1;
    46.       }
    47.       // 一定不要忘了归位，比如[1,4,0,0]时候，第三行无解，此时[1,4,8,0]，如果第三行不归零，下一次now直接变成了8，而不是0
    48.       arr[start] = 0;  
    49.   }
    51.   boolean check(int[] arr,int start) {
    52.       // 检查列
    53.       for(int i = start-1;i>=0;i--) {
    54.           if((arr[start]&arr[i])!=0)
    55.               return false;
    56.       }
    57.       // \斜对角线
    58.       int now = arr[start]<<1;
    59.       for(int i = start-1;i>=0;i--,now<<=1) {
    60.           if((now&arr[i])!=0)
    61.               return false;
    62.       }
    63.       // /斜对角线
    64.       now = arr[start]>>1;
    65.       for(int i = start-1;i>=0;i--,now>>=1) {
    66.           if((now&arr[i])!=0)
    67.               return false;
    68.       }
    69.       return true;
    70.   }
    71. }

    52. N皇后 II

    image.png

    1. class Solution {
    3.   int res = 0;
    5.   public int totalNQueens(int n) {
    6.       int[] len = new int[n];
    7.       dfs(len,0);
    8.       return res;
    9.   }
    11.   void dfs(int[] arr,int start){
    12.       if(start==arr.length){
    13.           res++;
    14.           return;
    15.       }
    17.       int now = arr[start];
    19.       while(now<=(1<<(arr.length-1))){
    20.           if(now==0) {
    21.               now=1;
    22.               arr[start] = 1;
    23.           } else {
    24.               arr[start] = now;
    25.           }
    26.           // 判断
    27.           if(check(arr,start)) {
    28.               dfs(arr,start+1);
    29.           }
    30.           now=now<<1;
    31.       }
    32.       // 一定不要忘了归位，比如[1,4,0,0]时候，第三行无解，此时[1,4,8,0]，如果第三行不归零，下一次now直接变成了8，而不是0
    33.       arr[start] = 0;  
    34.   }
    36.   boolean check(int[] arr,int start) {
    37.       // 检查列
    38.       for(int i = start-1;i>=0;i--) {
    39.           if((arr[start]&arr[i])!=0)
    40.               return false;
    41.       }
    42.       int now = arr[start]<<1;
    43.       for(int i = start-1;i>=0;i--,now<<=1) {
    44.           if((now&arr[i])!=0)
    45.               return false;
    46.       }
    47.       now = arr[start]>>1;
    48.       for(int i = start-1;i>=0;i--,now>>=1) {
    49.           if((now&arr[i])!=0)
    50.               return false;
    51.       }
    52.       return true;
    53.   }
    54. }

    2. 两数相加

    image.png

    1. class Solution {
    2.   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    3.       ListNode dummy = new ListNode();
    4.       ListNode pre = dummy;
    5.       boolean f = false;  // 进位
    6.       while(l1!=null || l2!=null || f){
    7.           int v1 = l1==null?0:l1.val; // 这样不必单独判断某个链表是不是空了
    8.           int v2 = l2==null?0:l2.val;
    9.           int v = v1+v2;
    10.           if(f){
    11.               v++;
    12.           }
    13.           if(v>=10){
    14.               v-=10;
    15.               f=true;
    16.           } else {
    17.               f = false;
    18.           } 
    19.           pre.next = new ListNode(v);
    20.           pre = pre.next;
    21.           if(l1!=null){
    22.               l1=l1.next;
    23.           }
    24.           if(l2!=null){
    25.               l2=l2.next;
    26.           }
    27.       }
    28.       return dummy.next; 
    29.   }
    30. }

    445. 两数相加 II

    image.png

  • 用栈

    • 然后依次出栈
      1. /**
      2. * Definition for singly-linked list.
      3. * public class ListNode {
      4. *     int val;
      5. *     ListNode next;
      6. *     ListNode(int x) { val = x; }
      7. * }
      8. */
      9. class Solution {
      10. public ListNode addTwoNumbers(ListNode h1, ListNode h2) {
      11.    Stack<ListNode> s1 = new Stack();
      12.    Stack<ListNode> s2 = new Stack();
      13.    ListNode l1 = h1;
      14.    ListNode l2 = h2;
      15.    while(l1!=null) {
      16.        s1.push(l1);
      17.        l1=l1.next;
      18.    }
      19.    while(l2!=null){
      20.        s2.push(l2);
      21.        l2 = l2.next;
      22.    }
      23.    ListNode dummy = new ListNode();
      24.    boolean f = false;
      25.    while(!s1.isEmpty() || !s2.isEmpty() || f) {
      26.        int v1 = s1.isEmpty()?0:s1.pop().val;
      27.        int v2 = s2.isEmpty()?0:s2.pop().val;
      28.        int v = v1+v2;
      29.        if(f){
      30.            v+=1;
      31.        }
      32.        if(v>=10) {
      33.            v-=10;
      34.            f = true;
      35.        } else {
      36.            f = false;
      37.        }
      38.        ListNode p = new ListNode(v);
      39.        p.next = dummy.next;
      40.        dummy.next = p;
      41.    }
      42.    return dummy.next;
      43. }
      44. }

      55. 跳跃游戏

      image.png

  • 遍历数组，判断当前节点可以到达的最远距离，更新最远距离

    1. class Solution {
    2.   public boolean canJump(int[] nums) {
    3.       if(nums.length==1)
    4.           return true;
    5.       int last = nums[0]; // 当前可以到达的最远距离
    6.       if(last>=nums.length-1)
    7.           return true;
    8.       for(int i = 1; i < nums.length;i++) {
    9.           if(last<i) { // 当前距离不可达
    10.               return false;
    11.           }
    12.           last = Math.max(i+nums[i],last);
    13.           if(last>=nums.length-1)
    14.               return true;
    15.       }
    16.       return false;
    17.   }
    18. }

    45. 跳跃游戏 II

    image.png
    我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

    1. class Solution {
    2.   public int jump(int[] nums) {
    3.       int end = 0; // 上一次跳跃最后可以达到的位置
    4.       int maxPos = 0; // 已经探索到的最大的位置
    5.       int len = nums.length;
    6.       if(len==1)
    7.           return 0;
    8.       int step = 0;
    10.       for(int i = 0 ; i < len;i++) {
    11.           maxPos = Math.max(maxPos,i+nums[i]);
    12.           if(maxPos>=len-1) { // 从当前节点跳跃可以跳到最后位置及其以后的位置
    13.               return step+1;
    14.           }
    15.           if(i==end) { // 已经到达了上一次探索的极限，需要加一步了
    16.               step++;
    17.               end = maxPos; // 这一步可以探索到的极限
    18.           }
    19.       }
    20.       return step;
    21.   }
    22. }

    128. 最长连续序列

    image.png

  • 去重

  • 遍历每个元素，找每个开头

    1. class Solution {
    2.   public int longestConsecutive(int[] nums) {
    3.       Set<Integer> set = new HashSet();
    4.       for(int i:nums){ // 去重
    5.           set.add(i);
    6.       }
    8.       int longest = 0;
    9.       for(int now:set) {
    10.           // 如果没有比当前数字小一的数字，那它就是开头的数字
    11.           if(!set.contains(now-1)) {
    12.               int nowLong = 1;
    13.               // 一次找比他大的数字
    14.               while(set.contains(now+1)) {
    15.                   now++;
    16.                   nowLong++;
    17.               }
    18.               longest = Math.max(longest,nowLong);
    19.           }
    20.       }
    21.       return longest;
    22.   }
    23. }

347. 前 K 个高频元素

image.png

  • 用hash记录每个元素出现的次数
  • 使用一个k大小的小顶堆

  • 遍历hash，如果大于堆顶，弹出，加入当前元素

    1. class Solution {
    2.   public int[] topKFrequent(int[] nums, int k) {
    3.       Map<Integer,Integer> map = new HashMap();
    4.       for(int num:nums){
    5.           map.put(num,map.getOrDefault(num,0)+1);
    6.       }
    7.       PriorityQueue<int[]> set = new PriorityQueue(new Comparator<int[]>(){
    8.           public int compare(int[] m,int[] n) {
    9.               return m[1]-n[1];
    10.           }
    11.       });
    12.       for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    13.           if(set.size()<k) {
    14.               set.add(new int[]{entry.getKey(),entry.getValue()});
    15.           } else {
    16.               if(set.peek()[1]<entry.getValue()) {
    17.                   set.poll();
    18.                   set.add(new int[]{entry.getKey(),entry.getValue()});
    19.               }
    20.           }
    21.       }
    22.       int[] ret = new int[k];
    23.       for (int i = 0; i < k; ++i) {
    24.           ret[i] = set.poll()[0];
    25.       }
    26.       return ret;
    28.   }
    29. }