**142. 环形链表 II**

https://leetcode.cn/problems/linked-list-cycle-ii/

哈希法：

我的思路：

* 维护一个集合存储走过的节点，遇到走过的节点，进行一次判断，如果该节点在集合里面，则直接返回该节点。

```python
 class Solution:
     def detectCycle(self, head: ListNode) -> ListNode:
         dic = set()
         while head:
             if head not in dic:
                 dic.add(head)
             else:
                 return head
             head = head.next
         return
```

非常简单的思路，但为此做出的牺牲就是空间消耗

时间复杂度为：O(n)

空间复杂度为：O(n)


双指针：

大佬思路：

https://leetcode.cn/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/

```python
 class Solution:
     def detectCycle(self, head: ListNode) -> ListNode:
         fast = slow = head
         while fast and fast.next:
             fast = fast.next.next
             slow = slow.next
             if fast == slow:
                 ans = head
                 while ans != slow:
                     slow = slow.next
                     ans = ans.next
                 return ans
         return
```

这是一道数学题，认真看完，会有收获，遇到链表题都可以尝试双指针。

时间复杂度：O(n)，第二次相遇中，慢指针须走步数 a < a + ba<a+b；第一次相遇中，慢指针须走步数 a + b - x < a + ba+b−x<a+b，其中 xx 为双指针重合点与环入口距离；因此总体为线性复杂度；

空间复杂度：O(1)

PS：哈希法比双指针的快一点点


**92. 反转链表 II**

https://leetcode.cn/problems/reverse-linked-list-ii/

思路：

* 局部反转列表，由于要返回整个列表，需要构建头结点dummy_node
* 采用局部断链、接链的方法，一步一步反转，每一次反转2个节点，需要反转right-left次
* 如何反转2个节点：画图，自己断链，注意断链的顺序（可以看为两步）
  * 第一步，cur和next交换位置
  * 第二步，把next进节点进行头插法
  * 注意：pre节点始终不变，cur节点也始终不变

```python
 class Solution:
     def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
         pre = dummy = ListNode(-1)
         dummy.next = head
         for _ in range(left-1):  # 进行left-1次后移，直到pre指向需要反转的节点的前一个节点
             pre = pre.next
         cur = pre.next
         for _ in range(right-left):
             next = cur.next
             cur.next = next.next
             next.next = pre.next  
             pre.next = next
         return dummy.next
```

```python
 # 也可以写成 
 next = cur.next
 cur.next, next.next, pre.next = next.next, pre.next, next
 # 花里胡哨的方式，不推荐
```


**138. 复制带随机指针的链表**

https://leetcode.cn/problems/copy-list-with-random-pointer/

解法0 ：

深拷贝

```python
 class Solution(object):
     def copyRandomList(self, head):
         return copy.deepcopy(head)
```

解法一（连接法）：

连接法是将原链表和新链表连在一起，即 1 -> 1' -> 2 -> 2' -> 3 -> 3'，新链表节点始终在原链表节点的后面 构建连接的链表 复制random节点，如果有random，就复制（这里不需要判断cur.next）是否存在，因为肯定存在 最后一步，将链表断开，采用了头结点的方式，画个图断个链就行了 important！！！ 为什么采用构建链表的方法？？？因为不确定random到底指向哪里，所以要事先构建新链表的全貌！！！

```python
 class Solution(object):
     def copyRandomList(self, head):
         if not head: return
         # 连接法
         cur = head
         while cur:
             new_node = Node(cur.val)
             new_node.next = cur.next
             cur.next = new_node
             cur = new_node.next
         # 复制random节点
         cur = head
         while cur:
             if cur.random:
                 cur.next.random = cur.random.next
             cur = cur.next.next
         # 利用头结点断开链接
         p = dummy = Node(-1)
         cur = head
         while cur:
             p.next = cur.next
             cur.next = p.next.next
             p = p.next
             cur = cur.next
         return dummy.next
```

解法二（哈希法）：

维护一个字典，来储存新链表，key为旧链表节点，value为新链表节点 第一步，构建链表，存入dic 第二步，遍历原列表，复制next节点和random节点 由于要返回整个链表，毫无疑问是采用头结点的方式返回

```python
 class Solution(object):
     def copyRandomList(self, head):
         if not head: return 
         dic = {}
         cur = head
         while cur:
             new_node = Node(cur.val)
             dic[cur] = new_node
             cur = cur.next
         cur = head
         while cur:
             if cur.next:
                 dic[cur].next = dic[cur.next]
             if cur.random:
                 dic[cur].random = dic[cur.random]
             cur = cur.next
         return dic[head]
```



【python】链表基础

#### 377. 组合总和 Ⅳ

https://leetcode.cn/problems/combination-sum-iv/

```
1.递归思路
- 确定出口，rest < 0 or rest == 0，分别返回0，1
- 确定递归体，每次递归进行循环（数字可以重复），p计数 p+=p(rest-i)

可以发现，时间复杂度是target ^ len(nums)，即kⁿ，指数，太高了

2.稍微剪枝一下
- 把rest < i的条件放在循环中，rest<0的话就不用进入下一层

时间复杂度依旧是指数级，底数为target，但是快了很多，可以从程序运行时间观测得出

3.dp思路
- 边界条件
- 构建dp[0 for _ in range(n+1)]，初始dp[0]=1
- 根据递归递推式，构建dp状态转移方程
important！！dp先写递推式，再构建状态转移方程，不然直接写dp谁会啊
效率优化很明显
```

```python
from typing import List
import time
from functools import wraps

def time_cal(func):
    @wraps(func)
    def inner(*args, **kwargs):
        t1 = time.time()
        res = func(*args, **kwargs)
        t2 = time.time()
        print(f"程序耗费时间: {t2-t1} 秒")
        return res
    return inner

class Solution:
    @time_cal
    def a(self, nums: List[int], target: int) -> int:
        def process(nums, rest):
            if rest < 0:
                return 0
            if rest == 0:
                return 1
            p = 0
            for i in nums:
                p += process(nums, rest-i)
            return p 
        ans = process(nums, target)
        return ans

    @time_cal
    def b(self, nums: List[int], target: int) -> int:
        def process(nums, rest):
            if rest == 0:
                return 1
            p = 0
            for i in nums:
                if rest < i:
                    continue
                p += process(nums, rest-i)
            return p 
        ans = process(nums, target)
        return ans

    @time_cal
    def c(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1,target+1):  # 从1开始构建dp
            for num in nums:  # 如果 target > 当前值，dp[i] += dp[i-num]
                if i >= num:
                    dp[i] += dp[i-num]
        return dp[target]

s = Solution()
print(s.a(nums=[4,2,1], target=32))
print(s.b(nums=[4,2,1], target=32))
print(s.c(nums=[4,2,1], target=32))
```

![](https://content.hackertalk.net/pub/rwv2rp-a9YaPM9)


#### 494. 目标和

https://leetcode.cn/problems/target-sum/

```
递归思路：
- 确定递归出口，遍历完所有的数，且此时和为target，返回1，否则返回0，回溯
- 每个数可以加，也可以减，返回两种情况之和

相当easy，但是我憋不出dp方程了，麻了，我去看看大佬怎么写，未完待续
```

```python
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        def dfs(rest, index):
            if index == len(nums):
                return 1 if rest == 0 else 0
            res = 0
            res += dfs(rest + nums[index], index + 1)  # 相加
            res += dfs(rest - nums[index], index + 1)  # 相减
            return res
        res = dfs(target, 0)
        return res 
```

【Python】dp之组合问题

关于去除数字、字母的题型

首先要知道，对于数字，字母，什么情况字典序最大

* `s[i] < s[i-1]`时，`s[i-1]`应该移除，`213`中`2`应该移除，即从左到右，移除逆序第一个数
* 如何实现以上的移除逆序操作，稍加观察即可发现，该题型是典型的后进先出，即可以用栈来实现，对于这种只保留顺序数字（字符）的栈，我们叫做单调栈


#### 402. 移掉 K 位数字

https://leetcode.cn/problems/remove-k-digits/

```python
思路：
- 当前一个数大于后面一个数时，移除前面这个数
    - 为什么用while，可能出现前面的数都是顺序，最后一个比前面数都小的情况
    - k保证移除k个，stack保证不越界
- 用栈来存放数字
- 保留`len(num) - k`个数，如果k不为0时退出while循环，则表示stack中的数都是顺序，只需要保留remain个数
- 由于lstrip("0")，可能返回`""`的情况，最后做一个短路
```

最终优化版本：

```python
class Solution(object):
    def removeKdigits(self, num, k):
        stack = []
        remain = len(num) - k
        for digit in num:
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        return ''.join(stack[:remain]).lstrip('0') or '0'
```

```
时间复杂度和空间复杂度分析
- 时间复杂度：O(n)，循环为n，最好为n，最坏为n+k
- 空间复杂度：O(n)，维护了一个单调栈
```

![](https://content.hackertalk.net/pub/WDrwyl-0wzx79N)

#### 316. 去除重复字母

#### 1081. 不同字符的最小子序列（两题一模一样）

https://leetcode.cn/problems/remove-duplicate-letters/

https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters/

```python
思路：
- 维护一个dic计数
- stack单调栈
- 遍历s，遍历完该数，计数器--，即计数器表现的是后续还有n个该数
- 遍历核心体：
    - 如果不在栈中则加入栈（确保栈中字符不重复）
    - 栈不为空 & 栈逆序 & 逆序第一个字符计数器 >= 1，逆序第一个字符出栈，当前字符再入栈
```

```python
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        dic = collections.Counter(s)
        stack = []
        for i in s:
            if i not in stack:
                while stack and stack[-1] > i and dic[stack[-1]] > 0:
                    stack.pop()
                stack.append(i)
            dic[i] -= 1
        return ''.join(stack)
```

```
时间复杂度和空间复杂度分析
- 时间复杂度：
    - O(n²)，循环为n，判断字符是否在stack中也是n，即为n²
- 空间复杂度：O(n)，维护了一个单调栈和一个字典
```

降低时间复杂度解法：

```
利用集合查询时间复杂度为O(1)的特性，将时间复杂度降为O(n)，（Counter也是循环s进行计数）
空间复杂度依然是O(n)，毕竟2n和3n没什么区别是吧，😁
```

```python
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        dic = collections.Counter(s)
        container = set()
        stack = []
        for i in s:
            if i not in container:
                while stack and stack[-1] > i and dic[stack[-1]] > 0:
                    container.discard(stack.pop())
                stack.append(i)
                container.add(i)
            dic[i] -= 1
        return ''.join(stack)
```

![](https://content.hackertalk.net/pub/4ZPWlo-zNk4rJl)


#### 321. 拼接最大数

https://leetcode.cn/problems/create-maximum-number/

```
思路：
- 定义函数获取数组中（保留相对位置）最大数
    - 单调栈，获取逆序最大数
    - 保留k个（注意）
- 定义函数拼接2个数组，获取最大数
- 每个数组可以保留的长度为 0 <= n <= len(nums)，循环，获取2个数组所有的组合，再进行拼接

这里有一些骚操作，比较list的大小，获取max(list([1,2], [2,1]))
```

```python
class Solution:
    def maxNumber(self, nums1, nums2, k):
        def get_max(num, k):
            stack = []
            drop = len(num) - k
            for i in num:
                while drop and stack and stack[-1] < i:
                    stack.pop()
                    drop -= 1
                stack.append(i)
            return stack[:k]
        
        def merge(A, B):
            res = []
            while A or B:
                bigger = A if A > B else B
                res.append(bigger.pop(0))
            return res

        ans = []
        for i in range(k+1):
            if i <= len(nums1) and k-i <= len(nums2):
                ans.append(merge(get_max(nums1, i), get_max(nums2, k-i)))
        return max(ans)
```

![](https://content.hackertalk.net/pub/WDrGgy-0D2yvYq)

【Python】单调栈之拼接最大数字、字符串

求组合问题，回溯+剪枝，非常优秀


#### 40. 组合总和 II

https://leetcode.cn/problems/combination-sum-ii/


思路：

* 求不重复的的全排列，首先确定用回溯+剪枝
* 递归结束条件：
  * 当rest剩余值 < 0时，return
  * 当rest == 0时，把该排列加入ans中
* 递归体：
  * 如果求全排列（不要求重复），先不考虑剪枝情况，每个数只取一遍，从startIndex开始，直接path.append(当前值)
  * 递归函数，rest = rest - candidates[i]， startIndex = i+1
  * 回溯，将之前的路pop掉
* 考虑剪枝（要求不重复）
  * candidates.sort()，非常重要，便于剪枝
  * 此时，为了得到不重复的排列，每层append一个值，必须保证每层append的值不一样，需要进行判断，跳过该枝丫

```python
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        n = len(candidates)
        ans = []
        # path中的元素可以相同，但是path整体不应该相同
        # 剪枝策略：同一个节点产生的分支，边上减去的数相同的分支，只保留第一个，即每一层，保证path.append()的值都不相同
        def backtracking(candidates, rest, path, startIndex):
            if rest < 0:
                return
            if rest == 0:
                ans.append(path[:])
                return
            for i in range(startIndex, n):
                if i > startIndex and candidates[i] == candidates[i-1]: continue
                path.append(candidates[i])
                backtracking(candidates, rest - candidates[i], path, i+1)
                path.pop()

        backtracking(candidates, target, [], 0)
        return ans
```


#### 216. 组合总和 III

https://leetcode.cn/problems/combination-sum-iii/

思路：同上

PS：为什么组合②比组合③简单？！

```python
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        def backtracking(path, rest, startNum):
            if rest < 0 or len(path) > k:
                return 
            if rest == 0 and len(path) == k:
                ans.append(path[:])
                return
            for cur_num in range(startNum, 10):
                path.append(cur_num)
                backtracking(path, rest-cur_num, cur_num+1)
                path.pop()
        backtracking([], n, 1)
        return ans
```


PS：这两天在面试华为od，忘记更新了，看看情况出个华为od面经，想要了解od的可以私信我

【Python】回溯之组合问题

解数独需要两个前置知识：

* 回溯算法原理
* 校验数独是否合法

回溯算法基础理论：

```abap
# 回溯算法
# - 都可以抽象为树形结构，最重要的就是剪枝
# - 一般来说回溯算法是没有返回值的。
# - 函数名叫：backtracking or backtrack

def backtracking():
  if 终止条件:
      收集结果
      return 
  for 集合元素：
      处理节点
      递归函数
      回溯操作
  return xxx
```


校验数独是否合法：

#### 36. 有效的数独

https://leetcode.cn/problems/valid-sudoku/

解法1（暴力解法）

思路：

* 直接对行和列循环，进行遍历，如果当前位置不为空
  * 判断行内是否重复
  * 判断列内是否重复
  * 判断9方格里是否重复（(row // 3) * 3 计算从行开始）
* 全部结束后返回true

**暴力循环行和列和九方格进行判断，时间较慢，空间占用少**

```python
from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for x in range(9):
            for y in range(9):
                if board[x][y] != '.':
                    for i in range(9):  # 判断行里是否重复
                        if i == y: continue
                        if board[x][i] == board[x][y]:
                            return False
                    for j in range(9):  # 判断列里是否重复
                        if j == x: continue
                        if board[j][y] == board[x][y]:
                            return False
                    startRow = (x // 3) * 3
                    startcol = (y // 3) * 3
                    for i in range(startRow,startRow + 3):  # 判断9方格里是否重复
                        for j in range(startcol,startcol + 3):
                            if i == x and j == y: continue
                            if board[i][j] == board[x][y]:
                                return False
        return True
```

解法2（哈希法）

思路：

* 构建三个列表，里面都包含了9个字典，每个字典用于存储该行（列、九宫格）的数字
* 直接对行和列循环，进行遍历，如果当前位置不为空
  * 判断行内是否重复
  * 判断列内是否重复
  * 判断9方格里是否重复（(row // 3) * 3 计算从行开始）
* return True

**采用构建字典的方式，避免了暴力循环，时间更快了，空间占用也不多**

```python
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [{} for _ in range(9)]
        col = [{} for _ in range(9)]
        nine = [{} for _ in range(9)]
        for i in range(9):
            for j in range(9):
                tmp = board[i][j]
                if tmp == ".":
                    continue
                if tmp in row[i]:
                    return False
                if tmp in col[j]:
                    return False
                if tmp in nine[(j // 3) * 3 + (i // 3)]:
                    return False
                row[i][tmp] = None
                col[j][tmp] = None
                nine[(j // 3) * 3 + (i // 3)][tmp] = None
        return True
```

![](https://content.hackertalk.net/pub/28k9P3-eanZnwy)


好了，现在开始解决解数组的问题

#### 37. 解数独

https://leetcode.cn/problems/sudoku-solver/


思路：

* 首先确定采用递归算法
* 确定回溯函数：
  * 递归返回值：False -> 需要进行回溯， True -> 不需要回溯，
  * 遍历每个数，将1~9逐个放入空位置，放入以后，校验当前数独表是否合法，如不合法，则进行回溯，撤销当前放入的数。
    * 每放置一个数，都需要进行递归，因为，根据递归结果来确定是否需要回溯
    * ！！！important -> 当九个数都放完了，但是都不合法，则回溯。
  * 所有的回溯函数都没有出错，说明九宫格填完了

**为什么不能传入row和col的参数，填完的行和列不再进入递归？

因为行、列数不是递增关系，遍历完一行（列）后又变为1**

```python
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def backtracking(board):
            for i in range(9):  #遍历行
                for j in range(9):  #遍历列
                    if board[i][j] != ".":  continue
                    for k in range(1,10):  #(i, j) 这个位置放k是否合法
                        if isValid(i, j, k, board):
                            board[i][j] = str(k)  #放置k
                            if backtracking(board): return True  #如果找到合适一组立刻返回
                            board[i][j] = "."  #回溯，撤销k
                    return False  #9个数都试完了，都不行，那么就返回false
            return True  #遍历完没有返回false，说明找到了合适棋盘位置了
        
        def isValid(row, col, val, board):
            for i in range(9):  #判断行里是否重复
                if board[row][i] == str(val):
                    return False
            for j in range(9):  #判断列里是否重复
                if board[j][col] == str(val):
                    return False
            startRow = (row // 3) * 3
            startcol = (col // 3) * 3
            for i in range(startRow,startRow + 3):  #判断9方格里是否重复
                for j in range(startcol,startcol + 3):
                    if board[i][j] == str(val):
                        return False
            return True
        
        backtracking(board)
```



【Python】回溯之解数独

#### 41. 缺失的第一个正数

https://leetcode.cn/problems/first-missing-positive/


暴力解法，直接哈希

思路：

- 边界情况，最大值小于1 or 最小值大于1，直接返回1

- 维护1个字典，存放所有的正整数，记录最小值和最大值

- if 最小值大于1，return 1

- 最大值 - 最小值 + 1 = len(dic)，return 最大值 + 1

- else 则中间有缺少的正整数，遍历最小值到最大值，返回不在dic中的正整数

```python
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        min_, max_ = min(nums), max(nums)
        if min_ > 1 or max_ < 1:
            return 1
        dic = {}
        min_num, max_num = 1e20, 0
        for i in range(len(nums)):
            if nums[i] > 0 and nums[i] not in dic:
                dic[nums[i]] = None
                if nums[i] < min_num:
                    min_num = nums[i]
                if nums[i] > max_num:
                    max_num = nums[i]
        if min_num > 1:
            return 1
        if max_num - min_num + 1 == len(dic):
            return max_num + 1
        else:
            for i in range(min_num, max_num):
                if i not in dic:
                    return i
```


时间复杂度为O(n)，2次n的遍历，空间复杂度为O(n)，维护了一张哈希表

![](https://content.hackertalk.net/pub/KdrOMD-NY0zJnr)

【Python】哈希之查找缺失正数

反转链表（https://leetcode.cn/problems/reverse-linked-list/）

画个图

!!!注意：python自有的交换，千万不能写错顺序！！！！

可以分开写，但分开写需需要tmp进行暂存

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

反转相邻列表（https://leetcode.cn/problems/swap-nodes-in-pairs/submissions/）

暴力破解法：

直接进行交换（也可以理解为反转），下面的k个一组反转需要引入一个计数器

```python
 class Solution:
     def swapPairs(self, head: ListNode) -> ListNode:
         if not head:
             return 
         if not head.next:
             return head
         # 先进行第一次交换
         tmp = head.next
         head.next = tmp.next
         tmp.next = head
         ans = tmp
         # 交换后tmp即为头结点，后续继续交换就行，最后还是输出tmp
         while head.next:
             p = head.next 
             q = head.next.next
             if not q:
                 return ans
             head.next = p.next
             p.next = q.next
             head = q.next = p
 ​
         return ans
```

K个一组反转链表（https://leetcode.cn/problems/reverse-nodes-in-k-group/）

思路：

* 前k个反转，k+1 ~ 2k个反转...确定用递归
* 反转k个需要计数，画个图，head -> head.next -> ... -> cur -> head ->head.next，环形
* 当链表数量<k时，直接返回head
* 当链表数量>=k时，进行递归
* 递归体：
  * 进行反转，需要进行k次偏移，用count计数，具体偏移过程参考反转链表
  * 最后将反转链表后的头结点返回

最重要的就是画图，画图，画图

```python
 class Solution:
     def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
         cur = head
         count = 0
         while cur and count < k:
             cur = cur.next
             count += 1            
         if count == k:
             cur = self.reverseKGroup(cur, k)
             while count:
                 head.next, head, cur = cur, head.next, head
                 count -= 1
             head = cur   
         return head
```

【Python】递归之反转链表

##### 23. 合并K个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists/

思路：

* 考虑边界条件，lists为`[]、[[]]、[[], []]`的情况
* 遍历，获取所有的数放入列表
* 排序，初始化头指针和辅助指针，再遍历形成链表
* 返回头指针

```python
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
            
        li = []
        for link_list in lists:  # 把所有的数放入列表
            while link_list:
                li.append(link_list.val)
                link_list = link_list.next
        if not li:
            return None

        li.sort()
        cur = head = ListNode(val=li[0])
        li = li[1:]
        while li:
            new_node = ListNode(li[0])
            cur.next = new_node
            cur = new_node
            li = li[1:]
        return head
```

只打败了26%的人？？？哪里出了问题

不对啊，需要排序，为什么我要排序后再遍历？我就不可以遍历的同时排序吗。

PS： max、min这种的函数无法做到删除操作，所以，采用堆进行排序

最小堆优化版本：

```python
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        import heapq
        if not lists:
            return None
            
        li = []
        for link_list in lists:  # 把所有的数放入列表
            while link_list:
                li.append(link_list.val)
                link_list = link_list.next
        if not li:
            return None

        heapq.heapify(li)  # 建堆
        cur = head = ListNode(val=heapq.heappop(li))
        while li:
            new_node = ListNode(val=heapq.heappop(li))
            cur.next = new_node
            cur = new_node
        return head
```

![](https://content.hackertalk.net/pub/a81EVG-0p7qgeO)


堆的知识补充：

堆是完全二叉树，完全二叉树的定义自行百度

堆有特性：向下（上）调整，即所有的根父节点 > 孩子节点。因此根节点为最大的数

堆排序的特性：堆排序是交换排序，不打乱原有位置，比较稳定。时间复杂度O(nlogn)

```python
# 对于堆的向下调整（向上调整）
def sift(li, low, high):
    """
    low: 当前根节点
    high: 堆最后一个节点
    """
    tmp = li[low]  # 存根节点
    i = low
    j = 2 * i + 1  # 先指向左节点
    while j <= high:
        if j + 1 <= high and li[j+1] > li[j]:  # 右节点存在且大于左节点，j指向右节点
            j += 1
        if li[j] > tmp:  # 孩子大于父节点，孩子上位
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            # 孩子不能上位，tmp补上
            break
    li[i] = tmp  # 到叶子节点的时候，tmp进空位

# 对于堆的建立
from random import randint
li = [randint(1, 100) for _ in range(10)]
print(f"初始列表:{li}")
for i in range((len(li)-2)// 2, -1, -1):
    sift(li, i, len(li)-1)
print(f"建立的堆：{li}")
# 堆建立只保证 根父节点 > 孩子节点，根节点为最大的
# 对于堆排序，把最大的换到后面去，其余的数进行堆的向下调整
for j in range(len(li)-1, -1, -1):
    li[0], li[j] = li[j], li[0]
    sift(li, 0, j-1)
print(f"排序后的堆:{li}")
```


Python内置函数

```python
import heapq
ls = [6,4,5,4,3,2,1,1]
heapq.heapify(ls)  # 建堆
print(ls)
# for i in range(len(ls)-1, -1, -1):
    # ls[i], ls[0] = ls[0], ls[i]
    
# heapq.heappop(ls)  # 获得堆最小值
# heapq.heappush(ls, 8)  # 加入堆

# heapq.heappushpop(ls, 8)  # 获得堆最小值，同时将一个数加入堆，有返回值
# heappushpop先push后pop，空堆不报错

# heapq.heapreplace(ls, 9)  # 获得堆最小值，同时将一个数加入堆，有返回值
# heapreplace先pop后push，表现为空堆报错
print(ls)
```

【Python】堆之合并链表

####  电话号码的字母组合（leetcode 17）

思路：

* 构建哈希表进行数字和字母的映射
* 构建递归函数，需要回溯pop(path)
* 递归退出条件：当index越界，即遍历完digits列表时，退出递归，将当前path加入res
* 递归body：递归获取字符串，对字符串进行遍历，递归N层获取n个字符，当res.append(path)以后，再进行pop(path)

```python
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        dic = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        } 
        
        def backtrack(index: int):
            if index == len(digits):
                res.append("".join(path))
            else:
                digit = digits[index]
                for letter in dic[digit]:
                    path.append(letter)
                    backtrack(index + 1)
                    path.pop()

        path = []
        res = []
        backtrack(0)
        return res
```



【Python】回溯之排列组合

**括号生成问题（leetcode 22）**

思路：

* 确定使用递归
* 确定递归剪枝条件：
  * 当左括号left大于n时，非法，剪枝
  * 当右括号right比左括号left多时，非法，剪枝
* 对于获得排列组合题，构建集合，递归函数带上路径path
* 路径就加个左括号，left就++，加个右括号right就++

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = set()
        self.dfs(n, 0, 0, "", res)
        return list(res)

    def dfs(self, n, left, right, path, res):
        if left > n or right > left:
            return 
        if len(path) == n * 2:
            res.add(path)
            return
        self.dfs(n, left+1, right, path+"(", res)
        self.dfs(n, left, right+1, path+")", res)
```



#### 最长有效括号（leetcode 32）

妈呀，这是我在面试华为的时候，出的一道题。

当时用栈做出来了，现在试试DP，逆天的DP，脑子不够用了

**DP思路**：

*  先对s进行基本的修正，左边为`)`的不可能匹配成功，右边为`(`不能匹配成功，直接strip掉
* 边界条件返回0
* 构建dp，dp[0]肯定为0，从1开始遍历
* 判断s[i]为`(`的情况，匹配失败dp[i] = 0
* 判断s[i]为`)`的情况:
  * 如果 i >= 1 并且 s[i-1] == "("，匹配成功，如果 i == 1, dp[i-2] -> dp[-1] == 0
  * `i == 0 or s[i-1] == ")"`的情况，i==0时，dp[0]=0，不管； 剩下`s[i-1] == ")"`的情况，注意 `i - dp[i-1] > 0`即确定与s[i]对应的"("存在，且为"("，即可得出 `dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]`


举个栗子🌰："()(())"，i指向5时，`dp[i-dp[i-1]-2] -> dp[5-2-2] == dp[1] == 2`，"(())"，i指向3时，`dp[i-dp[i-1]-2] -> dp[-1] == 0`

PS: `dp[i-dp[i-1]-2]`在这种情况下，可能存在也可能不存在，不存在则为 dp[-1] = 0，没有赋值就是0，存在就直接加


```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        s = s.lstrip(")").rstrip("(")
        if len(s) == 0:
            return 0
        dp = [0 for _ in range(len(s))]
        for i in range(1, len(s)):
            # if s[i] == '(': dp[i] = 0    # 以(结尾非法，dp初始化就为0，可以省略
            if s[i] == ')':  # 如果为右括号，左边匹配成功且i>=2，dp依赖
                if i >= 1 and s[i-1] == '(':
                    dp[i] = dp[i-2] + 2
                else:  # 如果匹配不成功，i - dp[i-1]为s[i]的左括号位置（如果有的话）
                    if i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
                        dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
        return max(dp)
```


再次强调：第二题DP仅用于锻炼DP能力，本题最优解还是用栈比较好

【Python】括号匹配问题

leetcode第一题 两数之和（medium）

![](https://content.hackertalk.net/pub/k0B1Gz-6gPKngQ)

想刷力扣而被第一题劝退的同学们看好了，下面就是N数之和的终极攻略，开启你的刷题之路吧。

-----------------------------华丽的分割线----------------------------

思路（直接确定递归，需要把N数之和降维成两数之和，n-2个数暴力遍历）：

* 维护一个集合（题目要求返回不重复的元组）作为ans
* 对数组排序，便于递归剪枝
* 定义递归函数
  * 确定递归函数的参数和返回值
    * 参数：nums数组，startIndex索引，rest还有几个数，target目标和，path之前的路径，ans答案集合
    * 返回值：None
  * 递归终止条件：如果rest剩余需要的数 < 2，退出递归
  * 2数之和，在startIndex之后的数组中，找到了就加入ans，没找到就啥也不干
  * N数之和，暴力遍历也需要剪枝
    * 剪枝1：此时target < 剩余数最小值 * 个数 or target > 剩余数最大值 * 个数（这就是排序的目的），就直接break，即不存在
    * 剪枝2：举个栗子：[1,1,1,2,3,4,5]重复的，计算一次1后就可以直接pass，直接从2开始

```python
class Solution:
    def NSum(self, nums: List[int], target: int, N: int) -> List[List[int]]:
        N, target = N, target  # 获取n数和target，获取 N 数
        if not nums or len(nums) < N or N < 2: 
            return []
        nums.sort()     
        ans = set()
        self.find_sum(nums, 0, N, target, [], ans)
        return list(ans)

    def find_sum(self, nums, startIndex, rest, target, path, ans):
        if rest < 2: return  # 如果 rest == 1，不存在
        if rest == 2:  # 两数求和
            d = set()  # 维护一个集合
            for i in range(startIndex, len(nums)):
                if target - nums[i] in d:  # 当两数之和为target时，加到ans中
                    ans.add(tuple(path + [target - nums[i], nums[i]]))
                else:
                    d.add(nums[i])
        else:
            for i in range(startIndex, len(nums)):
                # 剪枝1: target比剩余数字能组成的最小值还要小 或 比能组成的最大值还要大，就可以停止循环了
                if target < nums[i] * rest or target > nums[-1] * rest: 
                    break
                # 剪枝2: 去重
                if i > startIndex and nums[i] == nums[i - 1]: 
                    continue
                # 递归
                self.find_sum(nums, i + 1, rest - 1, target - nums[i], path + [nums[i]], ans)
        return
```

有了以上的思路，你就可以解决2、3、4数之和了，是不是很快乐，一次解决三道题

【Python】递归之N数之和

思路：

* 确定递归出口：target判断完毕，返回0
* 利用了Counter函数
  * Counter(a) & Counter(b)判断交集
  * Counter(a) - Counter(b)获得差集
* 对stickers构建couter字典，遍历stickers，逐个匹配target，返回最小匹配次数

```python
class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        @cache
        def dfs(rest):
            if not rest:
                return 0
            ans = 1e20
            rest_dic = Counter(rest)
            for i in range(N):
                # 判断模式串和目标串是否有交集
                if dic[i] & rest_dic:
                    # 获得删除字符后的字符串
                    rest = "".join(k * v for k, v in (rest_dic - dic[i]).items())
                    # 如果之后没有匹配成功，rest没有置0，则ans=1e20
                    ans = min(ans, dfs(rest)+1)
            return ans

        N = len(stickers)
        dic = [Counter(s) for s in stickers]        
        res = dfs(target) 
        return res if res != 1e20 else -1
```

#### 691. 贴纸拼词

https://leetcode.cn/problems/stickers-to-spell-word/submissions/

【Python】递归之拼接字符串

```
规定A对应1，B对应2... Z对应26
举个栗子： 111就可以转化为 'AAA', 'KA', 'AK'
给定一个只有数字字符组成的str，返回一共有多少种转化结果
```

暴力递归思路：

* 可以把这个字符串想成0 ~ N-1位，当在第index位的时候，只考虑N-index的方法，相加即为index位的方法。f(n) = f(n-1) + f(n-2)


* 确定递归出口，
  * 当index到达末尾，即无其他方法，计为 **1**
  * 当index位置上为“0”时，即方案错误，无法转化，计为0

    （index可以看做头，以"0"为首部的数字没办法转化）
* 确定递推式
  * 单转：直接index+1
  * 双转：确定index+1不越界，且，这两位数小于27
  * 单转 + 双转，即为所有的可能


DP思路：

* 构建dp，由于字符串转化数是根据index位置决定的，线性的，只需要构建一维数组，为什么是N+1，因为当index走到最后（越界）时，只有一种转化方法，dp[N] = 1
* 判断依赖关系：index依赖于index+1的方法，所以从后往前填充dp
* 填充dp
  * 判断情况，头为"0"时，决策错误，无转化方法
  * 单转：直接加
  * 双转：判断是否符合情况再加（我这样写比较帅，但是多进行了一次赋值操作）
* 返回值：index从0开始

```python
def translate_str(string):
    if not string or len(string) == 0:  # 边界条件
        return 0
    
    def process(string, index):
        # 只考虑index之后的转化，0~index不需要考虑
        if len(string) == index:
            return 1
        if string[index] == "0":  # 之前做的决定有问题
            return 0
        
        # 存在两种情况：单转和双转
        # 单转
        ways = process(string, index+1)
        # 双转，index+1不越界，且，string[index, index+2]小于27
        if index+1 < len(string) and int(string[index:index+2]) < 27:
            ways += process(string, index + 2)
        return ways
    return process(string, 0)


def dp_translate_str(string):
    if not string or len(string) == 0:  # 边界条件
        return 0
    N = len(string)
    dp = [0 for _ in range(N+1)]
    dp[N] = 1
    for i in range(N-1, -1, -1):
        if string[i] == "0":  # 当为0时，决策错误
            continue
        dp[i] = dp[i+1]
        dp[i] += dp[i+2] if i + 1 < N and int(string[i:i+2]) < 27 else 0
        
    return dp[0]






print(translate_str("11111"))  # 8
print(translate_str("12313"))  # 6
print(translate_str("13035643242311"))  # 0，里面有个30，没办法转

print(dp_translate_str("11111"))
print(dp_translate_str("12313"))
print(dp_translate_str("13035643242311"))
```


题目同：可以自己练习一下

#### 剑指 Offer 46. 把数字翻译成字符串

https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

【Python】动态规划之数字转化字符串

递归思路：

* 确定递归结束条件
  * bag < 0时，非法，标记为无效解
  * index 越界，结束递归
* 递归分支
  * 不要当前货物，index往下走
  * 要当前货物，标记为无效解的需要进行置0，有效解则 v[index] + index往下走


DP思路：

* 根据暴力递归写DP


* 构建dp二位数组new int [N+1][bag+1]，为什么要+1，因为递归中有越界判断
* 确定依赖关系
  * index依赖于下一层的index （important）
  * 最后一层的dp[index]全部为0，因为递归中 len(w) == index return 0
* 构建dp
  * 从倒数第二层index开始，rest从0~bag 或 bag~0都可以，没有依赖关系
* 最后return dp[0][bag]，就是从0开始遍历货物，bag为空的情况

```python

def max_value(w, v, bag):
    """
    params w: 货物的重量
    params v: 货物的价值
    params bag: 背包容量
    return : 不超重的情况下，返回背包的最大价值
    """
    if not w or not v or len(w) == 0 or len(v) == 0:  # 边界条件
        return 0

    # 当前考虑到了index货物，index后的所有货物可以自由选择
    # 做的选择不能超过背包容量
    # 返回最大价值
    def process(startIndex, w, v, bag):
        # if bag <= 0:  # 如果背包 < 0，则是无效解
        #     return 0
        if startIndex == len(w):  # 如果开始索引越界，就没了
            return 0
            
        p1 = process(startIndex+1, w, v, bag)  # 不要当前的货
        # 要当前的货
        if bag - w[startIndex] < 0:  # 如果bag容量小于0，为无效解，value为0
            p2 = 0
        else:
            p2 = v[startIndex] + process(startIndex+1, w, v, bag-w[startIndex])  
        return max(p1, p2)

    return process(0, w, v, bag)
    
def dp_value(w, v, bag):
    if not w or not v or len(w) == 0 or len(v) == 0:  # 边界条件
        return 0
    N = len(w)
    dp = [[0 for j in range(bag+1)] for i in range(N+1)]  # 构建动态规划表
    # 确定依赖，startIndex依赖于下一层的startIndex，
    for startIndex in range(N-1, -1, -1):
        for rest in range(bag, -1, -1):
            # 没拿的情况
            p1 = dp[startIndex+1][rest]
            # 如果拿了超重，无效解计0，有效解正常计算
            p2 = 0 if rest - w[startIndex] < 0 else v[startIndex] + dp[startIndex+1][rest-w[startIndex]] 
            dp[startIndex][rest] = max(p1, p2)
    return dp[0][bag]

         
        
w = [3,2,4,7,3,1,7]
v = [5,6,3,19,12,4,2]
bag = 15
print(max_value(w, v, bag))
print(dp_value(w, v, bag))

```

【Python】动态规划之背包问题

面试官基本按照简历面，但是简历写的太差了，没有突出重点，自己的知识也没有完全cover简历，基础较差，面试效果不理想。

1、自我介绍

2、简历写了学过数据结构和算法

question1：笔试中递归题的时间复杂度你是怎么做的？

answer1：递归的时间复杂度一般都是2的n次方（胡说八道ing）

面试官纠正：在递归函数中，需要进行拆解，并不都是2的n次方，比如这道题就是O(n)

question2：你了解哪些数据结构？数组和链表有什么区别？

answer2：数组、链表、栈和队列、二叉树、字符串。数组在内存中是开辟一片连续的内存地址储存，而链表的内存地址不一定连续，链表依靠指针来指向下一个数据的内存地址，浪费了一定的内存。

question3：说一下链表和数组的各种操作的时间复杂度分析，和原理，以及使用场景。

answer3：数组，增删都是O(n)查改都是O(1)；链表，查删改都是O(n)，插入是O(1)。原理：数组是分配的连续的内存地址，链表有额外的空间存储下一个数据的指针。使用场景：链表用于需要遍历的场景，数组用于查询频繁的场景。（说完，面试官笑笑不说话）

PS：请忽略我的胡说八道。

补充：- 数组：

              无序数组：查询修改O(1)，插入O(1)（直接到最后），删除末尾元素O(1)，删除任意一个元素O(n)。

              有序数组：查询修改O(1)，插入（基于二分查找）O(n+logn)，删除末尾元素O(1)，删除任意一个元素O(n)。

            -  链表：

              有序链表：查询O(n)、插入O(n)、删除O(n)    失去了链表插入快速的特性

              无序链表：查询O(n)、插入O(1)（头插、尾插）、删除O(n)

原理：数组是分配的连续的内存地址，链表有额外的空间存储下一个数据的指针。

举个栗子：得到数组本身id，再加上数组的索引，由于数组每个元素的空间是固定的，所以元素的内存地址为：id+索引*每个元素的固定大小。即可实现O(1)的查询。

使用场景：

* 数组：数据较少、查询密集型业务
* 链表：插入删除密集型，对动态性要求高

3、简历写了熟悉redis、mysql数据库，了解linux基础，学过计算机网络

question4：你说你了解linux基础，你有没有linux开发经验，如何解决linux系统下多线程争夺内存问题。

answer4：有项目部署在linux上的经验。（试探性）查看内存占用情况，再分析问题解决问题？（面试官笑笑不说话）

question5：你说你了解mysql数据库，知道mysql怎么优化吗？

answer5：mysql靠索引优化（再次试探）？索引分为主键、外键、联合索引、唯一索引...

question6：你说你学过计算机网络，你学了哪些？

answer6：窝学过http、https、tcp、udp协议。

question6-2：那你能说一下tcp/ip协议的底层架构吗，在五层架构模型上。

answer6-2：卒....

补充：

![](https://content.hackertalk.net/pub/r1gmoM-x4exXrp)

![](https://content.hackertalk.net/pub/1NEAVr-7rEqMgl)

4、简历写了学过算法

question7：你了解哪些排序算法？讲一下原理，分析一下时间复杂度。

answer7：慢一点的冒泡排序，快一点的快速排序。冒泡排序就是巴拉巴拉，快排就是巴拉巴拉，时间复杂度冒泡O(n²)快排O(nlogn)。

question8：写个快排吧，面试结束了

answer8：..........


估计是凉了，哎

乐易网络面试

前些天一直在找便宜的云服务器，偶然间发现一免费的云平台，这里推荐给大家。

就是阿贝云，网站是https://www.abeiyun.com

说一下感受

1、阿贝云虽然是一小众的云平台，重在免费，该有的东西都有，还能免备案这是最舒服的。

2、使用了一天，上了项目，网速不慢。

3、唯一要指出来就是磁盘太小。

分享免费云服务器

拉取了rustbuster的v3.0.3版本文件, 二进制文件无法使用, 执行结果如下:

```bash
[root_cn@archlinux target]$ ./rustbuster-v3.0.3-x86_64-unknown-linux-gnu
./rustbuster-v3.0.3-x86_64-unknown-linux-gnu: error while loading shared libraries: libssl.so.1.1: cannot open shared object file: No such file or directory
```

拉取了main源码, 想自行尝试编译, 然后卡在了openssl, 以下为报错信息:

```rust
The following warnings were emitted during compilation:

warning: openssl-sys@0.9.47: build/expando.c:4:24: error: pasting "RUST_VERSION_OPENSSL_" and "(" does not give a valid preprocessing token
warning: openssl-sys@0.9.47:     4 | #define VERSION2(n, v) RUST_VERSION_##n##_##v
warning: openssl-sys@0.9.47:       |                        ^~~~~~~~~~~~~
warning: openssl-sys@0.9.47: build/expando.c:5:23: note: in expansion of macro ‘VERSION2’
warning: openssl-sys@0.9.47:     5 | #define VERSION(n, v) VERSION2(n, v)
warning: openssl-sys@0.9.47:       |                       ^~~~~~~~
warning: openssl-sys@0.9.47: build/expando.c:10:1: note: in expansion of macro ‘VERSION’
warning: openssl-sys@0.9.47:    10 | VERSION(OPENSSL, OPENSSL_VERSION_NUMBER)
warning: openssl-sys@0.9.47:       | ^~~~~~~

error: failed to run custom build command for `openssl-sys v0.9.47`

Caused by:
  process didn't exit successfully: `/mnt/d/work/file/rust/rustbuster/target/debug/build/openssl-sys-c5a482a9e0e49574/build-script-main` (exit status: 101)
  --- stdout
  cargo:rustc-cfg=const_fn
  cargo:rerun-if-env-changed=X86_64_UNKNOWN_LINUX_GNU_OPENSSL_LIB_DIR
  X86_64_UNKNOWN_LINUX_GNU_OPENSSL_LIB_DIR unset
  cargo:rerun-if-env-changed=OPENSSL_LIB_DIR
  OPENSSL_LIB_DIR unset
  cargo:rerun-if-env-changed=X86_64_UNKNOWN_LINUX_GNU_OPENSSL_INCLUDE_DIR
  X86_64_UNKNOWN_LINUX_GNU_OPENSSL_INCLUDE_DIR unset
  cargo:rerun-if-env-changed=OPENSSL_INCLUDE_DIR
  OPENSSL_INCLUDE_DIR unset
  cargo:rerun-if-env-changed=X86_64_UNKNOWN_LINUX_GNU_OPENSSL_DIR
  X86_64_UNKNOWN_LINUX_GNU_OPENSSL_DIR unset
  cargo:rerun-if-env-changed=OPENSSL_DIR
  OPENSSL_DIR unset
  cargo:rustc-link-lib=ssl
  cargo:rustc-link-lib=crypto
  OPT_LEVEL = Some("0")
  TARGET = Some("x86_64-unknown-linux-gnu")
  HOST = Some("x86_64-unknown-linux-gnu")
  CC_x86_64-unknown-linux-gnu = None
  CC_x86_64_unknown_linux_gnu = None
  HOST_CC = None
  CC = None
  CFLAGS_x86_64-unknown-linux-gnu = None
  CFLAGS_x86_64_unknown_linux_gnu = None
  HOST_CFLAGS = None
  CFLAGS = None
  CRATE_CC_NO_DEFAULTS = None
  DEBUG = Some("true")
  CARGO_CFG_TARGET_FEATURE = Some("fxsr,sse,sse2")
  running: "cc" "-O0" "-ffunction-sections" "-fdata-sections" "-fPIC" "-g" "-fno-omit-frame-pointer" "-m64" "-Wall" "-Wextra" "-E" "build/expando.c"
  cargo:warning=build/expando.c:4:24: error: pasting "RUST_VERSION_OPENSSL_" and "(" does not give a valid preprocessing token
  cargo:warning=    4 | #define VERSION2(n, v) RUST_VERSION_##n##_##v
  cargo:warning=      |                        ^~~~~~~~~~~~~
  cargo:warning=build/expando.c:5:23: note: in expansion of macro ‘VERSION2’
  cargo:warning=    5 | #define VERSION(n, v) VERSION2(n, v)
  cargo:warning=      |                       ^~~~~~~~
  cargo:warning=build/expando.c:10:1: note: in expansion of macro ‘VERSION’
  cargo:warning=   10 | VERSION(OPENSSL, OPENSSL_VERSION_NUMBER)
  cargo:warning=      | ^~~~~~~
  exit status: 1

  --- stderr
  thread 'main' panicked at /home/root_cn/.cargo/registry/src/mirrors.sjtug.sjtu.edu.cn-4f7dbcce21e258a2/openssl-sys-0.9.47/build/main.rs:126:13:

  Header expansion error:
  Error { kind: ToolExecError, message: "Command \"cc\" \"-O0\" \"-ffunction-sections\" \"-fdata-sections\" \"-fPIC\" \"-g\" \"-fno-omit-frame-pointer\" \"-m64\" \"-Wall\" \"-Wextra\" \"-E\" \"build/expando.c\" with args \"cc\" did not execute successfully (status code exit status: 1)." }

  Failed to find OpenSSL development headers.

  You can try fixing this setting the `OPENSSL_DIR` environment variable
  pointing to your OpenSSL installation or installing OpenSSL headers package
  specific to your distribution:

      # On Ubuntu
      sudo apt-get install libssl-dev
      # On Arch Linux
      sudo pacman -S openssl
      # On Fedora
      sudo dnf install openssl-devel

  See rust-openssl README for more information:

      https://github.com/sfackler/rust-openssl#linux

  note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
warning: build failed, waiting for other jobs to finish...
```

经过检查openssl与rust均为最新版本, 

```bash
[root_cn@archlinux target]$ sudo pacman -S rust
[sudo] password for root_cn:
warning: rust-1:1.77.2-1 is up to date -- reinstalling
resolving dependencies...
looking for conflicting packages...

Package (1)  Old Version  New Version  Net Change

extra/rust   1:1.77.2-1   1:1.77.2-1     0.00 MiB

Total Installed Size:  249.41 MiB
Net Upgrade Size:        0.00 MiB

:: Proceed with installation? [Y/n] n
[root_cn@archlinux target]$ sudo pacman -S openssl
warning: openssl-3.2.1-1 is up to date -- reinstalling
resolving dependencies...
looking for conflicting packages...

Package (1)   Old Version  New Version  Net Change

core/openssl  3.2.1-1      3.2.1-1        0.00 MiB

Total Installed Size:  11.45 MiB
Net Upgrade Size:       0.00 MiB

:: Proceed with installation? [Y/n] n
```

在网上找了一下, 查到资料, 在[rust-openssl的issues](https://github.com/sfackler/rust-openssl/issues/1227)中提到类似报错, 得到解释如下:

> If you are cross compiling to MUSL, you either need to point openssl-sys to the location that you have a copy of OpenSSL cross compiled to MUSL, or tell it to build a copy of OpenSSL itself with the vendored feature.
>
>	如果你是交叉编译到MUSL，你需要将openssl-sys指向你有一个交叉编译到MUSL的OpenSSL副本的位置，或者告诉它用vendored特性构建一个OpenSSL本身的副本。

由于不会rust, 依靠关键词"交叉编译"+"cargo"搜索到了[cargo交叉编译rust程序](https://blog.csdn.net/tyc880616/article/details/104371502), 顺着找到文件:

```
[root_cn@archlinux .cargo]$ cat ~/.cargo/config
[source.crates-io]
replace-with = 'sjtu' # 指定使用下面哪个源，修改为source.后面的内容即可

# 中国科学技术大学
[source.ustc]
registry = "https://mirrors.ustc.edu.cn/crates.io-index"

# 上海交通大学
[source.sjtu]
registry = "https://mirrors.sjtug.sjtu.edu.cn/git/crates.io-index/"

# 清华大学
[source.tuna]
registry = "https://mirrors.tuna.tsinghua.edu.cn/git/crates.io-index.git"

# rustcc社区
[source.rustcc]
registry = "https://code.aliyun.com/rustcc/crates.io-index.git"
```

没有找到交叉编译的设置, 由于本人不会rust, 线索断了, 尝试向大家寻求一波帮助, 非常感谢阅读.



急切寻求rust编译问题帮助(archlinux, openssl)

永久免费，无需注册

[https://good.xjai.top](https://good.xjai.top)

分享免费GPT4站点

[MoienTajik/AspNetCore-Developer-Roadmap (github.com)](https://github.com/MoienTajik/AspNetCore-Developer-Roadmap/blob/master/ReadMe.zh-Hant.md)

![](https://github.com/MoienTajik/AspNetCore-Developer-Roadmap/raw/master/aspnetcore-developer-roadmap.zh-Hant.png)



【轉貼】ASP.NET Core Developer Roadmap in 2024

南京大学数字金融 - 新华报业集团联合诚邀全职博士后！

【研究方向涵盖】

数智传播、数智金融经济、数据金融经济、数智政务、数智监管治理，以及“大数据、大模型、大计算”全新范式等方向理论与实践

 【具体研究领域】

包括 Bigdata4SocialScience、AI4SocialScience、LLM4SocialScience、Blockchain4SocialScience，以及先进信息技术融合创新在数智金融经济、数智传播社会、数智健康医疗、数智政务治理中的应用。

【薪资待遇优渥】

年薪可达 30 万人民币左右，另有绩效奖金及江苏省和南京市人才补贴。具体薪资需与HR面议，总收入依据专业背景和技能经验而定（计算机 AI 背景者薪资更优）。

【欢迎学科交叉、专业背景不限】

不限制专业背景，致力于构建一个多元、开放、包容的科研环境，因此，欢迎计算机、软件、大数据、人工智能、区块链、隐私计算、数据安全、数据科学等背景的博士人才，也热切邀请具有人文社科背景的博士加入我们的团队，共同探索信息技术与社会科学的交叉前沿。也欢迎其他编程能力强的理工科博士毕业生（即使没有AI等背景也欢迎）。

【南京大学研究中心】

南京大学研究中心为双院士领军的校级科研和创新平台，详情请见：fintech.nju.edu.cn。

【团队氛围】

学科交叉、理论与实践相结合、国际化视野、行业前沿视角和项目。

【联系我们】

请感兴趣的朋友将个人简历发送至邮箱:blockchainfintech@126.com。

【更多招募】 南京大学研究中心招收硕士生、博士生、博士后、青年教师、研究员，也欢迎访问、客座、联培以及科研助理（有些岗位可兼职或远程合作）等

欢迎加入我们，您将在这个富有挑战性和机遇的环境中，开启广阔的职业发展道路，实现个人价值与学术梦想的双赢！

期待您的加入，携手共创数智未来！

南京大学研究中心诚募博士后



![](https://image.hackertalk.net/images/62537abc-405f-44da-a67e-9f18082f3d74)















sqlmap -u "xxxxx.com/#/login" --all  --delay 1 --batch --random-agent

[CRITICAL]can't establish SSL connection.

![](https://image.hackertalk.net/images/4a856cac-750c-4972-aa1f-4bf02f000394)

sqlmap -r win.txt --dbs

**

[CRITICAL] anti-CSRF token 'XSRF-TOKEN' can't be found 


**


