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

Commit12e004c

Browse files
author
applewjg
committed
add
Change-Id: Ib581f574559afe39c0f5e22fb79ffec45a3f56bf
1 parent950f25f commit12e004c

File tree

4 files changed

+309
-0
lines changed

4 files changed

+309
-0
lines changed

‎BinaryTreePreorderTraversal.java

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 25, 2014
4+
Problem: Binary Tree Preorder Traversal
5+
Difficulty: Easy
6+
Source: http://oj.leetcode.com/problems/binary-tree-preorder-traversal/
7+
Notes:
8+
Given a binary tree, return the preorder traversal of its nodes' values.
9+
For example:
10+
Given binary tree {1,#,2,3},
11+
1
12+
\
13+
2
14+
/
15+
3
16+
return [1,2,3].
17+
Note: Recursive solution is trivial, could you do it iteratively?
18+
19+
Solution: 1. Iterative way (stack). Time: O(n), Space: O(n).
20+
2. Recursive solution. Time: O(n), Space: O(n).
21+
3. Threaded tree (Morris). Time: O(n), Space: O(1).
22+
*/
23+
24+
/**
25+
* Definition for binary tree
26+
* public class TreeNode {
27+
* int val;
28+
* TreeNode left;
29+
* TreeNode right;
30+
* TreeNode(int x) { val = x; }
31+
* }
32+
*/
33+
publicclassSolution {
34+
publicList<Integer>preorderTraversal_1(TreeNoderoot) {
35+
List<Integer>res =newArrayList<Integer>();
36+
if(root ==null)returnres;
37+
res.add(root.val);
38+
List<Integer>left =preorderTraversal(root.left);
39+
List<Integer>right =preorderTraversal(root.right);
40+
res.addAll(left);
41+
res.addAll(right);
42+
returnres;
43+
}
44+
publicvoidpreorderTraversalRe(TreeNoderoot,List<Integer>res) {
45+
if (root ==null)return;
46+
res.add(root.val);
47+
preorderTraversalRe(root.left,res);
48+
preorderTraversalRe(root.right,res);
49+
}
50+
publicList<Integer>preorderTraversal_2(TreeNoderoot) {
51+
List<Integer>res =newArrayList<Integer>();
52+
if(root ==null)returnres;
53+
preorderTraversalRe(root,res);
54+
returnres;
55+
}
56+
publicList<Integer>preorderTraversal_3(TreeNoderoot) {
57+
List<Integer>res =newArrayList<Integer>();
58+
if(root ==null)returnres;
59+
Stack<TreeNode>stk =newStack<TreeNode>();
60+
stk.push(root);
61+
while (stk.isEmpty() ==false) {
62+
TreeNodecur =stk.pop();
63+
res.add(cur.val);
64+
if (cur.right !=null)stk.push(cur.right);
65+
if (cur.left !=null)stk.push(cur.left);
66+
}
67+
returnres;
68+
}
69+
publicList<Integer>preorderTraversal_4(TreeNoderoot) {
70+
List<Integer>res =newArrayList<Integer>();
71+
if(root ==null)returnres;
72+
Stack<TreeNode>stk =newStack<TreeNode>();
73+
TreeNodecur =root;
74+
while (stk.isEmpty() ==false ||cur !=null) {
75+
if (cur !=null) {
76+
stk.push(cur);
77+
res.add(cur.val);
78+
cur =cur.left;
79+
}else {
80+
cur =stk.pop();
81+
cur =cur.right;
82+
}
83+
}
84+
returnres;
85+
}
86+
publicList<Integer>preorderTraversal_5(TreeNoderoot) {
87+
List<Integer>res =newArrayList<Integer>();
88+
if(root ==null)returnres;
89+
TreeNodecur =root;
90+
while (cur) {
91+
if (cur.left ==null) {
92+
res.add(cur.val);
93+
cur =cur.right;
94+
}else {
95+
TreeNodenode =cur.left;
96+
while (node.right !=null &&node.right !=cur)
97+
node =node.right;
98+
if (node ==null) {
99+
node.right =cur;
100+
res.add(cur.val);
101+
cur =cur.left;
102+
}else {
103+
node.right =null;
104+
cur =cur.right;
105+
}
106+
}
107+
}
108+
returnres;
109+
}
110+
}

‎RotateImage.java

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 25, 2014
4+
Problem: Rotate Image
5+
Difficulty: Easy
6+
Source: https://oj.leetcode.com/problems/rotate-image/
7+
Notes:
8+
You are given an n x n 2D matrix representing an image.
9+
Rotate the image by 90 degrees (clockwise).
10+
Follow up:
11+
Could you do this in-place?
12+
13+
Solution: 1. 123 -> 147 -> 741 (preferable)
14+
456 258 852
15+
789 369 963
16+
2. Rotate one-fourth of the image clockwise.
17+
*/
18+
publicclassSolution {
19+
publicvoidrotate_1(int[][]matrix) {
20+
intn =matrix.length;
21+
if (n <=1)return;
22+
for(inti=0;i<n;i++){
23+
for(intj=0;j<i;j++){
24+
inttmp =matrix[i][j];
25+
matrix[i][j]=matrix[j][i];
26+
matrix[j][i]=tmp;
27+
}
28+
}
29+
30+
for(inti=0;i<n;i++){
31+
for(intj=0;j<n/2;j++){
32+
inttmp =matrix[i][j];
33+
matrix[i][j]=matrix[i][n-1-j];
34+
matrix[i][n-1-j] =tmp;
35+
}
36+
}
37+
}
38+
publicvoidrotate_2(int[][]matrix) {
39+
intn =matrix.length;
40+
if (n <=1)return;
41+
intlevel =0;
42+
while (level <n /2) {
43+
for (inti =level;i <n -1 -level; ++i) {
44+
inttmp =matrix[i][level];
45+
matrix[i][level] =matrix[n -1 -level][i];
46+
matrix[n -1 -level][i] =matrix[n -1 -i][n -1 -level];
47+
matrix[n -1 -i][n -1 -level] =matrix[level][n -1 -i];
48+
matrix[level][n -1 -i] =tmp;
49+
}
50+
++level;
51+
}
52+
}
53+
}

‎RotateList.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 25, 2014
4+
Problem: Rotate List
5+
Difficulty: Easy
6+
Source: https://oj.leetcode.com/problems/rotate-list/
7+
Notes:
8+
Given a list, rotate the list to the right by k places, where k is non-negative.
9+
10+
For example:
11+
Given 1->2->3->4->5->NULL and k = 2,
12+
return 4->5->1->2->3->NULL.
13+
14+
Solution: Notice that k can be larger than the list size (k % list_size).
15+
This solution traverses the list twice at most.
16+
*/
17+
18+
/**
19+
* Definition for singly-linked list.
20+
* struct ListNode {
21+
* int val;
22+
* ListNode *next;
23+
* ListNode(int x) : val(x), next(NULL) {}
24+
* };
25+
*/
26+
/**
27+
* Definition for singly-linked list.
28+
* public class ListNode {
29+
* int val;
30+
* ListNode next;
31+
* ListNode(int x) {
32+
* val = x;
33+
* next = null;
34+
* }
35+
* }
36+
*/
37+
publicclassSolution {
38+
publicListNoderotateRight(ListNodehead,intk) {
39+
if (head ==null)returnhead;
40+
intn =1;
41+
ListNodetail =head,cur =head;
42+
while (tail.next !=null) {
43+
tail =tail.next;
44+
++n;
45+
}
46+
k =k %n;
47+
if (k ==0)returnhead;
48+
for (inti =0;i <n -k -1; ++i)
49+
cur =cur.next;
50+
ListNodenewHead =cur.next;
51+
tail.next =head;
52+
cur.next =null;
53+
returnnewHead;
54+
}
55+
}

‎ScrambleString.java

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 25, 2014
4+
Problem: Scramble String
5+
Difficulty: Medium
6+
Source: https://oj.leetcode.com/problems/scramble-string/
7+
Notes:
8+
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
9+
Below is one possible representation of s1 = "great":
10+
great
11+
/ \
12+
gr eat
13+
/ \ / \
14+
g r e at
15+
/ \
16+
a t
17+
To scramble the string, we may choose any non-leaf node and swap its two children.
18+
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
19+
rgeat
20+
/ \
21+
rg eat
22+
/ \ / \
23+
r g e at
24+
/ \
25+
a t
26+
We say that "rgeat" is a scrambled string of "great".
27+
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
28+
rgtae
29+
/ \
30+
rg tae
31+
/ \ / \
32+
r g ta e
33+
/ \
34+
t a
35+
We say that "rgtae" is a scrambled string of "great".
36+
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
37+
38+
Solution: 1. Recursion + pruning.
39+
2. 3-dimensional dp.
40+
'dp[k][i][j] == true' means string s1(start from i, length k) is a scrambled string of string s2(start from j, length k).
41+
*/
42+
publicclassSolution {
43+
publicbooleanisScramble_1(Strings1,Strings2) {
44+
if (s1.compareTo(s2) ==0)returntrue;
45+
if (s1.length() !=s2.length())returnfalse;
46+
returnisScrambleRe(s1,s2);
47+
}
48+
publicbooleanisScrambleRe(Strings1,Strings2) {
49+
if (hasSameLetters(s1,s2) ==false)returnfalse;
50+
intlen =s1.length();
51+
if (len ==0 ||len ==1)returntrue;
52+
for (inti =1;i <len; ++i) {
53+
if (isScrambleRe(s1.substring(0,i),s2.substring(0,i))
54+
&&isScrambleRe(s1.substring(i),s2.substring(i))
55+
||isScrambleRe(s1.substring(0,i),s2.substring(len-i))
56+
&&isScrambleRe(s1.substring(i),s2.substring(0,len-i))) {
57+
returntrue;
58+
}
59+
}
60+
returnfalse;
61+
}
62+
publicbooleanhasSameLetters(Strings1,Strings2) {
63+
if (s1.compareTo(s2) ==0)returntrue;
64+
if (s1.length() !=s2.length())returnfalse;
65+
int[]count =newint[256];
66+
for (inti =0;i <s1.length(); ++i)count[(int)s1.charAt(i)]++;
67+
for (inti =0;i <s2.length(); ++i)count[(int)s2.charAt(i)]--;
68+
for (inti =0;i <256; ++i)
69+
if (count[i] !=0)returnfalse;
70+
returntrue;
71+
}
72+
publicbooleanisScramble(Strings1,Strings2) {
73+
if (s1.compareTo(s2) ==0)returntrue;
74+
if (s1.length() !=s2.length())returnfalse;
75+
intN =s1.length();
76+
boolean[][][]dp =newboolean[N+1][N][N];
77+
for (intk =1;k <=N; ++k) {
78+
for (inti =0;i <=N -k; ++i) {
79+
for (intj =0;j <=N -k; ++j) {
80+
dp[k][i][j] =false;
81+
if (k ==1)dp[1][i][j] = (s1.charAt(i) ==s2.charAt(j));
82+
for (intp =1;p <k && !dp[k][i][j]; ++p) {
83+
if (dp[p][i][j] &&dp[k-p][i+p][j+p] ||dp[p][i][j+k-p] &&dp[k-p][i+p][j])
84+
dp[k][i][j] =true;
85+
}
86+
}
87+
}
88+
}
89+
returndp[N][0][0];
90+
}
91+
}

0 commit comments

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