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
Appearance settings

Commit 74251ca

Browse filesBrowse files
author
王俊超
committed
commit
1 parent f852a8b commit 74251ca
Copy full SHA for 74251ca

File tree

Expand file treeCollapse file tree

12 files changed

+339
-14
lines changed
Filter options
Expand file treeCollapse file tree

12 files changed

+339
-14
lines changed

‎.idea/misc.xml

Copy file name to clipboardExpand all lines: .idea/misc.xml
+1-14Lines changed: 1 addition & 14 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/modules.xml

Copy file name to clipboardExpand all lines: .idea/modules.xml
+4Lines changed: 4 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎【231】【Power of Two】/src/Solution.java

Copy file name to clipboard
+28Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
* @author: wangjunchao(王俊超)
3+
* @time: 2018-10-09 09:24
4+
**/
5+
public class Solution {
6+
public boolean isPowerOfTwo(int n) {
7+
if (n < 1) {
8+
return false;
9+
}
10+
11+
int remainder;
12+
boolean result = false;
13+
while (n > 0) {
14+
// 求余数
15+
remainder = n % 2;
16+
n >>>= 1;
17+
18+
if (n == 0 && remainder == 1) {
19+
result = true;
20+
break;
21+
} else if (n > 0 && remainder == 1) {
22+
break;
23+
}
24+
}
25+
26+
return result;
27+
}
28+
}

‎【231】【Power of Two】/src/Test.java

Copy file name to clipboard
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
/**
2+
* @author: wangjunchao(王俊超)
3+
* @time: 2018-10-09 09:28
4+
**/
5+
public class Test {
6+
public static void main(String[] args) {
7+
Solution solution = new Solution();
8+
9+
System.out.println(solution.isPowerOfTwo(-1));
10+
System.out.println(solution.isPowerOfTwo(0));
11+
System.out.println(solution.isPowerOfTwo(1));
12+
System.out.println(solution.isPowerOfTwo(2));
13+
System.out.println(solution.isPowerOfTwo(16));
14+
System.out.println(solution.isPowerOfTwo(218));
15+
}
16+
}

‎【232】【Implement Queue using Stacks】/src/MyQueue.java

Copy file name to clipboard
+56Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
import java.util.LinkedList;
2+
import java.util.List;
3+
import java.util.Queue;
4+
5+
/**
6+
* @author: wangjunchao(王俊超)
7+
* @time: 2018-10-09 09:37
8+
**/
9+
class MyQueue {
10+
11+
private List<Integer> list;
12+
13+
/**
14+
* Initialize your data structure here.
15+
*/
16+
public MyQueue() {
17+
list = new LinkedList<>();
18+
}
19+
20+
/**
21+
* Push element x to the back of queue.
22+
*/
23+
public void push(int x) {
24+
list.add(x);
25+
}
26+
27+
/**
28+
* Removes the element from in front of queue and returns that element.
29+
*/
30+
public int pop() {
31+
return list.remove(0);
32+
}
33+
34+
/**
35+
* Get the front element.
36+
*/
37+
public int peek() {
38+
return list.get(0);
39+
}
40+
41+
/**
42+
* Returns whether the queue is empty.
43+
*/
44+
public boolean empty() {
45+
return list.isEmpty();
46+
}
47+
}
48+
49+
/**
50+
* Your MyQueue object will be instantiated and called as such:
51+
* MyQueue obj = new MyQueue();
52+
* obj.push(x);
53+
* int param_2 = obj.pop();
54+
* int param_3 = obj.peek();
55+
* boolean param_4 = obj.empty();
56+
*/

‎【232】【Implement Queue using Stacks】/src/Test.java

Copy file name to clipboard
+15Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
/**
2+
* @author: wangjunchao(王俊超)
3+
* @time: 2018-10-09 10:58
4+
**/
5+
public class Test {
6+
public static void main(String[] args) {
7+
MyQueue queue = new MyQueue();
8+
queue.push(1);
9+
queue.push(2);
10+
11+
System.out.println(queue.peek());
12+
System.out.println(queue.pop());
13+
System.out.println(queue.empty());
14+
}
15+
}

‎【234】【Palindrome Linked List】/src/ListNode.java

Copy file name to clipboard
+12Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
/**
2+
* @author: wangjunchao(王俊超)
3+
* @time: 2018-10-09 11:03
4+
**/
5+
public class ListNode {
6+
int val;
7+
ListNode next;
8+
9+
ListNode(int x) {
10+
val = x;
11+
}
12+
}

‎【234】【Palindrome Linked List】/src/Solution.java

Copy file name to clipboard
+58Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
/**
2+
* O(n) time and O(1) space
3+
* <pre>
4+
* 1->2->2->1
5+
* 1->2->3->2->1
6+
* 先找到第二个2的位置，将2及后面的链逆转，形成新的链A，再按A与原来的链，从头开开始比较
7+
* </pre>
8+
*
9+
* @author: wangjunchao(王俊超)
10+
* @time: 2018-10-09 11:02
11+
**/
12+
public class Solution {
13+
public boolean isPalindrome(ListNode head) {
14+
15+
// 没有节点或者只有一个结点
16+
if (head == null || head.next == null) {
17+
return true;
18+
}
19+
20+
int count = 0;
21+
ListNode node = head;
22+
while (node != null) {
23+
count++;
24+
node = node.next;
25+
}
26+
27+
// 找反向链的起始位置
28+
count = (count + 1) / 2;
29+
node = head;
30+
while (count >0) {
31+
count--;
32+
node = node.next;
33+
}
34+
35+
36+
ListNode reverseHead = new ListNode(0);
37+
ListNode temp;
38+
while (node != null) {
39+
temp = node.next;
40+
node.next = reverseHead.next;
41+
reverseHead.next = node;
42+
node = temp;
43+
}
44+
45+
reverseHead = reverseHead.next;
46+
47+
while (reverseHead != null) {
48+
if (head.val != reverseHead.val) {
49+
return false;
50+
}
51+
52+
reverseHead = reverseHead.next;
53+
head = head.next;
54+
}
55+
56+
return true;
57+
}
58+
}

‎【234】【Palindrome Linked List】/src/Solution2.java

Copy file name to clipboard
+38Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/**
2+
* O(n) time and O(n) space
3+
*
4+
* @author: wangjunchao(王俊超)
5+
* @time: 2018-10-09 11:02
6+
**/
7+
public class Solution2 {
8+
public boolean isPalindrome(ListNode head) {
9+
10+
if (head == null) {
11+
return true;
12+
}
13+
14+
// 反向链的头
15+
ListNode reverseHead = new ListNode(-1);
16+
17+
ListNode temp = head;
18+
ListNode node;
19+
// 头插法构建反向链
20+
while (temp != null) {
21+
node = new ListNode(temp.val);
22+
node.next = reverseHead.next;
23+
reverseHead.next = node;
24+
temp = temp.next;
25+
}
26+
27+
reverseHead = reverseHead.next;
28+
while (head != null) {
29+
if (head.val != reverseHead.val) {
30+
return false;
31+
}
32+
33+
head = head.next;
34+
reverseHead = reverseHead.next;
35+
}
36+
return true;
37+
}
38+
}

‎【234】【Palindrome Linked List】/src/Test.java

Copy file name to clipboard
+42Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
* @author: wangjunchao(王俊超)
3+
* @time: 2018-10-09 11:10
4+
**/
5+
public class Test {
6+
public static void main(String[] args) {
7+
test1();
8+
test2();
9+
test3();
10+
}
11+
12+
public static void test1() {
13+
Solution solution = new Solution();
14+
ListNode head = new ListNode(1);
15+
head.next = new ListNode(2);
16+
System.out.println(solution.isPalindrome(head));
17+
}
18+
19+
public static void test2() {
20+
Solution solution = new Solution();
21+
22+
ListNode head = new ListNode(1);
23+
head.next = new ListNode(2);
24+
head.next.next= new ListNode(2);
25+
head.next.next.next= new ListNode(1);
26+
head.next.next.next.next= new ListNode(2);
27+
head.next.next.next.next.next= new ListNode(2);
28+
head.next.next.next.next.next.next= new ListNode(1);
29+
System.out.println(solution.isPalindrome(head));
30+
}
31+
32+
public static void test3() {
33+
Solution solution = new Solution();
34+
35+
ListNode head = new ListNode(1);
36+
head.next = new ListNode(2);
37+
head.next.next= new ListNode(2);
38+
head.next.next.next= new ListNode(1);
39+
40+
System.out.println(solution.isPalindrome(head));
41+
}
42+
}

‎【235】【Lowest Common Ancestor of a Binary Search Tree】/src/Solution.java

Copy file name to clipboard
+56Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
import java.util.ArrayList;
2+
import java.util.List;
3+
4+
/**
5+
* Definition for a binary tree node.
6+
* <pre>
7+
* public class TreeNode {
8+
* int val;
9+
* TreeNode left;
10+
* TreeNode right;
11+
* TreeNode(int x) { val = x; }
12+
* }
13+
* </pre>
14+
*
15+
* @author: wangjunchao(王俊超)
16+
* @time: 2018-10-09 11:32
17+
*/
18+
class Solution {
19+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
20+
21+
List<TreeNode> pPath = new ArrayList<>();
22+
List<TreeNode> qPath = new ArrayList<>();
23+
24+
search(pPath, root, p);
25+
search(qPath, root, q);
26+
27+
TreeNode ancestor = pPath.get(0);
28+
29+
int idx = 1;
30+
while (idx < pPath.size() && idx < qPath.size()) {
31+
p = pPath.get(idx);
32+
q = qPath.get(idx);
33+
if (p != null && q != null && p.val == q.val) {
34+
ancestor = pPath.get(idx);
35+
idx++;
36+
} else {
37+
break;
38+
}
39+
}
40+
41+
return ancestor;
42+
}
43+
44+
public void search(List<TreeNode> path, TreeNode root, TreeNode node) {
45+
path.add(root);
46+
47+
if (root != null) {
48+
if (root.val > node.val) {
49+
search(path, root.left, node);
50+
}
51+
if (root.val < node.val) {
52+
search(path, root.right, node);
53+
}
54+
}
55+
}
56+
}

‎【235】【Lowest Common Ancestor of a Binary Search Tree】/src/TreeNode.java

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
/**
2+
* @author: wangjunchao(王俊超)
3+
* @time: 2018-10-09 11:33
4+
**/
5+
public class TreeNode {
6+
int val;
7+
TreeNode left;
8+
TreeNode right;
9+
10+
TreeNode(int x) {
11+
val = x;
12+
}
13+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.