每日刷题记录 (九)

转x33g5p2x  于2022-06-30 转载在 其他  
字(4.3k)|赞(0)|评价(0)|浏览(490)

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

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

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

解题思路:

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

  • 创建一个大小为k的小根堆

  • 然后往堆里放元素,

  • 当堆内元素小于k的时候, 直接放

  • 当堆内元素大于等于k的时候, 比较,

  • 如果新的元素大于堆顶元素, 那么就直接出堆, 然后再将该元素入堆

  • 最后堆内元素就是需要的元素.

代码实现:

  1. class Solution {
  2.     public int[] topKFrequent(int[] nums, int k) {
  3.         PriorityQueue<int[]> pq = new PriorityQueue<>(k,(o1,o2)->(o1[1]-o2[1]));
  4.         HashMap<Integer,Integer> map = new HashMap<>();
  5.         for (int num : nums) {
  6.             map.put(num,map.getOrDefault(num,0)+1);
  7.         }
  8.         for(int key : map.keySet()){
  9.             if(pq.size() < k) {
  10.                 pq.offer(new int[]{key,map.get(key)});
  11.             }else{
  12.                 if(map.get(key) > pq.peek()[1]) {
  13.                     pq.poll();
  14.                     pq.offer(new int[]{key,map.get(key)});
  15.                 }
  16.             }
  17.         }
  18.         int[] ans = new int[pq.size()];
  19.         int index = 0;
  20.         while (!pq.isEmpty()){
  21.             ans[index++] = pq.poll()[0];
  22.         }
  23.         return ans;
  24.     }
  25. }

第二题: 剑指 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个数组的内容存入大根堆中.
  • 遍历结束, 堆中的元素就是所需的内容.

代码实现:

  1. class Solution {
  2.     public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
  3.                 PriorityQueue<int[]> pq = new PriorityQueue<>(k,(o1,o2)->(o2[0]+o2[1]-o1[0]-o1[1]));
  4.         for(int left : nums1) {
  5.             for(int right : nums2) {
  6.                 if (pq.size() < k) {
  7.                     pq.offer(new int[]{left,right});
  8.                 }else{
  9.                     if (left + right < pq.peek()[0]+pq.peek()[1]) {
  10.                         pq.poll();
  11.                         pq.offer(new int[]{left,right});
  12.                     }
  13.                 }
  14.             }
  15.         }
  16.         List<List<Integer>> list = new ArrayList<>();
  17.         int size = pq.size();
  18.         while (size-- != 0) {
  19.             List<Integer> ret = new ArrayList<>();
  20.             ret.add(pq.peek()[0]);
  21.             ret.add(pq.peek()[1]);
  22.             pq.poll();
  23.             list.add(ret);
  24.         }
  25.         return list;
  26.     }
  27. }

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

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

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

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

解题思路:

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

代码实现:

  1. class Solution {
  2.     public String replaceWords(List<String> dictionary, String sentence) {
  3.         String[] str = sentence.split(" ");
  4.         // 堆dictionary进行排序, 让长度短的排前面例如: cat catt
  5.         Collections.sort(dictionary);
  6.         StringBuilder sb = new StringBuilder();
  7.         for(int i = 0; i < str.length; i++) {
  8.         	// 这里堆dictionary进行遍历
  9.             for(String s : dictionary){
  10.             	// 如果当前是前缀, 那么替换之后就跳出这个小循环
  11.                 if(str[i].startsWith(s)){
  12.                     str[i] = s;
  13.                     break;
  14.                 }
  15.             }
  16.             // 到这里进行拼接, 注意拼接空格.
  17.             sb.append(str[i]);
  18.             if(i!=str.length-1) sb.append(" ");
  19.         }
  20.         return sb.toString();
  21.     }
  22. }

第四题: 剑指 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, 就返回这个坐标.

代码实现:

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.         int left = 0;
  4.         int right = nums.length-1;
  5.         while(left <= right) {
  6.             int mid = left + (right-left) / 2;
  7.             if(nums[mid] > target) {
  8.                 right = mid - 1;
  9.             }else if(nums[mid] < target) {
  10.                 left = mid + 1;
  11.             }else {
  12.                 return mid;
  13.             }
  14.         }
  15.         return left;
  16.     }
  17. }

第五题: 剑指 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.

代码实现:

  1. class Solution {
  2.     public int peakIndexInMountainArray(int[] arr) {
  3.         int left = 1;
  4.         int right = arr.length-2;
  5.         while(left <= right) {
  6.             int mid = left + (right - left) / 2;
  7.             if (arr[mid] > arr[mid-1]) {
  8.                 left = mid + 1;
  9.             } else {
  10.                 right = mid - 1;
  11.             }
  12.         }
  13.         return right;
  14.     }
  15. }

第六题: 剑指 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. 因为此时左边有不成对的.

代码实现:

  1. class Solution {
  2.     public int singleNonDuplicate(int[] nums) {
  3.         int left = 0;
  4.         int right = nums.length-1;
  5.         while(left < right) {
  6.             int mid = left + (right - left) / 2;
  7.             if(mid % 2 == 0) {
  8.                 if (nums[mid] == nums[mid+1])
  9.                     left = mid + 1;
  10.                 else 
  11.                     right = mid;
  12.             }else {
  13.                 if (nums[mid] == nums[mid - 1])
  14.                     left = mid + 1;
  15.                 else
  16.                     right = mid;
  17.             }
  18.         }
  19.         return nums[left];
  20.     }
  21. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://wangzhi430.blog.csdn.net/article/details/125533586

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构leetcode算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com