跳转到主要内容

这是本节的多页打印视图。 .

返回本页常规视图.

博客

文章、算法笔记与踩坑记录。

文章、算法笔记与踩坑记录。

1 - 算法

记录一些刷leetcode的算法总结

记录一些刷leetcode的算法总结。

1.1 - 动态规划背包问题总结

动态规划背包问题的常见题型的解题思路和代码实现

背包问题总结

  • 一共有2种背包:
    • 01背包
    • 完全背包
  • 一共有4种求解目标:
    • 求最大价值
    • 求组合数
    • 求排列数
    • 给target,求最少/最多的物品数量

其中01背包不考虑排列数,完全背包不考给出target的最多物品数量

最大价值题型

题型1:01背包(最大价值)

def knap01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):              # 物品外循环
        for j in range(capacity, w - 1, -1):       # 背包倒序
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

416. 分割等和子集

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2: return False
        target = total // 2
        dp = [0] * (target + 1)
        for num in nums:                          # 物品
            for j in range(target, num - 1, -1):  # 背包倒序
                dp[j] = max(dp[j], dp[j - num] + num)
        return dp[target] == target

题型2:完全背包(最大价值)

def knapComplete(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):           # 物品外循环
        for j in range(w, capacity + 1):        # 背包正序
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[capacity]

这个题型在LeetCode上暂无对应题目

组合数题型

题型3:01背包 + 组合数

# 速查模板
def knap01_comb(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for num in nums:                             # 物品外循环
        for j in range(target, num - 1, -1):     # 背包倒序
            dp[j] += dp[j - num]
    return dp[target]

494. 目标和

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total or (total + target) % 2: return 0
        bag = (total + target) // 2
        dp = [0] * (bag + 1)
        dp[0] = 1
        for num in nums:                         # 物品
            for j in range(bag, num - 1, -1):    # 背包倒序
                dp[j] += dp[j - num]
        return dp[bag]

题型4:完全背包 + 组合数

# 速查模板
def complete_comb(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:                          # 物品外循环
        for j in range(coin, amount + 1):       # 背包正序
            dp[j] += dp[j - coin]
    return dp[amount]

518. 零钱兑换 II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:                      # 物品
            for j in range(coin, amount + 1):   # 背包正序
                dp[j] += dp[j - coin]
        return dp[amount]

排列数题型

题型5:完全背包 + 排列数

# 速查模板
def complete_perm(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for j in range(1, target + 1):              # 背包外循环
        for num in nums:                        # 物品内循环
            if j >= num:
                dp[j] += dp[j - num]
    return dp[target]

377. 组合总和 Ⅳ

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for j in range(1, target + 1):          # 背包外循环
            for num in nums:                    # 物品内循环
                if j >= num:
                    dp[j] += dp[j - num]
        return dp[target]

最少/最多物品数量题型

题型6:01背包 + 最少/最多物品数量

def knap01_max_len(nums, target):
    dp = [-float('inf')] * (target + 1)         # 初始化为负无穷
    dp[0] = 0
    for num in nums:                            # 物品外循环
        for j in range(target, num - 1, -1):    # 背包倒序
            dp[j] = max(dp[j], dp[j - num] + 1)
    return dp[target] if dp[target] != -float('inf') else -1

def knap01_min_len(nums, target):
    dp = [float('inf')] * (target + 1)          # 初始化为正无穷
    dp[0] = 0
    for num in nums:                            # 物品外循环
        for j in range(target, num - 1, -1):    # 背包倒序
            dp[j] = min(dp[j], dp[j - num] + 1)
    return dp[target] if dp[target] != float('inf') else -1

2915. 和为目标值的最长子序列的长度

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        dp = [-float('inf')] * (target + 1)
        dp[0] = 0
        for num in nums:                          # 每个数字只能用一次
            for j in range(target, num - 1, -1):  # 倒序遍历(01背包)
                dp[j] = max(dp[j], dp[j - num] + 1)
        return dp[target] if dp[target] != -float('inf') else -1

题型7:完全背包 + 最少物品数量

def complete_min_len(coins, amount):
    dp = [float('inf')] * (amount + 1)          # 初始化为正无穷
    dp[0] = 0
    for coin in coins:                          # 物品外循环
        for j in range(coin, amount + 1):       # 背包正序
            dp[j] = min(dp[j], dp[j - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

322. 零钱兑换

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:                       # 物品
            for j in range(coin, amount + 1):    # 背包正序
                dp[j] = min(dp[j], dp[j - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

2 - 长城突破

在中国大陆由于网路限制,在开发过程中总会遇到一些网络超时的情况,这个分类介绍一些常用情况的解决办法

序

中华有网,其广如海,然环伺四围,立藩篱若铜墙铁壁,号曰「防火长城」。此墙非砖石所筑,乃无形之壁,横亘于虚实之间,绝通衢,闭视听,划疆域于数字之界。

吾辈开发者,生于斯,长于斯,怀巧思而望寰宇,欲求索于外邦新技,览寰球之资讯。然每有探求,辄见「连接超时」之冰冷字样;欲访开源圣殿,往往「请求中断」而不得其门。讯息如涓涓细流忽遇巨坝截断,灵感似星火迸发即遭寒水浇熄。前沿论文,遥不可及;技术论坛,望而兴叹。同行切磋,因一墙之隔而成鸡犬相闻、老死难往来之局;开源协奏,因通途阻塞而似孤岛独奏、无人能相和。此间困顿,如陷数字泥沼,虽奋力挣扎,亦觉寸步难行,徒耗光阴与热忱于无形壁垒之前。

悲夫!呜呼!技艺本无界,思想应无疆。知识如光,当普照万物,何故画地为牢,自束手脚?文明之进步,端赖交流与碰撞,今高墙耸立,无异于闭目塞听,徒令技艺迟滞,灵感枯竭。每念及此,未尝不顿足捶胸,扼腕叹息。恨此墙之如鲠在喉,既阻滞文明交融之潮,复困顿苍生求索之路,使多少英才壮志,消磨于无尽的等待与徒劳的尝试之中。

然,困则思变,堵则谋通。虽有铜墙铁壁,亦难阻求知的灼灼之心与技术的脉脉潮涌。今特辟此篇,非为鼓动对抗,实乃求生之策、治学之需。意在集八方智慧,汇百家之术,或寻镜像之桥,或觅协议之道,或筑代理之隧。钻墙凿洞,虽非坦途,亦求于绝处逢生,于阻塞中开一隙天光。此举不为他求,惟愿能稍解信息饥渴,略平知识鸿沟,以泄心头之困顿,以解研习之燃眉,使我辈开发者之目光,不致困于方寸,而能观星辰大海。前路漫漫,道阻且长,然心向开阔,行则必至。

2.1 - APT 镜像源

为 Ubuntu 配置 APT 镜像源

为 Ubuntu 配置 APT 镜像源

ubuntu配置文件从旧版的/etc/apt/sources.list

变更为/etc/apt/sources.list.d/ubuntu.sources

清华镜像源

Types: deb
URIs: https://mirrors.tuna.tsinghua.edu.cn/ubuntu
Suites: noble noble-updates noble-backports
Components: main restricted universe multiverse
Signed-By: /usr/share/keyrings/ubuntu-archive-keyring.gpg

Types: deb
URIs: https://mirrors.tuna.tsinghua.edu.cn/ubuntu
Suites: noble-security
Components: main restricted universe multiverse
Signed-By: /usr/share/keyrings/ubuntu-archive-keyring.gpg

中科大镜像源

Types: deb
URIs: https://mirrors.ustc.edu.cn/ubuntu
Suites: noble noble-updates noble-backports
Components: main restricted universe multiverse
Signed-By: /usr/share/keyrings/ubuntu-archive-keyring.gpg

Types: deb
URIs: https://mirrors.ustc.edu.cn/ubuntu
Suites: noble-security
Components: main restricted universe multiverse
Signed-By: /usr/share/keyrings/ubuntu-archive-keyring.gpg

2.2 - Homebrew 安装指南

在Linux系统上安装Homebrew的详细步骤

Homebrew 国内网络环境下安装指南

创建brew用户

这是因为brew不支持使用root用户安装,如果没有非 root 用户需要创建一个

useradd -m -s $(which fish) brew
echo "brew:123456" | chpasswd
usermod -aG sudo brew

切换用户

su brew

设置镜像

打开~/.config/fish/config.fish

nano ~/.config/fish/config.fish

设置环境变量

set -x HOMEBREW_BREW_GIT_REMOTE "https://mirrors.ustc.edu.cn/brew.git"
set -x HOMEBREW_CORE_GIT_REMOTE "https://mirrors.ustc.edu.cn/homebrew-core.git"
set -x HOMEBREW_BOTTLE_DOMAIN "https://mirrors.ustc.edu.cn/homebrew-bottles"
set -x HOMEBREW_API_DOMAIN "https://mirrors.ustc.edu.cn/homebrew-bottles/api"

一行命令版本

echo 'set -x HOMEBREW_BREW_GIT_REMOTE "https://mirrors.ustc.edu.cn/brew.git"' >> ~/.config/fish/config.fish
echo 'set -x HOMEBREW_CORE_GIT_REMOTE "https://mirrors.ustc.edu.cn/homebrew-core.git"' >> ~/.config/fish/config.fish
echo 'set -x HOMEBREW_BOTTLE_DOMAIN "https://mirrors.ustc.edu.cn/homebrew-bottles"' >> ~/.config/fish/config.fish
echo 'set -x HOMEBREW_API_DOMAIN "https://mirrors.ustc.edu.cn/homebrew-bottles/api"' >> ~/.config/fish/config.fish

使配置生效

source ~/.config/fish/config.fish

安装brew

/bin/bash -c "$(curl -fsSL https://mirrors.ustc.edu.cn/misc/brew-install.sh)"

设置brew路径

/home/linuxbrew/.linuxbrew/bin/brew shellenv >> ~/.config/fish/config.fish

2.3 - Postgres 安装指南

在国内网络环境下安装Postgres数据库的详细步骤

国内网络环境下安装 Postgres 数据库

APT 安装

添加清华源仓库签名

sudo wget -q -O /etc/apt/keyrings/postgresql.asc \
  https://mirrors.tuna.tsinghua.edu.cn/postgresql/repos/apt/ACCC4CF8.asc

添加清华源仓库

sudo bash -c 'echo "Types: deb
URIs: https://mirrors.tuna.tsinghua.edu.cn/postgresql/repos/apt
Suites: $(lsb_release -cs)-pgdg
Components: main
Signed-By: /etc/apt/keyrings/postgresql.asc" > /etc/apt/sources.list.d/postgresql.sources'

更新源并安装

sudo apt update
sudo apt install postgresql-18 # 替换为版本号

启动

sudo systemctl start postgresql

验证

sudo systemctl status postgresql@18-main.service # 替换为版本号

连接

sudo -u postgres psql

3 - 杂七杂八

一时间想不到分类的文章放在这里

一时间想不到分类的文章放在这里。

3.1 - 制裁流氓软件云枢

在Mac平台下禁止云枢后台启动和窃取浏览器数据

制裁流氓软件云枢

禁止云枢安装浏览器监控插件

云枢这个流氓软件会在启动的时候往浏览器里塞一条强制安装浏览器拓展的策略ExtensionInstallForcelist,从而让你删都删不掉他的浏览器拓展

天知道这个浏览器拓展到底干了些什么,说不准就能看到咱们浏览记录,那我也是研究了好一会,终于找到了解决办法

思路

首先使用find命令查找Google Chrome的策略文件,看看云枢是怎么作妖的

mac@user~> sudo fd -i "com.google.Chrome.plist" / 2>/dev/null

查询结果:

/Library/Managed Preferences/xxx/com.google.Chrome.plist
/System/Volumes/Data/Library/Managed Preferences/xxx/com.google.Chrome.plist
/System/Volumes/Data/Users/xxx/Library/Preferences/com.google.Chrome.plist
/Users/user/Library/Preferences/com.google.Chrome.plist

其中以/System/Volumes开头的文件我们不用管,因为那是Mac文件系统的特性,是文件的实际存储位置

/Users/user/Library/Preferences/com.google.Chrome.plist是用户级别的,记录了一些浏览器的窗口大小等信息,与策略无关

其中真正起作用的实际上是这个/Library/ManagedPreferences/xxx/com.google.Chrome.plist文件 他的内容应该为

ExtensionInstallForcelist = (
    afiecjcblhjecgchlpknmdigpxxxxx # 这是云枢的浏览器拓展ID
);

但很恶心的一点就在于,你删除这个文件没用,因为云枢检测到策略缺失之后,会自动重新创建这个文件,然后继续强制安装浏览器拓展

解决办法

核心思路是占位并锁定

既然系统非要往那个位置写文件,我们就放一个空的、不可修改的假文件在那儿, 系统想覆盖它时会发现权限被锁死,从而写入失败。

具体步骤如下:

  1. 删除策略文件
sudo rm -f "/Library/Managed Preferences/xxx/com.google.Chrome.plist" #注意这里有个空格,必须用引号括起来
  1. 立刻创建一个空的假文件
sudo touch "/Library/Managed Preferences/xxx/com.google.Chrome.plist"
  1. 给文件加上"无敌"锁
sudo chflags uchg "/Library/Managed Preferences/xxx/com.google.Chrome.plist"

这样一来,连root权限也无法直接(可以先解锁再写)写这个文件了,也就是说云枢就没法再往里面写东西了,从而达到了禁止安装浏览器拓展的目的

  1. 杀掉缓存进程,让系统重新读取这个空文件
sudo killall cfprefsd
  1. 验证是否成功
defaults read "/Library/Managed Preferences/xxx/com.google.Chrome"

应该为空

终结云枢后台程序

云枢这个流氓软件点击退出之后,还会在后台一直运行他的守护进程YunShuManger和Helper,偷偷监控用户行为

解决办法

  1. 查找守护进程的配置文件
# 进入系统守护进程目录
cd /Library/LaunchDaemons

# 查找相关的配置文件
ls | grep -i eagleyun
ls | grep -i yunshu

# 输出结果:
com.eagleyun.sase.helper.plist
com.eagleyun.sase.servicemanager.plist
  1. 卸载守护进程
sudo launchctl unload com.eagleyun.sase.helper.plist
sudo launchctl unload com.eagleyun.sase.servicemanager.plist
  1. kill进程
sudo pkill -f -i yunshu