数据结构与算法练习

发表于 | 更新于 | 分类于

如何精通一个领域

  • 切碎知识点
  • 刻意练习
    • 练习缺陷，弱点地方
    • 感觉不舒服，不爽，枯燥
  • 反馈

基本常用的数据结构

时间和空间复杂度 描述
O（1） 常数复杂度
O（log n） 对数复杂度
O(n) 线性时间复杂度
O(n^2) 平方
O(n^3) 立方
O(2^n) 指数
O(n!) 阶乘

数组和链表的数据结构

数组：内存里一段连续的存储区域

  • 查询的时间复杂度：O(1)
  • 插入的时间复杂度：O(n)
  • 删除的时间复杂度：O(n)

链表：分为单链表和双链表

  • 查询的时间复杂度：O(n)
  • 插入的时间复杂度：O(1)
  • 删除的时间复杂度：O(1)
相关案例

206.翻转链表

1
2
3
4
5
6
7
8
9
10
11
class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, prev = head , None
        while cur:
            cur.next,prev,cur = prev,cur,cur.next
        return prev

24：交换链表相邻的两个元素

1
2
3
4
5
6
7
8
9
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre,pre.next = self,head
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
            pre.next, b.next, a.next = b,a,b.next
            pre = a
        return self.next

141.环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 解题思路:根据快慢指针来判断这个链表中是否有环形的存在
class Solution(object):
        def hasCycle(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            fast = slow = head
            while slow and fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if slow is fast:
                    return True
            return False

堆栈和队列

栈：先入后出
队列：先进先出

相关案例

20.判断括号是否合法

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        paren_map = {')':"(","]":"[","}":"{"}
        for c in s:
            if c not in paren_map:
                stack.append(c)
            elif not stack or paren_map[c] != stack.pop():
                return False
        return not stack

232.用栈来实现队列

225.用队列事现栈

优先队列

实现机制：

  1. 使用堆(heap)来实现
  2. 使用二叉搜索树
相关案例

703.实时判断数据流中k大的元素

239.滑动窗口最大值

映射(map) 和 集合（set）

如何解决哈希碰撞？

  • 拉链法
  • 开放寻址法

​ hashMap vs TreeMap
hashSet vs TreeSet
python中使用的是hashmap和hashset

相关案例

242.有效的异位字符

1
2
3
4
5
6
7
8
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dic1,dic2 = {},{}
        for item in s:
            dic1[item] = dic1.get(item,0)+1
        for item in t:
            dic2[item] = dic2.get(item,0)+1
        return dic1 == dic2

1.两数之和

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = dict()
        for i,x in enumerate(nums):
            if target - x in hash_map:
                return [hash_map[target - x],i]
            hash_map[x] = i

15.三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0 :l +=1
                elif s > 0:r -= 1
                else:
                    res.append((nums[i],nums[l],nums[r]))
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l +=1;r -= 1
        return list(map(list,res))

18.四数之和

树&二叉树&二叉搜索树

链表就是特殊化的Tree

Tree就是特殊化的图

实现二叉树

1
2
3
4
5
6
# python
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
二叉搜索树

二叉搜索树,也成为二叉搜索树,有序二叉树,排序二叉树,是指一颗空树或者具有下列性质的二叉树

  1. 左子树上所有节点的值均小于它的根节点的值
  2. 右子树上所有的值均大于它的根节点的值
  3. 左右子树也分别为二叉查找树
相关案例

98.验证二叉搜索树

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
# 低效法
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        inorder = self.inorder(root)
        return inorder == list(sorted(set(inorder)))
    def inorder(self,root):
        if root is None:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)

    
    
# 中序遍历
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.prev = None
        return self.helper(root)
    
    def helper(self,root):
        if root is None:
            return True
        if not self.helper(root.left):
            return False
        if self.prev and self.prev.val >= root.val:
            return False
        self.prev = root
        return self.helper(root.right)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if p.val < root.val > q.val:
            return self.lowestCommonAncestor(root.left,p,q)
        if p.val > root.val < q.val:
            return self.lowestCommonAncestor(root.right,p,q)
        return root

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root == None or root == p or root == q:return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left == None:
            return right
        elif right == None:
            return left
        else:
            return root

二叉树的遍历

前序遍历(Pre-order):根-左-右

中序遍历(in-order):左-根-右

后序遍历(Post-order):左-右-根

递归和分治

相关例题

50. Pow(x, 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
# 递归法
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if not n:
            return 1
        if n < 0:
            return 1/self.myPow(x,-n)
        if n % 2 :
            return x * self.myPow(x,n-1)
        return self.myPow(x*x,n/2)
 
# 非递归方式
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0:
            x = 1/x
            n = -n
        pow = 1
        while n:
            if n & 1:
                pow *= x
            x *=x
            n >>=1
        return pow

169. 求众数

1
2


贪心法

适用贪心法的场景

简单来说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解,这种子问题最优解成为最优子结构

贪心算法与动态规划的不同在于对每个子问题的解决方案都作出选择,不能回退,动态规划则会保存以前的运行结果,并根据以前的结果对当前进行选择,有回退的功能

相关案例

122.买卖股票的最佳时机 II

广度优先搜索

深度优先搜索

102.二叉树的层次遍历

1
2


104.二叉树的最大深度

111.二叉树的最小深度

22. 括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def generateParenthesis(self, n: int):
        self.list = []
        self._gen(0, 0, n, "")
        return self.list

    def _gen(self, left, right, n, result):
        if left == n and right == n:
            self.list.append(result)
            return
        if left < n:
            self._gen(left + 1, right, n, result + "(")

        if left > right and right < n:
            self._gen(left, right + 1, n, result + ")")

剪枝

把较差的枝叶剪掉

相关案例

51.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
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    def solveNQueens(self, n: int):
        if n < 1: return []
        self.result = []
        self.cols = set()
        self.pie = set()
        self.na = set()
        self.DFS(n, 0, [])
        return self._generate_result(n)

    def DFS(self, n, row, cur_state):
        if row >= n:
            self.result.append(cur_state)
            return
        for col in range(n):
            if col in self.cols or row + col in self.pie or row - col in self.na:
                continue
            self.cols.add(col)
            self.pie.add(row + col)
            self.na.add(row - col)

            self.DFS(n, row + 1, cur_state + [col])

            self.cols.remove(col)
            self.pie.remove(row + col)
            self.na.remove(row - col)

    def _generate_result(self, n):
        board = []
        for res in self.result:
            for i in res:
                board.append('.' * i + "Q" + '.' * (n - i - 1))
        return [board[i:i + n] for i in range(0, len(board), n)]


def solveNQueens( n: int):

    def DFS(queens, xy_dif, xy_sum):
        p = len(queens)
        if p == n:
            result.append(queens)
            return None
        for q in range(n):
            if q not in queens and p - q not in xy_dif and p + q not in xy_sum:
                DFS(queens + [q], xy_dif + [p - q], xy_sum + [p + q])

    result = []
    DFS([], [], [])
    return [['.' * i + 'Q' + '.' * (n - i - 1) for i in sol] for sol in result]

52

36/37 数读

1
2


二分查找

1
2


实战例题

69.x 的平方根

1
2
3
4
5
6
class Solution(object):
	def mySqrt(self,x):
		r = x
		while r * r > x:
			r = (r + x/r)/2
		return r

字典树

  1. Trie树的数据结构
    1. Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎用于文本词频统计 。它的优点是最大限度的减少无所谓的字符串比较，查询效率比哈希表高
  2. Trie树的核心思想
    1. Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的
  3. Trie树的基本性质
    1. 根节点不包含字符，除根节点之外每个节点只包含一个字符
    2. 从根节点到某一节点，路径经过的字符串连接起来，为该节点对应的字符串
    3. 每个节点所有子节点包含的字符都不相同
实战例题

208 实现 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
class Trie(object):
    def __init__(self):
        self.root = {}
        self.end_of_word = "#"

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_of_word] = self.end_of_word

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end_of_word in node

    def startWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

79. 单词搜索

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
END_OF_WORD = "#"


class Solution(object):
    def findWords(self, board, words):
        if not board or not board[0]: return []
        if not words: return []

        self.result = set()  # 用于装载最后的结果

        # 将word全部插入字典树中
        root = collections.defaultdict()
        for word in words:
            node = root
            for char in word:
                node = node.setdefault(char, collections.defaultdict())
            node[END_OF_WORD] = END_OF_WORD

        self.m, self.n = len(board), len(board[0])

        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] in root:
                    self._dfs(board, i, j, "", root)

    def _dfs(self, board, i, j, cur_word, cur_dict):
        cur_word += board[i][j]
        cur_dict = cur_dict[board[i][j]]

        if END_OF_WORD in cur_dict:
            self.result.add(cur_word)

        tmp, board[i][j] = board[i][j], "@"
        for k in range(4):
            x, y = i + dx[k], j + dy[k]
            if 0 <= x < self.m and 0 <= y < self.n and board[x][y] != "@" and board[x][y] in cur_dict:
                self._dfs(board, x, y, cur_word, cur_dict)
        board[i][j] = tmp

位运算

  1. 位运算介绍

    1. 计算机中的内存是以二进制的形式存储的，位运算说白了，就是直接对整数在内存中的二进制位进行操作

  2. 位运算常用操作

    1. | 符号 | 描述 | 运算规则 |
      | —- | —- | ———————————————————— |
      | & | 与 | 两个都为1时，才为1 |
      | | | 或 | 两个都为0时，才为0 |
      | ^ | 异或 | 两个相同为0，相异为1 |
      | - | 取反 | 0变1,1变0 |
      | << | 左移 | 各二进制位全部左移若干位，高位丢弃，低位补0 |
      | >> | 右移 | 各二进制位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算数右移），有的补0（符号右移） |

  3. 位运算的应用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    x & 1 == 1 OR == 0 判断奇偶（x%2==1）
    x = X&(X-1)=> 清零最低位的1
    x & -x => 得到最低位的1

    1.将x 最右边的n位清零 - x & （~0 << n）
    2.获取x的第n位值（0或1）-（x >> n） & 1
    3.获取x的第n位的幂值 - x & （1 << (n-1)）
    4.仅将第n位值为1 - x | （1 << n）
    5.仅将第n位置为0 - x & （~（1 << n））
    6.将x最高位至第n位（含）清零 - x & （（1 << n）-1）
    7.将第n为至第0位（含） 清零 - x &（~（（1 << (n+1)）-1））
实战例题

191.位1的个数

1
2
3
4
5
6
7
8
9
10
11
12
def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        rst = 0
        mask = 1
        for i in range(32):
            if n&mask:
                rst += 1
            mask = mask << 1
        return rst

231. 2的幂

1
2
def isPowerOfTwo(n):
    return n > 0 and not(n & n-1)

338.比特位计数

52. N皇后 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def totalNQueens(self,n):
    if n < 1:return []
    self.count = 0
    self.DFS(n,0,0,0,0)
    return self.count
def DFS(self,n,row,cols,pie,na):
    if row >= n:
        self.count += 1
        return 
    bits = (~(cols | pie | na)) & ((1 << n)-1) # 得到当前所有空位
    
    while bits:
        p = bits & -bits  # 取到最低位1
        self.DFS(n,row+1,cols | p,(pie | p) << 1,(na | p) >> 1)
        bits = bits & (bits - 1) # 去掉最低位的1

动态规划

1.递归 + 记忆化 – 》 递推

2.状态的定义 ： opt[n],dp[n],fib[n]

3.状态转移方程：opt[n] = best_of(opt[n-1],opt[n-2])

4.最优子结构

1
2
递推公式
F[n] =F[n-1] + F[n-2]