跟力扣斗智斗勇-log-1

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

分割线

数据结构与算法

课程: 速览 ing

链表反转问题

迭代(栈) / 递归

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


素数

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

  • 暴力法: 遍历 2 到 n\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]

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

分割线

快慢指针

常用于链表

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

    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. 寻找链表中点

    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.最长回文子序列 这个题

    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-取整与整除

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

分割线

借物表

[0]: ✔️ 仓库地址

[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/

[6]: 异或的用途