第一题: 剑指 Offer II 060. 出现频率最高的 k 个数字

LeetCode: 剑指 Offer II 060. 出现频率最高的 k 个数字

描述:
给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

解题思路:

这里使用优先级队列的思路,

• 创建一个大小为k的小根堆
• 然后往堆里放元素,
  • 当堆内元素小于k的时候, 直接放
  • 当堆内元素大于等于k的时候, 比较,
    • 如果新的元素大于堆顶元素, 那么就直接出堆, 然后再将该元素入堆
• 最后堆内元素就是需要的元素.

代码实现:

class Solution {public int[] topKFrequent(int[] nums, int k) {PriorityQueue<int[]> pq = new PriorityQueue<>(k,(o1,o2)->(o1[1]-o2[1]));HashMap<Integer,Integer> map = new HashMap<>();for (int num : nums) {map.put(num,map.getOrDefault(num,0)+1);}for(int key : map.keySet()){if(pq.size() < k) {pq.offer(new int[]{key,map.get(key)});}else{if(map.get(key) > pq.peek()[1]) {pq.poll();pq.offer(new int[]{key,map.get(key)});}}}int[] ans = new int[pq.size()];int index = 0;while (!pq.isEmpty()){ans[index++] = pq.poll()[0];}return ans;}}

第二题: 剑指 Offer II 061. 和最小的 k 个数对

LeetCode: 剑指 Offer II 061. 和最小的 k 个数对

描述:
给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。

解题思路:

• 创建一个大小为k的 大根堆
• 循环的将2个数组的内容存入大根堆中.
• 遍历结束, 堆中的元素就是所需的内容.

代码实现:

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {PriorityQueue<int[]> pq = new PriorityQueue<>(k,(o1,o2)->(o2[0]+o2[1]-o1[0]-o1[1]));for(int left : nums1) {for(int right : nums2) {if (pq.size() < k) {pq.offer(new int[]{left,right});}else{if (left + right < pq.peek()[0]+pq.peek()[1]) {pq.poll();pq.offer(new int[]{left,right});}}}}List<List<Integer>> list = new ArrayList<>();int size = pq.size();while (size-- != 0) {List<Integer> ret = new ArrayList<>();ret.add(pq.peek()[0]);ret.add(pq.peek()[1]);pq.poll();list.add(ret);}return list;}}

第三题: 剑指 Offer II 063. 替换单词

LeetCode: 剑指 Offer II 063. 替换单词
描述:
在英语中，有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

需要输出替换之后的句子。

解题思路:

• 将sentence变成字符串数组,
• 如果当前前缀中有dictionary中的字符串. 就替换掉.
• 替换后进行字符串的拼接.
• 这里需要注意的是 如果继承词有许多可以形成它的词根，则用最短的词根替换它。
• 解决方法让dictionary数组进行排序.

代码实现:

class Solution {public String replaceWords(List<String> dictionary, String sentence) {String[] str = sentence.split(" ");// 堆dictionary进行排序, 让长度短的排前面例如: cat cattCollections.sort(dictionary);StringBuilder sb = new StringBuilder();for(int i = 0; i < str.length; i++) {// 这里堆dictionary进行遍历for(String s : dictionary){// 如果当前是前缀, 那么替换之后就跳出这个小循环if(str[i].startsWith(s)){str[i] = s;break;}}// 到这里进行拼接, 注意拼接空格.sb.append(str[i]);if(i!=str.length-1) sb.append(" ");}return sb.toString();}}

第四题: 剑指 Offer II 068. 查找插入位置

LeetCode: 剑指 Offer II 068. 查找插入位置

描述:

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

解题思路:

• 这里用二分查找的方法
• 例如 nums = [1,3,5,6], target = 5
• 第一次二分, 就分为两部分, [1, 3] [ 5, 6] 这里3小于target, 就取右边.
• 第二次二分, 分为 [5] [6], 这里5等于target, 就返回这个坐标.

代码实现:

class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length-1;while(left <= right) {int mid = left + (right-left) / 2;if(nums[mid] > target) {right = mid - 1;}else if(nums[mid] < target) {left = mid + 1;}else {return mid;}}return left;}}

第五题: 剑指 Offer II 069. 山峰数组的顶部

LeetCode: 剑指 Offer II 069. 山峰数组的顶部

描述:
符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：

• arr.length >= 3
• 存在 i（0 < i < arr.length - 1）使得：
  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
。

解题思路:

• 这里使用二分法,
• 将数组划分成, 0~left 单调递增. right~len-1 单独递减
• 只要mid 比 mid-1大, 就让left = mid+1
• 只要mid 比 mid-1小, 就让right = mid-1
• 初始的时候, 让left = 1, right = len-1.

代码实现:

class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 1;int right = arr.length-2;while(left <= right) {int mid = left + (right - left) / 2;if (arr[mid] > arr[mid-1]) {left = mid + 1;} else {right = mid - 1;}}return right;}}

第六题: 剑指 Offer II 070. 排序数组中只出现一次的数字

LeetCode: 剑指 Offer II 070. 排序数组中只出现一次的数字

描述:
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

解题思路:

• 二分法. 按照道理, 两个出现的时候, 坐标是偶数 然后奇数,例如 [1,1] , 这里的坐标就是 0 和 1,
• 所以如果 mid 为奇数的时候, 比较 nums[mid] 和 nums[mid-1]的值,
  • 如果当前值相等. 就让left = mid+1. 因为此时左边都是成对的,
  • 如果当前值不相等. 就让right = mid -1. 因为此时左边有不成对的.
• 如果 mid 为偶数的时候, 比较 nums[mid] 和 nums[mid+1] 的值.
  • 如果当前值相等. 就让left = mid+1. 因为此时左边都是成对的,
  • 如果当前值不相等. 就让right = mid -1. 因为此时左边有不成对的.

代码实现:

class Solution {public int singleNonDuplicate(int[] nums) {int left = 0;int right = nums.length-1;while(left < right) {int mid = left + (right - left) / 2;if(mid % 2 == 0) {if (nums[mid] == nums[mid+1])left = mid + 1;else right = mid;}else {if (nums[mid] == nums[mid - 1])left = mid + 1;elseright = mid;}}return nums[left];}}