自娱自乐的精神乐园

余凯迪的博客

0%

发表于 分类于 阅读次数：

动态规划

有限集中的最优化问题

  1. 状态表示（化零为整）
  • 确定集合是什么
  • 属性和集合的关系（max，min，count）
  1. 状态计算（化整为零）
  • 划分为不同的子集，计算子集然后根据子集计算该集合的属性（不重复不遗漏）
  • 划分依据：寻找最后一个不同点

示例

1. 01背包问题

普通的状态转移方式，二维的状态表示
状态 dp[i][j] 表示前i个物品体积不超过j的最大价值
状态转移：dp[i][j] = max(dp[i-1][j], dp[i-v[i]]+w[i])

朴素解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# include<iostream>
# include<cstring>
using namespace std;

const int N=1010;
int v[N],w[N];
int dp[N][N];

int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=N;++i){
        cin>>v[i]>>w[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=N;++i){
        for(int j=0;j<=V;++j){
            dp[i][j] = dp[i-1][j];
            if(j>=v[i]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
            }
        }
    }
    cout<<dp[N][V];
    return 0;
}

状态优化解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# include<iostream>
# include<cstring>
using namespace std;

const int N=1010;
int v[N],w[N];
int dp[N];

int main(){
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=N;++i){
        cin>>v[i]>>w[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=N;++i){
        // 主要此时对体积的遍历，从小到大会影响到dp[j-v[i]]，从大到小保证更新j的时候，j-v[i]是 i-1 的值而不是 i 的值
        for(int j=V;j>=v[i];--j){
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    cout<<dp[V];
    return 0;
}

2. 完全背包问题

状态dp[i][j] 表示前i个物品体积不超过j的最大价值；
状态转移 dp[i][j]=max(dp[i-1][j], dp[i-1][j-v]+w, dp[i-1][j-2v]+2w, dp[i-1][j-3v]+3w, ...)
朴素的状态转移需要3重循环；考虑dp[i][j]和dp[i][j-v]的关系：
dp[i][j-v]=max(dp[i-1][j-v], dp[i-1][j-2v]+w, dp[i-1][j-3v]+2w,...)
可以看出dp[i][j]=max(dp[i-1][j], dp[i][j-v]+w)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>

using namespace std;
const int N=1010;
int v[N],w[N];

int dp[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>v[i]>>w[i];
    for(int i=1;i<=n;++i){
        for(int j=v[i];j<=m;++j){
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    cout<<dp[m];
    return 0;
}

3. 石子合并

区间dp问题
状态表示：f(i,j)表示所有将[i,j]合并为一堆的方案的集合；属性为最小值
状态计算：
f(i,j)=min(f(i,k)+f(k+1,j)+sum(i,j)) i≤k≤j-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>

using namespace std;

const int N = 310;

int v[N],f[N][N];
int pre_sum[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>v[i];
        // 先记录前缀和后续使用
        pre_sum[i] = pre_sum[i-1]+v[i];
    }
    // 先枚举区间，再枚举区间起点，再枚举区间分割点
    for(int len=2;len<=n;++len){
        for(int i=1;i+len-1<=n;++i){
            int j= i+len-1;
            f[i][j] = 1e8;
            for(int k=i;k<=j-1;++k){
                f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+pre_sum[j]-pre_sum[i-1]);
            }
        }
    }
    cout<< f[1][n];
    return 0;
}

最长公共子序列

状态表示：f(i,j)
集合：A[1-i]和B[1-j]所有公共子序列的集合
状态：最大值
状态转移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>

using namespace std;

const int N=1010;

char a[N],b[N];
int f[N][N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=m;++i)cin>>b[i];
    
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            f[i][j] = max( f[i][j-1], f[i-1][j]);
            if(a[i]==b[j])f[i][j] = max(f[i][j],f[i-1][j-1] + 1);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

发表于 更新于 分类于 ， 阅读次数：

993. 二叉树的堂兄弟节点

思路

本题的思路较为简单。比较是否为堂兄弟节点，根据定义关键有两点

  1. 深度相同
  2. 父节点不同

因此分别得到两个节点的深度和父节点，此题就能解答。

代码

代码为Python版本，python的函数可以有多个返回值（实际上作为一个tuple返回），便于编程和理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    """
    获取节点的深度和父节点，深度优先搜索
    """
    def dfs(self, root: 'TreeNode', x: 'int', depth: 'int'):
        if root is None:
            return None
        if root.left and root.left.val == x:
            return depth + 1, root
        if root.right and root.right.val == x:
            return depth + 1, root
        left_res = self.dfs(root.left, x, depth + 1)
        if left_res:
            return left_res
        right_res = self.dfs(root.right, x, depth + 1)
        if right_res:
            return right_res   
    
    def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool':
        # 获取节点深度信息和其父节点
        x_info = self.dfs(root, x, 0)
        y_info = self.dfs(root, y, 0)
        if x_info is None or y_info is None:
            return False
        if x_info[0] == y_info[0] and x_info[1] != y_info[1]:
            return True
        return False

994. 腐烂的橘子

思路

本题模拟题目中描述的过程即可以作答。
连续两次数组信息没有发生改变，即可认为达到了最终状态。
使用两个变量分别记录本轮新鲜橘子的个数和上一轮新鲜橘子的个数，前后不发生变化，则过程模拟即可退出。

代码

prev_fresh记录上一轮新鲜橘子个数
fresh记录本轮新鲜橘子的个数
本轮腐烂的橘子到下一轮进行统计，导致最后的结果需要-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':
        prev_fresh = -1
        minute = 0
        # 该函数对坐标为(r,c)相邻位置的橘子进行腐烂操作
        def infect(r,c):
            if r-1 >= 0 and grid[r-1][c] == 1:
                grid[r-1][c] = 2
            if r+1 <len(grid) and grid[r+1][c] == 1:
                grid[r+1][c] = 2
            if c-1 >= 0 and grid[r][c-1] == 1:
                grid[r][c-1] = 2
            if c+1 <len(grid[0]) and grid[r][c+1] == 1:
                grid[r][c+1] = 2
        
        while(1):
            fresh = 0
            rot = 0
            rot_corr = []
            for row in range(len(grid)):
                for col in range(len(grid[0])):
                    if grid[row][col] == 1:
                        fresh += 1
                    if grid[row][col] == 2:
                        rot += 1
                        rot_corr.append([row,col])
            for x in rot_corr:
                infect(x[0],x[1])
            
            if (fresh == prev_fresh):
                break
            minute += 1
            prev_fresh = fresh
            prev_rot = rot
            
        if fresh == 0:
            return minute - 1
        return -1

995. K 连续位的最小翻转次数

思路

对于每一个位置，两次翻转即还原。x与0异或保持原值，x以1异或得到1-x
如果K=1，要将每一个位置都置1，最朴素的想法就是从前往后遍历0，遇到0则进行翻转。那么对于K>1，我们同样对出现的0进行翻转操作，但是需要记录下翻转的终点，便于我们恢复。
如果走到最后，对于前面length-K位都为1，但是由于前面的操作导致末尾的K位中包含1，这就表明了不可能实现。

代码

使用一个辅助List，记录翻转操作的终点。
ls变量记录是否处于翻转阶段，第i为0时，意味着A[i:i+k]需要翻转（注意python语法，index是i到i+k-1），rev在结束位置后记上标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minKBitFlips(self, A: 'List[int]', K: 'int') -> 'int':
        rev = [0]*(len(A)+10)
        ls = 0
        ans = 0
        for i in range(len(A)):
            ls ^= rev[i]# 主要是用来判断该位置需不需要翻转
            A[i] ^= ls  #该位置之前多次操作最后的结果
            if A[i] == 0:
                ans += 1
                ls ^= 1 #flag翻转一下
                if i+K > len(A):
                    return -1
                rev[i+K] = 1 # 标记翻转的结束位置
        return ans

996. 正方形数组的数目

思路

通过递归实现深度优先搜索。
该过程类似每次挑选出一个数字，与已经是正方形数组的子数组最后一个数字，判断能否扩充子数组，直到成为原数组的一个排列。
DFS直接满足了找到了所有的排列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import copy
import math
class Solution:
    def isSqr(self,num):
        return int(math.sqrt(num))**2 == num

    def dfs(self, A, b):
        if len(A) == 0:
            return 1
        ans = 0
        for i in range(len(A)):
            if i==0 or A[i] != A[i-1]:
                if not self.isSqr(A[i]+b):
                    continue
                B = copy.deepcopy(A)
                B.remove(B[i])
                ans += self.dfs(B, A[i])
        return ans

    def numSquarefulPerms(self, A: 'List[int]') -> 'int':
        ans = 0
        A.sort() # 排序的原因是为了在搜索时避免重复查找
        for i in range(len(A)):
            if i==0 or A[i] != A[i-1]:
                B = copy.deepcopy(A)
                B.remove(B[i])
                ans += self.dfs(B, A[i])
        return ans

发表于 更新于 阅读次数：

今天折腾了半天，总算是拼拼凑凑搭建好了一个精（jian）美（lou）的博客页面。

着手弄这个博客呢，有好几个原因：

  1. 看别人的博客好看，就想着自己弄一个。不想太折腾，有必须体现程序员的逼格，gayhub是个好东西啊😏
  2. 读了不少的博客，积累了不少的技术知识，但是缺乏输出环境。除了平时在业务中需要使用，此外还需要一个沉淀的平台，来记录这些东西，毕竟写出来的东西大家看了能明白才能算是自己真的弄明白讲清楚。
  3. 此外就是需要一个完整的、可控的地方，记录自己的生活。现在各大互联网公司在移动时代，纷纷形成信息孤岛，对于个人就很难形成一个统一有机的整体。微信朋友圈里记录文字和视频，豆瓣里面有我喜欢的影音书籍，知乎里面有很多我喜欢的优质的文章，今日头条、微信公众号这些东西占据了我的碎片时间，如此种种。面对庞大的信息流，与其被其淹没，不如自己有一个自己的精神乐园。

利欲驱人万火牛，江湖浪迹一沙鸥。

愿大家都能够有一方精神乐土。