跟力扣斗智斗勇-log-1

⏩ 文章地址 | ✔️ 仓库地址 欢迎提交 pr !

一题二写，三数之和，题解四瞅五瞄六瞧，水平还七上八下九流，十分辣鸡
十天九考，八皇会面，题干七页六道五问，答案仅四行三言两语，一点不会

分割线

数据结构与算法

课程: 速览 ing

链表反转问题

迭代(栈) / 递归

这问题我面试时问我了,我回答的就是栈,面试官说栈要遍历两次,而递归一次就能出(函数参数添加 prev 节点)

素数

非素数(合数) / 素数(质数) : 都要排除 0 和 1

  • 暴力法: 遍历 2 到 n\sqrt{n} 之前的数字,如果能被整除,那么这个数字不是素数

    1
    for(int i = 2; i * i < x; i++){}

  • 埃塞法: 比如找 100 内有多少个素数 (25 个)

    构造 bool[100]

    找到 3 是素数, 那么 3x3=3, 3x4=12, 3x5=15…3x33=99 都不是素数,对应 bool[i]做标记,遍历时跳过

区分二叉树遍历

深度-广度优先遍历

  • 深度优先遍历: 递归

    1
    2
    3
    4
    5
    6
    7
    public void inOrder(TreeNode root) {
      if (root == null)
        return;
      inOrder(root.left);
      bstQueue.offer(root.val);
      inOrder(root.right);
    }

  • 广度优先遍历: 队列

    1
    2
    3
    4
    5
    6
    7
    public void inOrder(TreeNode root) {
      if (root == null)
        return;
      bstQueue.offer(root.val);
      inOrder(root.left);
      inOrder(root.right);
    }

前中后序遍历

前序也叫先序, 这三种都属于深度优先遍历

  • 基本上是递归模板,比如中序遍历 BST 如下:

    1
    2
    3
    4
    5
    6
    7
    public void inOrder(TreeNode root) {
      if (root == null)
        return;
      inOrder(root.left);
      bstQueue.offer(root.val);
      inOrder(root.right);
    }

    详见这个题解: https://github.com/Weidows-projects/public-post/blob/main/LeetCode/code/173.二叉搜索树迭代器.java

  • 前后序遍历: [3]

    1
    2
    3
    4
    5
    6
    7
    public void inOrder(TreeNode root) {
      if (root == null)
        return;
      bstQueue.offer(root.val);
      inOrder(root.left);
      inOrder(root.right);
    }
    1
    2
    3
    4
    5
    6
    7
    public void inOrder(TreeNode root) {
      if (root == null)
        return;
      inOrder(root.left);
      inOrder(root.right);
      bstQueue.offer(root.val);
    }

分割线

ArrayList-LinkedList

顺序遍历时间复杂度相同, n 相同时 LinkedList 空间更大

  • ArrayList:

    随机查询快, 插入和删除慢(不可随机)

    随机指的是对任意指定 index 的操作

  • LinkedList:

    随机查询慢, 插入和删除快(可随机)

    linkedlist 排序性能更好,并且较 arraylist 更节省空间 [4]

分割线

题解

160. 相交链表

https://github.com/Weidows-projects/public-post/blob/main/LeetCode/code/160.相交链表.py

  • 此方法简单描述就是交叉接尾
    [1]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution(object):
        def getIntersectionNode(self, headA, headB):
            """
            :type head1, head1: ListNode
            :rtype: ListNode
            """
            p, q = headA, headB
            while p != q:
                p = p.next if p else headB
                q = q.next if q else headA
            return p

    当前链表结尾后接上对方链表的头, 同时以两链表头为起点, 可以发现都走了 7 步后在交叉绿点相遇

分割线

方法

投票算法

可以看一下多数元素的题解 [2]

对于出现次数nn大于n2\frac{n}{2}的元素,能抵消其他元素还有余量,最后 candidate 必然是众数

分割线

快慢指针

常用于链表

  1. 判断是否存在 环, 相遇即成环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    func hasCycle(head *ListNode) bool {
      slow, fast := head, head
      for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
          return true
        }
      }
      return false
    }

  2. 寻找链表中点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    ListNode slow = head, fast = head;
    while (fast != tail) {
      slow = slow.next;
      fast = fast.next;
      if (fast != tail) {
        fast = fast.next;
      }
    }
    ListNode mid = slow;

分割线

动态规划

有的问题会需要前瞻后顾 找最优 "重叠" 子结构, 像是递归/迭代/贪心无法解决或者十分棘手, 瞥一眼又是中等+难度的, 多是 dp (dymanic-programming) 没跑了; 这种问题有个大致框架: [5]

  1. 状态矩阵 dp[n][n]

    dp[i][j] 一般存储第 i 到 j 位通过条件转换后的状态位/数值

  2. 条件转换方程

    条件: if-else

    转换方程: 类似 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 这种形式

  3. 最终结果就是最后一趟 i,j 的位置: 如下的 dp[0][ n - 1]

  • i, j 的遍历方向是根据转换方程来确定的, 比如 516.最长回文子序列 这个题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution(object):
        def longestPalindromeSubseq(self, s):
            """
            :type s: str
            :rtype: int
            """
            if len(s) < 2:
                return len(s)

            n = len(s)
            dp = [[0] * n for _ in range(n)]
            for i in range(n - 1, -1, -1):
                dp[i][i] = 1
                for j in range(i + 1, n):
                    if s[i] == s[j]:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    else:
                        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
            return dp[0][n - 1]

    在确定 dp[i][j] 前, 需要已经确定 dp[i+1][j] 和 dp[i][j-1]

    也就是说: 外层 i 为逆序,从上往下推, 内层 j 为正序从左往右推 (x 为所推的值)

    i \ j0123456789
    91
    81x
    71xx
    61xxx
    51xxxx
    41xxxxx
    31xxxxxx
    21xxxxxxx
    11xxxxxxxx
    01xxxxxxxxx

分割线

坑

python-取整与整除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 整除: 对于正数是int(), 对于负数是round()
print(3//2)          # 1
print(-3//2)         # -2
print(9//5)          # 1
print(-9//5)         # -2
# 向下取整
print(int(3 / 2))    # 1
print(int(-3 / 2))   # -1
# 四舍五入
print(round(3 / 2))  # 2
print(round(-3 / 2)) # -2
# 还有其他区别
print(int(14 - 3 / 2))  # 12 (14-1.5=12.5 -> 12)
print(int(14 - 3 // 2)) # 13 (14-1=13)
print(int(- 3 / 2))     # -1 (-1.5 -> -1)
print(int(-3 // 2))     # -2

分割线

借物表

[1]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/

[2]: https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/

[3]: https://blog.csdn.net/u013834525/article/details/80421684

[4]: jdk8 下 ArrayList 与 LinedList 排序效率对比

[5]: https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/zui-chang-hui-wen-zi-xu-lie-by-leetcode-hcjqp/