题意整理。  给定一个背包，能容纳体积为V。然后有n种物品，每种物品有一个对应的体积和价值。每种物品只提供一个。 求这个背包最多能装多大价值的物品。 如果背包恰好装满，最多能装多大价值的物品。  方法一（动态规划） 1.解题思路 第一问：  状态定义：dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品。 状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即dp1[j]=Math.max(dp1[j−v[i]]+w[i],dp1[j])dp1[j]=Math.max(dp1[j-v[i]]+w[i],dp1[j])d...

题意整理。  键盘输入两个字符串str和substr。 求substr在str中出现的次数。  方法一（循环+字符函数） 1.解题思路  遍历字符串。 检查当前字符的类型。如果是字母，字母计数加1；如果是空格，空格计数加1；如果是数字，数字计数加1；如果以上都不是，其它计数加1。  动图展示：  2.代码实现 #include <iostream> #include <string> using namespace std; int main() { string str; getline(cin, str); int whitespace = 0; int digit...

题意整理。  给定一个n行m列的矩阵。 有q次查询，每次查询给定子矩阵的左上角坐标和右下角坐标，输出子矩阵中所有元素的累加和。  方法一（二维前缀和） 1.解题思路  首先对矩阵进行预处理，得到对应的前缀和矩阵。 利用前缀和矩阵相应区域的加减运算，即可得到对应子矩阵中所有元素的累加和。  图解展示（图中presum[3][4]除了包括绿色部分，还包括其它重叠的部分，其它几项也一样，另外presum[1][1]被多减了一次，所以最后要加一次）：  2.代码实现 import java.util.*; public class Main { public static void main(Stri...

题意整理。  键盘输入两个字符串str和substr。 求substr在str中出现的次数。  方法一（利用find函数） 1.解题思路  首先将字符数组转化为字符串str1和str2。 从str1下标i开始查找str2，如果找得到，计数加1，并且i从找到的位置，后移一位。  动图展示：  2.代码实现 #include <iostream> #include <cstring> using namespace std; int main() { char str[100] = { 0 }; char substr[100] = { 0 }; cin.getline(s...

题意整理。  编写一个函数，比较两个字符串的大小。 前者大于后者返回1，小于返回-1，等于返回0.。  方法一（循环） 1.解题思路  通过循环逐一比较两字符串中对应位置每个字符的大小。 如果src当前字符小于dst，说明src小于dst，返回-1。如果src当前字符大于dst，说明src大于dst，返回1。如果相等，则指针后移。 如果src后面还有字符，返回1。如果dst后面还有字符，返回-1。如果都没有，返回0。  动图展示：  2.代码实现 #include <iostream> #include <cstring> using namespace std; in...

题意整理。  给定长度为n的字符串。 求"abb"型子序列的个数。  方法一（后缀和数组） 1.解题思路  首先进行预处理，得到对应的后缀和数组。 suffix[i+1][j]表示str中第i个字母之后的对应字母出现次数，所以可以在O(1)O(1)O(1)时间内，获得当前字母之后的对应字母出现次数。然后计算对应生成的"abb"型子序列的个数。  举例说明：对于字符串"abcbcc"，若当前字母为a，则可生成一个"abb"，三个"acc"，出现在a之后的b有2个，出现在a之后的c有3个，假设这个出现次数记为t，则对应新增的"abb"型子序列的个数为t∗(t−1)/2t*(t-1)/2t∗(t−1...

题意整理。  给定一个长度为n的数组。 有q次查询，每次查询给定左右边界l和r，输出下标在l、r之间的所有元素的累加和。  方法一（前缀和） 1.解题思路  首先对数组进行预处理，得到对应的前缀和数组。 利用前缀和数组r下标对应的值减去l-1下标对应的值，即可得到下标在l、r之间的所有元素的累加和。  图解展示：  2.代码实现 import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextIn...

题意整理。  给定一个数组。 将数组中所有0元素移到末尾，非0元素移到开头，同时保持非0元素相对位置不变。  方法一（双指针） 1.解题思路  定义两个指针id和i，id总是指向第一个0所在位置，i指向游标所在位置，遍历数组所有元素。 i指向元素不为0，则交换i、id位置元素，同时id指针后移。  举例说明：对应数组[1,0,3,4,0,-3]，id本来指向1，i指针开始也指向1，由于不等于0，交换i、id位置元素，由于在同一位置，所以数组相当于没有变化，id指针后移，此时id指向0，i指向0时，不作处理，i指向3时，交换i、id位置元素，数组变为[1,3,0,4,0,-3]，同时id后移一位...

题意整理。  键盘输入一个正整数n，创建大小为n的动态数组。 将数组中的元素初始化为 n、n+1、...、2n - 1，并输出数组中的元素。  方法一（指针） 1.解题思路  首先新建数组，然后给数组中的元素按要求赋值。 最后输出数组中的元素。  动图展示：  2.代码实现 #include <iostream> using namespace std; int main() { int n; cin >> n; //新建数组 int* p=new int[n]; //给数组元素赋值 for(int i=0;i<n;i++){ p[i]=n+i; } //输出数组...

题意整理。  键盘输入一个字符串以及一个正整数m。 将原字符串第m个字符开始的所有字符复制到一个新字符串，输出新字符串，要求使用指针实现。  方法一（指针） 1.解题思路  定义一个指针p指向原字符串第m个字符，指针q指向新字符串第0个字符。 从第m个元素开始，遍历原字符串。将p指针指向元素赋值给q指针，同时让p、q指针后移。  动图展示：  2.代码实现 #include <iostream> using namespace std; int main() { char str[30] = { 0 }; cin.getline(str, sizeof(str)); int m; ...

题意整理。  键盘输入一个字符串。 -获取该字符串的长度，并输出，要求使用指针实现。  方法一（指针） 1.解题思路  定义一个指针指向字符串开头。 只要指针对应元素不是'\n'，将指针后移，同时长度加1。  动图展示：  2.代码实现 #include <iostream> using namespace std; int main() { char str[100] = { 0 }; cin.getline(str, sizeof(str)); int len=0; char *p=str; //只要指针没有指向换行符位置 while(*p!='\0'){ //长度加1，指针p...

题意整理。  给定某公司按照季度和每个季度对应3个月份统计的数据。 使用二维数组保存这些数据，并计算公司年销售总额。  方法一（二维数组） 1.解题思路  使用二维数组，初始化每季度对应月份的销售额。 两层循环遍历数组中所有元素，求累加和（系统已给出这部分实现）。  动图展示：  2.代码实现 #include <iostream> using namespace std; int main() { int arr[4][3] = { //使用二维数组，初始化每季度对应月份的销售额 {22,66,44}, {77,33,88}, {25,45,65}, {11,66,99} }; ...

题意整理。  键盘随机输入6个整数，保存到数组中。 使用选择排序对数组中的元素进行排序，输出排序后的元素。  方法一（选择排序） 1.解题思路  外层循环遍历前len-1个元素，内层循环中，使用临时遍历min记录最小值所在下标，遍历当前元素后面所有元素，比较得出最小值所在下标。 每次内层循环走完，交换i、min位置元素。  动图展示：  2.代码实现 #include <iostream> using namespace std; int main() { int arr[6] = { 0 }; int len = sizeof(arr) / sizeof(int); for (i...

题意整理。  键盘随机输入6个整数，保存到数组中。 使用冒泡排序对数组中的元素进行排序，输出排序后的元素。  方法一（冒泡排序） 1.解题思路  外层循环遍历前len-1个元素，内层循环遍历当前元素后面所有元素。 如果后面元素比当前元素小，则交换位置。  动图展示：  2.代码实现 #include <iostream> using namespace std; int main() { int arr[6] = { 0 }; int len = sizeof(arr) / sizeof(int); for (int i = 0; i < len; i++) { cin &g...