Skip to content

Commit fc8850b

Browse files
sclcodersclcoder
committed
动态规划、二叉树的各种遍历
1 parent b8016b7 commit fc8850b

Some content is hidden

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

41 files changed

+3063
-365
lines changed

‎src/com/interviewCode/_1_爬楼梯.java renamed to ‎src/com/interviewCode/_00_偶遇的面试题/_1_爬楼梯.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.interviewCode;
1+
package com.interviewCode._00_偶遇的面试题;
22
public class _1_爬楼梯 {
33
public static void main(String[] args) {
44
/** n阶台阶的走法 每次走m个台阶（m<=n）

‎src/com/interviewCode/_2_Counting_Bits.java renamed to ‎src/com/interviewCode/_00_偶遇的面试题/_2_Counting_Bits.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.interviewCode;
1+
package com.interviewCode._00_偶遇的面试题;
22
import java.util.ArrayList;
33
import java.util.List;
44
public class _2_Counting_Bits {

‎src/com/interviewCode/_3_Balance_scals_array.java renamed to ‎src/com/interviewCode/_00_偶遇的面试题/_3_Balance_scals_array.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.interviewCode;
1+
package com.interviewCode._00_偶遇的面试题;
22
import java.util.ArrayList;
33
import java.util.List;
44

‎src/com/interviewCode/_4_子集.java renamed to ‎src/com/interviewCode/_00_偶遇的面试题/_4_子集.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.interviewCode;
1+
package com.interviewCode._00_偶遇的面试题;
22
import java.util.ArrayList;
33
import java.util.List;
44

‎src/com/interviewCode/_01_数组_排序/_164_最大间距.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package com.interviewCode._01_数组_排序;
2+
3+
/**
4+
* https://leetcode-cn.com/problems/maximum-gap/
5+
*
6+
* 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
7+
* 如果数组元素个数小于 2，则返回 0。
8+
*
9+
* 示例 1:
10+
*
11+
* 输入: [3,6,9,1]
12+
* 输出: 3
13+
* 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
14+
*
15+
* 示例 2:
16+
*
17+
* 输入: [10]
18+
* 输出: 0
19+
* 解释: 数组元素个数小于 2，因此返回 0。
20+
*
21+
* 说明:
22+
*
23+
* 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
24+
* 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
25+
*
26+
*
27+
* 暴力解法并不难实现
28+
* 难点在线性条件下实现，考虑灵活使用指针来实现
29+
*/
30+
public class _164_最大间距 {
31+
public int maximumGap(int[] nums) {
32+
return 0;
33+
}
34+
}

‎src/com/interviewCode/_01_数组_排序/_16_16_部分排序.java

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.interviewCode._01_数组_排序;
2+
3+
/**
4+
* https://leetcode-cn.com/problems/sub-sort-lcci/
5+
* 给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。
6+
* 注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
7+
*
8+
* 示例：
9+
*
10+
* 输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
11+
* 输出： [3,9]
12+
*
13+
* 提示：
14+
* 0 <= len(array) <= 1000000
15+
*
16+
* 查找逆序对
17+
* 正序遍历一次找到升序的逆序对的最右边
18+
* 逆序遍历一次找到降序的逆序对的最左边
19+
*
20+
*/
21+
public class _16_16_部分排序 {
22+
23+
public int[] subSort(int[] array) {
24+
int m = -1;
25+
int n = -1;
26+
27+
if (array.length == 0) return new int[]{m,n};
28+
29+
int max = array[0];
30+
// 正序查找逆序对的最右边
31+
for (int i = 1; i < array.length; i++) {
32+
if (max <= array[i]){
33+
max = array[i];
34+
} else {
35+
// array[i]值小于max，是个逆序对
36+
n = i;
37+
}
38+
}
39+
40+
if (n == -1) return new int[]{m,n}; // 没有逆序对可以直接退出了
41+
// 逆序查找逆序对的最左边
42+
int min = array[array.length - 1];
43+
for (int i = array.length - 2; i >= 0 ; i--) {
44+
if ( array[i] >= min){
45+
min = array[i];
46+
} else {
47+
// array[i]值大于min，是个逆序对
48+
m = i;
49+
}
50+
}
51+
return new int[]{m,n};
52+
}
53+
}

‎src/com/interviewCode/_01_数组_排序/_75_颜色分类.java

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.interviewCode._01_数组_排序;
2+
3+
/**
4+
* https://leetcode-cn.com/problems/sort-colors/
5+
*
6+
* 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
7+
*
8+
* 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
9+
*
10+
* 注意:
11+
* 不能使用代码库中的排序函数来解决这道题。
12+
*
13+
* 示例:
14+
*
15+
* 输入: [2,0,2,1,1,0]
16+
* 输出: [0,0,1,1,2,2]
17+
*
18+
* 进阶：
19+
* 一个直观的解决方案是使用计数排序的两趟扫描算法。
20+
* 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
21+
* 你能想出一个仅使用常数空间的一趟扫描算法吗？
22+
*
23+
* 一趟扫描出结果的算法
24+
* 使用多指针:
25+
* 1 2 0 2 1 2 0 1 2 0 1 2
26+
* 原理: 遇到2向后边交换 遇到0 向前交换 遇到1可以按兵不动
27+
* 定义指针 p0 、p2 分别指向头尾 p0用来标记存放0的空间 p2用来标记用来存放2的空间
28+
* 指针cur作为遍历时的游标
29+
* 当cur == 1 时 跳过 cur++
30+
* 当cur == 0 时 cur 和 p1 交换 p0++ ， cur++
31+
* 当cur == 2 时 cur 和 p2交换数据 p2-- , cur 需要和 p0 比较决定是否向前交换
32+
* 当cur > p2 时迭代结束
33+
*
34+
*
35+
*/
36+
public class _75_颜色分类 {
37+
public void sortColors(int[] nums) {
38+
int p0 = 0;
39+
int p2 = nums.length - 1;
40+
int cur = 0;
41+
42+
while (cur <= p2) {
43+
int v = nums[cur];
44+
45+
if (v == 1) {
46+
cur++;
47+
}
48+
if (v == 0) {
49+
swap(nums, cur, p0);
50+
cur++;
51+
p0++;
52+
}
53+
54+
if (v == 2) {
55+
swap(nums, cur, p2);
56+
p2--;
57+
}
58+
}
59+
}
60+
61+
public void swap(int[] nums, int i , int j){
62+
int temp = nums[i];
63+
nums[i] = nums[j];
64+
nums[j] = temp;
65+
}
66+
}

‎src/com/interviewCode/_01_数组_排序/_88_合并两个有序数组.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package com.interviewCode._01_数组_排序;
2+
3+
/**
4+
* https://leetcode-cn.com/problems/merge-sorted-array/
5+
* 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
6+
* 说明:
7+
* 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
8+
* 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素
9+
* 示例:
10+
*
11+
* 输入:
12+
* nums1 = [1,2,3,0,0,0], m = 3
13+
* nums2 = [2,5,6], n = 3
14+
*
15+
* 输出: [1,2,2,3,5,6]
16+
*
17+
* 使用双(三)指针: 指针p1、p2分别指向数组1、2的元素尾部 指针cur指向数组1的尾部。从后向前遍历比较大小，大者存放的数组1的尾部并更新cur指针位置
18+
* 具体逻辑看代码 画图看
19+
*/
20+
public class _88_合并两个有序数组 {
21+
public void merge(int[] nums1, int m, int[] nums2, int n) {
22+
int p1 = m - 1;
23+
int p2 = n - 1;
24+
int cur = m + n - 1;
25+
while (p2 >= 0) { // p2 < 0 时 说明排序完成，此时num1数组已经全部有序了，即便p1还大于0
26+
if (p1 >= 0 && nums2[p2] < nums1[p1]){ // num1数组数据移动
27+
nums1[cur--] = nums1[p1--];
28+
} else {
29+
nums1[cur--] = nums2[p2--]; // num2数组数据移动
30+
}
31+
}
32+
}
33+
}

‎src/com/interviewCode/_01_数组_排序/_977_有序数组的平方.java

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package com.interviewCode._01_数组_排序;
2+
3+
/**
4+
*
5+
* 给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
6+
*
7+
*
8+
*
9+
* 示例 1：
10+
*
11+
* 输入：[-4,-1,0,3,10]
12+
* 输出：[0,1,9,16,100]
13+
*
14+
* 示例 2：
15+
*
16+
* 输入：[-7,-3,2,3,11]
17+
* 输出：[4,9,9,49,121]
18+
*
19+
*
20+
*
21+
* 提示：
22+
*
23+
* 1 <= A.length <= 10000
24+
* -10000 <= A[i] <= 10000
25+
* A 已按非递减顺序排序。
26+
*
27+
A 已经排好序了，负数部分平方值大到小，非负数部分小到大。
28+
问题就可以转化为类似于88. 合并两个有序数组。
29+
把数组分为两部分，一部分为前0-k的负数部分，另一部分为k+1 - length 的非负数部分。
30+
利用两个指针i，j和创建一个空数组，分别从头遍历负数部分，从尾遍历非负数部分，进行平方值比较。平方值较大的放入空数组尾部，直到 i <= j.
31+
*
32+
*/
33+
public class _977_有序数组的平方 {
34+
public int[] sortedSquares(int[] A) {
35+
if (A == null || A.length == 0) return new int[0];
36+
int l = 0;
37+
int r = A.length - 1;
38+
int cur = r;
39+
40+
int[] result = new int[A.length];
41+
42+
while (l <= r) { // 注意相等时的条件
43+
44+
int lv = A[l] * A[l];
45+
int rv = A[r] * A[r];
46+
47+
if (lv < rv){
48+
result[cur--] = rv;
49+
r--;
50+
} else {
51+
result[cur--] = lv;
52+
l++;
53+
}
54+
}
55+
return result;
56+
}
57+
58+
59+
}

‎src/com/leetcode/binaryTree/Test/TestMorris.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package com.leetcode.binaryTree.Test;
2+
import com.leetcode.binaryTree.com.mj.printer.BinaryTrees;
3+
import com.leetcode.binaryTree.common.BinarySearchTree;
4+
5+
import java.util.Random;
6+
7+
public class TestMorris {
8+
/**
9+
* 一个可以构建一个搜索二叉树的类
10+
*/
11+
private static class MorrisTree extends BinarySearchTree<Integer> {
12+
/**
13+
* morris遍历方法
14+
*/
15+
public void morris(){
16+
Node<Integer> node = root;
17+
while (node != null){
18+
if (node.left != null){
19+
// 寻找前驱节点
20+
Node<Integer> pred = node.left;
21+
while (pred.right != null && pred.right != node){
22+
pred = pred.right;
23+
}
24+
if (pred.right == null){
25+
pred.right = node;
26+
node = node.left;
27+
} else { // pred == node
28+
// 输出node .....
29+
System.out.print(node.element + " ");
30+
pred.right = null;
31+
node = node.right;
32+
}
33+
} else { // node.left == null
34+
// 输出node
35+
System.out.print(node.element + " ");
36+
node = node.right;
37+
}
38+
}
39+
}
40+
}
41+
42+
public static void main(String[] args) {
43+
MorrisTree tree = new MorrisTree();
44+
for (int i = 0; i < 10; i++) {
45+
tree.add(new Random().nextInt(200));
46+
}
47+
BinaryTrees.println(tree);
48+
System.out.println("------------------");
49+
tree.morris();
50+
System.out.println("------------------");
51+
BinaryTrees.println(tree);
52+
}
53+
54+
55+
}

0 commit comments

Comments
 (0)