Fork me on GitHub

MS 100题-1

1.把二元查找树转变成排序的双向链表(树)

思路:

  1. 中序递归遍历的方式,将前驱后继相连,因为 Java 是引用传递,所以需要在返回值处更新 PNode 值。
  2. 本处使用了 lombok,所以 idea 要提前安装 lombok 插件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.ToString;
import org.junit.Test;

public class BST2List {

@Test
public void testList(){
BSTreeNode pNode = null,pHead;
BSTreeNode node1 = new BSTreeNode(1,null,null);
BSTreeNode node3 = new BSTreeNode(3,null,null);
BSTreeNode node2 = new BSTreeNode(2,node1,node3);
BSTreeNode node5 = new BSTreeNode(5,null,null);
BSTreeNode node7 = new BSTreeNode(7,null,null);
BSTreeNode node6 = new BSTreeNode(6,node5,node7);
BSTreeNode root = new BSTreeNode(4,node2,node6);

pHead = converts(root,pNode);
while(pHead != null && pHead.left != null){
pHead = pHead.left; // 回溯到链表头
}
while(pHead!=null){
System.out.print(pHead.value+" ");
pHead = pHead.right;
}
System.out.println();

}

/**
*
* @param root
* @param pNode 当前 root 的前驱结点
*/
private BSTreeNode converts(BSTreeNode root, BSTreeNode pNode) {
if(null == root){
return pNode;
}
BSTreeNode pCur = root;

// 递归左子树
if(pCur.left != null){
pNode = converts(pCur.left,pNode);
}

// 左右相连
pCur.left = pNode;
if(pNode != null){
pNode.right = pCur;
}
// 更新前驱结点
pNode = pCur;


// 递归右子树
if(pCur.right!= null){
pNode = converts(pCur.right,pNode);
}
return pNode;
}

@Data
@AllArgsConstructor
@ToString
public class BSTreeNode{
int value;
BSTreeNode left;
BSTreeNode right;
}
}

2. 求子数组的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import org.junit.Test;

/**
* 输入一个整形数组,数组里有正数也有负数。
* 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
* 求所有子数组的和的最大值。要求时间复杂度为 O(n)。
例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为 3, 10, -4, 7, 2, 因此输出为该子数组的和 18。
*/
public class 求子数组的最大和 {

@Test
public void findMax(){
int[] a = {1,-2,3,10,-4,7,2,-5};
int[] sum = new int[a.length];
int max = Integer.MIN_VALUE;
sum[0] = a[0];
for(int i = 1;i<a.length;++i){
sum[i] = Math.max(a[i],sum[i-1]+a[i]);
if(sum[i]>max){
max = sum[i];
}
}
System.out.println(max);
}
}

3. 多线程顺序打印0~100

输入数字N,使用N个线程执行打印操作,要求顺序打印0~100之间的数字
以 N=4 为例,格式为:

线程 0 打印数字 0
线程 1 打印数字 1
线程 2 打印数字 2
线程 3 打印数字 3
线程 0 打印数字 4
线程 1 打印数字 5

线程 3 打印数字 99

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

import java.util.Scanner;

/**
* 多线程顺序打印0~100
*/
public class thread implements Runnable {

private String name;
private int threadId;
private static Object object; // 静态对象用于上锁
private static int count = 0; // 静态变量用于计数
private int totalCount;


public thread(Object object,String name, int threadId, int totalCount) {
this.object = object;
this.name = name;
this.threadId = threadId;
this.totalCount = totalCount;
}

@Override
public void run() {

synchronized (object) {
while (count < 100) {
if (count % totalCount == threadId) {
System.out.println(this.name + " 打印数字 " + count);
++count;
object.notifyAll();
} else {
try {
object.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Object object = new Object();
int N = sc.nextInt();
if (N == 0) {
return;
}

for (int i = 0; i < N; ++i) {
new Thread(new thread(object,"线程 " + i, i, N)).start();
}
}
}

4. 最大数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import org.apache.commons.lang.ArrayUtils;
import org.junit.Test;

import java.util.*;

/**
*
* 输入一个非负的整形数组,然后输出使用输入数组里的元素组合成的最大数字
* 如:输入[45, 9 ,7],输出字符串 “9745”
* 另外,输入数组可以有重复的数字
*/

public class test01 {


@Test
public void getResult(){
int[] num = {45,729,72};
String[] numStr = new String[num.length];

if(ArrayUtils.isEmpty(num)){
return;
}
for(int i = 0;i<num.length;++i){
numStr[i] = String.valueOf(num[i]);
}
Arrays.sort(numStr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
});
for(int i = 0;i<num.length;++i){
System.out.print(numStr[i]);
}

}
}

5. 在二元树中找出和为某一值的所有路径(树)

例如 输入整数 22 和如下二元树
10
/ \
5 12
/ \
4 7

则打印出两条路径: 10, 12 和 10, 5, 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
/**
* DFS 遍历的方式,叶节点处满足条件,则直接打印返回
* 注意 list 中元素的进出时机
*
*/
public class 和为某值的所有路径 {

static List<Integer> list = new ArrayList<>();

@Test
public void testResult() {
TreeNode node4 = new TreeNode(4, null, null);
TreeNode node7 = new TreeNode(7, null, null);
TreeNode node5 = new TreeNode(5, node4, node7);
TreeNode node12 = new TreeNode(12, null, null);
TreeNode node10 = new TreeNode(10, node5, node12);
int target = 22;
int sum = 0;
getResult(node10, target, sum);
}

private void getResult(TreeNode root, int target, int sum) {
if (root == null) {
return;
}
if (sum + root.val > target) {
return;
}
list.add(root.val);
if (root.left == null && root.right == null) {
if (sum + root.val == target) {
printList(list);
}
list.remove(list.size() - 1);
return;
}
getResult(root.left, target, sum + root.val);
getResult(root.right, target, sum + root.val);
list.remove(list.size() - 1);

}

private void printList(List<Integer> list) {
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println();
}

@Data
@AllArgsConstructor
@NoArgsConstructor
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}
}
-------------The End-------------