![]()
情人节是啥玩意, 真不熟.
Contains Duplicate
https://neetcode.io/problems/duplicate-integer/question?list=neetcode150
要求时间复杂度 O (n) 所以不能用 map, 于是用 unordered_set.
unordered_set: 基于哈希表实现, 查找, 插入, 删除都是 O (1) 复杂度.
set: 基于红黑树实现, 有序, 复杂度 O (logn). 可以顺序遍历或范围查找.
class Solution {
public:
bool hasDuplicate(vector<int>& nums) {
unordered_set<int> flag;
for(int i = 0; i < nums.size(); ++i){
flag.insert(nums[i]);
}
for(int elem : flag){
cout << elem << " ";
}
if(flag.size() < nums.size())
return true;
else
return false;
}
};
|
Valid Anagram
https://neetcode.io/problems/is-anagram/question?list=neetcode150
没啥好说的.
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size())
return false;
int a[30] = {0}, b[30] = {0};
for(int i = 0; i < s.size(); ++i){
++a[(int)(s[i] - 'a')];
++b[(int)(t[i] - 'a')];
}
for(int i = 0; i < 26; ++i)
if(a[i] != b[i])
return false;
return true;
}
};
|
Two Sum
https://neetcode.io/problems/two-integer-sum/question?list=neetcode150
同样没啥好说的.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_set<int> diff;
vector<int> ans(2, 0);
for(int i = 0; i < nums.size(); ++i){
diff.insert(target - nums[i]);
}
for(int i = 0; i < nums.size(); ++i){
if(diff.find(nums[i]) != diff.end()){
for(int j = nums.size() - 1; j > i; --j){
if(nums[j] == target - nums[i]){
ans[0] = i;
ans[1] = j;
return ans;
}
}
}
}
return ans;
}
};
|
Group Anagrams
https://neetcode.io/problems/anagram-groups/question?list=neetcode150
unordered_map 平均时间复杂度也是 O (1).
用 string 作 key 可以避免手写哈希函数的痛苦.
class Solution {
private:
struct Array {
int data[30]={0};
};
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
Array count;
unordered_map<string, vector<string>> mp;
for(int i = 0; i < strs.size(); ++i) {
for(int j = 0; j < strs[i].size(); ++j) {
++count.data[(int)(strs[i][j] - 'a')];
}
string str = "";
for(int j = 0; j < 26; ++j) {
str += to_string(count.data[j]) + '?';
count.data[j] = 0;
}
mp[str].push_back(strs[i]);
}
for(auto it = mp.begin(); it != mp.end(); ++it) {
ans.push_back(it->second);
}
return ans;
}
};
|
Top K Frequent Elements
正常情况可以用最小堆, 复杂度 O (nlogk), 但是题目要求 O (n), 所以可以使用空间复杂度更高的桶排序方法.
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<vector<int>> bucket(nums.size()+1);
vector<int> count(2025, 0);
for(int i = 0; i < nums.size(); ++i) {
nums[i] += 1001;
++count[nums[i]];
}
int maxcount = 0;
for(int i = 0; i < count.size(); ++i) {
if(count[i] == 0) continue;
bucket[count[i]].push_back(i - 1001);
}
int temp = k;
vector<int> ans;
for(int i = bucket.size() - 1; i >= 0; --i) {
if(bucket[i].size() <= 0) continue;
for(auto it = bucket[i].begin(); it != bucket[i].end(); ++it) {
if(temp <= 0) return ans;
ans.push_back(*it);
temp --;
}
if(temp <= 0) return ans;
}
return ans;
}
};
|
Encode and Decode Strings
https://neetcode.io/problems/string-encode-and-decode/question?list=neetcode150
主要内容是怎么在字符串列表里搞个分隔符. 计网好像学过好几个解决方案但是我忘光了, 反正没有长度要求就用了最唐的把字符串长度写出来的方法.
class Solution {
public:
string encode(vector<string>& strs) {
string ans = "";
for(int i = 0; i < strs.size(); ++i) {
ans += "@" + to_string(strs[i].size()) + "@" + strs[i];
}
cout<<ans;
return ans;
}
vector<string> decode(string s) {
vector<string> ans;
for(int i = 0; i < s.size(); ++i) {
int len = 0;
if(s[i] == '@') {
len = 0;
++i;
while(s[i] != '@') {
len = len * 10 + (int)(s[i] - '0');
++i;
}
string temp = "";
for(int j = 0; j < len; ++j) {
temp += s[++i];
}
ans.push_back(temp);
}
}
return ans;
}
};
|
Products of Array Except Self
https://neetcode.io/problems/products-of-array-discluding-self/question?list=neetcode150
好吧我才知道 product 还有乘积的意思.
题目要求不许用除法, 所以用类似前缀和的方法, 算左边所有元素的和 × 右边所有元素的和.
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> left, right(nums.size() + 5);
int temp = 1;
for(int i = 0; i < nums.size(); ++i) {
temp *= nums[i];
left.push_back(temp);
}
temp = 1;
for(int i = nums.size() - 1; i >= 0; --i) {
temp *= nums[i];
right[i] = temp;
}
vector<int> ans;
ans.push_back(right[1]);
for(int i = 1; i < nums.size() - 1; ++i) {
ans.push_back((int)(left[i-1] * right[i+1]));
}
ans.push_back(left[nums.size() - 2]);
return ans;
}
};
|
想优化空间复杂度的话其实 right 和 left 两个数组都是不必要的, 不过写出来容易理解一点.
Valid Sudoku
https://neetcode.io/problems/valid-sudoku/question?list=neetcode150
没看懂这题是何意味, 查一遍就完事了, 理论时间复杂度 O (1).
想优化可以用位运算, 但是我都 O (1) 了我管你这那的.
#include<cstring>
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool flag[10];
int num;
for(int i = 0; i < 9; ++i) {
memset(flag, 0, sizeof(flag));
for(int j = 0; j < 9; ++j) {
if(board[i][j] != '.') {
num = (int)(board[i][j] - '0');
if(flag[num])
return false;
flag[num] = true;
}
}
}
for(int i = 0; i < 9; ++i) {
memset(flag, 0, sizeof(flag));
for(int j = 0; j < 9; ++j) {
if(board[j][i] != '.') {
num = (int)(board[j][i] - '0');
if(flag[num])
return false;
flag[num] = true;
}
}
}
for(int i = 0; i < 3; ++i) {
for(int m = 0; m < 3; ++m) {
memset(flag, 0, sizeof(flag));
for(int j = 0; j < 3; ++j) {
for(int k = 0; k < 3; ++k) {
if(board[j + 3 * i][k + 3 * m] != '.') {
num = (int)(board[j + 3 * i][k + 3 * m] - '0');
if(flag[num])
return false;
flag[num] = true;
}
}
}
}
}
return true;
}
};
|
Longest Consecutive Sequence
https://neetcode.io/problems/longest-consecutive-sequence/question?list=neetcode150
本来以为是类似最长上升子序列的题, 结果闹了半天根本不关心数字出现顺序, 只要出现了就可以, unordered_map 解决.
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, bool> mp;
for(int i = 0; i < nums.size(); ++i) {
mp[nums[i]] = true;
}
int ans = 0;
for(int i = 0; i < nums.size(); ++i) {
if(mp[nums[i] - 1] != true) {
int t = 0;
for(int j = nums[i];; ++j) {
if(mp[j]) ++t;
else break;
}
ans = (ans > t)?ans:t;
}
}
return ans;
}
};
|
第一小节做完了, 猜猜我能坚持多久.
