方法论

看数据范围，判断考察的算法

image.png
根据算法和模板，分析题意，写代码。

剑指offer

13. 找出数组中重复的数字

题目详情

https://www.acwing.com/problem/content/14/

分析

利用题目条件，一个萝卜一个坑的思想（魔方盲拧编码思想）

  1. class Solution {
  2.     public int duplicateInArray(int[] nums) {
  3.         int n = nums.length;
  4.         // 题目要求
  5.         for (int num : nums) {
  6.             if (num < 0 || num > n - 1) return -1;
  7.         }
  8.         for (int i = 0; i < n; ++i) {
  9.             // 一个萝卜一个坑
  10.             while (nums[i] != i) {
  11.                 // 自己坑错了，但对的坑里有对的萝卜了，说明这俩萝卜相等
  12.                 if (nums[i] == nums[nums[i]]) return nums[i];
  13.                 // 将i位置的萝卜放到正确的坑
  14.                 swap(nums, i, nums[i]);
  15.             } 
  16.         }
  17.         return -1;
  18.     }
  20.     private void swap(int[] nums, int a, int b) {
  21.         int temp = nums[a];
  22.         nums[a] = nums[b];
  23.         nums[b] = temp;
  24.     }
  25. }

14. 不修改数组找出重复的数字（二分查找）

题目详情

https://www.acwing.com/problem/content/15/

分析

本题涉及的二分查找算是一种变形，不是查找一个数字，查到了就return，而是二分查找取值区间，所以需要实现[left, mid], [mid+1, right]这样的全覆盖，而且当left==right的时候就退出循环，所以while (left < right)。就本体来讲，是找到一个区间，里面取值范围跨度<区间内数字个数

  1. class Solution {
  2.     public int duplicateInArray(int[] nums) {
  3.         // 抽屉原理，至少有一个重复数字
  4.         // 用递归思想来做，把取值区间分成两部分，至少有一个区间内有重复数字
  5.         int left = 1, right = nums.length - 1;
  6.         while (left < right) { // 注意！
  7.             int mid = left + (right - left) / 2;
  8.             int sum = 0; // 有多少数字在取值[left, mid]区间内
  9.             for (int num: nums) {
  10.                 if (num >= left && num <= mid) sum++;
  11.             }
  12.             if (sum > mid - left + 1) right = mid; // 注意！在取值区间[left, mid]里继续搜索
  13.             else left = mid + 1; // [mid+1, right]里继续搜索
  14.         }
  15.         return left; // right == left
  16.     }
  17. }

二分查找模板

  1. int bsearch_1(int l, int r)
  2. {
  3.     while (l < r)
  4.     {
  5.         int mid = l + r >> 1;
  6.         if (check(mid)) r = mid;
  7.         else l = mid + 1;
  8.     }
  9.     return l;
  10. }

15. 二维数组中的查找（略）

16. 替换空格（略）

17. 从尾到头打印链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public int[] printListReversingly(ListNode head) {
  11.         Deque<Integer> stack = new ArrayDeque<>();
  12.         ListNode temp = head;
  13.         while (temp != null) {
  14.             stack.addFirst(temp.val);
  15.             temp = temp.next;
  16.         }
  17.         int[] result = new int[stack.size()];
  18.         int i = 0;
  19.         while (!stack.isEmpty()) result[i++] = stack.removeFirst();
  20.         return result;
  21.     }
  22. }

Java的Stack类已经不再使用，而是使用Deque实现。

Deque使用小结：
将元素添加到队尾或队首：addLast()/offerLast()/addFirst()/offerFirst()
从队首／队尾获取元素并删除：removeFirst()/pollFirst()/removeLast()/pollLast()
从队首／队尾获取元素但不删除：getFirst()/peekFirst()/getLast()/peekLast()