知一杂谈

数据结构与算法思想

字数统计: 7.1k阅读时长: 32 min
2019/08/29
人生只有贪心,没有动态规划。

数据结构

  • 数组
  • 栈,先进后出
  • 队列,先进先出
    • 双端队列,双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两边进行。
    • 环形队列,环形队列是一种特殊的队列结构,保证了元素也是先进先出的,但与一般队列的区别是,他们是环形的,即队列头部的上个元素是队列尾部,通常是容纳元素数固定的一个闭环。
  • 堆,一种特别的树状数据结构。堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
  • 链表
    • 单向链表。
    • 双向链表。
    • 跳表,一种带多级索引的链表。
  • 散列表,是根据键而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。
    • 二叉树,二叉树是一个连通的无环图,并且每一个顶点的度不大于3。
    • 红黑树,是一种自平衡二叉查找树。
    • 字典树(Trie)
  • 图,图(Graph)是由顶点的有穷非空集合和顶点之间的边的集合组成。
  • 布隆过滤器,一个概率型数据结构,可以用来判断一个元素是否在一个集合中。判断某个元素在,可能会被误判;判断某个元素不在,那么一定不在。

算法思想

分治法

分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

例子:快排、归并排序、MapReduce

贪心算法

贪心算法就是在每一步的选择中都按照当前最优的选择,从而希望最终结果得到最优解。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

例子:最小生成树、哈夫曼编码

动态规划(Dynamic Programming)

动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。
若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

递归+记忆=递推

适用情况:

  1. 具有最优子结构性质。
  2. 无后效性,子问题确定后不会再改变。
  3. 子问题重叠的性质。

例子:背包问题
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
https://www.zhihu.com/question/23995189/answer/613096905

回溯法(backtracking)

回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  1. 找到一个可能存在的正确的答案
  2. 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。

例子:八皇后问题

https://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://www.cnblogs.com/zuzZ/p/8178950.html

分支界限法

与贪婪算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。

概率算法

例子:
数值随机化算法
蒙特卡罗(Monte Carlo)算法
拉斯维加斯(Las Vegas)算法
舍伍德(Sherwood)算法

https://zhuanlan.zhihu.com/p/42619498

练习题

15. 三数之和

题目

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路

初读这道题时忽略了一个点,就是在检查时,如果有两个重复的数字可以都用上组成一个三元组集合,但是在返回结果的时候不能第一个数字参与组成三元组后第二个相同数字继续组成三元组。

有三种思路,先进性排序处理,然后再进行处理。第一种就是做三层枚举;第二种就是两层枚举,在进行 set O(1) 查找;第三种是一层枚举,然后从剩余列表中的左右两边进行查找,满足三元组的添加记录。

下面是主要介绍第三种思路的细节

  1. 排序处理
  2. 从第 0 位置开始遍历
    1. 分别取剩余数组的首尾值进行求和
    2. 如果大于零则向前移动尾部游标
    3. 如果小于零则向后移动头部游标
    4. 如果等于零则添加记录
      1. 添加记录后对首尾游标向中间移动一格
    5. 如果首尾游标没有相交则继续 2.1 步骤处理
  3. 进行下一位置的遍历,直到数组尾部
  4. 返回结果

整个流程思路基本是这样子的,然后我们对于边界情况的处理单独进行描述

  1. 如果当前遍历位置值大于 0 则直接返回结果
  2. 对于我在 ① 中描述的情况,需要在 2.1 之前进行与判断,当前位置与上一位置值相同则跳过,进行排重处理
  3. 同样的情况处理在 4.1 之后也要进行首尾游标移动方向相邻值的排重处理

解题思维

  1. 首先需要做到的是充分理解题意,至少要做到能肉眼推导正确结果。
  2. 解决方案一般都会有多种,合理选择最优方案进行骨架设计 ②,充分考虑时间和空间复杂度。
  3. 然后解决边界条件 ③,优化代码可读性。
  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
import java.util.*;

public class ThreeSum {

public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resp = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
int l = i + 1;
int r = nums.length - 1;
if (i > 0 && nums[i-1] == nums[i]) continue;
while (l < r){
int sum = nums[i] + nums[l] + nums[r];
if ( sum> 0) r--;
else if (sum < 0) l++;
else if (sum == 0){
resp.add(Arrays.asList(nums[i], nums[l] , nums[r]));
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++;
r--;
}
}
}
return resp;
}
}


22. 括号生成

题目

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

1
2
3
4
5
6
7
8
9
10
11
12
[---
title: 51. N皇后
date: 2019-08-20
tags: [算法, leetcode]
id: 1
---
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路

根据递归做暴力处理,同时进行剪枝操作。

解答

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

public class GenerateParenthesis {
public static void main(String[] args) {
GenerateParenthesis obj = new GenerateParenthesis();
List<String> stringList = obj.generateParenthesis(3);
System.out.println(stringList);
}

public List<String> generateParenthesis(int n) {
List<String> collect = new ArrayList<>();
gen(collect, "", n, n);
return collect;
}

public void gen(List<String> collect, String cur, int left, int right) {
if (left == 0 && right == 0) {
collect.add(cur);
return;
}
if (left > 0) {
gen(collect, cur + "(", left - 1, right);
}
if (right > 0 && right > left) {
gen(collect, cur + ")", left, right - 1);
}
}
}


49、242. 字母异位词

第一题:

242. 有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:

输入: s = “rat”, t = “car”
输出: false

说明:
你可以假设字符串只包含小写字母。

解答第一个思路是使用 HashMap 进行字频统计再对比,第二个思路是字符串排序后进行比较。

第二题:

49. 字母异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明:

所有输入均为小写字母。
不考虑答案输出的顺序。

练习输出:

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

public class Anagram {
public static void main(String[] args) {
System.out.println(isAnagram("anagram", "nagaram"));
System.out.println(isAnagram2("anagram", "nagaram"));
groupAnagrams(new String[]{"eat", "ate", "aaa"});
}

public static boolean isAnagram(String s, String t) {
if (null == s && null == t) {
return true;
} else if (null == s || null == t) {
return false;
} else if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> left = new HashMap<>();
Map<Character, Integer> right = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
left.put(s.charAt(i), left.getOrDefault(s.charAt(i), 0) + 1);
}
for (int j = 0; j < t.length(); j++) {
right.put(t.charAt(j), right.getOrDefault(t.charAt(j), 0) + 1);
}
for (Map.Entry<Character, Integer> c : left.entrySet()) {
if (!c.getValue().equals(right.getOrDefault(c.getKey(), 0))) {
return false;
}
}

return true;
}

public static boolean isAnagram2(String s, String t) {
if (null == s && null == t) {
return true;
} else if (null == s || null == t) {
return false;
} else if (s.length() != t.length()) {
return false;
}
char[] left = s.toCharArray();
char[] right = t.toCharArray();
Arrays.sort(left);
Arrays.sort(right);
for (int i = 0; i < left.length; i++) {
if (left[i] != right[i]) {
return false;
}
}
return true;
}

public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> res = new HashMap<>();
for (String sr : strs) {
char[] chars = sr.toCharArray();
Arrays.sort(chars);
String sortedSr = new String(chars);
if (!res.containsKey(sortedSr)) {
res.put(sortedSr, new ArrayList<>());
}
List<String> mapVal = res.get(sortedSr);
mapVal.add(sr);
}
List<List<String>> rep = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : res.entrySet()) {
rep.add(entry.getValue());
}
return rep;
}
}


51. N皇后

题目

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SolveNQueens {
public static void main(String[] args) {
SolveNQueens queens = new SolveNQueens();
System.out.println(queens.solveNQueens(5));
}

public List<List<String>> solveNQueens(int n) {
List<List<String>> resp = new ArrayList<>();
Set<Integer> cols = new HashSet<>();
Set<Integer> pie = new HashSet<>();
Set<Integer> na = new HashSet<>();
dfs(n, 0, new ArrayList<>(), resp, cols, pie, na);
return resp;
}

public void dfs(int max, int row, List<String> curState, List<List<String>> resp,
Set<Integer> cols, Set<Integer> pie, Set<Integer> na) {
// 终结条件
if (row >= max) {
if (curState.size() == max) {
resp.add(curState);
}
return;
}
// 循环列
for (int col = 0; col < max; col++) {
if (cols.contains(col) || pie.contains(row + col) || na.contains(row - col)) {
continue;
}
cols.add(col);
pie.add(row + col);
na.add(row - col);
curState.add(trans(col, max));
int size = curState.size();
List<String> newState = (max - row == 1) ? new ArrayList<String>() {{
addAll(curState);
}} : curState;
// 递归层
dfs(max, row + 1, newState, resp, cols, pie, na);
cols.remove(col);
pie.remove(row + col);
na.remove(row - col);
curState.remove(size - 1);
}
}

public String trans(int point, int max) {
char[] chars = new char[max];
for (int i = 0; i < max; i++) {
chars[i] = i == point ? 'Q' : '.';
}
return String.valueOf(chars);
}
}


69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
  由于返回类型是整数,小数部分将被舍去。

思路

二分查找比较

需要注意的地方有两个

  1. 注意开始边界问题
  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
28
29
30
31
32
33
34
35
public class MySqrt {
public static void main(String[] args) {
MySqrt mySqrt = new MySqrt();
System.out.println(mySqrt.mySqrt(2147395599));

}

// 边界问题
// 1. 0\1边界
// 类型长度越界
public int mySqrt(int x) {
if (x == 0) return 0;
if (x == 1) return 1;
return mySqrt(x, 0, x);
}

public int mySqrt(long x, long left, long right) {
long cur = (right - left) / 2 + left;
long cur2 = cur * cur;
if (cur2 == x) {
return (int) cur;
} else if (right - left == 1) {
return (int) left;
}

if (cur2 < x) {
left = cur;
} else if (cur2 > x) {
right = cur;
} else {
return (int) cur;
}
return mySqrt(x, left, right);
}
}

扩展

牛顿迭代法


98. 验证二叉搜索树

题目

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:

1
2
3
  2
/ \
1 3

输出: true
示例 2:

输入:

1
2
3
4
5
  5
/ \
1 4
  / \
  3 6

输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。

思路

首先拿到这个题看起来思路比较简单,实现起来还有有点困难,而且在思考过程中踩过一个坑,又爬上来的。哎,看题还是要全面点。

  1. 首先想到就是中序遍历了,放到一个列表中,然后比较大小即可。
  2. 或者是做一个递归操作,判断当前节点是否在一个范围即可。

思路是这么两个思路,代码实现起来为了执行效率做了短路处理,就是边遍历边检查,遇到错误就一路返回不再进行后面处理,当然这是思路理顺后的优化。

中序遍历没坑,直接写就行了,有坑的是第二种操作,刚开始觉得只要比较当前节点的父节点和两个子节点就好了,就像下面画的,已 C 点为当前节点进行处理,实际是一个错误的思路,并且情况也分析的不对。

意识到问题后就重新分析,把当前节点作为最底端的节点,我们去比较的都是当前节点和父辈及以上的节点的大小,也就是拆出来四种情况。

其中 表示当前节点,和其它点的相对位置表示左右子节点关系,min -> max 指向当前节点值必须在此区间中才可以,+∞-∞ 为单点情况的边界表示。最后拆分出这四种子情况,只要任一节点符合这四种情况之一即当前节点满足,当所有节点均满足则二叉搜索🌲有效,事实根据这个思路写出的代码验证是可行的。比较开心的是重新思考后的思路写出来的代码一次通过✌️。

代码

解法1

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root){
return forEachNode(root, new ArrayList<>());
}

public boolean forEachNode(TreeNode node, List<Integer> val){
if (null == node) {
return true;
}
if (!forEachNode(node.left, val)){
return false;
}
if (!validOrAdd(val, node)){
return false;
}
if (!forEachNode(node.right, val)){
return false;
}
return true;
}
public boolean validOrAdd(List<Integer> val, TreeNode node){
if(val.size() > 0 && val.get(val.size() - 1) >= node.val){
return false;
}else{
return val.add(node.val);
}
}
}

解法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
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root){
return subValidBSTLeft(root, null, null);
}

public boolean subValidBSTLeft(TreeNode node, Integer min, Integer max) {
if (null == node){
return true;
}
if (null == min && null == max){
}else if (null == min && null !=max && node.val < max){
}else if (null != min && null == max && min < node.val){
}else if (null != min && null != max && min < node.val && node.val < max){
}else {
return false;
}
// left
if (!subValidBSTLeft(node.left, min, node.val)){
return false;
}
// right
if (!subValidBSTLeft(node.right, node.val, max)){
return false;
}
return true;
}
}

102. 二叉树的层次遍历

问题

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resp = new ArrayList<>();
levelOrder(root, 0, resp);
return resp;
}
public void levelOrder(TreeNode cur, int cur_level, List<List<Integer>> resp) {
if(null == cur){
return;
}
if(cur_level == resp.size()){
resp.add(new ArrayList<>());
}
resp.get(cur_level).add(cur.val);
levelOrder(cur.left, cur_level+1, resp);
levelOrder(cur.right, cur_level+1, resp);
}
}

一次过


104. 二叉树的最大深度

问题

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

解答

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxDepth(TreeNode root) {
return maxDepth(root, 0);
}
public int maxDepth(TreeNode cur, int level) {
if(null == cur) return level;
int left_level = maxDepth(cur.left, level + 1);
int right_level = maxDepth(cur.right, level + 1);
return left_level > right_level ? left_level: right_level;
}
}

一次过


111. 二叉树的最小深度

题目

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最小深度 2.

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int minDepth(TreeNode root) {
return minDepth(root, 0);
}

public int minDepth(TreeNode cur, int level) {
if (null == cur) return level;
if (null == cur.left && null == cur.right) {
return level + 1;
} else if (null != cur.left && null == cur.right) {
return minDepth(cur.left, level + 1);
} else if (null == cur.left && null != cur.right) {
return minDepth(cur.right, level + 1);
} else {
int left_level = minDepth(cur.left, level + 1);
int right_level = minDepth(cur.right, level + 1);
return left_level > right_level ? right_level : left_level;
}
}
}

141. 环形链表

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

正常的解题思路,通过记录走过的节点来判断是否有环。

时间复杂度:O(n),对于含有 n 个元素的链表,我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1) 的时间。

空间复杂度:O(n),空间取决于添加到哈希表中的元素数目,最多可以添加 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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<Integer> points = new HashSet<Integer>();
ListNode cur = head;
while (null != cur){
int curHashCode = cur.hashCode();
if(points.contains(curHashCode)){
return true;
}
points.add(curHashCode);
cur = cur.next;
}
return false;
}
}

第二种解题思路是双指针大小步,一个指针每次走一步,另一个指针每次走两步,如果有环的话则两个指针最终会相遇。

在最糟糕的情形下,时间复杂度为 O(N+K),也就是 O(n)。

空间复杂度:O(1),我们只使用了慢指针和快指针两个结点,所以空间复杂度为 O(1)。

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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (null == head){
return false;
}else if (null == head.next){
return false;
}else if (head == head.next.next){
return true;
}
ListNode minCur = head.next;
ListNode maxCur = head.next.next;
while (minCur != maxCur){
if (null == minCur.next){
return false;
}else if (null == maxCur.next){
return false;
}else if (null == maxCur.next.next){
return false;
}
minCur = minCur.next;
maxCur = maxCur.next.next;
if (minCur == maxCur){
return true;
}
}
return false;
}
}

146. LRU缓存

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

链接:https://leetcode-cn.com/problems/lru-cache

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
from collections import OrderedDict

class LRUCache(object):

def __init__(self, capacity):
"""
:type capacity: int
"""
self._cache = OrderedDict()
self._size = capacity

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self._cache:
return -1
val = self._cache.pop(key)
self._cache[key] = val
return val

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self._cache:
self._cache.pop(key)
self._cache[key] = value
else:
if len(self._cache) == self._size:
self._cache.popitem(last=False)
self._cache[key] = value


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

有序字典的解法
时间复杂度 O(1)
空间复杂度 O(capacity)

Java 解法需要 LinkedHashMap TODO

LRU(Least Recently Used)最少最近使用,一种页面置换算法。

LFU(Least Frequently Used)最近最不常用。

其它

LRU


206. 反转链表

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class ReverseLinkedList {
public static void main(String[] args) {
ListNode listNode = ListNode.of(
1,
ListNode.of(
2,
ListNode.of(
3,
ListNode.of(
4,
ListNode.of(
5, null
)
)
)
)
);
ListNode next = listNode;
while (null != next) {
System.out.println(next.val);
next = next.next;
}

System.out.println("===");
ListNode reverse = reverse3(listNode);

ListNode next2 = reverse;
while (null != next2) {
System.out.println(next2.val);
next2 = next2.next;
}
}

/**
* 官方推荐的
* @param head
* @return
*/
public static ListNode reverse2(ListNode head) {
// prev -> curr -> nextTemp
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}

/**
* 自己写的
* @param head
* @return
*/
public static ListNode reverse(ListNode head) {
// cur -> prev -> tmp
ListNode cur = head;
ListNode next = head.next;
head.next = null;
while (null != cur) {
ListNode tmp = null;
if (null != next) {
tmp = next.next;
next.next = cur;
}
if (null == next) {
break;
}
cur = next;
next = tmp;
}
return cur;
}

/**
* 复写的
* 1. 记录前一个节点,当前节点
* 2. 迭代
* 3. 取出当前节点到临时变量
* 4. -- 现在有 prev -> curr -> next 三个节点
* 5. 将 curr.next -> prev,改变指向方向
* 6. 依次挪动节点位置 prev = curr , curr = nextTemp
* 7. 最后返回 prev
*
* 时间复杂度 O(n)
* 空间复杂度 O(1)
* @param head
* @return
*/
public static ListNode reverse3(ListNode head) {
// prev -> curr -> next
ListNode prev = null;
ListNode curr = head;
while (null != curr) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}

208. 实现 Trie (前缀树)

题目

实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

分析

前缀树
Trie
字典树

解答

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
public class Trie {
private final int SIZE = 26;
private Node root;

private class Node {
private boolean isStr;
private int num;
private Node[] child;

public Node() {
child = new Node[SIZE];
isStr = false;
num = 1;
}
}

public Trie() {
root = new Node();
}

public void insert(String word) {
if (null == word || word.isEmpty()) {
return;
}
Node pNode = this.root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (pNode.child[index] == null) {
Node tmp = new Node();
pNode.child[index] = tmp;
} else {
pNode.child[index].num++;
}
pNode = pNode.child[index];
}
pNode.isStr = true;
}

public boolean search(String word) {
if (null == word || word.isEmpty()) {
return false;
}
Node pNode = this.root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (pNode.child[index] == null || (word.length() - i == 1 && pNode.child[index].isStr == false)) {
return false;
}
pNode = pNode.child[index];
}
return true;
}

public boolean startsWith(String prefix) {
if (null == prefix || prefix.isEmpty()) {
return false;
}
Node pNode = this.root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (pNode.child[index] == null) {
return false;
}
pNode = pNode.child[index];
}
return true;
}
}


703. 数据流中的第K大元素

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.PriorityQueue;

public class KthLargest {
private PriorityQueue<Integer> minHeap;
private int kSize;

public KthLargest(int k, int[] nums) {
kSize = k;
minHeap=new PriorityQueue<Integer>(kSize);
for (int i = 0; i< nums.length; i++){
add(nums[i]);
}
}

public int add(int val) {
if (minHeap.size() < kSize){
minHeap.offer(val);
}else if (minHeap.peek() < val){
minHeap.poll();
minHeap.offer(val);
}
return minHeap.peek();
}
}

Java中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。

关于堆操作:https://shmilyaw-hotmail-com.iteye.com/blog/1775868

操作说明:

方法名功能描述
add(Ee)在队列头部增加一个元素,如果容量已满,则抛出异常,成功则返回true。
clear()清空
contains(Objecto)检查是否包含当前参数元素
offer(Ee)在队列头部增加一个元素,如果容量已满,则返回false,成功加入,返回true。
peek()返回队列头部节点,但不移除队列头节点。
poll()将队列头部元素移出队列并返回。
remove(Objecto)将队列头部元素移出队列并返回,如果队列为空,则抛出异常。
size()返回长度

原文作者:noogel

原文链接:https://noogel.xyz/2019/08/29/2.html

发表日期:2019-08-29

版权声明:本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 数据结构
  2. 2. 算法思想
    1. 2.1. 分治法
    2. 2.2. 贪心算法
    3. 2.3. 动态规划(Dynamic Programming)
    4. 2.4. 回溯法(backtracking)
    5. 2.5. 分支界限法
    6. 2.6. 概率算法
  3. 3. 练习题
    1. 3.1. 15. 三数之和
      1. 3.1.1. 题目
      2. 3.1.2. 解题思路
      3. 3.1.3. 解题思维
      4. 3.1.4. 解题代码
    2. 3.2. 22. 括号生成
      1. 3.2.1. 题目
      2. 3.2.2. 思路
      3. 3.2.3. 解答
    3. 3.3. 49、242. 字母异位词
    4. 3.4. 51. N皇后
      1. 3.4.1. 题目
      2. 3.4.2. 思路
      3. 3.4.3. 解题
    5. 3.5. 69. x 的平方根
      1. 3.5.1. 思路
      2. 3.5.2. 解答
      3. 3.5.3. 扩展
    6. 3.6. 98. 验证二叉搜索树
      1. 3.6.1. 题目
      2. 3.6.2. 思路
      3. 3.6.3. 代码
    7. 3.7. 102. 二叉树的层次遍历
      1. 3.7.1. 问题
      2. 3.7.2. 解答
    8. 3.8. 104. 二叉树的最大深度
      1. 3.8.1. 问题
      2. 3.8.2. 解答
    9. 3.9. 111. 二叉树的最小深度
      1. 3.9.1. 题目
      2. 3.9.2. 解答
    10. 3.10. 141. 环形链表
    11. 3.11. 146. LRU缓存
      1. 3.11.1. 其它
    12. 3.12. 206. 反转链表
    13. 3.13. 208. 实现 Trie (前缀树)
      1. 3.13.1. 题目
      2. 3.13.2. 分析
      3. 3.13.3. 解答
    14. 3.14. 703. 数据流中的第K大元素