Happy丶

966

notyour_young_
Zach_Tang
hk18
yxc
rp1213
xfrn

## 解题思路

### KMP

class Solution {
public:
int strStr(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s, p = ' ' + p;

vector<int> next(m + 1);

for(int i = 2, j = 0; i <= m; i ++ ) {
while(j && p[i] != p[j + 1]) j = next[j];
if(p[i] == p[j + 1]) j ++;
next[i] = j;
}

for (int i = 1, j = 0; i <= n; i ++) {
while(j && s[i] != p[j + 1]) j = next[j];
if(s[i] == p[j + 1]) j ++;
if(j == m) return i - m;
}
return -1;
}
};


class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for(int fast = 0; fast < nums.size(); fast ++){
if(nums[fast] != val) nums[slow ++] = nums[fast];
}
return slow;
}
};


### 时间复杂度 $O(n)$

#### 连标题一定画图！！！！

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy = new ListNode(-1);

for(auto p = dummy;;){
auto q = p;
for(int i = 0; i < k && q; i ++) q = q->next;
if(!q) break;

auto a = p->next, b = a->next;
for(int i = 0; i < k - 1; i ++) {
auto c = b->next;
b->next = a;
a = b, b = c;
}
auto c = p->next;
p->next = a, c->next = b;
p = c;
}
return dummy->next;
}
};


## 解题思路

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:

struct Cmp{
bool operator() (ListNode* a, ListNode* b){
return a->val > b->val;
}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, Cmp>  heap;
auto dummy = new ListNode(-1), tail = dummy;
for(auto l : lists) if(l) heap.push(l);

while(heap.size()){
auto t = heap.top();
heap.pop();

tail->next = t;
tail = tail->next;

if(t->next) heap.push(t->next);
}
return dummy->next;
}
};


## 解题思路

class Solution {
public:
string leftRotateString(string str, int n) {
int len = str.size();
reverse(str.begin(), str.end());
reverse(str.begin(), str.end() - n);
reverse(str.begin() + len - n, str.end());
return str;
}
};


class Solution {
public:
string leftRotateString(string str, int n) {
int len = str.size();
string s = str + str;
return s.substr(n,len);
}
};


## 解题思路

### hash表

class Solution {
public:
vector<int> findNumbersWithSum(vector<int>& nums, int target) {
unordered_set<int> hash;
for(auto x : nums){
if(hash.count(target - x)) return vector<int>{target - x, x};
hash.insert(x);
}
return vector<int>();
}
};


## 解题思路

### 不符合题意的hash表做法(很傻)

class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums) {
unordered_map<int, int> hash;
for(auto num : nums){
hash[num] ++;
}
for(auto num : nums){
if(hash[num] == 1)
return num;
}
return -1;
}
};


## 解题思路

### 位运算

1. 所有数异或一遍，剩下的就是两个不相同的数的异或值 x ^ y
2. x 和 y 肯定在某一位(第k位)上一个为0，一个为1
3. 找出所有第k位为1的数，剩下的就是所有第k位为0的数
4. 分别对这两个集合做异或运算，集合一就剩下x，集合二就剩y。
5. 返回x和y

class Solution {
public:
vector<int> findNumsAppearOnce(vector<int>& nums) {
int sum = 0;
for(auto x : nums) sum ^= x; // 将所有数都异或一遍 sum = x ^ y。想同的数异或为0

int k = 0;
while(!(sum >> k & 1)) k ++; // 找出 x 和 y 在第 k 位不同（此处是求第k位为1的）

int first = 0;
for(auto x : nums)
if(x >> k & 1) // 求出所有第k位为1的数
first ^= x; // 运算完后first就是两个不同的数之一

return vector<int>({first, sum ^ first});
}
};


### hash表

#### 时间复杂度 O(n)

hash表的存取是O(1)，遍历了两遍数组为2n，所以时间复杂度为O(n);

class Solution {
public:
vector<int> findNumsAppearOnce(vector<int>& nums) {
vector<int> ans;
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i ++){
hash[nums[i]]++;
}
for(auto x : nums){
if(hash[x] == 1) ans.push_back(x);
}
return ans;
}
};


/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool ans = true;
bool isBalanced(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* root){
if(!root) return 0;
int left = dfs(root->left), right = dfs(root->right);
if(abs(left - right) > 1) ans = false;
return max(left, right) + 1;
}

};


/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int treeDepth(TreeNode* root) {
if (!root) return 0;
return max(treeDepth(root->left),treeDepth(root->right)) + 1;
}
};