【CSDN 竞赛—第10期】所有题目解法的思考和总结

目录

一、 熊孩子拜访

二、 走楼梯

三、括号上色

四、喜水青蛙

---

一、 熊孩子拜访

已知存在一个长度为n的整数序列A。 A中所有元素按照从小到达的顺序进行排序。 现在执行操作倒置一段序列。 请找到A序列里的倒置子序列。

我的解题思路（通过所有测试用例）： 

class Solution:
    def __init__(self) -> None:
        pass
    def solution(self, n, arr):
        result = []
        # 保存右值
        max = 0
        # 保存左值
        min = 0
        next = 0
        for item in arr:
            if next>item and item>max:
                max=next
                min=item
            elif next<min and item>max:
                min=next
            next=item
        result.append(str(min))
        result.append(str(max))
        if len(result)==0:
            result=["0","0"]
        return result
 
if __name__ == "__main__":
    n = int(input().strip())
    arr = [int(item) for item in input().strip().split()]
    sol = Solution()
    result = sol.solution(n, arr)
    print(" ".join(result))

输入描述：第一行输入整数 n ，第二行输入 n 个整数（1<=n<=1000）

输出描述：输出被倒置的数列的左值和右值，如果没有，输入0 0

例如：

 

 

---

二、 走楼梯

现在有一截楼梯， 根据你的腿长， 你一次能走 1 级或 2 级楼梯， 已知你要走 n 级楼梯才能走到你的目的楼层， 请实现一个方法， 计算你走到目的楼层的方案数。

我的解题思路：

class Solution:
    def __init__(self) -> None:
        pass
 
    def solution(self, n):
        if isinstance(n, int) and n > 0:
            basic_dic = {1: 1, 2: 2}
            if n in basic_dic.keys():
                return basic_dic[n]
            else:
                return self.solution(n - 1) + self.solution(n - 2)
        else:
            return False
 
 
if __name__ == "__main__":
    n = int(input().strip())
    sol = Solution()
    result = sol.solution(5)
    print(result)

输入和输出： 

---

如果采用非递归，如何实现呢？——递推法

类似的一道题：一栋楼有N阶楼梯，兔子每次可以跳1、2或3阶，问一共有多少种走法？

def solution(n):
  if isinstance(n,int) and n > 0:
    # 如果台阶数总共有3个，那么有4种走法：
    # 1 1 1 
    # 1 2
    # 2 1
    # 3    
    # 如果n为4，有7种走法
    # 1 3
    # 3 1
    # 22
    # 1111
    # 211
    # 121
    # 112
    # 有4级台阶
    # temp=1，h1=2，h2=4，h3=1+2+4，返回7
    # 有5级台阶
    # temp=1,h1=2,h2=4,h3=1+2+4
    # temp=2,h1=4,h2=1+2+4,h3=2+4+1+2+4，返回13
    h1,h2,h3 = 1,2,4
    basic_dic = {1:1,2:2,3:4}
    if stairs in basic_dic.keys():
      return basic_dic[n]
    else:
      while n>=4:
        temp = h1
        h1 = h2
        h2 = h3
        h3 = temp + h1 + h2
        n-=1
      return h3
  else:
    return False
# 总结：
# 如果一次可以走1、2或3步的话，那么：第N级楼梯的走法是N-1级楼梯的走法+N-2级楼梯的走法+N-2级楼梯的走法

---

三、括号上色

小艺酱又得到了一堆括号。 括号是严格匹配的。 现在给括号进行上色。 上色有三个要求： 1、 只有三种上色方案， 不上色， 上红色， 上蓝色。 2、 每对括号只有一个上色。 3、 相邻的两个括号不能上相同的颜色， 但是可以都不上色。 问括号上色有多少种方案？ 答案对1000000007取模。

以下代码参考：

【3.29百度笔试编程解析】CodeForces 149D 括号染色问题 dp+dfs好题_和你在一起^_^的博客-CSDN博客题目大意给一个给定括号序列，给该括号上色，上色有三个要求1、只有三种上色方案，不上色，上红色，上蓝色2、每对括号必须只能给其中的一个上色3、相邻的两个不能上同色，可以都不上色题目分析求0-len-1这一区间内有多少种上色方案，很明显的区间DPdp[l][r][i][j]表示l-r区间两端颜色分别是i,j的方案数0代表不上色，1代表上红色，2代表上蓝色对于l-r区间，有3种情况1...https://blog.csdn.net/weixin_42462804/article/details/105194872

import sys
 
s = input()
num = strlen = len(s)
tmp = [0 for i in range(num)]  # 记录左括号的位置
match = [0 for i in range(num)]  # 记录右匹配的位置
dp = [[[[0 for i in range(3)] for i in range(3)] for i in range(num)] for i in range(num)]
# 由内向外建立多维dp 数组的形式
# dp=np.arange(3*3*num*num).reshape(num,num,3,3)
# 0代表不上色，1代表上红色，2代表上蓝色
mod = 1000000007
 
 
def getmatch(len):
    p = 0
    for i in range(len):
        if (s[i] == '('):
            tmp[p] = i
            p = p + 1
        else:
            match[i] = tmp[p - 1]
            match[tmp[p - 1]] = i
            p = p - 1
 
 
def dfs(l, r):
    if (l + 1 == r):  # 边界条件
        dp[l][r][0][1] = 1
        dp[l][r][1][0] = 1
        dp[l][r][0][2] = 1
        dp[l][r][2][0] = 1
        return
    if (match[l] == r):  # 如果匹配的话方案数相加
        dfs(l + 1, r - 1)
        for i in range(3):
            for j in range(3):
                if (j != 1):
                    dp[l][r][0][1] = (dp[l][r][0][1] + dp[l + 1][r - 1][i][j]) % mod;
                if (i != 1):
                    dp[l][r][1][0] = (dp[l][r][1][0] + dp[l + 1][r - 1][i][j]) % mod;
                if (j != 2):
                    dp[l][r][0][2] = (dp[l][r][0][2] + dp[l + 1][r - 1][i][j]) % mod;
                if (i != 2):
                    dp[l][r][2][0] = (dp[l][r][2][0] + dp[l + 1][r - 1][i][j]) % mod;
        return
    else:  # 否则方案数相乘，乘法原理
        p = match[l]
        dfs(l, p)
        dfs(p + 1, r)
        for i in range(3):
            for j in range(3):
                for k in range(3):
                    for q in range(3):
                        if not ((k == 1 and q == 1) or (k == 2 and q == 2)):
                            dp[l][r][i][j] = (dp[l][r][i][j] + (dp[l][p][i][k] * dp[p + 1][r][q][j]) % mod) % mod
 
 
if __name__ == '__main__':
    getmatch(strlen)
    dfs(0, strlen - 1)
    ans = 0
    for i in range(3):
        for j in range(3):
            ans = (ans + dp[0][strlen - 1][i][j]) % mod;
    sys.stdout.write(str(ans))

---

本题属于括号匹配，用到区间上的动态规划（DP），可以参考以下博文学习入门：

区间dp入门_阿阿阿安的博客-CSDN博客_区间dp一.什么是区间dp?顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。二.核心思路既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的...https://blog.csdn.net/qq_40772692/article/details/80183248

---

四、喜水青蛙

总是喜欢在水里嬉戏的青蛙， 某天要过河拜访一位朋友。已知河道中长满了带刺的不知名生物， 能通过的路只有一条直线， 长度为L。直线上随机分布着m块石头。 青蛙的最小跳跃距离是s， 最大跳跃距离是t。青蛙想要尽可能的少踩石头， 那么它通过河道最少会踩到多少石头？

输入描述：

多组数据输入，其中每组数据：
第一行输入1个整数L(1<=L<=1e9)。
第二行输入3个整数：s、t、m(1<=s<=t<=10，1<=m<=100)。
第三行输入m个不同的整数，表示m个石子在数轴上的分布位置。
每行所有相邻整数用空格隔开。

输出描述：

输出青蛙过河最少会踩到的石子数量，
每组输入数据对应的输出结果单独成行。

输入样例：

10
2 3 5
2 3 5 6 7

输出样例：

2

---

以下代码来自：
https://bbs.csdn.net/topics/607060820https://bbs.csdn.net/topics/607060820

#include 
#include 
#include 
void solution(int L, int ar[], int arr[]);
void move(int s, int count, int L,  int ar[],  int arr[]);
int res=INT_MAX;
int main(){
    int L;
    int ar[3];
    int *arr;
    scanf("%d",&L);
    for(int i=0;i<3;i++){
        scanf("%d",&ar[i]);
    }
    arr=malloc(sizeof(int)*ar[2]);
    for(int i=0;i2];i++){
        scanf("%d",&arr[i]);
    }
    solution(L,ar,arr);
    printf("%d",res);
}
void solution(int L, int ar[], int arr[]){
    int s=0;
    int count=0;
    move(s, count, L,  ar,  arr);
}
void move(int s, int count, int L, int ar[],int arr[]){
    if(s
        for(int i=0;i2];i++){
            if(s==arr[i]){
                count++;
            }
        }
        for(int j=ar[0];j<=ar[1];j++){
            move(s+j,count,L,ar,arr);
        }
//        move(s+ar[0],count,L,ar,arr);
//        move(s+ar[1],count,L,ar,arr);
    }else{
        if(res>count){
            res=count;
        }
    }
}