每日刷题记录 (九)

第一题: 剑指 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];
    }
}