Algo_Easy_MAP
學習算法
Vector
Leetcode 56
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
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>> megred;
vector<int> prev = intervals[0];
for (int i = 1; i < intervals.size(); i++)
{
vector<int> interval = intervals[i];
if (interval[0] <= prev[1])
{
prev[1] = max(prev[1], interval[1]);
}
else
{
megred.push_back(prev);
prev = interval;
}
}
megred.push_back(prev);
return megred;
}
};Leetcode 238
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<int> productExceptSelf(vector<int> &nums)
{
int n = nums.size();
vector<int> pre(n);
vector<int> suf(n);
pre[0] = 1;
suf[n - 1] = 1;
for (int i = 1; i < n; i++)
{
pre[i] = pre[i - 1] * nums[i - 1];
}
for (int i = n - 2; i >= 0; i--)
{
suf[i] = suf[i + 1] * nums[i + 1];
}
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
ans[i] = pre[i] * suf[i];
}
return ans;
}
};Leetcode 54
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<int> result;
int n, m = 0;
vector<int> spiralOrder(vector<vector<int>> &matrix)
{
n = matrix.size();
m = matrix[0].size();
int top = 0, bottom = n - 1;
int left = 0, right = m - 1;
vector<int> v;
while (top <= bottom && left <= right)
{
for (int i = left; i <= right; i++)
{
v.push_back(matrix[top][i]);
}
top++;
for (int i = top; i <= bottom; i++)
{
v.push_back(matrix[i][right]);
}
right--;
if (top <= bottom)
{
for (int i = right; i >= left; i--)
{
v.push_back(matrix[bottom][i]);
}
bottom--;
}
if (left <= right)
{
for (int i = bottom; i >= top; i--)
{
v.push_back(matrix[i][left]);
}
left++;
}
}
return v;
}
};
Leetcode 48
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
void rotate(vector<vector<int>> &matrix)
{
int n = matrix.size();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
swap(matrix[i][j], matrix[j][i]);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n / 2; j++)
{
swap(matrix[i][j], matrix[i][n - j - 1]);
}
}
}
};Hash
Leetcode 36
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
bool isValidSudoku(vector<vector<char>> &board)
{
unordered_set<char> rows[9];
unordered_set<char> cols[9];
unordered_set<char> boxs[9];
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] == '.')
continue;
int boxIndex = (i / 3) * 3 + j / 3;
/*
9*9 -> 3*3
[0,0] [0,3] [0,6] / 3
[3,0] [3,3] [3,6] / 3
[6,0] [6,3] [6,6] / 3
*/
if (rows[i].count(board[i][j]) || cols[j].count(board[i][j]) || boxs[boxIndex].count(board[i][j]))
{
return false;
}
rows[i].insert(board[i][j]);
cols[j].insert(board[i][j]);
boxs[boxIndex].insert(board[i][j]);
}
}
return true;
}
};Leetcode 49
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<string>> groupAnagrams(vector<string> &strs)
{
unordered_map<string, vector<string>> mp;
mp.clear();
for (auto s : strs)
{
auto word = s;
sort(word.begin(), word.end());
mp[word].push_back(s);
}
vector<vector<string>> r;
for(auto m : mp){
r.push_back(m.second);
}
return r;
}
};Leetcode 128
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int longestConsecutive(vector<int> &nums)
{
unordered_set<int> s(nums.begin(), nums.end());
int longest = 0;
for (auto n : nums)
{
// check is the started number
if (!s.count(n-1)){
int length = 1;
while(s.count(n + length)){
length++;
}
longest = max(longest,length);
}
}
return longest;
}
};Two Pointer
Leetcode 167
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0;
int right = numbers.size()-1;
int total = 0;
while(left < right){
total = numbers[left] + numbers[right];
if(total == target ){
return {left+1,right+1};
}else if(total > target) {
right--;
}else{
left++;
}
}
return {-1,-1};
}
};Leetcode 125
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
bool isPalindrome(string s)
{
int start = 0;
int end = s.size() - 1;
while (start <= end)
{
if (!isalnum(s[start]))
{
start++;
continue;
}
if (!isalnum(s[end]))
{
end--;
continue;
}
if (tolower(s[start]) != tolower(s[end]))
{
return false;
}else{
start++;
end--;
}
}
return true;
}
};Leetcode 15
思路
- 使用i指針指向頭
- 分別使用slow和fast快慢指針去尋找和nums[i]相加為0的數
- 判斷假設當前數字和前一個相同，直接移動slow，避免出現重複答案
while (nums[slow] == nums[slow - 1] && slow < fast) {
slow++;
}#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
int slow = i + 1;
int fast = nums.size() - 1;
while (slow < fast)
{
int total = nums[i] + nums[slow] + nums[fast];
if (total > 0)
{
fast--;
}
else if (total < 0)
{
slow++;
}
else
{
res.push_back({nums[i], nums[slow], nums[fast]});
slow++;
while (nums[slow] == nums[slow - 1] && slow < fast)
{
slow++;
}
}
}
}
return res;
}
};Leetcode 11
class Solution {
public:
int maxArea(vector<int>& height) {
int r = height.size()-1;
int l = 0;
int w = 0;
while(l < r) {
w = max(w, (r-l)*min(height[l],height[r]));
height[l] < height[r] ? l++ : r--;
}
return w;
}
};Leetcode 42
class Solution {
public:
int trap(vector<int>& height) {
int l = 0;
int r = height.size()-1;
int w = 0;
int lmax = height[l];
int rmax = height[r];
while(l < r){
if(lmax < rmax){
l++;
lmax = max(lmax,height[l]);
w += lmax - height[l];
}else{
r--;
rmax = max(rmax,height[r]);
w += rmax - height[r];
}
}
return w;
}
};Stack
Leetcode 150
- 判斷是否為符號，不是存stack，否則做運算
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<string> st;
for(auto t : tokens){
if(t != "+" && t != "-" && t != "*" && t != "/"){
st.push(t);
}else {
int a = stoi(st.top());
st.pop();
int b = stoi(st.top());
st.pop();
if(t == "+"){
int c = b + a;
st.push(to_string(c));
}else if(t == "-"){
int c = b - a;
st.push(to_string(c));
}else if(t == "*"){
int c = b * a;
st.push(to_string(c));
}else if(t == "/"){
int c = b / a;
st.push(to_string(c));
}
}
}
return stoi(st.top());
}
};Leetcode 739
- stack存index位置，找到大於的話，就把大於元素的index和當前最大得idx做運算
- 因為有在vector設初始值0，所以都沒有大於元素後會自動為0
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> st;
vector<int> vc(temperatures.size(),0);
for(int i=0;i<temperatures.size();i++){
while(!st.empty() && temperatures[i] > temperatures[st.top()]){
int idx = st.top();
st.pop();
vc[idx] = i-idx;
}
st.push(i);
}
return vc;
}
};Leetcode 155
方法1
- 使用
vector<pair<int,int>來代替stack - pair的first存當前元素，second存之前的最小值
class MinStack {
private:
vector<pair<int,int>> st;
public:
MinStack() {
}
void push(int val) {
if(st.empty()){
st.push_back({val,val});
}else{
st.push_back({val,min(val,st.back().second)});
}
}
void pop() {
st.pop_back();
}
int top() {
return st.back().first;
}
int getMin() {
return st.back().second;
}
};
方法2
- 使用雙stack
- data 這個stack來存放任何值
- minStack存放比當前top元素小的值，保持最小元素在頂端
- 當minStack的頂端元素比data接收到的元素小的時候，重新push自己的top以維護top永遠為最小
class MinStack {
private:
stack<int> data;
stack<int> minstack;
public:
MinStack() {
}
void push(int val) {
data.push(val);
if(minstack.empty() || val < minstack.top()){
minstack.push(val);
}else{
minstack.push(minstack.top());
}
}
void pop() {
data.pop();
minstack.pop();
}
int top() {
return data.top();
}
int getMin() {
return minstack.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/Leetcode 921
- 因為只有
( 能和 )結合，因此判斷(就好，如果可以的話就pop出stack，不行則push
class Solution {
public:
int minAddToMakeValid(string s) {
stack<char> st;
int count = 0;
for(char str : s) {
if(st.empty()){
st.push(str);
}else if(st.top() == '(' && str == ')'){
st.pop();
}else{
st.push(str);
}
}
return st.size();
}
};Linklist
Leetcode 206
- 用指針維護
/**
* Definition for singly-linked list.
* 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* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* next = nullptr;
ListNode* cur = head;
while(cur){
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};Leetcode 21
- 使用dummy代替直接操作head，在刪除或變更節點的時候更方便
/**
* Definition for singly-linked list.
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy,*temp;
dummy = new ListNode();
temp = dummy;
while(list1 && list2){
if(list1->val < list2->val){
temp->next = list1;
list1 = list1->next;
}else{
temp->next = list2;
list2 = list2->next;
}
temp = temp->next;
}
if(list1) temp->next = list1;
if(list2) temp->next = list2;
return dummy->next;
}
};Leetcode 141
- 當行成cycle時，一定會讓雙指針只到相同的地方
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
return true;
}
}
return false;
}
};Leetcode 19
- 先讓head移動到指定的n節點，接著讓head移動直到nullptr，同時跟著動dummy
- 當head到nullptr時，dummy的下一個必為要刪除的元素，因此進行練表刪除動作
/**
* Definition for singly-linked list.
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* res = new ListNode(0,head);
ListNode* dummy = res;
for(int i=0;i<n;i++){
head = head->next;
}
while(head != nullptr){
head = head->next;
dummy = dummy->next;
}
dummy->next = dummy->next->next;
return res->next;
}
};Leetcode 138
- 使用hashMap儲存已經便利過的元素，key為節點，value為節點的值，之所以用hashMap的原因是因為避免random指向尚未生成的節點
- 之後在便利cur並且使用hashMap的key來當作Node
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head) return nullptr;
Node* cur = head;
unordered_map<Node*,Node*> old_to_new;
old_to_new.clear();
while(cur){
old_to_new[cur] =new Node( cur->val);
cur = cur->next;
}
cur = head;
while(cur){
old_to_new[cur]->next = old_to_new[cur->next];
old_to_new[cur]->random = old_to_new[cur->random];
cur = cur->next;
}
return old_to_new[head];
}
};Leetcode 2
- merge 用dummy搭配tmp模板話,插入值用
new ListNode
/**
* Definition for singly-linked list.
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *dummy,*tmp;
dummy = new ListNode();
tmp = dummy;
int carry = 0;
while(l1 != nullptr || l2 != nullptr || carry != 0){
int v1 = (l1 != nullptr) ? l1->val : 0;
int v2 = (l2 != nullptr) ? l2->val : 0;
int v = v1 + v2 + carry;
carry = v / 10;
int sum = v%10;
tmp->next = new ListNode(sum);
tmp = tmp -> next;
if(l1 != nullptr)l1 = l1->next;
if(l2 != nullptr)l2 = l2->next;
}
return dummy->next;
}
};Binary Search
Binary Search 核心
mid區間
(left+right)/2當left和right為大數容易overflowleft + (right-left)/2推薦(left+right) >> 1當left和right為大數容易overflow
核心模板
- 不用check單純找數字
int main(){
vector<int> nums;
int l = 0;
int r = nums.size()-1;
while(l <= r){
int mid = l + (r-l)/2;
if(nums[mid] > target) r = mid - 1;
else l = mid + 1;
// ...
}
// ...
}
- 需要check
```c++
bool check(){
// ...
}
int main(){
int l = 0;
int r = nums.size();
while(l <= r){
int mid = l + (r-l)/2;
if(check(mid)) r = mid;
else l = mid + 1;
}
}- 為非遞增單調序列
- 判斷右邊的數大小再做搜尋
int binSearch(vector<int>& nums,int l,int r){
int mid = l + (r-l)/2;
if(nums[mid] > nums[r]) return binSearch(nums,mid+1,r);
if (nums[l] > nums[mid]) return binSearch(nums,l,mid);
}Leetcode 367
class Solution {
public:
bool isPerfectSquare(int num) {
if(num == 0) return false;
if(num == 1) return true;
int l = 1;
int r = num;
while(l <= r){
int mid = l + (r-l)/2;
if(num % mid == 0 && mid == num/mid){
return true;
}else if(mid > num/mid){
r = mid-1;
}else{
l = mid+1;
}
}
return false;
}
};Leetcode 74
第一種解法，題目給的為遞增2D，使用線性搜
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows = matrix.size();
int col = matrix[0].size()-1;
int row = 0;
while(row < rows && col > -1){
int cur = matrix[row][col];
if(cur == target) return true;
if(cur > target) col--;
else row++;
}
return false;
}
};第二種使用BinarySearch
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = matrix[0].size();
int start = 0;
int end = row*col -1;
while(start <= end){
int mid = start + (end-start)/2;
if(matrix[mid/col][mid%col] == target) return true;
else if(matrix[mid/col][mid%col] > target) end = mid-1;
else start = mid+1;
}
return false;
}
};2D特別處理方法
- 對於所有的2D皆可用
mid/col表示x，mid%col表示y
Leetcode 153
- 此題為非遞增單調序列
class Solution {
public:
int binarySearch(vector<int>& nums,int l,int r){
int mid = l + (r-l)/2;
if(nums[r] < nums[mid]){
return binarySearch(nums,mid+1,r);
}
if(nums[l] > nums[mid]){
return binarySearch(nums,l,mid);
}
return nums[l];
}
int findMin(vector<int>& nums) {
return binarySearch(nums,0,nums.size()-1);
}
};Leetcode 875
class Solution {
public:
bool check(vector<int>& piles,int k,int h){
long int hours = 0;
for(int p : piles){
int tmp = p / k;
hours += tmp;
if(p % k != 0) hours ++;
}
return hours <= h;
}
int minEatingSpeed(vector<int>& piles, int h) {
int l = 1;
int r = 1000000000;
while(l <= r){
int mid = l + (r-l)/2;
if(check(piles,mid,h)) r = mid-1;
else l = mid+1;
}
return l;
}
};Saliding Window
滑窗思想
- 使用雙指針維護窗口大小，大小為
j-i+1 - 也可以使用vector或其他datastruct來維護窗口
Leetcode 643
- 這題就是很標準的窗口題，移動窗口的時候將不要的扣去
- accumulatie會將指定範圍內的所有值相加
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
double sum =0;
double maxSum =0;
sum = accumulate(nums.begin(),nums.begin()+k,0);
maxSum = sum;
for(int i=k;i<nums.size();i++){
sum += nums[i]-nums[i-k];
maxSum = max(maxSum,sum);
}
return maxSum/k;
}
};Leetcode 1004
- 雙層的while我都會想成類似窗口的模板，第一個while遍歷，第二個則是用來維護窗口大小
- 此提的話可以填入k個數字，因此在還有k且滿足條件下可以動k，而縮窗口的時候遇到滿足k條件的也要還原k值
- 因為縮的窗口會是已經便利過的，也可以理解為backtrack要恢復狀態
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int i =0;
int n = nums.size();
int start = 0;
int width = 0;
while(i < n){
while(i < n && k < 1 && nums[i] == 0){
if(nums[start] == 0) k++;
width = max(width,i-start);
start++;
}
if(i < n && k > 0 && nums[i] == 0)k--;
i++;
}
width = max(width,n-start);
return width;
}
};Leetcode 3
- 使用set的話可以查看是否有填入，沒有的話就將I往前
- 反回的就是窗口的大小
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i=0;int j=0;int ans =0;
unordered_set<char> st;
while(j < s.size()){
while(st.find(s[j]) != st.end()){
st.erase(s[i]);
i++;
}
st.insert(s[j]);
ans = max(ans,j-i+1);
j++;
}
return ans;
}
};Leetcode 424
- 先用map拿到最多出現的字，當大於窗口大小減去出現最多次的字大於k時維護窗口
class Solution {
public:
int characterReplacement(string s, int k) {
unordered_map<char,int> ump;
int i=0;int j=0;int maxl =0;
int ans=0;
while(j < s.size()){
ump[s[j]]++;
maxl = max(maxl,ump[s[j]]);
if( (j-i+1)-maxl > k){
ump[s[i]]--;
i++;
}
ans = max(ans,j-i+1);
j++;
}
return ans;
}
};Leetcode 209
- 簡單維護窗口
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int i =0;int j=0;int ans=INT_MAX;
int sum=0;
while(j < nums.size()){
sum += nums[j];
while(sum >= target){
sum -= nums[i];
ans = min(ans,j-i+1);
i++;
}
j++;
}
return ans == INT_MAX ? 0 : ans;
}
};Leetcode 567
- 先計算當前兩個map是否相同大小，相同就返回
- 第二個遍歷如果m2在的位置在n1也有出現就減去，當兩者相同時代表s2裏有s1的順序值
class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector<char> m1(26,0),m2(26,0);
int n1 = s1.size();
int n2 = s2.size();
if(n1 > n2) return false;
for(int i=0;i<n1;i++){
m1[s1[i]-'a']++;
m2[s2[i]-'a']++;
}
if(m1 == m2) return true;
for(int i=n1;i<n2;i++){
m2[s2[i]-'a']++;
m2[s2[i-n1]-'a']--;
if(m1 == m2) return true;
}
return false;
}
};Binary Tree
構建BinaryTree
- 靜態版二叉樹
- 時間複雜度為O(m),空間複雜度為O(n),因為使用了長度為m的遞歸棧
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Node {
char value;
int lson;
int rson;
} tree[N]; // tree[0]不用表示空節點
int n = 1; // 記錄節點位置
int newNode(char val)
{
tree[n].value = val;
tree[n].lson = 0;
tree[n].rson = 0;
return n++;
}
void insert(int &father, int child, int l_r)
{
l_r == 0 ? tree[father].lson = child : tree[father].rson = child;
}
int dfn[N] = {0};
int dfn_timer = 0;
void dfn_order(int father)
{
if (father != 0)
{
dfn[father] = ++dfn_timer;
printf("dfn[%c].value=%d ", tree[father].value, dfn[father]);
dfn_order(tree[father].lson);
dfn_order(tree[father].rson);
}
}
int visit_time=0;
void visit_order(int father){
if(father != 0){
printf("visit[%c]=%d ",tree[father].value,++visit_time);
visit_order(tree[father].lson);
visit_order(tree[father].rson);
printf("visit[%c]=%d ",tree[father].value,++visit_time);
}
}
int deep[N] = {0};
int deep_timer = 0;
void deep_child(int father){
if(father != 0){
deep[father] = ++deep_timer;
printf("deep[%c]=%d ",tree[father].value,deep[father]);
deep_child(tree[father].lson);
deep_child(tree[father].rson);
--deep_timer;
}
}
int num[N] = {0};
int num_node(int father){
if(father == 0) return 0;
else{
num[father] = num_node(tree[father].lson)+ num_node(tree[father].rson) + 1;
printf("num[%c]=%d ",tree[father].value,num[father]);
return num[father];
}
}
void pre_order(int father){
if(father != 0) {
cout << tree[father].value;
pre_order(tree[father].lson);
pre_order(tree[father].rson);
}
}
void in_order(int father){
if(father != 0) {
in_order(tree[father].lson);
cout << tree[father].value;
in_order(tree[father].rson);
}
}
void post_order(int father){
if(father != 0) {
post_order(tree[father].lson);
post_order(tree[father].rson);
cout << tree[father].value;
}
}
int build_tree(){
int A = newNode('A');int B = newNode('B');int C = newNode('C');
int D = newNode('D');int E = newNode('E');int F = newNode('F');
int G = newNode('G');int H = newNode('H');int I = newNode('I');
insert(E,B,0);
insert(E,G,1);
insert(B,A,0);
insert(B,D,1);
insert(G,F,0);
insert(G,I,1);
insert(D,C,0);
insert(I,H,0);
int root = E;
return root;
}
int main(){
int root = build_tree();
cout << "dfn order: "; dfn_order(root);cout << endl;
cout << "visit order: "; visit_order(root);cout << endl;
cout << "deep child: " ; deep_child(root);cout << endl;
cout << "num of tree: " << num_node(root) << endl;
cout << "in order: " ; in_order(root);cout << endl;
cout << "pre order: " ; pre_order(root);cout << endl;
cout << "post order: ";post_order(root);cout << endl;
return 0;
}Leetcode 226
- tree的題目大部分都可以直接用dfs完成
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root)return 0;
TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
if(root->left) invertTree(root->left);
if(root->right) invertTree(root->right);
return root;
}
};Leetcode 104
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
int maxL = maxDepth(root->left);
int maxR = maxDepth(root->right);
return max(maxL,maxR)+1;
}
};Leetcode 110
- 是否平衡為最後節點個數為深度
class Solution {
public:
int check(TreeNode* root){
if(!root) return 0;
int l = check(root->left);
int r = check(root->right);
if(l == -1 || r == -1 || abs(l-r) > 1) return -1;
return max(l,r)+1;
}
bool isBalanced(TreeNode* root) {
if(!root) return true;
return check(root) == -1 ? false : true;
}
};Leetcode 543
class Solution {
public:
int check(TreeNode* root){
if(!root) return 0;
int l = check(root->left);
int r = check(root->right);
if(l == -1 || r == -1 || abs(l-r) > 1) return -1;
return max(l,r)+1;
}
bool isBalanced(TreeNode* root) {
if(!root) return true;
return check(root) == -1 ? false : true;
}
};Leetcode 100
- 是否相同檢查節點值就好,如果一方null另一方還沒，代表不一樣，同時都為null則遍歷結束
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q) return true;
if(!p || !q) return false;
if(p->val != q->val) return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
};Leetcode 101
- 對稱樹將原本root拆成左son和右son,將他們當成兩棵樹後再遍歷
class Solution {
public:
bool check(TreeNode* n1,TreeNode* n2){
if(!n1 && !n2 ) return true;
if(!n1 || !n2) return false;
return n1->val == n2->val && check(n1->left, n2->right) && check(n1->right,n2->left);
}
bool isSymmetric(TreeNode* root) {
return check(root->left,root->right);
}
};Leetcode 112
class Solution {
public:
bool check(TreeNode* root,int target,int sum){
if(!root) return false;
sum += root->val;
if(!root->left && !root->right){
return sum == target;
}
bool l = check(root->left,target,sum);
bool r = check(root->right,target,sum);
return l || r;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(!root) return false;
int sum = 0;
return check(root,targetSum,sum);
}
};Leetcode 572
- 在check的時候，同時check一邊就行，再用AND判斷
class Solution {
public:
bool check(TreeNode* node,TreeNode* subRoot){
if(node == NULL && subRoot == NULL) return true;
if(!node || !subRoot) return false;
if(node->val != subRoot->val) return false;
return check(node->left,subRoot->left) && check(node->right,subRoot->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(!subRoot) return true;
if(!root) return false;
if(check(root, subRoot)) return true;
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};Leetcode 102
- 遍歷節點的時候將樹扁平化成1維陣列,扁平化的方法則用BFS遍歷樹
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
queue<TreeNode* > q;
q.push(root);
while(!q.empty()){
int n = q.size();
vector<int> path;
for(int i =0;i<n;i++){
TreeNode* node = q.front();
q.pop();
if(node -> left != nullptr) q.push(node->left);
if(node -> right != nullptr) q.push(node->right);
path.push_back(node->val);
}
res.push_back(path);
}
return res;
}
};Leetcode 230
- 將樹扁平化成1D陣列後，排序找到第k小的值
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector<int> vc;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int n = q.size();
for(int i=0;i<n;i++){
TreeNode* node = q.front();
q.pop();
if(node->left != nullptr) q.push(node->left);
if(node->right != nullptr) q.push(node->right);
vc.push_back(node->val);
}
}
sort(vc.begin(),vc.end());
return vc[k-1];
}
};Leetcode 530
- 尋找Node中的最小數中先扁平化成1D陣列後,用tow pointer的方式尋找在2 nodes中的最小值
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
vector<int> vc;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int n = q.size();
for(int i = 0;i<n;i++){
TreeNode* node = q.front();
q.pop();
if(node->left != nullptr) q.push(node->left);
if(node->right != nullptr) q.push(node->right);
vc.push_back(node->val);
}
}
sort(vc.begin(),vc.end());
int i =0;
int j =1;
int ans = INT_MAX;
while(i < j && j != vc.size()) {
ans = min(ans,abs(vc[i]-vc[j]));
i++;
j++;
}
return ans;
}
};Leetcode 98
- 判斷是符合合題目的二叉搜索樹(BST)
- 題目要求：
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
- 題目要求：
第一種拆判斷值後做中序遍歷
class Solution {
public:
bool slove(TreeNode* root,long small,long big){
if(root == nullptr )return true;
if(root->val <= small || root->val >= big) return false;
return slove(root->left,small,root->val) && slove(root->right,root->val,big);
}
bool isValidBST(TreeNode* root) {
if(!root) return true;
return slove(root,LONG_MIN,LONG_MAX);
}
};第二種使用stack做中序遍歷
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> q;
TreeNode* prev = nullptr;
while(root != nullptr || !q.empty()){
while(root != nullptr){
q.push(root);
root = root->left;
}
root = q.top();
q.pop();
if(prev != nullptr && root->val <= prev->val)return false;
prev = root;
root = root->right;
}
return true;
}
};Leetcode 235
- 在BST(二叉搜索樹)上找尋LCA(公共祖先)
- 將root拆成左右子樹，後尋找符合條件的1.右邊一定要大於root 2.左邊一定要小於root
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return root;
if(p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right,p,q);
if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left,p,q);
return root;
}
};Leetcode 208
- Trie樹
// 初始化Trie樹的Node,children用來存字母index(a->0,z->25)
class TrieNode {
public:
TrieNode* children[26];
bool isEnd;
TrieNode(){
isEnd = false;
for(int i =0;i<26;i++){
children[i] = nullptr;
}
}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
// 插入時如果沒有對應的值時(存word的index)，建立一個新的節點
void insert(string word) {
TrieNode* node = root;
for(char w : word) {
int index = w - 'a';
if(node->children[index] == nullptr) node->children[index] = new TrieNode();
node = node->children[index];
}
node->isEnd = true;
}
// 查找不斷往tree上的node找，值到遍歷完tree
bool search(string word) {
TrieNode* node = root;
for(char w : word ){
int index = w - 'a';
if(node->children[index] == nullptr) return false;
node = node->children[index];
}
return node->isEnd;
}
// 只要有查找到需要的值就結束，不用遍歷完tree
bool startsWith(string prefix) {
TrieNode* node = root;
for(char p : prefix) {
int index = p -'a';
if(node->children[index] == nullptr) return false;
node = node->children[index];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/Leetcode 2583
- 使用BFS紀錄每一次的sum，并且preiority_queue使用大到小排列，超過題目要求的k時做pop
class Solution {
public:
long long kthLargestLevelSum(TreeNode* root, int k) {
priority_queue<long long, vector<long long>, greater<>> pq;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int n = q.size();
long long sum = 0;
for(int i=0;i<n;i++){
TreeNode* node = q.front();
q.pop();
sum += node->val;
if(node->left != nullptr) q.push(node->left);
if(node->right != nullptr) q.push(node->right);
}
pq.push(sum);
if(pq.size() > k) pq.pop();
}
return pq.size() < k ? -1 : pq.top();
}
};Leetcode 2641
- 第一次BFS先計算當前level的總和
- 第二次BFS計算這一層node的總和減去同個parent中node的總和
class Solution {
public:
TreeNode* replaceValueInTree(TreeNode* root) {
if(root == nullptr) return nullptr;
queue<TreeNode*> q;
q.push(root);
vector<int> sum_;
sum_.push_back(root->val);
while(!q.empty()){
int n = q.size();
int sum = 0;
for(int i=0;i<n;i++){
TreeNode* node = q.front();
q.pop();
if(node->left) {
sum += node->left->val;
q.push(node->left);
}
if(node->right){
sum += node->right->val;
q.push(node->right);
}
}
sum_.push_back(sum);
}
// for(auto v : sum_)cout << v << endl;
// twice bfs
q.push(root);
int level = 0;
while(!q.empty()){
int n = q.size();
for(int i = 0;i<n;i++){
TreeNode* node = q.front();
q.pop();
int leftAndRight = (node->left?node->left->val:0)+(node->right?node->right->val:0);
if(node->left){
node->left->val = leftAndRight;
q.push(node->left);
}
if(node->right){
node->right->val = leftAndRight;
q.push(node->right);
}
node->val = sum_[level] - node->val;
}
level++;
}
return root;
}
};Heap
Heap介紹
- 特色：具有最大堆和最小堆
- 最大堆：跟節點永遠是最大值
- 最小堆：跟節點永遠是最小值
二叉堆
- 概念：二叉堆是一顆完全二叉樹，樹的每層都會滿，除了最後一層不一定
i > 1的節點，其父節點i/2- 如果
2i>n那麼i節點沒有孩子，如果2i+1>n那麼節點i沒有右孩子 - 如果i有孩子，那麼左孩子為2i，右孩子為2i+1
- 操作：
- 進堆：每次把元素放進堆，使跟節點保持最小(最小堆)
- 出堆：每次取出的堆頂，也就是最小值。同時調整堆，使新的堆頂最小
實現
- 可以直接使用
priority_queue，因為是由堆實現的priority_queue默認由小排到大，可以使用priority_queue<T,vector<T>,geather<>>來自訂排序geather為struct，可以自定義，默認由小到大，以下使用cmp代替原本的geather
struct cmp { bool operator()(pair<int,int>a,pair<int,int>b){ return a.second < b.second; } }; - 也可以使用數組實現
Leetcode 1046
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> maxHeap;
for(int stone : stones){
maxHeap.push(stone);
}
while(maxHeap.size() > 1){
int x = maxHeap.top();
maxHeap.pop();
int y = maxHeap.top();
maxHeap.pop();
if(x != y){
maxHeap.push(x-y);
}
}
return maxHeap.size() > 0 ? maxHeap.top() : 0;
}
};Leetcode 215
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq;
for(int n : nums) pq.push(n);
for(int i=0;i<k-1;i++){
pq.pop();
}
return pq.top();
}
};Leetcode 347
struct cmp {
bool operator()(pair<int,int>a,pair<int,int>b){
return a.second < b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> mp;
for(int n : nums ) mp[n]++;
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
for(auto m : mp) {
pq.push({m.first,m.second});
}
vector<int> ans;
while(k-- > 0){
ans.push_back(pq.top().first);
pq.pop();
}
return ans;
}第二種解法
vector<int> topKFrequent(vector<int>& nums, int k){
unordered_map<int,int> mp;
for(int n : nums ) mp[n]++;
vector<vector<int>> vc(nums.size()+1);
for(auto m : mp) {
vc[m.second].push_back(m.first);
}
vector<int> ans;
for(int i=vc.size()-1;i>=0;i--){
for(int v : vc[i]){
ans.push_back(v);
if(ans.size()==k) return ans;;
}
}
return {};
}Leetcode 973
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
priority_queue<pair<int,vector<int>>> pq;
for(vector<int> point : points) {
int x = point[0];
int y = point[1];
int dis = x*x + y*y;
pq.push({dis,point});
if(pq.size() > k) pq.pop();
}
vector<vector<int>> ans;
while(!pq.empty()){
pair<int,vector<int>> top = pq.top();
ans.push_back(top.second);
pq.pop();
}
return ans;
}
};Leetcode 23
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<int,vector<int>,greater<int>> pq;
ListNode* head = new ListNode();
ListNode* dummy = head;
for(int i=0;i<lists.size();i++){
ListNode* l = lists[i];
while(l != nullptr) {
pq.push(l->val);
l = l->next;
}
}
while(!pq.empty()){
int top = pq.top();
dummy->next = new ListNode(top);
dummy = dummy->next;
pq.pop();
}
return head->next;
}
};