算法题

python version

Posted on Feb.4, 2020


递归

  • 斐波那契数列(如:爬楼梯)
  • fib1 \(O(2^{n})\): f(n-1)+f(n-2)，因为n每增1，新增几乎成倍的重复计算 [递归]
  • fib2 \(O(n)\): list.append(li[-1]+li[-2])，空间换时间 [迭代]
  • fib3 \(O(n)\): c=a+b a=b b=c，空间为O(1),速度也比fib2快(append略微耗时) [迭代]
  • 汉诺塔
  • 更典型：大问题可以靠几部分小问题完成，而小问题本质上和大问题是一个问题，只是规模小。
  • 二分查找、斐波那契还可以通过非递归的方式解决。但汉诺塔问题是不用递归就很难解决的。

查找

  • 内置函数
    •       x in li 返回bool型
      li.index(x) 返回下标
      #li.find(x) 上面两种列表可用，find只有字符串可以用
  • 线性查找(顺序查找)
  • 二分查找(对于有序列表)
    • #引用，浅复制，深复制
    普通的列表赋值是引用。切片才是浅复制。如果要完全复制，用深复制copy.deepcopy()。 对于查找，不要用切片，因为复制要存储、要时间，对于候选区把下标low/high记录下来就好了。
    #尾递归
    二分查找 可以用①循环的方式写。也可以用②递归的方式。 然后把递归放在最后，有些编程语言(python不是)可以把尾递归优化成循环，和①一样的效率，因为它递归跳进来不用跳出去，和循环一样。

排序

时间复杂度，稳定性，初始序列对复杂度影响，每一次是否放在最终位置。
    插入排序 ①直接插入排序 O(N2) 排序Low B三人组:1、3、5
    ②希尔排序 O(Nd)
    交换排序 ③冒泡排序 O(N2)
    ④快速排序 O(NlogN) 排序NB三人组:4、6、7
    选择排序 ⑤简单选择排序 O(N2)
    ⑥堆排序 O(NlogN)
    ⑦归并排序 O(NlogN)
    ⑧基数排序 O(P(N+B)) 没什么人用的排序:2、8、9
    ⑨桶排序
  • Python内置函数sorted()和列表方法sort()可以使用key参数指定排序规则，并且都是稳定排序。
    list.sort()和sorted()都接受一个参数reverse(True or False)来
    • 紧挨着换的，都是稳定的；飞(跨越)着换的，都是不稳定的。

搜索

  • BFS
    •           性价比之王的宽度优先搜索
          
#字典存图
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}

#传入参数，至少是图graph和起始点vertex
def BFS(graph, s):
    queue = []
    queue.append(s)
    #python里的集合，用的是哈希表(hash)。查找比数组要快些。
    seen = set()
    seen.add(s)

    while (len(queue) > 0):
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
        print(vertex)
          
      
              LeetCode 547. 朋友圈
          给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
          示例 1:
            输入:
            [[1,1,0],
             [1,1,0],
             [0,0,1]]
            输出: 2
            说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
            第2个学生自己在一个朋友圈。所以返回2。

            示例 2:

            输入:
            [[1,1,0],
             [1,1,1],
             [0,1,1]]
            输出: 1
            说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
          
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        count = 0
        for i in range(len(M)):
            if M[i][i] == 1:
                count += 1
              #然后bfs，一层层把所有连通的朋友找到。先距离为1的，然后距离为2的。遍历连通子图，并作出动作(这里动作是M[j][j] = 2)。
                self.BFS(i, M)
        return count


    def BFS(self, student, M):
        queue = []
        queue.append(student)
        while len(queue):
            size = len(queue)
            #你看这个i没用到。其实这个if写不写oj都能通过。但这条语句控制了每轮搜索的点到起点的距离相同。按距离一批一批地清晰划分出pop出队的点。
            for i in range(0, size) :
                #出队列
                j = queue.pop(0)
                #动作
                M[j][j] = 2
                for k in range(len(M[0])):
                    if M[j][k] == 1 and M[k][k] == 1:
                  #M[j][k]==1保证距离为1的入队，M[k][k]==1保证没有被遍历到的才入队
                          queue.append(k)
  • DFS
    • BFS遍历里queue改为stack，vertex = stack.pop()就成了DFS遍历。
    如果面试官不特别要求，dfs都可以用递归的方式来实现。
    注意三要素：#定义 #出口 #拆解 
              LeetCode 93. 复原IP地址
          给定一个只包含数字的字符串，复原它并返回所有可能的IP地址格式。
          示例 输入: "25525511135"  输出: ["255.255.11.135", "255.255.111.35"]
          
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        #深度优先搜索
        #定义
        def dfs(s, part, ips, ip):
            #出口
            if part == 4:
                if s == "":
                    ips.append(ip[1:])
                return
            #拆解
            for i in range(1, 4):
                if i <= len(s):
                    if int(s[:i]) <= 255:
                        dfs(s[i:], part+1, ips, ip+"."+s[:i])
                    if s[0] == "0": break

        ips = []
        dfs(s, 0, ips, "")
        return ips

序列化

1.将内存中的数据持久化存储时 2.网络传输时 需要序列化。
  • 什么是序列化
    将“内存”中结构化的数据变成“字符串”的过程
    序列化：object to string - 反序列化：string to object
  • 常用方式

    • •XML

    •Json

    •Thrift(by Facebook)

    •ProtoBuf(by Google)

  • 序列化算法
    • 一些序列化的例子：
    • 比如一个数组， 里面都是整数， 我们可以简单的序列化为”[1,2,3]”
    • 一个整数链表， 我们可以序列化为， ”1->2->3”
    • 一个哈希表(HashMap)， 我们可以序列化为， ”{\”key\”: \”value\”}”
  • 二叉树如何序列化
    • 你可以使用任何你想要用的方法进行序列化， 只要保证能够解析回来即可。 LintCode 采用的是 BFS 的方式对二叉树数据进行序列化， 这样的好处是， 你可以更为容易的自己画 出整棵二叉树。

动态规划

  • dp步骤：
    • •1.确定状态
    •2.转移方程
    •3.初始条件&边界情况
    •4.计算顺序 
    dp题目特点：1.计数 2.求最值 3.求存在性
       LeetCode 322. 零钱兑换
       给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
       
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        MAX = 10000000

        dp = [MAX] * (amount+1)
        dp[0] = 0

        for i in range(amount+1):
            #for j, coin in enumerate(coins):
            for coin in coins:
                if i - coin < 0:
                    continue
                dp[i] = min(dp[i-coin]+1, dp[i])

        return -1 if dp[amount]==MAX else dp[amount]
       
  
    1.确定状态
根据两个思想：①最后一步 ②子问题
f(X)=如:最少用多少枚硬币拼出X，X为问题规模
f[X]或写为dp[i],我们用方括号。圆括号往下做就成了对函数的递归。而dp我们会开辟一个数组。
开辟数组时，
s1 = [1]*5
s2 = [1 for i in range(5)]是一个效果。

2.转移方程
dp[i] = min{dp[i-2]+1,dp[i-5]+1,dp[i-7]+1}

3.初始条件&边界情况
(以下f视为dp)
两个问题，X-2/5/7小于0怎么办? 什么时候停下来？
边界情况：f[-1] = f[-2] = … .= 正无穷
初始条件：f[0] = 0

用转移方程算不出来，需要手工定义，即初始条件。如f[1]可用转移方程算出正无穷，但f[0]不能，它等于0，与转移方程的结果矛盾。
不要数组越界，就是考虑边界情况。

4.计算顺序
一般按从小到大。
比如这里，计算f[X]时，f[X-2]、f[X-5]、f[X-7]应该都已经得到结果了，它们在for循环里趟次靠前。

leetcode使用

  • 刷题清单 CS-Notes|Leetcode题解-目录.md
  • 题目笔记
    • 算法小抄
  • 题解 Discuss → High-voted solution → Top comments
  • 插件 九章刷题小助手
  • 根据Company tag & Frequency tag来刷
  • Documentation 记录文档，把这么一个思路记录下来。思维、时间复杂度、其他解法、必要注释。
    一定要亲自写，还能在重复过程中refine它，这才成为你知识库的一部分。[亲历亲为]
  • 刷题最好一种语言从一而终
  • 记录

练习网站

  • https://leetcode-cn.com/problemset/lcof/
  • https://www.nowcoder.com/interview/center
  • https://github.com/CyC2018/CS-Notes

Proficient Python

Coding style

是写出bug free的基础
  • 面试心得，值得一看
  • 令狐冲jiuzhang from 34:00

    • 独孤九剑——总决式
    想要做到Bug Free 最重要的是优化你的Coding Style
    技巧：子函数 + 好的命名风格

  • 避免三层以上的缩进
    方式1:break 方式2:def another_func(self)
    因为if...else越多越容易出bug
  • 命名法 python最主流是蛇形命名法
    驼峰-findLongestString()
    蛇形-find_longest_string()
  • 代码质量(Coding Quality)很重要
  • 好的代码质量包括:
  • -Bug Free
  • -好的代码风格(Coding Style)，包括变量名命名规范有意义，合理的使用空格，善用空行
  • 见PEP8 Python 编码规范 Pycharm command+option+L
  • VSCode command+P+搜索: Convert Indentaion to Spaces
  • -容易让人读懂的逻辑。要把复杂的事情用简单的方式，别把简单的事情写复杂了
  • -没用冗余代码
  • -有边界检测和异常处理
    最基本比如，进来后先检测参数
      关于OJ的测试用例
      
class Solution:
    def print_name(self,s):
    print(s)

object1 = Solution()
object1.print_name('绑定方法对象，实例是隐含的') #lintcode后台就是这么做。

object2 = Solution()
Solution.print_name(object2, '未绑定的方法对象，需要传递一个实例')