Skip to content

Commit 674c93d

Browse files
linwtlinwt
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+
}

‎剑指Offer_Java/Test11.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package offer;
2+
3+
// 二进制中1的个数
4+
public class Test11 {
5+
public int NumberOf1(int n) {
6+
if (n == 0) return 0;
7+
int num = 0;
8+
while (n != 0) {
9+
num++;
10+
n = n & (n - 1);
11+
}
12+
return num;
13+
}
14+
15+
public int NumberOf12(int n) {
16+
char[] ch = Integer.toBinaryString(n).toCharArray();
17+
int num = 0;
18+
for (char c : ch) {
19+
if (c == '1') num++;
20+
}
21+
return num;
22+
}
23+
}

‎剑指Offer_Java/Test12.java

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package offer;
2+
3+
// 数值的整数次方
4+
public class Test12 {
5+
public double Power(double base, int exponent) {
6+
if (base == 0) {
7+
return 0;
8+
}
9+
if (exponent == 0) {
10+
return 1;
11+
}
12+
double res = 1;
13+
for (int i = 0; i < Math.abs(exponent); i++) {
14+
res *= base;
15+
}
16+
if (exponent < 0) {
17+
res = 1 / res;
18+
}
19+
return res;
20+
}
21+
}

‎剑指Offer_Java/Test13.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package offer;
2+
3+
// 调整数组顺序使奇数位于偶数前面
4+
public class Test13 {
5+
public void reOrderArray(int[] array) {
6+
int len = array.length, l = 0, r = array.length - 1;
7+
int[] res = new int[len];
8+
for (int i = 0; i < len; i++) {
9+
// 逆序获取偶数，从后往前放入新数组
10+
if (array[len - i - 1] % 2 == 0) {
11+
res[r] = array[len - i - 1];
12+
r--;
13+
}
14+
// 顺序获取奇数，从前往后放入新数组
15+
if (array[i] % 2 == 1) {
16+
res[l] = array[i];
17+
l++;
18+
}
19+
}
20+
for (int i = 0; i < len; i++) {
21+
array[i] = res[i];
22+
}
23+
}
24+
}

‎剑指Offer_Java/Test14.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 ListNode {
5+
int val;
6+
ListNode next = null;
7+
8+
ListNode(int val) {
9+
this.val = val;
10+
}
11+
}
12+
*/
13+
14+
// 链表中倒数第k个结点
15+
public class Test14 {
16+
public ListNode FindKthToTail(ListNode head, int k) {
17+
if (head == null || k == 0) {
18+
return null;
19+
}
20+
ListNode slow = head, fast = head;
21+
for (int i = 1; i < k; i++) {
22+
if (fast.next != null) {
23+
fast = fast.next;
24+
} else {
25+
return null;
26+
}
27+
}
28+
while (fast.next != null) {
29+
fast = fast.next;
30+
slow = slow.next;
31+
}
32+
return slow;
33+
}
34+
}

‎剑指Offer_Java/Test15.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package offer;
2+
3+
/*
4+
public class ListNode {
5+
int val;
6+
ListNode next = null;
7+
8+
ListNode(int val) {
9+
this.val = val;
10+
}
11+
}*/
12+
13+
// 反转链表
14+
public class Test15 {
15+
public ListNode ReverseList(ListNode head) {
16+
if (head == null) {
17+
return null;
18+
}
19+
ListNode pre = null, after = null;
20+
while (head != null) {
21+
after = head.next;
22+
head.next = pre;
23+
pre = head;
24+
head = after;
25+
}
26+
return pre;
27+
}
28+
}

0 commit comments

Comments
 (0)