Lego time lapse

Lego time lapse:

----

https://www.google.com/amp/s/www.pro-lapse.com/how-to-shoot-a-lego-time-lapse-video/amp/

Time-Lapse calculate:

----

https://www.pro-lapse.com/time-lapse-calculator/?_gl=1*jdhck0*_ga*YW1wLURMWUVwUWxJbEZVbnJZTDd4VWJTMDNkN085OGdIQW4yUWNYSHNzMmNVQW5KR21RSzdFTGV3M08zNl9wTVN2bzI.

那些年我們追的韓劇韓綜 -2020

12月

====

Seoul connects u: g-idle

Seoul connects u: oh my girl

11月

====

百日的郎君

Bvndit roadview trip

10月

====

Bu:QUEST of itzy

轄區現場

9月

====

Weeekly we clear

我的大叔

8月

7月

6月

====

今生是第一次

5月

====

Let's go your with bvndit

Bvndit dingo 엄마의 영상편지

4月

3月

====

愛的迫降

2月

1月

====

金秘書為何那樣

德魯納酒店

love playlist season 3

playlist. Just one bite

playlist. In seoul

playlist. W.H.Y

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

  }

}

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

  }

}

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

  }

}

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

  }

}