面试需要多次做的编程

面试需要多次做的编程题目

二叉树根节点到叶子所有路径

dfs + 回溯

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
import java.util.*;

public class 二叉树根到节点所有路径 {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(6);
root.left.right = new TreeNode(234);
root.right.left = new TreeNode(12);
root.right.right = new TreeNode(2);

new 二叉树根到节点所有路径().new Solution().solve(root);
}

private static class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int val) {
this.val = val;
}
}

public class Solution {
public void solve(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
dfsTrace(root, new ArrayList<>(), ans);

for (List<Integer> path : ans) {
for (Integer e : path) {
System.out.print(e + " ");
}
System.out.println();
}
}

public void dfsTrace(TreeNode node, List<Integer> path, List<List<Integer>> ans) {
if (node.left == null && node.right == null) {
path.add(node.val);
ans.add(new ArrayList<>(path));
path.remove(path.size() - 1);
return;
}

path.add(node.val);

if (node.left != null) {
dfsTrace(node.left, path, ans);
}
if (node.right != null) {
dfsTrace(node.right, path, ans);
}
path.remove(path.size() - 1);
}
}
}

Java快速排序

链表排序

归并排序

反转M~N

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
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == right) {
return head;
}

ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;

ListNode pre = dummyNode;
int count = 1;
while (count != left) {
pre = pre.next;
count += 1;
}

ListNode leftNode = pre.next;

ListNode curNode = pre.next;
ListNode nextNode = curNode.next;
// 开始反转
while (count != right) {
ListNode nextnextNode = nextNode.next;
nextNode.next = curNode;
curNode = nextNode;
nextNode = nextnextNode;

count += 1;
}

pre.next = curNode;
leftNode.next = nextNode;

return dummyNode.next;
}
}

剑指 Offer 24. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;

ListNode curNode = head;

while (curNode != null) {
ListNode next = curNode.next;
curNode.next = prev;

prev = curNode;
curNode = next;
}9-

return prev;
}
}

202. 快乐数

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
class Solution {
public int getNext(int num) {
int ans = 0;

while (num != 0) {
int temp = num % 10;
ans += temp * temp;
num /= 10;
}

return ans;
}

public boolean isHappy(int n) {
int slow = n, fast = getNext(n);

while (fast != 1 && slow != fast) {
slow = getNext(slow);

fast = getNext(getNext(fast));
}

if (fast == 1) {
return true;
}

return false;
}
}

300. 最长递增子序列

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
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;

int[] dp = new int[n];

// 边界
Arrays.fill(dp, 1);

for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
}

return Arrays.stream(dp).max().getAsInt();
}
}

// O(nlogn)
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;

// 以i结尾的最长序列
int[] dp = new int[n];
// 保存长度为i的序列中的尾数最小的
int[] g = new int[n+1];
int ans = 1;

// 边界
Arrays.fill(dp, 1);
g[1] = nums[0];

for (int i = 1; i < n; i++) {
int left = 1, right = ans;

// 找出当前nums[i]在g中的位置
while (left <= right) {
int mid = left + (right - left >> 1);

if (g[mid] == nums[i]) {
// 如果相等,那么不能加,所以此处用right-1平衡下面的+1
right = mid - 1;
break;
} else if (g[mid] > nums[i]) {
right = mid - 1;
} else {
left = mid + 1;
}
}

ans = Math.max(ans, right + 1);
g[right + 1] = nums[i];
}

return ans;
}
}

148. 排序链表

使用归并

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}

// 注意,tail是不包括的
public ListNode sortList(ListNode head, ListNode tail) {
if (head == null) {
return head;
}

if (head.next == tail) {
// 非常注意这里满的写法,因为需要断掉
head.next = null;
return head;
}

// 找到中点,注意这里是需要注意的,fast需要等于tail,所以fast.next也是需要判断的
ListNode slow = head, fast = head;
while (fast != tail) {
fast = fast.next;
slow = slow.next;

if (fast != tail) {
fast = fast.next;
}
}

ListNode left = sortList(head, slow);
ListNode right = sortList(slow, tail);

return merge(left, right);
}

public ListNode merge(ListNode node1, ListNode node2) {
ListNode dummy = new ListNode(-1);
ListNode node = dummy;

while (node1 != null && node2 != null) {
if (node1 != null && node2 != null) {
if (node1.val < node2.val) {
node.next = node1;
node1 = node1.next;
} else {
node.next = node2;
node2 = node2.next;
}
}

node = node.next;
}

if (node1 != null) {
node.next = node1;
}
if (node2 != null) {
node.next = node2;
}

return dummy.next;
}
}

Author: Jcwang

Permalink: http://example.com/2022/09/02/%E5%85%AB%E8%82%A1%20%E9%9D%A2%E8%AF%95%E9%9C%80%E8%A6%81%E5%A4%9A%E6%AC%A1%E5%81%9A%E7%9A%84%E7%BC%96%E7%A8%8B/