本文主要是介绍9.18（40. 组合总和 II 43.字符串相乘），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
40. 组合总和 II
本题是上一道题最后一种解法的变形，只需要在其中天上一个条件即可
程序代码如下（可正确运行）
class Solution {
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<vector<int>> result;vector<int> res;sort(candidates.begin(), candidates.end());com(candidates, 0, target, res, result);return result;//直接返回就行了}void com(vector<int> &candidates, int index, int target, vector<int> res, vector<vector<int>> &result) {if (target == 0) {result.push_back(res);return;}else if (target < 0) return;else {for (int i = index; i < candidates.size(); i++) {res.push_back(candidates[i]);com(candidates, i + 1, target - candidates[i], res, result);res.pop_back();while (i<=candidates.size()-2&&candidates[i + 1] == candidates[i])i++;}}}
};int main() {int n,target;cin >> n>>target;vector<int> arr(n);for (int i = 0; i < n; i++) {cin >> arr[i];}Solution bb;vector<vector<int>> s = bb.combinationSum2(arr,target);for (int i = 0; i < s.size(); i++) {for (int j = 0;j< s[i].size(); j++) {cout<<s[i][j]<<" ";}cout << endl;}return 0;
}
43.字符串相乘
long long支持的十进制大约是19位，因此对于110位的数据来说只能理解成字符串。
思路一：
把数据写成vector的形式，Node是一种数据结构，里面包含factor和power分别表示系数以及对应的级数；采用的策略就是对构建的向量逐步调整。
// prictice.cpp: 定义控制台应用程序的入口点。
//#include "stdafx.h"
#include<cmath>
#include<iostream>
#include<string>
#include<cassert>
#include<vector>
#include<limits>
#include <algorithm> //引入这个之后排序才能使用
using namespace std;
//思路：类似于链表下的乘法struct Node{int factor;//表示系数int power;//表示次方
};
class Solution {
public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0")return "0";string s;vector<Node> sn1(num1.size());vector<Node> sn2(num2.size());vector<Node> result;//长度是未知的for (int i = 0; i < num1.size(); i++) {sn1[i].factor = num1[num1.size()-i-1]-'0';sn1[i].power = i;}for (int i = 0; i < num2.size(); i++) {sn2[i].factor = num2[num2.size() - i - 1]-'0';sn2[i].power = i;}//对两个字符串进行处理，即使是long long也没法存储，因此只能这样for (int i = 0; i < num1.size(); i++) {for (int j = 0; j < num2.size(); j++) {Node *p = new Node();Node *b = new Node();p->factor = sn1[i].factor*sn2[j].factor;p->power = sn1[i].power + sn2[j].power;if (p->factor / 10 > 0) {b->factor = p->factor / 10;b->power = p->power+1;p->factor = p->factor % 10;}if(result.size()==0||p->power>result[result.size() - 1].power)result.push_back(*p);else result[p->power].factor += p->factor;//可以直接使用索引delete p;//释放if (b != NULL) {if (b->power>result[result.size() - 1].power)result.push_back(*b);else result[b->power].factor += b->factor;delete b;}}//每次走完一个内部循环，就重新调整一下for (int i = 0; i < result.size() - 1; i++) {//先更改前面的if (result[i].factor >= 10) {result[i + 1].factor += result[i].factor / 10;result[i].factor %= 10;}}if (result[result.size() - 1].factor >= 10) {Node *a = new Node();a->factor = result[result.size() - 1].factor / 10;result[result.size() - 1].factor %= 10;a->power = result.size();result.push_back(*a);delete a;}}//接下来开始对result进行转化for (int i = result.size() - 1; i >= 0; i--) {s += result[i].factor+'0';}return s;}
};int main() {string num1, num2;//设置两个字符串cin >> num1 >> num2;//输入Solution bb;string s = bb.multiply(num1,num2);cout<<s<<endl;return 0;
}这篇关于9.18（40. 组合总和 II 43.字符串相乘）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
