Fork me on GitHub

MS 100题-1

Posted on | Edited on | In | Views:

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
73
74

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
27

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
40

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
72

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