C/C++每日一练(20230222)

目录

1. 部分复制字符串(★)

2. 按字典顺序排列问题(★★)

3. 地下城游戏(★★★)

附录

动态规划

1. 部分复制字符串

将字符串2小写字母复制到字符串1：编写程序,输入字符串s2,将其中所有小写字母复制到字符串数组strl中。例如：aal1bb22cc33de4AA55BB”,生成的strl为"aabbccde"。

代码：

#include<stdio.h>int main()
{int sum=0,t=0,i;char s[50],s1[50];scanf("%s",s);for(i=0;s[i]!='\\0';i++){if(s[i]>='a'&&s[i]<='z'){s1[t++]=s[i];}}s1[t]='\\0';printf("%s",s1);
}

输入输出：

aal1bb22cc33de4AA55BB
aabbccde

2. 按字典顺序排列问题

输入若干英文单词，将每个单词的首字母转换成大写字母，其他字母为小写，并按字典顺序排列（原题为代码填空题，以下代码已补全）

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int cmp(const void *a, const void *b)
{return strcmp(*(char **)a, *(char **)b);
}int main(int argc, char *argv[])
{int n = 0;int i;printf("how many words?\\n");scanf("%d", &n);char **s = new char *[n];for (i = 0; i < n; i++){s[i] = new char[100];scanf("%s", s[i]);char *t = s[i];while (*t != '\\0'){if (t == s[i] && (*t >= 'a' && *t <= 'z'))*t = *t - 'a' + 'A';if (t > s[i] && (*t >= 'A' && *t <= 'Z'))*t = *t - 'A' + 'a';t++;}}qsort(s, n, sizeof(char *), cmp);for (i = 0; i < n; i++){printf("%s\\n", s[i]);}return 0;
}

输入输出：

how many words?
3
by
boy
book
Book
Boy
By

3. 地下城游戏

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

说明:

• 骑士的健康点数没有上限。

• 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

代码：

#include <bits/stdc++.h>
using namespace std;class Solution
{
public:int calculateMinimumHP(vector<vector<int>> &dungeon){int row = dungeon.size();int col = dungeon[0].size();int dp[row][col] = {0};dp[row - 1][col - 1] = max(1 - dungeon[row - 1][col - 1], 1);for (int i = row - 2; i >= 0; i--){dp[i][col - 1] = max(dp[i + 1][col - 1] - dungeon[i][col - 1], 1);}for (int i = col - 2; i >= 0; i--){dp[row - 1][i] = max(dp[row - 1][i + 1] - dungeon[row - 1][i], 1);}for (int i = row - 2; i >= 0; i--){for (int j = col - 2; j >= 0; j--){dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1);}}return dp[0][0];}
};int main()
{Solution s;vector <vector <int>> nums = {{-2,-3,3},{-5,-10,1},{10,30,-5}};cout << s.calculateMinimumHP(nums) << endl;return 0;
}

输出：

7

附录

动态规划

基本概念

动态规划：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，这种多阶段最优化决策解决问题的过程就称为动态规划(DP)。动态规划算法通常用于求解具有最优性质的问题

算法设计

1：找出最优解的性质，并描述其结构特征
2：递归定义最优值
3：以自底向上的方式计算最优值
4：根据计算最优值时得到的信息构造出最优解

具体步骤

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

能采用动态规划求解的问题的一般要具有3个性质

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
(3) 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。