算法列表

发表于

  • 线性结构

  • 排序算法

  • 二叉树

  • 并查集

  • 树形结构

  • 回文数

  • 方向数组

  • 记忆化

  • 大整数加法

  • 动态规划

  • 双指针（滑动窗口）

  • 二分专题

20220607_th

算法列表

线性结构

206. 反转链表

24. 两两交换链表中的节点

92. 反转链表 II

876. 链表的中间结点

141. 环形链表

19. 删除链表的倒数第 N 个结点

21. 合并两个有序链表

445. 两数相加 II

682. 棒球比赛

排序算法

905. 按奇偶排序数组

75. 颜色分类

剑指 Offer 51. 数组中的逆序对

二叉树

112. 路径总和

129. 求根节点到叶节点数字之和

543. 二叉树的直径

105. 从前序与中序遍历序列构造二叉树

236. 二叉树的最近公共祖先

235. 二叉搜索树的最近公共祖先

108. 将有序数组转换为二叉搜索树

98. 验证二叉搜索树

并查集

200. 岛屿数量

959. 由斜杠划分区域

树形结构

215. 数组中的第K个最大元素

264. 丑数 II

23. 合并K个升序链表

1508. 子数组和排序后的区间和

947. 移除最多的同行或同列石头

695. 岛屿的最大面积

综合练习

61. 旋转链表

25. K 个一组翻转链表

844. 比较含退格的字符串

面试题40. 最小的k个数

226. 翻转二叉树

101. 对称二叉树

110. 平衡二叉树

538. 把二叉搜索树转换为累加树

1046. 最后一块石头的重量

面试笔试算法（一）

euler-1.3或5的倍数（时间复杂度）

euler-2.偶斐波那契数（空间复杂度）

euler-4.最大回文乘积（回文数）

euler-36.双进制回文数（n进制回文数）

euler-8.连续数字最大乘积（滑动窗口法）

euler-11.方阵中的最大乘积（方向数组）

euler-14.最长考拉兹序列（记忆化）

面试笔试算法（二）

euler-13.大和（大整数加法）

#78. 大整数加法（大整数加法）

euler-25.1000位斐波那契数（大整数加法）

#471. 大整数乘法

euler-15.网格路径（动态规划、组合数）

euler-18.最大路径和 I（动态规划）

双指针【滑动窗口】

209. 长度最小的子数组

3. 无重复字符的最长子串

567. 字符串的排列

76. 最小覆盖子串

713. 乘积小于 K 的子数组

1208. 尽可能使字符串相等

826. 安排工作以达到最大收益

986. 区间列表的交集

475. 供暖器

二分专题（一）

#388. 奇怪的刮刮乐（排序+二分查找）

#386. 吃瓜群众（排序+二分查找）

#387. 吃瓜群众升级版（排序+二分查找）

#390. 原木切割（二分答案）

#389. 暴躁的程序猿（二分答案）

#393. 切绳子（二分答案）

#391. 数列分段（二分答案）

二分专题（二）

#82. 伐木

#394. 跳石头

#599. 两数之和1

#600. 杨氏矩阵

#485. 均分纸牌

#504. 删数

#505. 最大整数

#519. 优雅数

真题

字节一面

  • 实现语言：C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 链表是否有环
*/
typedef struct ListNode {
	int data;
	struct ListNode *next;
} ListNode;
bool hasCycle(ListNode *head) {
	ListNode *fast = head, slow = head;
	while (fast && fast->next) {
		slow = slow->next;
		fast = fast->next->next;
		if (fast == slow) return ture;
	}
	return false;
}

字节二面

  • 实现语言：OC
  • 实现方案：递归
1
2
3
4
5
6
7
8
9
10
/**
 打印 View 的所有子视图的 frame。
*/
- (void)func:(UIView *)view {
	NSLog(@"%@", NSStringFromCGRect(view.frame));
	
	for (UIView *subView in view.subviews) {
		[self func:subView];
	}
}

滴滴

  • 实现语言：C
  • 实现方案：滑动窗口法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 实现1个函数，找出给定字符串中，最长的连续重复字符串子串。
 举例：
 给定字符串：
 abcdedfadasfasfafsssssdfasffwwwdfdswwweewerssss
 返回：sssss
 */
void func(string s) {
    int n = (int)s.size();
    int j = 0, idx = 0, mmax = 0;
    for (int i = 0; i < n; i++) {
        while (j < n && s[j] == s[i]) {
            j++;
        }
        if (mmax < j - i) {
            mmax = j - i;
            idx = i;
        }
        if (j > i) i = j - 1;
    }
    cout << s.substr(idx, mmax) << endl;
}

懂车帝一面

  • 实现语言：C++
  • 实现方案：层序遍历之逐层遍历
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
/**
 根据二叉树，输出一个数组，要数组的子元素是二叉树中某一层的所有元素的集合。
*/
vector<vector<int>> func(struct TreeNode* root) {
	if (!root) return nil;
	
	vector<vector<int>> ans;
	queue<struct TreeNode> que;
	que.push(root);
	while (!que.empty()) {
		vector<int> vec;
		for (int i = 0, I = que.size(); i < I; i++) {
			struct TreeNode *root = que.top();
			que.pop();
			vec.push_back(root->val);
			
			if (root->left) {
				que.push(root->left);
			}
			if (root->right) {
				que.push(root->right);
			}
		}
		ans.push_back(vec);
	}
	return ans;
}