每日刷题记录 (九)
文章目录
第一题: 剑指 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 catt
Collections.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] > 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;
else
right = mid;
}
}
return nums[left];
}
}