跟力扣斗智斗勇-log-1

跟力扣斗智斗勇-log-1
数据结构与算法
链表反转问题
素数
区分二叉树遍历
深度-广度优先遍历
前中后序遍历
ArrayList-LinkedList
题解
160. 相交链表
数组中落单的两个数
方法
投票算法
快慢指针
动态规划
坑
python-取整与整除
借物表

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

数据结构与算法

课程: 速览 ing

链表反转问题

迭代(栈) / 递归

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

素数

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

暴力法: 遍历 2 到 $\sqrt{n}$ 之前的数字,如果能被整除,那么这个数字不是素数
for(int i = 2; i * i < x; i++){}
埃塞法: 比如找 100 内有多少个素数 (25 个)
构造 bool[100]
找到 3 是素数, 那么 3x3=3, 3x4=12, 3x5=15…3x33=99 都不是素数,对应 bool[i]做标记,遍历时跳过

区分二叉树遍历

深度-广度优先遍历

深度优先遍历: 递归

public void inOrder(TreeNode root) {
  if (root == null)
    return;
  inOrder(root.left);
  bstQueue.offer(root.val);
  inOrder(root.right);
}

广度优先遍历: 队列

public void inOrder(TreeNode root) {
  if (root == null)
    return;
  bstQueue.offer(root.val);
  inOrder(root.left);
  inOrder(root.right);
}

前中后序遍历

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

基本上是递归模板,比如中序遍历 BST 如下:
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]

public void inOrder(TreeNode root) {
  if (root == null)
    return;
  bstQueue.offer(root.val);
  inOrder(root.left);
  inOrder(root.right);
}

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]

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 步后在交叉绿点相遇

数组中落单的两个数

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。^[6]

https://github.com/Weidows-projects/public-post/blob/main/LeetCode/code/数组中落单的两个数.py

def findTwoSingleNum(array):
    # 两个独立数的异或
    buff = 0
    for i in array:
        buff ^= i

    bias = 0
    # 从末尾轮着找为'1'的位 (也就是两独立数不同的位)
    while (buff & 1 != 1):
        buff >> 1
        bias += 1

    res_0, res_1 = 0, 0
    # 通过第bias位的0和1分为两个child-array, 分别all-XOR后就是两个结果
    for i in array:
        if (i >> bias & 1 == 1): res_1 ^= i
        else: res_0 ^= i

    return [res_0, res_1]

# 4:    100
# 5:    101
# 4^5:  001
# xxx1&1: 1
arr = [1, 1, 2, 2, 3, 3, 4, 5]
print(findTwoSingleNum(arr))

方法

投票算法

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

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

快慢指针

常用于链表

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

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
}

寻找链表中点

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]

状态矩阵 dp[n][n]
dp[i][j] 一般存储第 i 到 j 位通过条件转换后的状态位/数值
条件转换方程
条件: if-else
转换方程: 类似 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 这种形式
最终结果就是最后一趟 i,j 的位置: 如下的 dp[0][ n - 1]

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

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 \ j	0	1	2	3	4	5	6	7	8	9
9										1
8									1	x
7								1	x	x
6							1	x	x	x
5						1	x	x	x	x
4					1	x	x	x	x	x
3				1	x	x	x	x	x	x
2			1	x	x	x	x	x	x	x
1		1	x	x	x	x	x	x	x	x
0	1	x	x	x	x	x	x	x	x	x

坑

python-取整与整除

# 整除: 对于正数是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