笔试题

一共五题，第一道简单/普通难度，第二道普通难度，三四五大概是普通/困难吧．

分组交换链表

一个链表两个一组，前后两组交换，递归

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
class ListNode {
	int val;
	ListNode next = null;
}

public class Solution {
	public ListNode reorderList(ListNode head) {
		// 跳出
		if (head == null) {
			return head;
		} else if (head.next == null) {
			return head;
		} else if (head.next.next == null) {
			return head;
		} else if (head.next.next.next == null) {
			return head;
		}
		// 递归到最后
		ListNode nextHead = reorderList(head.next.next.next.next);
		ListNode thirdNode = head.next.next;
		thirdNode.next.next = head;
		head.next.next = nextHead;
		return thirdNode;
	}
}

可能的字符串

在每个字符串中选择一个字符，组成所有自负不重复的子字符串

例如 ab,ca,ccb –> acb , bac

很明显用回溯算法，但是没写出来，只好用暴力解法，结果超时.

下面是一个四不像．

edit : 第二天再写，只花了五分钟就改好了（果然还是考试时太着急了点），下面是成品（没有跑太多测试）：

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
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Solution {

	public int result = 0;
	public int sumFloor;

	public List<String> handleInput() {
		List<String> list = new ArrayList<String>();
		// 输入handle
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		in.nextLine();
		for (int i = 0; i < n; i++) {
			list.add(in.nextLine());
		}
		in.close();
		return list;
	}

	public int findSubString(List<String> ss) {
		Set<Character> stack = new HashSet<>();
		sumFloor = ss.size();
		backstack(0, stack, ss);
		return result;
	}

	// 回溯算法
	public void backstack(int floor, Set<Character> stack, List<String> ss) {
		// 跳出条件
		if (floor == sumFloor) {
			result++;
			return;
		}
		// 遍历可以放入stack的元素
		for (char c : ss.get(floor).toCharArray()) {
			if (stack.contains(c)) {
				return;
			} else {
				stack.add(c);
				backstack(floor + 1, stack, ss);
				stack.remove(c);
			}
		}
	}

	public static void main(String[] args) {
		Solution foo = new Solution();
		List<String> ss = new ArrayList<>();
		ss.add("ab");
		ss.add("ca");
		ss.add("ccb");
		System.out.println(foo.findSubString(ss));
	}
}

后记

算法题挺久没刷了，手生了．

leetcode的题目都是写接口，对手动处理输入不熟悉．