Skip to content

Commit 674c93d

Browse files
authored
Add files via upload
1 parent fe0ff9f commit 674c93d

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

67 files changed

+1882
-0
lines changed

剑指Offer_Java/Test01.java

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package offer;
2+
3+
// 二维数组中的查找
4+
public class Test01 {
5+
public boolean Find(int target, int[][] array) {
6+
int row = array.length - 1;
7+
int col = 0;
8+
while (row >= 0 && col <= array[0].length - 1) {
9+
if (array[row][col] > target) {
10+
row--;
11+
} else if (array[row][col] < target) {
12+
col++;
13+
} else {
14+
return true;
15+
}
16+
}
17+
return false;
18+
}
19+
}

剑指Offer_Java/Test02.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package offer;
2+
3+
// 替换空格
4+
public class Test02 {
5+
// 通过删增来替换字符串
6+
public String replaceSpace(StringBuffer str) {
7+
for (int i = 0; i < str.length(); i++) {
8+
if (str.charAt(i) == ' ') {
9+
str.deleteCharAt(i);
10+
str.insert(i, "%20");
11+
}
12+
}
13+
return str.toString();
14+
}
15+
16+
// 构造新字符串
17+
public String replaceSpace2(StringBuffer str) {
18+
String res = "";
19+
for (int i = 0; i < str.length(); i++) {
20+
char s = str.charAt(i);
21+
if (s == ' ') {
22+
res += "%20";
23+
} else {
24+
res += s;
25+
}
26+
}
27+
return res;
28+
}
29+
30+
// 调用替换字符串方法
31+
public String replaceSpace3(StringBuffer str) {
32+
return str.toString().replaceAll("\\s", "%20");
33+
}
34+
}

剑指Offer_Java/Test03.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package offer;
2+
3+
import java.util.ArrayList;
4+
5+
/*
6+
class ListNode {
7+
int val;
8+
ListNode next = null;
9+
ListNode(int val) {
10+
this.val = val;
11+
}
12+
}
13+
*/
14+
15+
// 从尾到头打印链表
16+
public class Test03 {
17+
private ArrayList<Integer> list = new ArrayList<Integer>();
18+
19+
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
20+
if (listNode == null) {
21+
return list;
22+
}
23+
printListFromTailToHead(listNode.next);
24+
list.add(listNode.val);
25+
return list;
26+
}
27+
}

剑指Offer_Java/Test04.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package offer;
2+
3+
import java.util.Arrays;
4+
5+
/*
6+
class TreeNode {
7+
int val;
8+
TreeNode left;
9+
TreeNode right;
10+
TreeNode(int x) {
11+
val = x;
12+
}
13+
}
14+
*/
15+
16+
// 重建二叉树
17+
public class Test04 {
18+
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
19+
if (pre.length == 0 || in.length == 0) {
20+
return null;
21+
}
22+
TreeNode root = new TreeNode(pre[0]);
23+
for (int i = 0; i < in.length; i++) {
24+
if (pre[0] == in[i]) {
25+
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
26+
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
27+
}
28+
}
29+
return root;
30+
}
31+
}

剑指Offer_Java/Test05.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package offer;
2+
3+
import java.util.Stack;
4+
5+
// 用两个栈实现队列
6+
public class Test05 {
7+
Stack<Integer> stack1 = new Stack<Integer>();
8+
Stack<Integer> stack2 = new Stack<Integer>();
9+
10+
public void push(int node) {
11+
while (!stack2.isEmpty()) {
12+
stack1.push(stack2.pop());
13+
}
14+
stack1.push(node);
15+
while (!stack1.isEmpty()) {
16+
stack2.push(stack1.pop());
17+
}
18+
}
19+
20+
public int pop() {
21+
return stack2.pop();
22+
}
23+
}

剑指Offer_Java/Test06.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package offer;
2+
3+
// 旋转数组的最小数字
4+
public class Test06 {
5+
public int minNumberInRotateArray(int[] array) {
6+
if (array.length == 0) {
7+
return 0;
8+
}
9+
for (int i = 0; i < array.length - 1; i++) {
10+
if (array[i] > array[i + 1]) {
11+
return array[i + 1];
12+
}
13+
}
14+
return 0;
15+
}
16+
}

剑指Offer_Java/Test07.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package offer;
2+
3+
// 斐波那契数列
4+
// 1,1,2,3,5,8,12
5+
public class Test07 {
6+
// 递推
7+
public int Fibonacci(int n) {
8+
int f0 = 0, f1 = 1;
9+
if (n == 0) {
10+
return f0;
11+
}
12+
if (n == 1) {
13+
return f1;
14+
}
15+
for (int i = 2; i <= n; i++) {
16+
int temp = f0;
17+
f0 = f1;
18+
f1 = temp + f1;
19+
}
20+
return f1;
21+
}
22+
23+
// 递归
24+
public int Fibonacci2(int n) {
25+
int f0 = 0, f1 = 1;
26+
if (n == 0) {
27+
return f0;
28+
}
29+
if (n == 1) {
30+
return f1;
31+
}
32+
return Fibonacci(n - 1) + Fibonacci(n - 2);
33+
}
34+
}

剑指Offer_Java/Test08.java

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package offer;
2+
3+
// 跳台阶
4+
// f(1)=1 f(2)=2 f(3)=3 f(4)=5 f(5)=8
5+
public class Test08 {
6+
public int JumpFloor(int target) {
7+
int a = 1, b = 1;
8+
for (int i = 0; i < target; i++) {
9+
int temp = a;
10+
a = b;
11+
b += temp;
12+
}
13+
return a;
14+
}
15+
}

剑指Offer_Java/Test09.java

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package offer;
2+
3+
// 变态跳台阶
4+
// f(1)=1 f(2)=2 f(3)=4 f(4)=8
5+
// f(n)=2的n-1次方
6+
public class Test09 {
7+
public int JumpFloorII(int target) {
8+
int res = 1;
9+
for (int i = 1; i < target; i++) {
10+
res *= 2;
11+
}
12+
return res;
13+
}
14+
}

剑指Offer_Java/Test10.java

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package offer;
2+
3+
// 矩形覆盖
4+
// 类似斐波那契数列:f(1)=1 f(2)=2 f(3)=3 f(4)=5
5+
public class Test10 {
6+
public int RectCover(int target) {
7+
int a = 0, b = 1;
8+
if (target == 0)
9+
return 0;
10+
for (int i = 0; i < target; i++) {
11+
int temp = a;
12+
a = b;
13+
b += temp;
14+
}
15+
return b;
16+
}
17+
}

0 commit comments

Comments
 (0)