Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5791d79

Browse files
committed
commit changes to gh-pages aug 21
1 parent54baa3c commit5791d79

File tree

6 files changed

+77
-7
lines changed
  • _includes/_root
  • populating-next-right-pointers-in-each-node
  • populating-next-right-pointers-in-each-node-ii
  • word-break

6 files changed

+77
-7
lines changed
Lines changed: 28 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,30 @@
1+
##Improved version of[Populating Next Right Pointers in Each Node](../populating-next-right-pointers-in-each-node)
12

2-
##TODO
3-
* write down thinking
3+
This time, finding next is a bit difficult.
4+
`node.right.next = node.next.left` is no longer working.
45

6+
But parent's next is also useful, and only need to seach a little more nodes.
7+
8+
```
9+
1
10+
/ \
11+
2 3
12+
\ \
13+
4 5
14+
/ / \
15+
6 7 8
16+
```
17+
18+
*`6.next` =`7` =`5.left` =`4.next.left`
19+
*`4.next` =`5` =`3.right` =`2.next.right`
20+
21+
Searching path is like
22+
23+
* node's parent's left
24+
* node's parent's right
25+
* take node's parent's next as parent and search again
26+
27+
28+
Note:
29+
30+
`connect(right)` before`connect(left)`, because`left nodes` depend on`right nodes' next`

‎_includes/_root/populating-next-right-pointers-in-each-node/README.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,8 @@
1+
##First glance
2+
3+
It would be an easy problem if[Binary Tree Level Order Traversal](../binary-tree-level-order-traversal) works.
4+
Yet, a queue is not allow because of that constant space is required.
5+
16
##Recursion
27

38
connecting left and right child is easy, just`node.left.next = node.right`

‎_includes/_root/word-break/README.md

Lines changed: 39 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,41 @@
1+
##All break
12

2-
##TODO
3-
* write down thinking
3+
Brute force is my favourite. However,`2 ^ n` seems a huge number.
44

5+
6+
##Something like[Jump Game II](../jump-game-ii)
7+
8+
That`s[0..i]` can be`break` indicates`s[i + each d in dict]` can be`break`.
9+
10+
Make a table`P`, such that,`P[i]` means if`s[0..i]` can be`break`.
11+
12+
```
13+
dict { leet, code }
14+
15+
Table:
16+
17+
0 1 2 3 4 5 6 7 8 Index
18+
* l e e t c o d e
19+
1 0 0 0 1 0 0 0 1
20+
21+
```
22+
23+
Calculating`P[i]`
24+
25+
```
26+
dict { leet, code }
27+
28+
Table:
29+
30+
0 1 2 3 4 5 6 7 8 Index
31+
* l e e t c o d e
32+
1 0 0 0 1 ? ? ? ?
33+
^
34+
i
35+
```
36+
37+
here if`P[i]` wants to be true, either`s[0..i]``(leetc)` or`s[4..i]``(c)` must be in the dict.
38+
39+
So,
40+
41+
`P[i] = P[0..j] && s[j..i] in dict, j = 0..i`

‎populating-next-right-pointers-in-each-node-ii/index.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,8 @@
11
---
22
layout:solution
33
title:Populating Next Right Pointers in Each Node II
4-
date:2014-07-23 02:42:48 +0800
4+
date:2014-08-20 17:35:02 +0800
5+
eaten:true
56
---
67
{% assign leetcode_name = {{page.path | remove: '/index.md'}} %}
78
{% assign leetcode_readme = {{leetcode_name | append: '/README.md' | prepend: '_root/' }} %}

‎populating-next-right-pointers-in-each-node/index.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
---
22
layout:solution
33
title:Populating Next Right Pointers in Each Node
4-
date:2014-08-12 19:19:37 +0800
4+
date:2014-08-20 16:49:17 +0800
55
eaten:true
66
---
77
{% assign leetcode_name = {{page.path | remove: '/index.md'}} %}

‎word-break/index.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,8 @@
11
---
22
layout:solution
33
title:Word Break
4-
date:2014-07-23 02:42:48 +0800
4+
date:2014-08-20 19:53:59 +0800
5+
eaten:true
56
---
67
{% assign leetcode_name = {{page.path | remove: '/index.md'}} %}
78
{% assign leetcode_readme = {{leetcode_name | append: '/README.md' | prepend: '_root/' }} %}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp