1.最大子序和 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素）， 返回其最大和。
using namespace std; class Solution { public:
int maxSubArray(vector<int> &nums)
{
//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
int result = INT_MIN;
int numsSize = int(nums.size());
int sum = 0;
for (int i = 0; i < numsSize; i++)
{
sum += nums[i];
result = max(result, sum);
//如果sum < 0，重新开始找子序串
if (sum < 0)//贪心算法原理，如果又小于0 的就不要了，不然不会最大。
{ sum = 0; }
}
return result;
}
};
int main() { Solution s; vector nums(6); cout<<"请输入六位数，中间空格："; for(int i=0;i<6;i++) {cin>>nums[i];} cout<<s.maxSubArray(nums )<<endl; system("pause"); return 0; }
2.买卖股票的最佳时机 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
using namespace std; class Solution { public:
int maxProfit(vector<int>& prices) {
int inf = 1e9;
int minprice = inf, maxprofit = 0;
for (int i=0;i<prices.size();i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}; int main() { Solution s; int prices[6]; for(int i=0;i<6;i++) {cin>>prices[i];} vector nums(prices, prices+6); cout<<s.maxProfit(nums )<<endl; system("pause"); return 0; } 3.The missing integer 现在有 9 个整数，这 9个整数都在 1 到 10 之间 （含 1和 10），而且每个整数只出现了一次。因此，肯定会有一个 整数缺失。现在把这个艰难的任务交给你，让你找到缺失的整数。 输入 1 行，9个在 1 到 10 之间的整数。 数据保证输入的 9个整数互不相等。 输出 先输出语句 The missing integer is: ，后面再跟上缺失的那个整数。 样例 标准输入复制文本 9 2 4 8 6 1 7 3 5 标准输出复制文本 The missing integer is:10
int n[11]; int main() { int a; for(int i=1;i<=9;i++) { scanf("%d",&a); n[a]=1; } for(int i=1;i<=10;i++) { if(!n[i]) { printf("The missing integer is:%d",i); break; } } return 0; }
4.1042 协助工作 现在需要把若干块已知边长的黑板（厚度忽略不计）搬进教室，请设计 程序判断黑板能否穿过教室的门。 输入 输入包括多组数据，每组数据包含 44 个正整数 h,w,a,b \ (1 \leq h,w,a,b \leq 20)h,w,a,b (1≤h,w,a,b≤20)，h,wh,w 分别表示表示门 的高度和宽度，a,ba,b 表示矩形黑板的两条边长。输入到文件结 束 EOF 为止。 输出如果黑板能被搬进课室，输出 Just do it. 。 否则，输出 We have a problem. 。 样例 标准输入复制文本 2 1 1 1 2 1 3 4 标准输出复制文本 Just do it. We have a problem.
using namespace std; int main(){ double h,w,a,b; while(scanf("%lf %lf %lf %lf", &h, &w, &a, &b) != EOF){ double maxlen = sqrt(hh + ww); double minbian = (a < b) ? a : b; if(minbian <= maxlen){ cout << "Just do it."; }else{ cout << "We have a problem."; } cout << endl; } }
5.题目描述： 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块 饼干。 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每 块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这 个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 示例 1： 输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。 示例 2: 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出 2.）
using namespace std;
class Solution { public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int numOfChildren = g.size(), numOfCookies = s.size();
int count = 0;
for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
while (j < numOfCookies && g[i] > s[j]) {
j++;
}
if (j < numOfCookies) {
count++;
}
}
return count;
}
};
int main() { Solution Y; vector nums1(3); vector nums2(3); for(int i=0;i<3;i++) {cin>>nums1[i];} for(int j=0;j<3;j++) {cin>>nums2[j];} cout<<Y.findContentChildren(nums1 ,nums2 )<<endl; system("pause"); return 0; }
6.题目描述： 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻 的地块上，它们会争夺水源，两者都会死去。 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表 示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ， 不能则返回 false。 示例 1： 输入：flowerbed = [1,0,0,0,1], n = 1 输出：true 示例 2: 输入：flowerbed = [1,0,0,0,1], n = 2 输出：false
using namespace std;
class Solution {
public: bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int length = flowerbed.size();
for (int i = 0; i < length; i++) {
if (flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == length-1 || flowerbed[i+1] == 0)){
n--;
//把花种上
flowerbed[i] = 1;
}
if (n <= 0){
return true;
}
}
return false;
}
}; int main() { Solution Y; vector shuzu(5); int n; for(int i=0;i<5;i++) {cin>>shuzu[i];} cin>>n; if(Y.canPlaceFlowers( shuzu , n ))
{cout<<"可以种";}
else {cout<<"不可以种";} system("pause"); return 0; }
跳过了第二组的第三第四小题，剑值offer104/100 剑指 Offer II 104. 排列的数目 题目描述： 给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。 题目数据保证答案符合 32 位整数范围。 示例 1： 输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1)、(1, 1, 2)、(1, 2, 1)、(1, 3)、(2, 1, 1)、(2, 2)、(3, 1) 请注意，顺序不同的序列被视作不同的组合。 示例 2： 输入：nums = [9], target = 3 输出：0
class Solution { public:
int combinationSum4(vector<int>& nums, int target) {
//动态规划方法
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int& num : nums) {
if (num <= i && dp[i - num] < INT_MAX - dp[i]) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
};
剑指 Offer II 100. 三角形中最小路径之和 题目描述： 给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。 示例 1： 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释： 解释：如下面简图所示：
2
3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11） class Solution { public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<vector<int>> dp = triangle;
for(int i = 1; i < dp.size(); i++){
for(int j = 0; j <= i; j++){
if(j == 0){
dp[i][j] += dp[i-1][j];
}
else if(j == i){
dp[i][j] += dp[i-1][j-1];
}
else{
if(dp[i-1][j-1] < dp[i-1][j]){
dp[i][j] += dp[i-1][j-1];
}
else{
dp[i][j] += dp[i-1][j];
}
}
}
}
int lastline = triangle.size()-1;
int r = dp[lastline][0];
for(int i = 0; i < dp.size(); i++){
if(dp[lastline][i] < r){
r = dp[lastline][i];
}
}
return r;
}
};
7.一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？
using namespace std;
class Solution { public:
int uniquePaths(int m, int n) {
long long ans = 1;
for (int x = n, y = 1; y < m; ++x, ++y) {
ans = ans * x / y;
}
return ans;
}
};
int main() { Solution Y; int m,n; cout<<"请输入m n："; cin>>m>>n; cout<<"走法有"<<Y.uniquePaths(m,n); system("pause"); return 0; }
在排序数组中查找元素的第一个和最后一个位置 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。 进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 示例 1： 输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4] class Solution { public:
int binarySearch(vector<int>& nums, int target, bool lower) {
int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
return vector<int>{leftIdx, rightIdx};
}
return vector<int>{-1, -1};
}
}; 8.将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编 程求出正整数N的所有整数分解式子。输入格式：每个输入包含一个测试用例，即正整数N (0<N≤30)。 输出格式： 按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N1={n1,n2,⋯}和N2={m1,m2,⋯}，若存在i使得n1=m1,⋯,ni=mi，但是ni+1<mi+1,则N1序列必定在N2序列之前输 出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。
using namespace std;
int a;
int b[31];
int sum=0;
int n=0;
int tag=0;
void DFS(int x);
int main()
{
scanf("%d",&a);
DFS(1);
system("pause");
return 0;
}
void DFS(int y)
{
if(sum==a)
{
printf("%d=",a);
int i;
for(i=0;i<n;i++)
{
if(i!=n-1)
{
printf("%d+",b[i]);
}
if(i==n-1)
{
printf("%d",b[i]);
}
}
tag++;
if(tag%4==0||a==b[n-1])
{
printf("\n");
}
else if(tag%4!=0&&n!=0)
{
printf(";");
}
return;
}
if(sum>a)
{
return;
}
if(sum<a)
{
int x;
for(x=y;x<=a;x++)
{
b[n++]=x;
sum+=x;
DFS(x);
sum-=x;
n--;
}
}
}
9.假设有N项物品，大小分别为s1、s2、…、si、…、sN，其中si为满足1≤si≤100的整数。要把这 些物品装入到容量为100的一批箱子（序号1-N）中。装箱方法是：对每项物品, 顺序扫描箱子，把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程，并输出每个物品所在的箱子 序号，以及放置全部物品所需的箱子数目。 输入格式： 输入第一行给出物品个数N（≤1000）；第二行给出N个正整数si（1≤si≤100，表示第i项物品的大 小）。 输出格式： 按照输入顺序输出每个物品的大小及其所在的箱子序号，每个物品占1行，最后一行输出所需的箱子数目 输入样例： 8 60 70 80 90 30 40 10 20 输出样例： 60 1 70 2 80 3 90 4 30 1 40 5 10 1 20 2 5
using namespace std; int main() {
int n;
int m = 0;
cin >> n;
int s[n][2],b[n];
for (int i = 0; i < n; i++)
{
cin >> s[i][0]; b[i] = 100;
}
for (int i = 0; i < n; i++)
{
int flag = 1, j = 0;
while (flag)
{
if (b[j] >= s[i][0])
{
flag = 0;
b[j] -= s[i][0];
s[i][1] = j + 1;
}
else
{
j++;
if (j > m) m = j;
}
}
}
for (int i = 0; i < n; i++)
{
cout << s[i][0] << " " << s[i][1] << endl;
}
cout << m + 1 << endl; return 0; }
10.Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000……个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住 了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。 输入格式 仅包含一个正整数n，其中n<=100000 输出格式 输出一行，即前n个质数的乘积模
using namespace std;
bool zs(int x) {
int i;
for(i=2;i<=sqrt((double)x);i++)
if(x%i==0)
return false;
return true;
}
int main() {
int n,i,cj=1,cnt;
cin>>n;
for(i=2,cnt=0;cnt<n;i++)
{
if(zs(i))
{
cj=(cj*i)%50000;
cnt++;
}
}
cout<<cj<<endl;
return 0;
}
11.有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。 示例 1: 输入: k = 5 输出: 9
using namespace std; class Solution{ public:
int getKthMAgicNmber(int k){
int *ans = new int[k];//申请一个k个整形变量空间，没有赋初值，并定义一个整型指针ans指向该地址空间开始处
ans[0]=1;
int p3=0,p5=0,p7=0;
for(int i=1;i<k;i++){
int t3=ans[p3]*3;
int t5=ans[p5]*5;
int t7=ans[p7]*7;
ans[i]=min(min(t3,t5),t7);
if(ans[i]==t3) p3++;
if(ans[i]==t5) p5++;
if(ans[i]==t7) p7++;
}
return ans[k-1];
}
}; int main() {
Solution y;
int z;
cout<<"请输入你要查询的位数：";
cin>>z;
cout<<"输出："<<y.getKthMAgicNmber(z);
system("pause");
return 0;
}
12.通过删除字母匹配到字典里最长单词 给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。 如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。 示例 1： Input：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] Output："apple" 示例 2： 输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea", "abpcplaaa", "abpcllllll", "abccclllpppeeaaaa"] 输出："apple" 提示： 1 <= s.length <= 1000 1 <= dictionary.length <= 1000 1 <= dictionary[i].length <= 1000
class Solution {public:
string findLongestWord(string s, vector<string>& dictionary) {
const int n = s.size();
int next[26];
fill_n(next, 26, -1);
int trans[n + 1][26];
fill_n(trans[n], 26, -1);
for (int i = n - 1;0 <= i;--i) {
next[s[i] - 'a'] = i + 1;
copy_n(next, 26, trans[i]);
}
string_view ans = "";
for (const auto& e : dictionary) {
int state = 0;
for (char c : e) {
state = trans[state][c - 'a'];
if (state == -1) break;
}
if (state == -1) continue;
if (e.size() > ans.size() || e.size() == ans.size() && e < ans)
ans = e;
}
return string(ans);
}
};
13.删除有序数组中的重复项 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 输入：nums = [1,1,2] 输出：2, nums = [1,2] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
using namespace std;
class Solution { public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
int j = 0;
for (int i = 1; i < nums.size(); i++)
if (nums[j] != nums[i]) nums[++j] = nums[i];
return ++j;
}
};
int main() {
Solution y;
int n;
cout<<"请输入你要输入的数组长度："<<endl;
cin>>n;
int *nums=new int[n];
cout<<"请输入长度为"<<n<<"的数组"<<endl;
for(int i=0;i<n;i++)
{cin>>nums[i];}
for(int j=0;j<n;j++){
cout<<nums[j];
}
vector<int> shuzu(nums,nums+n);
cout<<"计算后的数组为："<<y.removeDuplicates(shuzu);
system("pause");
return 0;
}
14.三数之和 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例 1： 输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]
class Solution { public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
15.用最少数量的箭引爆气球 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。 给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。 示例 1： 输入：points = [[10,16],[2,8],[1,6],[7,12]]输出：2解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
class Solution { public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) {
return 0;
}
sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {
return u[1] < v[1];
});
int pos = points[0][1];
int ans = 1;
for (const vector<int>& balloon: points) {
if (balloon[0] > pos) {
pos = balloon[1];
++ans;
}
}
return ans;
}
};
class Solution { public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[0] < v[0];
});
int n = intervals.size();
vector<int> f(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (intervals[j][1] <= intervals[i][0]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
return n - *max_element(f.begin(), f.end());
}
};
17.LLP 是一个从不讽刺人的品学兼优的好孩子，她最近沉迷学习化学而不能自拔。然而计算一个分子的相对分子质量使她烦不胜烦，因此她决定请你写一个程序来帮助她计算这种麻烦的事情。 已知： ① CCC 代表的碳元素的相对原子质量为 12.0112.0112.01，HHH 代表的氢元素的相对原子质量为 1.0081.0081.008，OOO 代表的氧元素的相对原子质量为 16.0016.0016.00，NNN 代表的氮元素的相对原子质量为 14.0114.0114.01。 ② 一个分子的相对分子质量等于组成这个分子的所有原子的相对原子质量的和：例如，分子式为 C6H5OHC_6H_5OHC6H5OH 的分子的相对分子质量为：12.01×6+1.008×5+16.00+1.008=94.10812.01 \times 6+1.008 \times 5+16.00+1.008=94.10812.01×6+1.008×5+16.00+1.008=94.108。 输入 输入首先是一个整数 n (1≤n≤100)n \ (1 \leq n \leq 100)n (1≤n≤100)，代表接下来有 nnn 个分子式。 接下来的 nnn 行，每行有一个字符串形式的分子式。数据保证字符串的长度不超过 909090。 在分子式中，只可能出现 C,H,O,NC,H,O,NC,H,O,N 四种字母。 在分子式中，每个代表元素的字母后面可能会出现数字，这些数字将不小于 111 且不大于 100100100。 输出 对于每组输入，在单独的一行内输出它的相对分子质量。你应当至少保留 333 位小数。 你的答案将被认定为正确当且仅当你的答案和标准答案的差值小于等于 0.0010.0010.001。 具体而言，假设你给出的答案是 aaa，标准答案是 bbb，只有 ∣a−b∣≤0.001|a-b| \leq 0.001∣a−b∣≤0.001 你的答案才算正确
int main(){
double molecularWeight(char ch);//函数声明
int n, tempn;//暂存数字
double temp, ans;//temp-暂存分子量
char str[90];//字符串
int flag = -1;//当前位是字母，flag = 1， 当前位是数字，flag = 0，初始化为-1（既不是数字也不是字母)
scanf("%d", &n);
while(n--){
tempn = 0;
temp = 0;
ans = 0;
scanf("%s", str);
int i;
for(i = 0;i < strlen(str);i++){
if(str[i] >= 'A' && str[i] <='Z'){
if(flag == 1){//当前是字母并且前一位是字母
ans = ans + temp; }else{//当前是字母并且前面是数字
temp = temp * tempn;
ans = ans + temp;
tempn = 0; }
temp = molecularWeight(str[i]);//求分子量
flag = 1;//当前位是字母，flag = 1
}else{
tempn = tempn * 10 + str[i] - '0';//求数字
flag = 0;//当前位是数字，flag = 0
}}
if(flag == 1){//最后一位是字母的话，加上当前位的分子量
temp = molecularWeight(str[i - 1]);
ans = ans + temp; }else{//最后面是数字
ans = ans + temp * tempn; }
printf("%.3lf\n", ans);
}
}double molecularWeight(char ch){double temp;if(ch == 'C'){ temp = 12.01; }else if(ch == 'H'){ temp = 1.008; }else if(ch == 'O'){ temp = 16; }else if(ch == 'N'){ temp = 14.01; }return temp; } 18.周期串 如果一个字符串可以被某个长度为 kkk 的字符串重复一次或多次得到，则称这个字符串的周期为 kkk。例如，字符串 abcabcabcabc 以 333 为周期（当然，它也以 6,126,126,12 等等为周期）。 现在请你编写一个程序，求出任一长度不超过 808080 的字符串的最小正周期。 输入 输入首先是一个整数 n (1≤T≤1000)n \ (1 \leq T \leq 1000)n (1≤T≤1000)，代表有 nnn 组数据。 每组数据占一行，是一个长度不超过 808080 的字符串，保证字符串中只有英文字母。两组相邻的输入之间有一个空行。输出每组数据在一行内输出一个整数 kkk，代表该字符串的最小正周期。两组相邻的输出之间应当有一个空行。 P.s.: 如果字符串最小正周期串是它本身，则 k=k=k= 字符串长度。
int main() {
int t;
char str[80];
scanf("%d", &t);
while(t--){
scanf("%s", &str);
int len = strlen(str);
for(int i = 1;i <= len;i++)
{//假设 i 是周期
int flag = 1;//i 是周期的话，flag = 1，不是的话 flag 为 0
if(len % i ==0){//假设 i 是周期，肯定可以被长度整除
for(int j = i;j < len;j++){
if(str[j] != str[j % i])
{flag = 0;
break; }
}
if(flag == 1)
{printf("%d\n", i);
printf("\n");
break; }
}
}
}
return 0; }
19.拼车 假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限 制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为 一个向量）。 这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息： 必须接送的乘客数量； 乘客的上车地点； 以及乘客的下车地点。 这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一 定在你的行驶方向上）。 请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有 乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请 返回 false）。 示例 1： 输入：trips = [[2,1,5],[3,3,7]], capacity = 4 输出：false 示例 2： 输入：trips = [[2,1,5],[3,3,7]], capacity = 5 输出：true 示例 3： 输入：trips = [[2,1,5],[3,5,7]], capacity = 3 输出：true 示例 4： 输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11 输出：true 提示： 你可以假设乘客会自觉遵守 “先下后上” 的良好素质 trips.length <= 1000 trips[i].length == 31 <= trips[i][0] <= 100 0 <= trips[i][1] < trips[i][2] <= 1000 1 <= capacity <= 100000 class Solution { public: bool carPooling(vector<vector>& trips, int capacity) { vector diff(1050, 0); unordered_map<int, int> mp; for (auto trip: trips) { diff[trip[1]] += trip[0]; diff[trip[2]+1] -= trip[0]; mp[trip[2]] += trip[0]; } for (int i = 0; i <= 1000; i++) { if (i != 0) { diff[i] += diff[i-1]; } if (diff[i] - mp[i] > capacity) { return false; } } return true; } };
20.二维区域和检索 - 矩阵不可变 给定一个二维矩阵 matrix，以下类型的多个请求： 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。 实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下 角 (row2, col2) 所描述的子矩阵的元素 总和 。 示例 1： 输入: ["NumMatrix","sumRegion","sumRegion","sumRegion"] [[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]] 输出: [null, 8, 11, 12] 解释: NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和) 提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 200-105 <= matrix[i][j] <= 105 0 <= row1 <= row2 < m 0 <= col1 <= col2 < n 最多调用 104 次 sumRegion 方法 class NumMatrix { public: int add[250][250]; NumMatrix(vector<vector>& matrix) { int rLen = matrix.size(), cLen = matrix[0].size(); memset(add, 0, sizeof(add)); for (int i = 1; i <= rLen; i++) { for (int j = 1; j <= cLen; j++) { add[i][j] = add[i-1][j] + add[i][j-1] + matrix[i- 1][j-1] - add[i-1][j-1]; } } } int sumRegion(int row1, int col1, int row2, int col2) { return add[row2+1][col2+1] - add[row2+1][col1] - add[row1] [col2+1] + add[row1][col1]; } };
二叉树中和为某一值的路径 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 class Solution { public:
vector<vector<int>> ret;
vector<int> path;
void dfs(TreeNode* root, int target) {
if (root == nullptr) {
return;
}
path.emplace_back(root->val);
target -= root->val;
if (root->left == nullptr && root->right == nullptr && target == 0) {
ret.emplace_back(path);
}
dfs(root->left, target);
dfs(root->right, target);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int target) {
dfs(root, target);
return ret;
}
};
21.453. 最小操作次数使数组元素相等 给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。 示例 1： 输入：nums = [1,2,3]输出：3解释： 只需要3次操作（注意每次操作会增加两个元素的值）： [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4] 示例 2： 输入：nums = [1,1,1]输出：0 class Solution { public:
int minMoves(vector<int>& nums) {
int minNum = *min_element(nums.begin(),nums.end());
int res = 0;
for (int num : nums) {
res += num - minNum;
}
return res;
}
};
22.21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4] 示例 2： 输入：l1 = [], l2 = []输出：[] 示例 3： 输入：l1 = [], l2 = [0]输出：[0]
class Solution {
public: ListNode mergeTwoLists(ListNodel1,ListNode l2){ ListNode dummy = ListNode(-1); ListNode prev =&dummy; while(l1 != nullptr && l2 != nullptr){ if(l1->val < l2->val) {prev->next = l1; l1=l1->next;} else { prev->next = l2; l2= l2->next;} prev = prev->next;} prev->next =l1== nullptr?l2:l1; return dummy.next; } };
23.炒股 小明很喜欢炒股，他记录了一段时间内一支股票股价的变化。现在小明想知道这支股票股价最高连续上升的天数。 输入分两行。 第一行：一个整数 N (1≤N≤1000)N \ (1 \leq N \leq 1000)N (1≤N≤1000)。 第二行：NNN 个用空格隔开的整数，表示连续 NNN 天的股价，1≤股价≤200001 \leq 股价 \leq 200001≤股价≤20000，保证相邻两天股价一定有变化。 输出只有一行。 输出一个整数，代表最高股价连续上升的天数。 样例 标准输入 10 15 1 2 20 5 13 2 15 9 1 标准输出 3
int main(){
int n,t,cnt=0,ans=0,pre=-1;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&t);
if(t>pre) //price is rising
{
++cnt;
ans = ans>cnt?ans:cnt; //if cnt is bigger update the answer
}
else //price drop down
{
cnt = 1; //restart cnt
}
pre = t; //update pre to continue next loop
}
printf("%d\n",ans);
return 0;
}
24.替换空格 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例 1： 输入：s = "We are happy."输出："We%20are%20happy." class Solution { public: string replaceSpace(string s) { int count = 0, len = s.size(); // 统计空格数量 for (char c : s) { if (c == ' ') count++; } // 修改 s 长度 s.resize(len + 2 * count); // 倒序遍历修改 for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) { if (s[i] != ' ') s[j] = s[i]; else { s[j - 2] = '%'; s[j - 1] = '2'; s[j] = '0'; j -= 2; } } return s; } };
25.两数之和 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
using namespace std;
class Solution { public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret(2);
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
ret[0]=i;
ret[1]=j;
}
}
}
return ret;
}
};
int main(){
Solution y;
int n=6;
vector<int> nums(6);
cout<<"请输入你要输入的六位数，用空格隔开:"<<endl;
for(int i=0;i<6;i++)
{cin>>nums[i];}
int target;
cout<<"请输入你的目标值："<<endl;
cin>>target;
cout<<"得到：["<<y.twoSum(nums,target)[0]<<","<<y.twoSum(nums,target)[1]<<"]"<<endl;
system("pause"); }