moving cursor to begin of line,
i.e. '\r'
line feed, 換行, //win //Unix
moving one line forward,
i.e. '\n'
2022年11月23日 星期三
2022年11月7日 星期一
2022年4月13日 星期三
1038, binary search tree to greater sum tree
1038, binary search tree to greater sum tree
====
tree, BST
====
試想一下一個BST: [4,1,6]
GreaterSum就是 [4+6, 1+4+6, 6], 也就是固定先加總右子 >>> 再來node >>> 再來左子
1. 如何開始: root開始, 照右>中>左
2. 如何結束: 當!node就return, 終究走完
====
class Solution {
public:
TreeNode* BstToGst(TreeNode* root){
int sum=0
SumNode(root, &sum)
return root
}
void SumNode (TreeNode* node, int& sum){
if(node == NULL) return
SumNode(node->right, sum)
sum+=node->val
node->val = sum
SumNode(node->left, sum)
}
}
938, range sum of BST
938, range sum of BST
====
tree, BST
DFS
BFS
====
DFS:
1. 如何開始: 先從root開始
每次都加
node(如果符合range則node->value 否則0),
node->left,
node->right
2. 如何結束: 如果本身!node 就return 0
====
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int H){
if(!root) return 0
return (root->val >= L && root->val <=H ? root->val : 0) + rangeSumBST(root->left, L, H) + rangeSumBST(root->right, L, H)
}
}
====
BFS:
1. 如何開始: root加到queue, 每次加左子右子
2. 如何停止: queue空
====
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int H){
queue<TreeNode*> pq
int sum=0
pq.push(root)
while(!pq.empty()){
TreeNode* cur = pq.front
pq.pop()
if(cur->val >= L && cur->val <= H)
sum+=cur->val
if(cur->left) pq.push(cur->left)
if(cur->right) pq.push(cur->right)
}//while pq.empty
return sum
}
}
2022年4月11日 星期一
1315, Sum of nodes with even-vlaues grandparent
====
1315, Sum of nodes with even-vlaues grandparent
====
tree,
DFS,
BFS
====
DFS:
1. 照順序 從root檢查 root's parent/grandparent
加總sum(global
左子/右子樹加入dfs
2. 如何起始：root, Null, Null
如何停止：檢查左子右子是否空 才扔DFS
----
class Solution {
public:
int sum=0
int sumEvenGradparent(TreeNode* root){
dfs(root, null, null)
return sum
}
void dfs(TreeNode* node, TreeNode* parent, TreeNode* grandpa){
if(!root) return
if(grandpa && grandpa->val%2==0)
sum += root->val
if(node->left) dfs(node->left, node, parent)
if(node->right) dfs(node->right, node, parent)
}
}
====
BFS:
1. 如何起始：q.push(root)
如何停止：
for整個程式->while q.empty時停止
for加總->如果node為空就return 0, 不然就return node->val
2. q.push左子 右子
應該在while !q.empty內
但是在node->val%2外
因為目的是走過/檢查過所有的node, 因此不侷限在%2的case
----
class Solution{
public:
int sum=0
int func(TreeNode* root){
return root? root->val : 0
}
int sumEvenGrandparent(TreeNode* root){
if(!root) return
queue<TreeNode*> q
q.push(root)
while(!q.empty()){
TreeNode* node = q.front()
q.pop()
if(node->val%2==0){
if(node->left){
sum+= func(node->left->left) + func(node->left->right)
}
if(node->right){
sum+= func(node->right->left) + func(node->right->right)
}
}//if even
if(node->left) q.push(node->left)
if(node->right) q.push(node->right)
}//while q.empty
return sum
}
}
2022年4月10日 星期日
1302, Deepest leaves sum
====
1302, Deepest leaves sum====
tree
DFS, BFS
====
DFS:
1. 題目給一個TreeNode
從(root, 0//lvl, depth)開始DFS
2. 懶人法, vec<int>sum[i] 紀錄每i層depth的total
在DFS中
如果sum size等於傳入的lvl, 則表示這層depth第一次加入到sum, 所以sum.push_back
否則, 表示已經有index 'lvl', 加入到sum[lvl]
//初始root 0, sum size也零, sum.push_back == sum[0]
//root右子樹 1, sum size卻是2, 表示有左子樹加入過了, 合併到sum[lvl] == sum[1]
3. 最終return vector最後一個元素 == sum.back
----
class Solution {
public:
vec<int> sum
int deepestLeaveSum(TreeNode* root){
dfs(root, 0)
return sum.back()
}
void dfs(TreeNode* node, int lvl){
if(sum.size() == lvl)
sum.push_back(node->val)
else
sum[lvl] += node->val
if(node->left) dfs(node->left, lvl+1)
if(node->right) dfs(node->right, lvl+1)
}
}
====
BFS:
1. 題目給一個TreeNode
依照lvl/depth加入queue, pop all並加總
2. 懶人法, 當queue不等於空
把sum清空
並且元素pop all並加總//for, 這樣就會得到每一層的sum
如果還有左子右子, push到queue
如果queue空, 表示最後一層leave做完了, return當次/最終sum
----
class Solution {
public:
int sum
int deepestLeaveSum(TreeNode* root) {
queue<TreeNode*> q
q.push(root)
while(!q.empty()){
sum=0
int qlen = q.size()
for(int i=0, i<qlen, i++) {
TreeNode* node = q.front()
q.pop()
sum+=node->val
if(node->left) q.push(node->left)
if(node->right) q.push(node->right)
}//for qlen
}//while q.empty
return sum
}
}
2022年4月6日 星期三
785, is graph bipartite
785, is graph bipartite
====
coloring,
bipartition,
BFS
====
1. 同886, 給予一個vec<vec<int>>graph
限制不同屬的規則(dislike)
新增一個vec<int>color
0初值, 1,-1兩類
新增一個queue q處理每次的相關元素
2. while(!q.empty) 檢查所有元素規則
for cur, 當次元素
for nei, cur元素的graph規則
如果color[nei] != 0則skip
如果color[nei]=0, 未走訪 => 看color[nei] 與color[cur]
分兩類
如果分不了兩類, false
如果走完, q空都沒有failed, 則true
====
class Solution {
public:
bool isBipartite(vec<vec<int>>&graph) {
int n= graph.size()
vec<int> color(n,0)
queue<int> q
for(int i=0, i<n, i++){
if(color[i] != 0)
continue
color[i]=1
for( q.push(i), !q.empty(), q.pop()) {
//這種寫法？！
int cur=q.front()
for( int nei: graph[cur]) {
if(color[nei] == 0) {
q.push(nei)
color[nei] = color[cur]==1 ? -1 : 1
}
if(color[nei] == color[cur])
return false
}//graph[cur].size
}//!q.empty()
}//for n
return true
}
}
886, possible bipartition
886, possible bipartition
====
Coloring
Bipartition
====
1. 與union類似（？
給予一個vec<vec<int>> dislike的rule, 跟N個元素
->
新增一個vec<vec<int>> graph, 紀錄需要走訪的關係
//類似於union的input
新增一個color(N, 0)
0未走訪, 1,2兩類
新增一個queue處理當次graph元素的所有關係
//?
2. while(!q.empty) 檢查所有元素規則
for u, 當次元素
for v, u元素的graph規則
如果color[v] != 0則skip
如果color[v]=0, 未走訪 => 看color[u] 與color[v]
分兩類
如果分不了兩類, false
如果走完, q空都沒有failed, 則true
====
class Solution {
public:
bool possibleBipartition(int N, vec<vec<int>&dislike) {
vec<vec<int>>graph(N, vec<int>())
queue<int> q
vec<int> color(N, 0)
for( i=0, i< dislike.size(), i++ ){
u= graph[i][0] -1
v= graph[i][1] -1
graph[u].push_back(v)
graph[v].push_back(u)
}
for( i=0, i<N, i++){
if(color[i] != 0)
continue
q.push(i)
color[i]=1 //起始
while( !q.empty() ){
u= q.front()
q.pop()
for( k=0, k<graph[u].size, k++ ){
v= graph[u][k]
if(color[v]==0){
q.push(v)
color[v] = color[u]==1 ? 2 : 1
}
if(color[v]==color[u])
return false
}//for graph[u].size
}//while
}//for N
return true
}
}
2022年3月31日 星期四
210, Course Schedule 2
210, Course Schedule 2
====
Topological sort
====
1. 給予一個node_number, 一個規則preReq vec<vec<>>
建立一個graph vec<vec<>>來紀錄topo //父子關係
2. 建立一個indegree
根據先後的規則 for紀錄每個node的深度
//聰明, 深度加在preReq的頭元素, 原則越多越深
//深度為0就是必須第一個走在前面的
3. 建立一個Queue nodes 存放走訪的點的順序,
//深度為0 加入queue
一個Int visit紀錄走過的點的數量, 判斷最終走過的點是不是全部點數量
//不是 則有cycle
4. 每當queue不為空
pop, push_back到ret
->
當次元素pop掉後, 去graph找接著的topo元素是哪些
->
這些topo元素, indegree -1
如果degree變0, 表示接著可以處理了, 加入queue
====
vec<int> findOrder(int numCourse, vector<pair<int, int>>& prerequest){
vec<vec<int>> graph(numCourse, vec<int>() )
vec<int> indegree(numCourse, 0)
queue<int> nodesQ
int visited=0
vec<int> ret
for( auto eq: prerequest ){
graph[eq.second].push_back( eq.first )
indegree[eq.first]++
}
for( int n, n<numCourse, n++)
if(indegree[n] == 0)
nodeQ.push(n)
while(!nodeQ.empty()){
visited++
int nid = nodeQ.front()
nodeQ.pop()
ret.push_back(nid)
for( auto topo:graph[nid] ){
indegree[topo]--
if(indegree[topo]==0)
nodeQ.push(topo)
}
}//while empty
return visited==numCourse ? ret : vec<int>()
}
2022年2月15日 星期二
207, Course schedule
207, Course schedule
====
Topological sort
Coloring
====
1. 給予一個n node number
一個vec<pair<int,int>>prerequest規則
2. prerequest表明<i,j>(有向圖)
如果要access i, 必須先有j
如果規則互斥(產生cycle) 則false
可能有很多方式
可用DFS 可用BFS 可用coloring
3. Coloring比較單純
生成一個map<int, vec<int>> adj來填入規則 //hashMap
->
adj[1].push_back(0)
生成一個vec<int> visited(n,0)來紀錄
如果走的過程中有碰到任何已經拜訪過的
則有cycle, false
否則true
====
class Solution{
public:
bool isCycle(vec<int>visited, vec<vec<int>>adj, int id){
if visited[id] == 1 return true
if visited[id] == 0{
visited[id]=1
for auto edge:adj[id]
if isCycle(visited, adj, edge) return true
}
visited[id]=2 //?
return false
}
bool canFinished(int n, vec<vec<int>>& pre){
map<int, vec<int>> adj
for auto edge: pre
adj[edge[1]].push_back(edge[0])
vec<int> visited(n, 0)
for auto prule: adj{
if(isCycle(visited, adj, prule.first)) return false
}//
return true
}
};
1091, Shortest path in binary matrix
1091, Shortest path in binary matrix
====
BFS,
Shortest path,
Path existed
====
1. 題目給予vec<vec<int>>matrix
從左上 欲走到右下
路徑上只能是0 可以走八個方向
2. 一個queue< pair<int,int>>做BFS
一個vec<vec<bool>> visited記錄走過
3. 起點是左上
找它的鄰近加入queue
紀錄每次queue.size
而後每次找鄰近 且 matrix[][]==0 加入queue
4. 每次round++
當有座標碰到右下
return round(左上）
====
class Solution {
public:
int shortestPathBinaryMatrix(.vec<vec<int>>& grid ){
int m= grid.size(), n= grid[0].size()
if( grid[0][0]!=0 || grid[m-1][n-1]!=0 ) return -1
queue< pair<int,int>> pq
pq.push({1,0}), pq.push({0,1}), pq.push({1,1})
vec<vec<bool>> visited=(m, vec<bool>(n, false))
int res=1 //第一輪
while(!pq.empty()){
int qSize= pq.size()
for(int t-qSize){
auto qFront= pq.front()
pq.pop()
int x= qFront.first
int y= qFront.second
if(x==m-1 && y==n-1) return res+1 //第n輪加上右下+1
if(x>=0 && y>=0 && x<m && y<n && !visited[x][y] && grid[x][y]==0){
visited[x][y]=true
pq.push({x-1,y-1}), pq.push({x-1,y}), pq.push({x-1,y+1})
pq.push({x,y-1}), pq.push({x,y+1})
pq.push({x+1,y-1}), pq.push({x+1,y}), pq.push({x+1,y+1})
}//if
}//for qSize
res++
}//while q.empty
return -1
}
};
994, rotting oranges
====
994, rotting oranges
====
BFS,
Shortest path,
Path existed
====
1. 給予一個箱子
'0'代表空
'1'代表好的
'2'代表爛的橘子
每分鐘爛的會向四個方向腐爛
求最大（久）箱子內還有好的
2. 起點是爛的->爛的(2) 座標/pair加入queue
隨後加入找好的(1)
但是要把它變爛(2)才 座標/pair加入queue
3. 多一個int fresh紀錄剩餘的好的
每次BFS加入記得扣掉
多一個int res紀錄第幾輪
return res
//剛開始的BFS還沒開始感染
//所以放在while裡面即可
4. 四個方向化成一個vector
vec<int> for={-1, 0, 1, 0, -1}
//只要1234, 2345 pair就好
====
class Solution{
public:
int orangesRotten( vec<vec<int>>& grid ){
int m= grid.size(), n= grid[0].size()
int fresh=0
queue< pair<int,int>> q
for i-m
for j-n
if grid[i][j] == 2
q.push(<i-1,j>), q.push(<i+1,j>), q.push(<i,j-1>), q.push(<i,j+1>);
if grid[i][j] == 1
fresh++
vec<vec<bool>> visited(m, vec<bool>(n, flase))
int res=-1
while( !q.empty() ){
int qSize= q.size()
while(qSize--){
auto fq= q.front()
q.pop()
int x= fq.first
int y= fq.second
if(x>=0 && y>=0 && x<m && y<n && !visited[x][y] && grid[x][y]==1){
visited[x][y]=true
grid[x][y]=2
q.push(<x-1,y>), q.push(<x+1,y>), q.push(<x,y-1>), q.push(<x,y+1>);
}//if
}//q.size
res++
}//q.empty
if(res==-1) return 0
if(fresh>0) return -1 //有橘子永遠不爛 莫急
}
};
2022年2月4日 星期五
1162, As far from land as possible
====
1162, As far from land as possible
====
BFS,
Shortest path
Path existed
====
1. 目標是water, '0'
能有與
起點land, '1'能有的最長距離
2.
定義一個queue<pair<int,int>>存放座標
BFS第一輪找的是起點->從'1'開始上下左右加第一輪BFS
3. 當queue不為空
front && pop座標
如果符合條件 //!visited && 是目標'0'
=>
visited true/ update cost/ 加入上下左右BFS
4. 當最遠的座標找到 會結束
=>
最遠的座標 在上一輪會將上下左右加入queue
=>
新的一輪 for step++
=>
都不符合條件 pop
一直都沒有符合條件的座標 所以都沒有加入queue
=>
while queue空了 跳出
=>
這次的step無作用
step-1才是預期
====
class Solution{
public:
int maxDistance( vec<vec<int>>& matrix ){
int m= matrix.size(), n= matrix[0].size()
vec<vec<bool>> visited= (m, vec<bool>(n, false))
queue<pair<int,int>> pq
for i-m
for j-n
if matrix(i,j) == 1
pq.push(i-1,j)
pq.push(i+1,j)
pq.push(i,j-1)
pq.push(i,j+1)
int step=0
while(!pq.empty()){
step++
int size=pq.size()
for t-size{
int x= pq.front().first
int y= pq.front().second
pq.pop()
if( x>=0 && y>=0 && x<m && y<n && matrix(x,y)==0 && !visited(x,y) ){
visited(x,y) = true
pq.push(x-1,y)
pq.push(x+1,y)
pq.push(x,y-1)
pq.push(x,y+1)
}//if
}//for
}//while
return step==1? -1: step-1
}
};
2022年2月3日 星期四
542, 01_matrix
====
542, 01_matrix
====
BFS,
Shortest path
Path existed
====
1. 題目希望將給予的matrix
化成
每個單元離它最近的'0'的距離
2. BFS用的是queue, 因為用了座標
所以用queue< pair<int,int> >來紀錄加入queue的座標
3. 從(0,0)開始做BFS
當queue不為空的時候
-> pop單元
-> 針對pop的動作處理BFS //加入新的單元
//新增step or cost
4. Visited是必須的
產生一個vec<vec<bool>>visited來紀錄已經處理過的單元
以免單元間產生無窮迴圈
->
當沒有visited
且
符合題目條件
則處理
BFS //push
====
class Solution{
public:
vec<vec<int>> updateMatrix( vec<vec<int>>&matrix ){
int m= matrix.size()
int n= matrix[0].size()
queue<pair<int,int>> pq
for i-m
for j-n
if(matrix(i,j) == 0){
//先從'0'開始 因為第一次與零的距離是“0”
//之後逐漸加一
pq.push({i-1, j});
pq.push({i+1, j});
pq.push({i, j-1});
pq.push({i,j-1});
//上下左右加入queue //所有第一層的node
}
int step=0
vec<vec<bool>> visited(m, vec<bool>(n, false) )
while( !pq.empty() ){
step++
int size= pq.size() //紀錄當前的queue size來控制當次需要做多少次
for(i=0; i<size; i++){
auto Front= pq.front()
int x=Front.first
int y=Front.second
pq.pop()
if(x>=0&& y>=0&& x<m&& y<n&& !visited(x,y)&& matrix(x,y)==1){
//開始找‘1’,因為開始要填1到0的距離
visited(x,y)=true
matrix(x,y)=step
//因為拜訪過了 且當前的距離已經填入
pq.push({x-1, j});
pq.push({x+1, j});
pq.push({i, y-1});
pq.push({i,y-1});
//第n次層的上下左右 加入queue
}//if
}//for
}//while
}
};
2022年2月1日 星期二
802, Find eventual safe states
====
802, Find eventual safe states
====
DFS,
cycle find
有向/無向圖找cycle不一樣
有向需要三個顏色(還沒看過/ 還在看/ 已經看完
無向需要兩個顏色(visited/ un-visited
過程中有碰到訪問過/看過的node
就是有cycle
====
a)
1. 題目給予一個graph
定義一個int dp(n, 0)初值
0, 還沒看過
-1,還在看
1,已經看完
2. DFS一進去
先將dp[i]=-1 //還在看
然後針對graph[i][]一一DFS檢查
如果有false則return false
3. 如果graph[i][]跑完 都沒看到cycle
//如果沒有看到dp==-1, i.e還在看
則dp[i]=1, i.e已經看完
return true
else
return dp[i]==1
4. main一個for跑DFS
如果false,就不加入結果
否則是安全的,加入
====
class Solution{
public:
bool DFS( vec<vec<int>>&graph, vec<int>&dp, int i){
if ( dp[i] ) //-1 ->false, 1 ->true
return dp[i]==1
dp[i]=-1
for auto t:graph[i].begin; t!=graph[i].end; t++
if ( !DFS( graph, dp, *t ) )
return false
dp[i]=1
return true;
}
vec<int> eventualSafe( vec<vec<int>>&graph ){
int n=graph.size()
vec<int> res
vec<int> dp(n, 0)
for i-n
if( DFS( graph, dp, i )
res.push_back(i)
return res
}
}
733, Flood Fill
====
733, Flood Fill
====
DFS,
from each un-visited node/island problems
====
1. 題目給予一個vec<vec<int>>M
一個起始的座標
以及變更的新數值
2. 定義一個vec<vec<bool>>visited
DFS( M, visited, i, j, m, n, new )走過上下左右的同值/同於起始 的所有node
====
class Solution{
void DFS( vec<vec<int>>& matrix, vec<vec<bool>>&visited, int i, int j, int m, int n, int old, int new){
if( i<0 || j<0 || i>=m || j>=n || matrix(i,j)!=old || visited(i,j) ) return;
visited(i,j)= true;
matrix(i,j)= new;
DFS( matrix, visited, i-1, j, m, n, matrix(i,j), new)
DFS i+1
DFS j-1
DFS j+1
}
vec<vec<int>> FloodFill( vec<vec<int>>& matrix, int x, int y, int newColor ){
int m= matirx.size(), n= matrix[0].size()
vec<vec<bool>> visited= (m, false)
if matrix(x,y)!=newColor
DFS( matrix, visited, x, y, matrix(x,y), newColor)
return matrix
}
2022年1月29日 星期六
841, Keys and rooms
====
841, Keys and rooms
====
DFS,
for each unvisited node/island problems
====
1. 題目給予固定長度n的房間 以及房間內含的鑰匙
題目定義第一間是沒有鎖的=>DFS開始的地方
生成一個n的visited
2. DFS走過所有的鑰匙
最終for檢查visited
如果還有房間un-visited則false
====
class Solution{
public:
void DFS( vec<vec<int>>&rooms, vec<bool>&visited, int node){
visited[node]=true
for auto k:rooms[node]
if( !visited[k] )
DFS( rooms, visited, k )
}
bool VisitedRoom( vec<vec<int>>& rooms ){
int n=rooms.size()
vec<bool> visited(n, false)
DFS( rooms, visited, 0 )
int i=0
for i-n
if !visited[i] return false
return true
}
2022年1月28日 星期五
1254, Number of closed islands
====
1254, Number of closed islands
====
DFS from each unvisited node/island problem
====
a)
----
1. 題目給予一個vec<vec<char>>的網絡（grid
生成一個vec<vec<bool>>的visited
來表示這個node是不是檢查過了
//因為DFS有上下左右 可能先前被查過了
2. （看題目）定義DFS的行為:
DFS( grid, visited, i, j, m, n )
->
如果超界, 如果是'0', 如果造訪過了 return
else,
visited改成true
這個node的上下左右去做DFS
3. 回到main（看題目）定義main的行為:
for for grid
如果是'1', 如果還沒造訪過 則
DFS( grid, visited, i, j, m, n )
count++
//因為DFS會做完, 能連到的都連完了, 才跳出
//就找到一個island
//如果for又找到 應該又是全新的island 故重新算重新加
====
class Solution{
void DFS( vec<vec<int>>&grid, vec<vec<bool>>&visited, int i, j, m, n){
if i<0 || j<0 || i>=m || j>=n || visited(i,j) || grid(i,j)!='1'
return
visited(i,j)=true
DFS( grid, visited, i-1, j, m, n)
DFS(i+1
DFS(j-1
DFS(j+1
}
public:
int closedIsland (vec<vec<int>>&grid){
int m=grid.size()
int n=grid[0].size()
vec<vec<bool>> visited(m, vec<bool>(n, false))
int count=0
for i-m
for j-n
if( grid [i][j] == '1' && !visited[i][j] ){
DFS( grid, visited, i, j, m, n)
count++
}
return count
}
};
2022年1月26日 星期三
1376, Time needed to inform all employees
====
1376, Time needed to inform all employees
====
DFS,
Time taken to reach all nodes, or share info to all graph nodes
====
1. 題目給予一個vec<int> manager
=>
生成一份vec<vec<int>> children
or
map<int, vec<int>> children
children用意在紀錄node擁有的child
(可視為hash map
2. 因為children會紀錄所mana<->child關係
所以從root(題目給的headID) 開始DFS
會走過所有node
3. 題目給予一個 vec<int>informTime
定義一個resource 為最終total結果
每次DFS,
一個current為加上目前informTime[i]的時間
每次DFS 比較max(resource, current)
最終return resource
====
class Solution{
int DFS( vec<vec<int>>&child, int node, vec<int>&time){
if child[node].size == 0
return 0
//本次node沒有children, time沒有增加, return
int ans= time[node]
int tempMax= 0
for(auto c: child[node]){
tempMax = max( tempMax, DFS( child, c, informTime)
//如果child有多個 會停在for裡面
//當有找到更大的結果 會丟給tempMax
//當次還沒return就不會被清零
//清零用意只是紀錄當次node子集裡的最大
}
return ans+tempMax
//結果等於 當前的time[node]
//加上
//子集裡面最大的time
}
public:
int numOfMinute( int n, int headID, vec<int>& manager, vec<int>& informTime){
vec<vec<int>> children(n)
for int i=0; i<n; i++
if manager[i] != -1
children[ manager[i] ].push_back(i)
return DFS( children, headID, informTime )
}
訂閱：
文章 (Atom)