面向机试编程
面向机试编程(Test Oriented Programming),在 2026 年考手撕,不亚于在 2012 年考汇编,代码正在变成很不值钱的玩意
# 数据定义
# 输入输出
ACM 模式要自定义输入输出
Java Scanner 输入
next():读取一个单词(以空格分隔),例如Hello World→HellonextLine():读取整行(包括空格),如果内容是字符串,最好以nextLine()读入整行的字符串,然后再按照需求splitnextInt():读取一个整数(以空格分隔)hasNext():是否有下一个输入,例如hasNextLine(), hasNextInt()
比如输入一个 3x3 的矩阵
/*
3
3
1 2 3
4 5 6
7 8 9
*/
public static void main(){
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int[][] matrix = new int[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
matrix[i][j] = scanner.nextInt();
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Java 输出
System.out.println("nmsl")
Go 输入输出
import (
"fmt"
"bufio"
"os"
)
func main() {
// 读整行
reader := bufio.NewReader(os.Stdin)
str, _ := reader.ReadString('\n')
// 挨个读
a, b := "", ""
// n 为输入的变量数量
n, _ := fmt.Scan(&str)
if n == 0 {
return
}
fmt.Println(sortString(str))
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 快速构建数据
手撕的时候并不会给严格的输入输出,有时候自定义的过了,代码逻辑没问题就问题不大
Java 快速初始化一个数组、List、二维数组、链表或二叉树
数组和 List 初始化:注意List.of在 JDK9+ 中才有,一些在线编辑器大多数只提供 JDK1.8,此时要用Arrays.asList
int arr[] = {1, 2, 3, 4};
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> list1 = List.of(1, 2, 3, 4, 5);
List<Integer> list2 = new ArrayList<>(Arrays.asList(1, 2));
List<Integer> list3 = new ArrayList<>(List.of(1, 2, 3));
2
3
4
5
二维数组初始化
int matrix[][] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
}
2
3
4
5
创建链表:定义结构体,通过头节点和数组快速创建链表
class ListNode{
int val;
ListNode next;
ListNode(int val){ this.val = val; }
}
int[] vals = {1, 2, 3, 4, 5}
ListNode h = new ListNode(-1), p = h;
for(int val: vals){
p.next = new ListNode(val);
p = p.next;
}
ListNode head = h.next;
2
3
4
5
6
7
8
9
10
11
12
13
Go 快速初始化一个 slice 数组、二维数组
slice := []int{1, 2, 3, 4, 5}
slice2D := [][]int{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
}
2
3
4
5
6
7
Go 的链表
// 定义链表节点
type ListNode struct {
Val int
Next *ListNode
}
// 数组转链表
values := []int{1, 2, 3, 4, 5}
dummy := &ListNode{}
current := dummy
for _, val := range values {
current.Next = &ListNode{Val: val}
current = current.Next
}
head := dummy.Next
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 字符串处理
# 统计单词出现次数
给定一段英文邮件,请统计这篇邮件中每个单词的出现次数,注意标点符号,每个单词默认由空格隔开
# 简化路径
把一个 Unix 的字符串路径简化,具体规则是将[../, ./]转化为回退一个目录和当前目录,并且对于[.., .]结尾的字符串,同样做这样的处理,另外需要将多个/转化为一个
- 简便方法:先将原字符串
split("/"),再维护一个 Deque,遍历字符串数组,碰到..就pollLast,略过.,其余字符串正常offer,而后构造一个 StringBuilder,将 Deque 中字符串依次 push,并在每个间隔加入/,即为答案 - 纯模拟:直接边遍历 path 边构造 StringBuilder,维护两个指针,分别指向倒数的两个
/位置(用于回退..)
后者的效率比前者高很多,但是处理起来异常麻烦,重点有四(感觉面试的时候写不出来,时间不够用,测试样例不确定)
- 处理多余的
/,用while(i > 0 && path.charAt(i-1) == '/') continue;实现 - 处理当前目录,即处理
/./或末尾的/.结构 - 回退上一目录,处理
/../或末尾的/..结构 - 指针的更新,每次在添加
/和回退时,都要对preTail, tail进行更新
简便方法的处理一定要学会,这才是面试能写出来的代码,利用栈(Deque)实现
class Solution {
public String simplifyPath(String path){
String[] p = path.split("/");
Deque<String> deque = new ArrayDeque<>();
for(String s: p){
if(s.equals("..")){
deque.pollLast();
continue;
} else if(s.equals(".") || s.equals("")){
continue;
}
deque.offer(s);
}
System.out.println(deque);
StringBuilder sb = new StringBuilder();
sb.append("/");
if(deque.isEmpty()){
return sb.toString();
}
while(!deque.isEmpty()){
String cur = deque.pollFirst();
sb.append(cur);
if(!deque.isEmpty()){
sb.append("/");
}
}
return sb.toString();
}
}
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
第一个关键是分割
String[] p = path.split("/")
这个分割规则有点怪,需要注意一下,按道理来说,每个分隔符会对其左右两侧的字符串进行提取,例如home/foo会被提取为["home", "foo"],但有这样几个特殊情况
- 分隔符左侧为空,将分割出空字符串:
/home→["", "home"] - 结尾的空字符串会被丢弃:
/home//→["", "home", "", ""]→["", "home"] - 连续的分隔符会导致空字符串:
//home//→["", "", "home"](末尾导致的两个空字符串被省去了)
一定要注意空字符串的处理
然后是 Deque 的使用,分成两部分理解就行
- 队列:入队正常
offer,出队有两种方式pollFirst, pollLast,按需求来就行,另外poll和pollFirst等价 - 栈:就是正常的
push / pop
# 找出第 N 个二进制字符串中的第 K 位
1545. 找出第 N 个二进制字符串中的第 K 位 (opens new window)
有二进制字符串
要求返回 0, 1 = 1, 0
翻转字符串:转化为一个 rune 数组操作,最后转化为 string 返回
func reverse(s string) string {
runes := []rune(s)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}
2
3
4
5
6
7
反转字符串:转化为一个 byte 数组操作,最后转化为 string 返回
func invert(s string) string {
bytes := []byte(s)
for i := 0; i < len(bytes); i++ {
if bytes[i] == '0'{
bytes[i] = '1'
} else {
bytes[i] = '0'
}
}
return string(bytes)
}
2
3
4
5
6
7
8
9
10
11
业务逻辑实现:注意 n 和 k 的下标都从 1 开始
func findKthBit(n int, k int) byte {
return S(n)[k-1]
}
func S(n int) string {
if n == 1 {
return "0"
}
pre := S(n-1)
return pre + "1" + reverse(invert(pre))
}
2
3
4
5
6
7
8
9
10
11
# 排序技巧
Go 的排序和二分查找
import (
"fmt"
"sort"
)
func main() {
intValue := []int{10, 20, 5, 8}
sort.Ints(intValue) // 使用sort包的Ints方法进行排序
target := binarySearch(row, 5)
fmt.Println("排序后的整数数组:", intValue)
}
func binarySearch(row []int, target int) bool {
i := sort.SearchInts(row, target)
if i < len(row) && row[i] == target {
return true
}
return false
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Java 里同样要掌握 Arrays.sort和 Comparator,通过 λ 表达式构造比较器重写排序规则,例如
Queue<Integer> queue = new PriorityQueue<>(
(a, b) -> kv.get(a) - kv.get(b)
);
2
3
上述例子中将会是一个升序,在 Java 的比较器里
| 返回值 | 意义 |
|---|---|
| < 0 | 表示 a 应排在 b 前面(a 小) |
| == 0 | 顺序无所谓 |
| > 0 | 表示 a 应排在 b 后面(a 大) |
同理还有Arrays.sort(T[] t, Comparator)
Integer[] nums = new Integer[]{1,1,1,1,2,2,3,4,4,4,5};
// 传入的是类 Integer[],如果是 int[] 可以直接排,不用重写
Arrays.sort(nums, (a, b) -> {
return a-b;
});
2
3
4
5
6
也可以不用大括号,更简洁
Arrays.sort(nums, (a, b) -> a-b);
# PriorityQueue 和 Arrays.sort
找到数组中出现频率最高的 k 个元素,示例
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
输入: nums = [1], k = 1
输出: [1]
2
3
4
5
思路很简单
- 哈希表统计元素出现频率
- 根据频率对元素排序
重点是排序如何完成,可以借用 PriorityQueue 构造小/大根堆,排序规则通过 λ 表达式传入
public static List<Integer> getK(int[] nums, int k){
Map<Integer, Integer> kv = new HashMap<>();
for(int i: nums){
kv.put(i, kv.getOrDefault(i, 0) + 1);
}
// 这是一个小根堆
Queue<Integer> queue = new PriorityQueue<>(
(a, b) -> kv.get(a) - kv.get(b)
);
for(int key: kv.keySet()){
queue.offer(key);
if(queue.size() > k){
queue.poll();
}
}
List<Integer> res = new ArrayList<>();
// 此时是从小到大排的
while(!queue.isEmpty()){
System.out.println(queue.peek());
res.add(queue.poll());
}
return res;
}
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
# 链表归并
148. 排序链表 (opens new window):给你链表的头结点head ,请将其按升序排列并返回排序后的链表,要求时间复杂度 O(nlogn),空间复杂度 O(1)
这样的时间复杂度要求只能用归并排序
/**
* 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);
}
// 含头不含尾
public ListNode sortList(ListNode head, ListNode tail){
if(head == null){
return null;
}
if(head.next == tail){
head.next = null;
return head;
}
ListNode mid = head, right = head;
while(right != tail){
mid = mid.next;
right = right.next;
if(right != tail){
right = right.next;
}
}
ListNode list1 = sortList(head, mid);
ListNode list2 = sortList(mid, tail);
return mergeList(list1, list2);
}
public ListNode mergeList(ListNode list1, ListNode list2){
ListNode head = new ListNode();
ListNode p = head, p1 = list1, p2 = list2;
while(p1 != null && p2 != null){
if(p1.val < p2.val){
p.next = p1;
p = p.next;
p1 = p1.next;
} else {
p.next = p2;
p = p.next;
p2 = p2.next;
}
}
while(p1 != null){
p.next = p1;
p = p.next;
p1 = p1.next;
}
while(p2 != null){
p.next = p2;
p = p.next;
p2 = p2.next;
}
return head.next;
}
}
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
合并链表 → 递归合并 → 排序
# 三数、四数之和
- 排序,确定首位,而后夹逼搜索第二、三个数,若大于 0 则左移右指针,小于 0 则右移左指针,若等于 0 则左右指针往中间收缩
- 升序后爆搜,第三个数和第四个数可以左右向中间逼近,减少一层循环(双指针),要注意避免重复的元素
对数组排序
Arrays.sort(nums);
List<List<int>>添加元素的小技巧,直接构造List<Integer>
res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
int k = j+1, l = n-1;
while(k < l){
long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
if(sum == target){
res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
while(k+1 < n && nums[k+1] == nums[k]){ k++; }
while(l-1 > 0 && nums[l-1] == nums[l]){ l--; }
k++; l--;
} else if (sum < target){
k++;
} else {
l--;
}
}
while(j+1 < n && nums[j+1] == nums[j]){ j++; }
}
while(i+1 < n && nums[i+1] == nums[i]){ i++; }
}
return res;
}
}
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
# 滑动窗口
# 最长无重复字符子串
3. 无重复字符的最长子串 (opens new window)
滑动窗口,最重要的是找准边界,一是如何定义,而是如何迭代,根据左右边界遍历一次数组,实现需求,在这里
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int end = 0, start = 0; end < n; end++) {
char c = s.charAt(end);
if (map.containsKey(c) && map.get(c) >= start) {
// 当碰到重复字符了,调整左边界
start = map.get(c) + 1;
}
ans = Math.max(ans, end-start+1);
// 更新每个字符的下标
map.put(c, end);
}
return ans;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 字母异位词
438. 找到字符串中所有字母异位词 (opens new window)
维护两个int[] arr = new int[26]记录出现的字符次数
char left = str.charAt(i-1);
char right = str.charAt(i+n-1);
sCount[right-'a']++;
sCount[left-'a']--;
2
3
4
利用Arrays.equals比较两个 int 数组是否相等
Arrays.equals(sCount, pCount)
完整实现
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int n = p.length(), m = s.length();
if(n > m) return res;
int[] sCount = new int[26], pCount = new int[26];
for(int i = 0; i < n; i++){
sCount[s.charAt(i)-'a']++;
pCount[p.charAt(i)-'a']++;
}
if(Arrays.equals(sCount, pCount)){
res.add(0);
}
for(int i = 1; i <= m-n; i++){
sCount[s.charAt(i-1)-'a']--;
sCount[s.charAt(i+n-1)-'a']++;
if(Arrays.equals(sCount, pCount)){
res.add(i);
}
}
return res;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
更优化的滑动:记录两个子串的“差值”,当“差值”为 0 时,两个子串异位相等,否则不等,从而不需要进行 equals 比较
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] count = new int[26];
for (int i = 0; i < pLen; ++i) {
++count[s.charAt(i) - 'a'];
--count[p.charAt(i) - 'a'];
}
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
if (differ == 0) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
if (count[s.charAt(i) - 'a'] == 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i) - 'a'] == 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
--count[s.charAt(i) - 'a'];
if (count[s.charAt(i + pLen) - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s.charAt(i + pLen) - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
++count[s.charAt(i + pLen) - 'a'];
if (differ == 0) {
ans.add(i + 1);
}
}
return ans;
}
}
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
# 数据结构
# LRU 缓存
146. LRU 缓存 (opens new window)
晕了,情况有点多,哈希表保证查找复杂度为 1,双向链表保证调整优先级复杂度为 1(实际上是删除的复杂度为 1)。即,先用哈希表查找结点,再在双向链表中直接操作该结点,如此保证复杂度均为 O(1)
- 在类里写类,直接
static class Node {}就行,本来想用PriorityQueue写,但是一想根本无法满足删除为 1 的复杂度
class LRUCache {
private Map<Integer, Node> map;
private int capacity;
private DeLinkedList list;
static class Node {
int key, val;
Node pre, next;
Node(){ this.val = -1; this.pre = null; this.next = null; }
Node(int key, int val){ this.key = key; this.val = val; this.next = null; pre = null; }
}
static class DeLinkedList {
public Node head, tail;
DeLinkedList(){
head = new Node();
tail = null;
}
public void insert(Node n){
// 当链表为空
if(tail == null){
tail = n;
n.pre = head;
n.next = null;
head.next = n;
return;
}
// 当链表不为空
n.next = head.next;
head.next.pre = n;
head.next = n;
n.pre = head;
}
// 删除链表中结点 n
public void delete(Node n){
// 当为尾结点
if(n.next == null){
if(n.pre == head){
tail = null; // 当只剩一个元素
} else {
tail = n.pre; // 当有多个元素
}
n.pre.next = null;
return;
}
n.pre.next = n.next;
n.next.pre = n.pre;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
list = new DeLinkedList();
}
public int get(int key) {
if(map.containsKey(key)){
Node n = map.get(key);
// 更新优先级
list.delete(n); // 删去原有结点
list.insert(n); // 头插
return n.val;
}
return -1;
}
public void put(int key, int value) {
if(map.containsKey(key)){
Node n = map.get(key);
map.remove(key);
list.delete(n);
}
while(map.size() >= capacity){
// 删除最久未使用元素
int k = list.tail.key; // 获取最久未使用元素 key
map.remove(k); // 在 map 中删去
list.delete(list.tail); // 在 list 中删去
}
// 再添加元素
Node n = new Node(key, value);
list.insert(n);
map.put(key, list.head.next);
}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# 最小栈
155. 最小栈 (opens new window):设计一个支持push,pop,top操作,并能在常数时间内检索到最小元素的栈
实现MinStack类
MinStack()初始化堆栈对象void push(int val)将元素val推入堆栈void pop()删除堆栈顶部的元素int top()获取堆栈顶部的元素int getMin()获取堆栈中的最小元素
class MinStack {
Deque<Integer> stack;
Deque<Integer> minStack;
public MinStack() {
stack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
}
public void push(int val) {
stack.push(val);
if(minStack.isEmpty()){
minStack.push(val);
return;
}
minStack.push(Math.min(minStack.peek(), val));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
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
只需要借用一个辅助栈就行,想太多了,辅助栈记录的是当前高度下栈中最小的元素(贪心比较就能实现)
# 动态规划
# 接雨水
class Solution {
public int trap(int[] height) {
int n = height.length, res = 0;
int[] leftMax = new int[n], rightMax = new int[n];
leftMax[0] = height[0];
rightMax[n-1] = height[n-1];
for(int i = 1; i < n; i++){
leftMax[i] = Math.max(leftMax[i-1], height[i]);
rightMax[n-i-1] = Math.max(rightMax[n-i], height[n-i-1]);
}
for(int i = 0; i < n; i++){
res += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return res;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
也可以用单调栈来写
# 最长公共子序列
1143. 最长公共子序列 (opens new window)
dp[i][j]表示text1[0:i]和text2[0:j]的最长公共子序列长度,这里对字符串的范围截取含头不含尾,即text1[k:k] == ""恒成立,故有
因为任何字符串和""一定没有公共子序列
状态转移方程,需要注意的是 dp 的长度为[m+1][n+1],含头不含尾嘛,所以这里和字符串下标的对应也相差 1
唉,背吧
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m+1][n+1];
for(int i = 0; i < m+1; i++) dp[i][0] = 0;
for(int i = 0; i < n+1; i++) dp[0][i] = 0;
for(int i = 1; i <= m; i++){
char c1 = text1.charAt(i-1);
for(int j = 1; j <= n; j++){
char c2 = text2.charAt(j-1);
if(c1 == c2){
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 打家劫舍
LCR 089. 打家劫舍 (opens new window):不能偷相邻住户,求盗窃最大值
状态转移方程
并且有
完整代码
func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
dp := make([]int, n)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i := 2; i < n; i++ {
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
}
return dp[n-1]
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LCR 090. 打家劫舍 II (opens new window):现在住户围成一圈,即此时不能同时偷第一家和最后一家(二者相邻)
需要对两段进行动态规划,一段是[0:n-1]一段是[1:n],因为围成一圈实际上是分成了两种情况,是从第一家开始偷还是从最后一家开始偷,同时从最后一家开始偷等价于从第二家开始偷
func rob(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
return max(rob1(nums, 0, len(nums)-1), rob1(nums, 1, len(nums)))
}
func rob1(nums []int, left, right int) int {
n := right - left
if n == 1 {
return nums[left]
}
dp := make([]int, n)
dp[0] = nums[left]
dp[1] = max(nums[left], nums[left+1])
for i := 2; i < n; i++ {
dp[i] = max(dp[i-2] + nums[left+i], dp[i-1])
}
return dp[n-1]
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
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
可以看到 go 中不允许函数重载(即使参数列表不一样)
# 树与回溯
# 组合总和
# 全排列
# 位运算
# 统计二进制中 1 个数
762. 二进制表示中质数个计算置位 (opens new window):因为 int 的取值范围为
// var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}
var primes = map[int]bool {
2: true, 3: true, 5: true, 7: true,
11: true, 13: true, 17: true, 19: true,
}
func countPrimeSetBits(left int, right int) (res int) {
// var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}
for i := left; i <= right; i++ {
ones := bits.OnesCount(uint(i))
// if slices.Contains(primes, ones){
// res++
// }
if primes[ones] {
res++
}
}
return res
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
go 中的位运算技巧
- int 转二进制:
uint(x) - 统计二进制中 1 的个数:
bits.OnesCount(i)
切片 slice 和哈希表 map 的存在判定
- 切片包含:
slices.Contains(slice, element) - 哈希表判定直接利用空为初始值(bool 为假,int 为 0):
map[element] == false / 0
# 并与或处理去重字符
1239. 串联字符串的最大长度 (opens new window)
用 Integer 类型的比特位特征表示字符串中各字母的占用,判别是否有重复字母
int mask = 0;
for(int i = 0; i < s.length(); i++){
int c = s.charAt(i) - 'a';
if(((mask >> c) & 1) != 0){
mask = 0;
break;
}
mask |= (1 << c);
}
2
3
4
5
6
7
8
9
判断两个字符串是否有重复字母:两字符串对应的 Integer 进行 & 操作(相同位均为 1 才为 1),若为 0,说明没有重复的位
if(mask == 0){
continue;
}
int n = masks.size();
for(int i = 0; i < n; i++){
int m = masks.get(i);
if((m & mask) == 0){
masks.add(m | mask);
res = Math.max(res, Integer.bitCount(m | mask));
}
}
2
3
4
5
6
7
8
9
10
11
# 快速幂和快速乘
50. Pow(x, n) (opens new window)
用乘法实现快速幂运算,快速是指 O(logn) 的时间复杂度,我老是想到“模指数算法”,总感觉差不多,感觉就是一样的
public static double myPow(double x, int n) {
long N = n;
boolean flag = N < 0;
N = N < 0 ? -N : N;
double res = 1, mul = x;
while(N > 0){
if((N & 1) == 1){
res *= mul;
}
mul *= mul;
N >>= 1;
}
return flag ? (1.0 / res) : res;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
快速乘:用加法实现快速乘运算,同样要求 O(logn) 的复杂度,这里计算
// 用加法计算 ax
public static int myMul(int a, int x){
boolean flag = (a > 0 && x < 0) || (a < 0 && x > 0);
a = Math.abs(a); x = Math.abs(x);
int add = a, ans = 0;
while(x != 0){
if((x & 1) == 1){
ans += add;
}
if(x != 1){
add += add;
}
// 用掉当前位,考虑更高位
x >>= 1;
}
return flag ? -ans : ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
29. 两数相除 (opens new window),这道题真的司马了,看不明白捏
# SQL 语句
# 排序和分组
去重和排序(默认升序),同时给author_id起一个别名,方便编写
select
distinct author_id as id
from
Views
where
author_id = viewer_id
order by
id;
2
3
4
5
6
7
8
若要降序排列,需要添加关键字desc在id之后
# 函数
length返回字符串长度,统计表中content大于 15 的数据项
select
tweet_id
from
Tweets
where
length(content) > 15;
2
3
4
5
6
# 左连接
MySQL中的 left join 是一种连接方式,它以左表为基准,返回左表中所有的行,同时返回右表中与左表匹配的行。如果右表中没有匹配的行,则用 NULL 填充
一个简单的左连接示例
select
*
from
Employees
left join
EmployeeUNI
on
Employees.id = EmployeeUNI.id;
2
3
4
5
6
7
8
1378. 使用唯一标识码替换员工ID (opens new window)
用表一的员工 ID 和表二的 ID 进行左连接:from 表一 left join 表二 on 表一.ID = 表二.ID
就相当于,表一表二通过 ID 这一字段横向扩展成了一张大表,而后正常在这张大表上select想要的内容就行
select
EmployeeUNI.unique_id, Employees.name
from
Employees
left join
EmployeeUNI
on
EmployeeUNI.id = Employees.id;
2
3
4
5
6
7
8
统计连接后为空的项
1068. 产品销售分析 I (opens new window)
select
Product.product_name, Sales.year, Sales.price
from
Sales
left join
Product
on
Sales.product_id = Product.product_id;
2
3
4
5
6
7
8
注意,连接后,比如表一左连接表二,如果主键在表二没有对应的项,则会产生存在空字段的数据项,例如 1581. 进店却未进行过交易的顾客 (opens new window)
Visits
+----------+-------------+
| visit_id | customer_id |
+----------+-------------+
| 1 | 23 |
| 2 | 9 |
| 4 | 30 |
| 5 | 54 |
| 6 | 96 |
| 7 | 54 |
| 8 | 54 |
+----------+-------------+
Transactions
+----------------+----------+--------+
| transaction_id | visit_id | amount |
+----------------+----------+--------+
| 2 | 5 | 310 |
| 3 | 5 | 300 |
| 9 | 5 | 200 |
| 12 | 1 | 910 |
| 13 | 2 | 970 |
+----------------+----------+--------+
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
显然,visit_id = 4的项在表二中并不存在,所以在连接后会出现
+----------------+----------+--------+-------------+
| transaction_id | visit_id | amount | customer_id |
+----------------+----------+--------+-------------+
| null | 4 | null | 30 |
2
3
4
这种数据项,那么显然在连接后,若字段transaction_id is null,则说明该用户“进店了但未消费”
题目要求返回每个用户进店后未消费的数量,即统计左连接后的大表中每个 id 对应的transaction_id is null的数量,使用 count 函数并取别名为count_no_trans
# Write your MySQL query statement below
select
Visits.customer_id, count(customer_id) as count_no_trans
from
Visits
left join
Transactions
on
Visits.visit_id = Transactions.visit_id
where
transaction_id is null
group by
customer_id;
2
3
4
5
6
7
8
9
10
11
12
13
# 自连接
简单的自连接和日期差函数:197. 上升的温度 (opens new window)
从温度表中找出所有比前一天温度高的项,每个数据项由 ID、日期、温度三个字段构成
- 计算日期差值函数(单位:日):
datediff(d2, d1) = (d2-d1)
select
w2.id
from
Weather w1
join
Weather w2
where
datediff(w2.recordDate, w1.recordDate) = 1
and
w2.temperature > w1.temperature;
2
3
4
5
6
7
8
9
10
自连接、分组均值及浮点:1661. 每台机器的进程平均运行时间 (opens new window)
计算每个进程的平均运行时间
- 计算均值函数:
avg(...) - 规定浮点格式:
round(..., 3),规定为 3 位小数 - 分组:
group by machine_id将同一台机器的数据项聚合在一起处理
select
a1.machine_id, round(avg(a2.timestamp-a1.timestamp), 3) as processing_time
from
Activity as a1
join
Activity as a2
on
a1.timestamp < a2.timestamp and a1.machine_id = a2.machine_id and a1.process_id = a2.process_id
group by
a1.machine_id;
2
3
4
5
6
7
8
9
10
示例:原数据
machine_id process_id activity_type timestamp
0 0 start 0.712
0 0 end 1.520
0 1 start 3.140
0 1 end 4.120
1 0 start 0.550
1 0 end 1.550
1 1 start 2.300
1 1 end 3.600
2
3
4
5
6
7
8
9
自连接后
a1.machine_id a1.process_id a1.timestamp a2.timestamp
0 0 0.712 1.520
0 1 3.140 4.120
1 0 0.550 1.550
1 1 2.300 3.600
2
3
4
5
分组并取均值后:这个分组取均值有点迷,怎么理解
machine_id processing_time
0 0.808 # (1.520 - 0.712 + 4.120 - 3.140) / 2
1 1.150 # (1.550 - 0.550 + 3.600 - 2.300) / 2
2
3