Combination Sum II
問題描述
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: ? All numbers (including target) will be positive integers. ? The solution set must not contain duplicate combinations. For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:
[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]分析
采用回溯算法，注意每個值只能使用一次，并且所有記過都是唯一的。
解答
class Solution {public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); vector<vector<int>> result; vector<int> combination; combinationsum(result, combination, candidates, target, 0); return result; } void combinationsum(vector<vector<int>> &res, vector<int> &com, vector<int> &arr, int tar, int begin) { if (!tar) { res.push_back(com); return ; } for (int i = begin; i < arr.size() && tar >= arr[i]; i++) { com.push_back(arr[i]); combinationsum(res, com, arr, tar - arr[i], i+1); com.pop_back(); while (i + 1 < arr.size() && arr[i] == arr[i + 1]) i++; } }};Multiply Strings
問題描述
Given two non-negative integers num1 and num2 rePResented as strings, return the product of num1 and num2. Note:
The length of both num1 and num2 is < 110.Both num1 and num2 contains only digits 0-9.Both num1 and num2 does not contain any leading zero.You must not use any built-in BigInteger library or convert the inputs to integer directly.分析
由于字符串的長度未知，且可能超出長整型的長度，所以我們運用手動乘法的方式來解決。
解答
class Solution {public: string multiply(string num1, string num2) { string sum(num1.size() + num2.size(), '0'); for (int i = num1.size() - 1; 0 <= i; i--) { int carry = 0; for (int j = num2.size() - 1; 0 <= j; j--) { int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry; sum[i + j + 1] = tmp % 10 + '0'; carry = tmp / 10; } sum[i] += carry; } size_t startpos = sum.find_first_not_of("0"); if (string::npos != startpos) { return sum.substr(startpos); } return "0"; }};Permutations
問題描述
Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the following permutations:
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]分析
使用回溯算法設計，比較經典的題目。
解答
class Solution {public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> result; getres(result, nums, 0); return result; } void getres(vector<vector<int>> &res, vector<int> &nums, int start) { if (start >= nums.size()) { res.push_back(nums); return ; } for (int i = start; i < nums.size(); i++) { swap(nums[start], nums[i]); getres(res, nums, start + 1); swap(nums[start], nums[i]); } }};Permutations II
問題描述
Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations:
[ [1,1,2], [1,2,1], [2,1,1]]分析
和上一問題相同，需要注意數字出現重復的情況。
解答
class Solution {public: vector<vector<int> > permuteUnique(vector<int> &num) { sort(num.begin(), num.end()); vector<vector<int> >res; getres(res, num, 0, num.size()); return res; } void getres(vector<vector<int>> &res, vector<int> num, int start, int end) { if (start == end - 1) { res.push_back(num); return; } for (int k = start; k < end; k++) { if (start != k && num[start] == num[k]) continue; swap(num[start], num[k]); getres(res, num, start + 1, end); } }};
