LeetCode Daily Question 5

Mar 9th 2022

3 月 9 日 每日一题

题目：215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

1
2
eg: Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

思路

这道题使用了 quickSort 的写法，通过 getPartition 找到第 n/2 大的位置，然后进行 while 循环直到找到 kth largest return。
尝试了另一种 Partition 的写法，个人感觉还是 swap 写法更易于理解。
本题应该还有其他解法，之后可能会做扩展。
因为明天 370 考试，故请假一天。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0;
        int right = nums.size() - 1;
        int target = nums.size() - k; //kth largest
        while(left < right){
            int mid = findPartition(nums, left, right);
            if(mid == target)
                return nums[mid];
            else if(mid < target)
                left = mid + 1;
            else
                right =  mid - 1;
        }
        return nums[left];//garbage value
    }

    int findPartition(vector<int>& nums, int left, int right){
        int pivot = nums[left];
        while(left < right){
            while(left < right && nums[right] >= pivot)
                right--;
            nums[left] = nums[right];
            while(left < right && nums[left] <= pivot)
                left++;
            nums[right] = nums[left];
            }
        nums[left] = pivot;
        return left;
    }
};
Read More
, ,

LeetCode Daily Question 4

Mar 8th 2022

3 月 8 日 每日一题

题目：217. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

1
2
eg: Input: nums = [1,2,3,1]
Output: true

思路

首先对 vector 进行 sort，之后遍历判断是否和上一个元素相同。时间复杂度 O(nlogn)空间复杂度取决于 sort。
有一个更简单的写法是直接用 set 判断 size。

1
return set<int>(nums.begin(), nums.end()).size() < nums.size();

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        int temp = 0;
        for(size_t i = 0; i < nums.size(); i++){
            if(i == 0){
                temp = nums[0];
            }
            else{
                if(nums[i] == temp)
                    return true;
                else
                    temp = nums[i];
            }
        }
        return false;
    }
};
Read More
,

LeetCode Daily Question 3

Mar 7th 2022

3 月 7 日 每日一题

题目：15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

1
2
eg: Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

思路

这道题的思路很简单，先 sort，再设 pivot，之后用双指针找到两数之和等于-pivot。如果遇到合适的 triplet，需要考虑之后的元素是否和当前的相等以避免重复。最后使用一个 while 来避免 pivot 重复。

1
2
while(i + 1 < nums.size() && nums[i + 1] == nums[i])
    i++;

但是因为 edge case 和一些很蠢的错折磨了很久，写到后面属实有点气急败坏…
几个教训：

  1. a && b 的计算
    先看 a，若 a 是假，则结束，整个表达式的值为假。
    若 a 是真，再看 b，如 b 为假，整个表达式为假。
    若 b 为真，则整个表达式为真。
    所以最后的 while 判断条件如果反过来就会导致[0]这个 case 越界。
  2. 完全没有必要使用指针，两个 int 即可
  3. 关于并列的 if 和 if else 并列区别很大，需要注意。
  4. 不建议使用 for(int i = 1…)这种从 1 开始遍历的写法，很容易想错导致越界访问。并且还是那句话，写之前就想清楚 edge case，最好在纸上列一下。
  5. 最后，气急败坏的状态下建议先做其他事，调整下大脑。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
    vector<vector<int>> threeSum(vector<int>& nums) {
    std::sort(nums.begin(),nums.end());
    vector<vector<int>> res;
    for(int i = 0; i < nums.size(); i++){
        int left = i + 1;
        int right = nums.size() - 1;
        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum < -nums[i])
                left++;
            else if(sum > -nums[i])
                right--;
            else{ //else可以避免2 -1 -1
                vector<int> temp = {nums[i], nums[left], nums[right]};
                res.push_back(temp);
                while(left < right && nums[left] == temp[1])
                    left++;
                while(left < right && nums[right] == temp[2])
                    right--;
            }
        }
        while(i + 1 < nums.size() && nums[i + 1] == nums[i])
            i++;
    }
    return res;
}
Read More
,

LeetCode Daily Question 2

Mar 6th 2022

3 月 6 日 每日一题

题目：49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

eg: Input: Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

思路

使用 count sort，以避免对每一个 str 进行 sort。首先建立一个对于 26 个字母的 count[26]，记录每个字母出现的次数，并且返回一个形式为 a2b2(abab)的 key。使用一个 unorder map 储存 <key,vector>，并且在最后把 vector 导入新建的 vector<vector> res。
时间复杂度为 O(mn) 空间复杂度为 O(26m)，m 为 str 数目，n 为单个 str 长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for(auto str: strs){
        groups[getKey(str)].push_back(str);
        }
    vector<vector<string>> res;
    for(auto ele: groups){
        res.push_back(ele.second);
    }
    return res;
}

string getKey(string str){
    int count[26] = {0};
    for(auto s:str){
        count[s-'a']++;
    }
    string key;
    for(int i = 0; i < 26; i++){
        if(count[i] > 0)
        key += char(i + 'a') + to_string(count[i]);
    }
    return key;
}
Read More
, ,

LeetCode Daily Question 1

Mar 5th 2022

3 月 5 日 每日一题

题目：56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

eg: Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6]overlaps, merge them into [1,6].

思路

首先对 interval 进行排序,之后遍历 interval，如果该 interval 是第一个，或者当前的 merged 的尾部和当前 interval 没有相交，直接 push。反之对 merged 尾部的【1】进行修改。注意 A or B 的反为（A 反&B 反 ）
时间复杂度为 O(nlogn) 空间复杂度为 O(n)(sort)

代码

1
2
3
4
5
6
7
8
9
10
11
vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b){return a[0] < b[0];});
        vector<vector<int>> merged;
        for(auto interval: intervals){
            if(merged.empty() || merged.back()[1] < interval[0])
                merged.push_back(interval);
            else
                merged.back()[1] = max(interval[1],merged.back()[1]);
        }
        return merged;
    }
Read More
,

Hello World

Mar 2nd 2022

Hello World

2022/03/02
地点“听会儿歌”

博客搭建于 22 年 2 月 3 日，套用了名为“prince”的模板，计划用来记录之后的每日一题和课上做的 project，也会记录一些日常生活。
在上 485 之前大概不会给博客加新功能。

就这样。

Read More

Hello World

Mar 2nd 2022

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Read More
Previous