1、随机数
#include<time.h>
srand((int)time(0));
rand()%x;
2、数值题
A：Single Number 类：
题型1）给一个数组，里面有两个元素只出现了一次，而其他所有元素都出现了两次，找到这两个元素，这个主要用位的方法：
vector<int> singleNumber(vector<int>& nums) {
// 首先所有的元素进行异或，将会得到这两个数的异或值
int num=nums[0];
for(int i=1;i<nums.size();i++){
num=num^nums[i];
}
// 找到异或得到的元素的最后一个1对应的值
int rest = num&(~num+1);
int left=0,right=0;
for(int i=0;i<nums.size();i++){
if((nums[i]&rest)==rest) left=left^nums[i];
else if((nums[i]&rest)==0) right=right^nums[i];
}
return vector<int>{left,right};
}
B：Count Numbers with Unique Digits ：
Given a non-negative integer n, count all numbers with uniques digits, x, where 0 ≤ x < 10^n.
这个题说的是给你一个n，指代n位的整数，求整数中，所有数字只出现一次的整数的数目。
我在想，这个地方是不是应该反过来查：
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(n == 0) return 1;
int count = 9, ret = 9;
// In each iteration, try adding 0 - 9 to the end of number
for(int i = 2; i <= n; ++i) {
// Advoid repeating digits. f(k) = f(k - 1) * (10 - k - 1)
count *= 11 - i;
ret += count;
}
// Add 0
return ret + 1;
}
};
C：Integer Break
（如果可以，还是有时间补补数学原理）
这个题是说给一个整数n，然后将它分裂成至少N个正整数(N>2)，然后将这N个正整数乘起来，返回正整数积最大的值。
这里，数学原因我不知道，但是我只知道最多只能有2个2，也就是说5以下，尽可能考虑2,；5以上，尽可能考虑3，如果余数为1，变为2*2；
class Solution {
public:
int integerBreak(int n) {
// 这里，数学原因我不知道，但是我只知道最多只能有2个2，也就是说5以下，尽可能考虑2,；5以上，尽可能考虑3，如果余数为1，变为2*2；
if(n==1||n==2) return 1;
if(n<5) return 2*(n-2);
else{
if(n%3==1){
int res = 4;
res = res * pow(3,(n-4)/3);
return res;
}else if(n%3==2){
return 2*pow(3,(n-2)/3);
}else{
return pow(3,n/3);
}
}
}
};
D：Divide Two Integers
（在不用乘、除和取模操作的情况下，进行除法，如果溢出，返回INT_MAX）
（可以用加减和左移右移运算符）
首先考虑单例的情况，divisor 为 0 的时候，返回 INT_MAX，而 dividend 为 0 的时候，返回 0，而 divisor 为 1 的时候，返回 dividend。
【abs() 主要用于对求整数的绝对值，在 "stdlib.h" 头文件里】
【fabs() 主要是求精度要求更高的 double，float 型的绝对值，在 <cmath> 头文件里】
【exp 主要就是计算 e 的多少次方】
【默认 log() 是取自然对数为底 即 ln】
【直接用换底公式 写个简单的表达式就完成了 例如: log2 x 写成 log(x)/log(2)】
double x1 = log(fabs(dividend));
double x2 = log(fabs(divisor));
long long res = double(exp(x1-x2));
class Solution {
public:
int divide(int dividend, int divisor) {
if(dividend==0) return 0;
else if (divisor==0&& dividend>0) return INT_MAX;
else if (divisor==0&& dividend<0) return INT_MIN;
else if (divisor==1) return dividend;
double x1 = log(fabs(dividend));
double x2 = log(fabs(divisor));
double res = exp(x1-x2);
bool ne = (dividend>0)^(divisor>0);
if(ne==false){
if(res<INT_MAX) return res;
else return INT_MAX;
}else if(ne==true){
if(-res>INT_MIN) return -res;
else return INT_MIN;
}
return 0;
}
};
E：Fraction to Recurring Decimal
[ 给两个数，分别代表分子和分母，然后，以字符串的形式返回分数的小数形式 ]
[ 如果分数部分是循环的，用括号的形式将重复的部分关起来 ]
举例：
Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".
（我原来的方法是把小数部分转换为字符串保存下来，然后再进行查找，重点在于这个查找方式）
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
// 分别判断分子分母是否为0，
if(numerator==0) return "0"; // 分子为0，那么直接返回 0
if(denominator==0) return ""; // 分母为0，那么直接返回 ""
string res="";
unordered_map<long,int> map;
if((numerator>0)^(denominator>0)) res+='-'; // 根据正负进行符号判别
long num1 = abs((long)numerator/(long)denominator);
res= res+ to_string(num1);
long num2 = abs((long)numerator%(long)denominator);
if(num2==0) return res; // 如果没有小数，那么就直接返回。
res = res +"."; // 在有小数的情况下，加上点。
// ---------------------------------------------------------------
while(num2){ // 这里对应的是余数
map[num2] = res.size();
num2=num2*10;
num1 = abs((long)num2 / (long)denominator);
res= res+ to_string(num1);
num2 = abs((long)num2 % (long)denominator);
if(map.find(num2)!=map.end()){
res.insert(map[num2],"(");
res = res+")";
break;
}
}
return res;
}
};
F：Maximal Square
// ------------------------用状态矩阵-------------------------
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size()==0) return 0;
int row_num = matrix.size();
int col_num = matrix[0].size();
int max_value=0;
// 构建一个状态矩阵
vector<int> record(col_num,0);
// 初始化状态矩阵
for(int i=0;i<col_num;i++) {
record[i]=matrix[0][i]=='0'?0:1;
max_value=max(max_value,matrix[0][i]-'0'); // 找到最大值
};
// 调整状态矩阵
for(int i=1;i<row_num;i++){
int tmp =record[0];
record[0]= matrix[i][0]-'0';
for(int j=1;j<col_num;j++){
int mmm = record[j];
if(matrix[i][j]=='1'){
record[j]=min(min(record[j],record[j-1]),tmp)+1; // 就是斜对角、左边、上边三个数的最小值。
max_value=max(max_value,record[j]);
}else record[j]=0;
tmp=mmm;
}
}
return max_value*max_value;
}
};
// 用真正的矩阵
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int row_num = matrix.size();
if(row_num==0) return 0;
int col_num = matrix[0].size();
int sum=0;
for(int i=0;i<col_num;i++){
int num = matrix[0][i]-'0';
sum = sum>num?sum:num;
}
for(int j=0;j<row_num;j++){
int num = matrix[j][0]-'0';
sum = sum>num?sum:num;
}
for(int i=1;i<row_num;i++)
for(int j=1;j<col_num;j++){
if(matrix[i][j]=='1'){
int num = min(min(matrix[i-1][j]-'0',matrix[i][j-1]-'0'),matrix[i-1][j-1]-'0')+1;
matrix[i][j] = num +'0';
sum = sum>num?sum:num;
}
}
return sum*sum;
}
};
3、链表类题
A：Linked List Random Node（随机数题目）
Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
B：Reverse Linked List ii（链表逆转）
(Reverse a linked list from position m to n. Do it in-place and in one-pass)
For example:
Given 1->2->3->4->5->NULL, m=2 and n=4
return 1->4->3->2->5->NULL.
ListNode* reverseBetween(ListNode* head, int m, int n) {
int count=0;
ListNode* left = new ListNode(-1); //我还是需要养成一个好习惯，建立一个新的节点
left->next = head;
for(;count<m-1;count++) left=left->next;
ListNode* cur = left->next, * back_up = left->next;
// left 为逆转链表前的那个节点，back_up 为逆转链表的最后一个节点。
// 这个是链表的逆转，逆转完了后，cur 为逆转完毕后的链表的下一个节点，before 为逆转之后的头节点。
ListNode* next=nullptr,*before=nullptr;
for(;count<n;count++){
next = cur->next;
cur->next = before;
before=cur;
cur=next;
}
left->next = before; back_up->next = cur;
return m==1?before:head;
}
C：Remove Duplicates from Sorted List ii
(给一个已排序的链表，删除所有有重复数字的节点，留下只出现过一次的数字的节点）
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// 如果一旦需要删除掉一个链表的节点，必须重新设定节点。
if(!head) return nullptr; // 节点不存在
// 声明一个头节点，并设头节点的指针。
ListNode begin(1);
ListNode* start = &begin;
// 进入循环体。
while(1){
if(head&&head->next&&head->val==head->next->val){
while(head&&head->next&&head->val==head->next->val) head = head->next;
if(!head->next) return begin.next;
else head=head->next;
}else if(!head->next){ // 只有一个节点
start->next = head;
start=start->next;
start->next =nullptr;
return begin.next;
}else if(head->next){ // 有连续两个节点，但是两个节点的值不相等。
start->next = head;
start= start->next;
head = head->next;
start->next =nullptr;
}
}
return begin.next;
}
};
4、数组题
A、Product of Array Except Self
（这个轮子比较重要，因为，直接抽象为入口是一个数组，返回的数组中每一个元素是其他元素的乘积，但是不能用除法）
For example, given [1,2,3,4], return [24,12,8,6].
虽然要求是用常数的空间复杂度，其实这里也不会那么苛刻，可以用一个满足返回值需求的数组
vector<int> productExceptSelf(vector<int>& nums){
int size = nums.size();
vector<int> vec(size,1);
// 每个数左边的乘积都有了。
for(int i=1;i<size;i++) vec[i]=nums[i-1]*vec[i-1];
// 接着计算右边的乘积。
int right = nums[size-1];
for(int i=size-2;i>=0;i--){
vec[i] = vec[i]*right;
right=right*nums[i];
}
return vec;
}
Shuffle an Array
[ 将数组进行漂移，返回数组任何一个可能的排列，这个叫做数组的漂移 ]
( 可见，现在的一个出题的趋势，就是走随机数，通过一定程度上的模拟随机）
STL中的函数random_shuffle()用来对一个元素序列进行重新排序（随机的）
ps：这个函数不仅可以用于 vector，还可以用于 数组：
template<class RandomAccessIterator>
void random_shuffle(
RandomAccessIterator _First, //指向序列首元素的迭代器
RandomAccessIterator _Last //指向序列最后一个元素的下一个位置的迭代器
);
C、对数组进行全排列【特别重要】
（这个部分非常重要，因为全排列的方式有很多种，需要找到最有效率的方式）
注意1：在进行交换之前，先进行全排列。这样方便过滤掉重复的数字。
注意2：将结果集放在最外面，方便随时调用。
注意3：设置数组的交换标志位。
class Solution {
private:
vector<vector<int>> res; // 将结果集放在最外面，方便随时调用
public:
void help(vector<int>& nums,int left){ // 在形参中设置交换的标志位
if(left==nums.size()){
res.push_back(nums);
return;
}
for(int i=left;i<nums.size();i++){
if(i!=left&&nums[i]==nums[left]) continue; // 跳过重复的值
swap(nums[i],nums[left]);
help(nums,left+1);
}
// 下面这个部分最为重要，因为需要逐步恢复标准的次序。
int temp_last = nums[left];
for (int i = left + 1; i < nums.size(); i++) {
nums[i-1] = nums[i];
}
nums[nums.size()-1] = temp_last;
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
if(nums.size()==0) return res;
sort(nums.begin(),nums.end()); // 在进行交换之前，先进行全排列，这样方便过滤掉重复的数字
help(nums,0);
return res;
}
};
D、Top K Frequent Elements（这个题目特别重要）
（返回元素频率排到前K个的元素）
这里的时间复杂度最快的是用到了O(n)，因为不管是在unordered_map的统计过程中，还是在拟快排找top k 的过程中，时间复杂度都只是O(n)
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
if(k==nums.size()) return nums;
// 算法复杂度小于O(nlogn) 也就意味着不能用排序，但其实排序也没什么用。
unordered_map<int,int> record;
for(int i=0;i<nums.size();i++) record[nums[i]]++;
// 用 pair对将统计数据反向存起来
vector<pair<int,int>> vec;
for(auto p: record) vec.push_back(make_pair(p.second,p.first));
if(k==vec.size()){
vector<int> res;
for(int i=0;i<k;i++){
res.push_back(vec[i].second);
}
return res;
}
// 确定最合适的位置
int other = vec.size()-k; // left的下标一定得是在other这个位置
// 用拟快排的思路去找 top k
int left=0,right = vec.size()-1;
while(1){
int left_ori = left, right_ori = right;
int mid = left+(right-left)/2;
swap(vec[mid],vec[left]);
pair<int,int> mid_value = vec[left];
while(left<right){
while(left<right && vec[right].first>=mid_value.first) right--;
if(left<right) vec[left] = vec[right];
while(left<right && vec[left].first<=mid_value.first) left++;
if(left<right) vec[right] = vec[left];
}
vec[left] = mid_value;
if(left==other){
vector<int> res;
for(int i=left;i<vec.size();i++){
res.push_back(vec[i].second);
}
return res;
}
// 这个地方最容易出问题。
if(left<other){
left = left+1;
right = right_ori;
}
if(left>other){
left = left_ori;
right = right-1;
}
}
}
};
另附1：STL 方法：
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) {
++freq[num];
}
vector<pair<int, int>> pa;
for (auto p : freq) {
pa.push_back(make_pair(-p.second, p.first));
}
nth_element(pa.begin(), pa.begin() + k, pa.end()); // 其实在nth_element中用的也是拟快排
vector<int> res;
for (int i = 0; i != k; ++i) {
res.push_back(pa[i].second);
}
return res;
}
};
Tip：STL中的nth_element()方法的使用 通过调用nth_element(start, start+n, end) 方法可以使第n大元素处于第n位置（从0开始,其位置是下标为 n的元素），并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后，但不能保证他们是有序的
另附2：STL 大顶堆的方法：
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k)
{
vector<int> v;
unordered_map<int, int> count_map;
for(auto n: nums) count_map[n]++;
priority_queue<pair<int, int>> maxHeap;
for(auto& pair: count_map) maxHeap.emplace(pair.second, pair.first);
while(k--)
{
v.push_back(maxHeap.top().second);
maxHeap.pop();
}
return v;
}
};
标准做法：
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k)
{
vector<int> v;
unordered_map<int, int> count_map;
for(auto n: nums) count_map[n]++;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> minHeap;
for(auto& pair: count_map)
{
minHeap.emplace(pair.second, pair.first);
if(minHeap.size() > k) minHeap.pop();
}
while(k--)
{
v.push_back(minHeap.top().second);
minHeap.pop();
}
return v;
}
};
链接：https://discuss.leetcode.com/topic/54560/five-efficient-solutions-in-c-well-explained
E：Missing Number:
（这个题之所以拿出来，是因为需要做原地归位交换）
class Solution {
public:
int missingNumber(vector<int>& nums) {
// 这一轮走完，一定能把合适的数放在合适的位置，不合适的数，放在空缺的位置上。
for(int i=0;i<nums.size();){
if(nums[i]!=i&&nums[i]<nums.size()) swap(nums[nums[i]],nums[i]);
else i++;
}
// 找到空缺位置上的数，也就是缺失的数
for(int i=0;i<nums.size();i++){
if(nums[i]>=nums.size()) return i;
}
// 如果都没有缺失，那么缺失的就是下一个数。
return nums.size();
}
};
F：Maximum Product of Word Lengths
（这里面用到了字符压缩，通过对字符串进行预处理，来判别两个字符串中有没有共同的字母）。方法是按位进行处理）：
class Solution {
public:
int maxProduct(vector<string>& words) {
int max_length=0;
vector<pair<string,int>> vec;
// 大小是绝对够的，所以用按位或的方式。
for(int i=0;i<words.size();i++){
int tmp =0;
for(auto c:words[i]){
int num = 2<<(c-'a');
tmp = (tmp|num);
}
vec.push_back(make_pair(words[i],tmp));
}
for(int i=0;i<vec.size();i++){
for(int j=i+1;j<vec.size();j++)
if(!(vec[i].second&vec[j].second)){
int length = vec[i].first.size()*vec[j].first.size();
max_length = max_length>length?max_length:length;
}
}
return max_length;
}
};
G：Kth Largest Element in an Array（在一个无序数组中，找到排序情况下第k大的元素）[这个轮子比较重要]
int findKthLargest(vector<int>& nums, int k) {
// 如果是第K大，那么肯定是在排好序的第K个下标位置，所以：k = nums.size()-k;
// ==================================
// 这个轮子就是如何用拟快排进行排序的，STL方法
k=nums.size()-k;
nth_element(nums.begin(),nums.begin()+k,nums.end());
return nums[k];
// ==================================
priority_queue 堆排的效率要低很多
priority_queue<int> p;
for(int i=0;i<nums.size();i++) p.push(nums[i]);
for(int i=0;i<k-1;i++) p.pop();
return p.top();'
// ==================================
// 自己造轮子,实现一个nth_element();
k=nums.size()-k;
int left=0,right=nums.size()-1;
int mid = left+(right-left)/2;
int mid_value = nums[mid];
swap(nums[mid],nums[left]);
while(1){
int mid = left+(right-left)/2;
int mid_value = nums[mid];
swap(nums[mid],nums[left]);
int left_ori=left,right_ori=right;
while(left<right){
while(left<right&&nums[right]>=mid_value) right--;
if(left<right) nums[left] = nums[right];
while(left<right&&nums[left]<=mid_value) left++;
if(left<right) nums[right] = nums[left];
}
nums[left]=mid_value;
if(left==k) return nums[left];
else if(left<k){
left=left+1;
right =right_ori;
}else if(left>k){
right =right-1;
left = left_ori;
}
}
return 0;
}
Tip：
priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现，也算是堆的另外一种形式。
优先队列是队列的一种，不过它可以按照自定义的一种方式（数据的优先级）来对队列中的数据进行动态的排序，每次的 push 和 pop 操作，队列都会动态的调整，以达到我们预期的方式来存储。
例如：我们常用的操作就是对数据排序，优先队列默认的是数据大的优先级高，所以我们无论按照什么顺序 push 一堆数，最终在队列里总是 top 出最大的元素。
priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数: priority_queue<Type, Container, Functional>
其中 Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。
Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list.
STL 里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话，
优先队列就是大顶堆，队头元素最大。
用法：示例：将元素5，3，2，4，6依次push到优先队列中，print其输出。
-
标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。（大顶堆）
priority_queue<int> pq; -
数据越小，优先级越高（小顶堆）
priority_queue<int, vector<int>, greater<int> >pq;
http://www.cnblogs.com/flyoung2008/articles/2136485.html
H：Rotate Image(nn；nm)**
[ 给你一个 n*n 的矩阵，将它顺时针旋转90度；]
感觉就是，只有n*n的矩阵，可以在原地进行旋转，但是n*m的矩阵，则必须用另一个矩阵进行置换。
void rotate(vector<vector<int>>& matrix) {
int num = matrix.size();
//方法就是先沿着中心线进行对折再沿着反水平线进行对折
for(int i=0;i<num;i++) for(int j=0;j<num/2;j++) swap(matrix[i][j],matrix[i][num-j-1]);
for(int i=0;i<num;i++) for(int j=0;j<num-i;j++) swap(matrix[i][j],matrix[num-1-j][num-1-i]);
}
[ 给你一个 n*m 的矩阵，将它顺时针旋转90度；]
----------------------------------------------------
m*n 的矩阵顺时针旋转90度
int b[3][4];
int m=4,n=3; // a 为4*3的原数据矩阵
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
b[j][n-1-i]=a[i][j];
}
}
m*n 的矩阵逆时针旋转90度
int b[3][4];
int m=4,n=3;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
b[m-1-j][j]=a[i][j];
}
}
m*n 的矩阵旋转180度
int b[4][3];
int m=3,n=4;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
b[n-i-1][m-j-1]=a[i][j];
}
}
I 蛇形矩阵（考了若干次，还是需要再写一遍），这里有两种蛇形矩阵，一种是正方形，一种是长方形
A)：正方形蛇形：
vector<vector<int>> generateMatrix(int n) {
// 腾讯笔试的时候，是要求按蛇形矩阵的形式进行输出，但是你要输出，也一定要先构建出这样一个对应的矩阵
vector<vector<int>> vec(n,vector<int>(n));
// 定义蛇形矩阵的层数
int level =1;
// 按圈顺时针对矩阵进行赋值
int count =1;
while(level<=n/2){
// 从level-1 到 n-1-level 水平
for(int i=level-1;i<n-level;i++){
vec[level-1][i]=count;
count++;
}
// 从level-1 到 n-1-level 竖直
for(int i=level-1;i<n-level;i++){
vec[i][n-level]=count;
count++;
}
// 从n-level 到 level 逆向水平
for(int i=n-level;i>level-1;i--){
vec[n-level][i]=count;
count++;
}
// 从n-level 到 level 逆向竖直
for(int i=n-level;i>level-1;i--){
vec[i][level-1]=count;
count++;
}
level++;
}
// 如果是奇数，则填补中间的那个数
if(n%2==1) vec[level-1][level-1]=count;
return vec;
}
B)：长方形蛇形（长方形受限于边短的那个长度，轮转完了后，需要对 第count 行（如果行数 m 大于列数）的 [count,m-count-1] 或者对第 count 列（如果列数 n 大于行数）的 [count,n-count-1] 进行填充。
J Permutations
（给一个数组，返回它的全排列：方法，深搜+回溯）
class Solution {
public:
vector<vector<int>> res;
int size=0;
void help(vector<int>& nums, vector<int>& vec, int n,int k){
if(k==nums.size()){
res.push_back(vec);
return;
}
for(int i=0;i<nums.size();i++){
if(find(vec.begin(),vec.end(),nums[i])==vec.end()){
vec.push_back(nums[i]);
help(nums,vec,size,k+1);
vec.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
if(nums.size()==1){
res.push_back(nums);
return res;
}
// 两种方法吧，第一种是用深搜，第二种是用交换，但是交换和深搜本身差别不大，所以统一用深搜。
vector<int> tmp;
size = nums.size();
for(int i=0;i<nums.size();i++){
tmp.push_back(nums[i]);
help(nums,tmp,size,1);
tmp.pop_back();
}
return res;
}
};
K：Remove Duplicates from Sorted Array II
(从排序数组中，移除出现超过3次的数字，并返回符合要求的数组的长度）
不管是出现几次，left 一定得是最直接的判断方式，不能和 left-2 对应的数字相同。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
//总而言之，只要不出现，nums[i]==nums[i-2]的情况就是符合要求的
int lens = nums.size();
if(lens<3) return lens;
int left=2;
for(int i=2;i<lens;i++){
if(nums[i]!=nums[left-2]){
nums[left]=nums[i];
left++;
}
}
return left;
}
};
L：3Sum Closest[方法很重要]
(给一个n个整数的数组，在里面找3个数，使得3个数的和最靠近所给的目标值。返回这三个数的和)
// 需要先读懂题，也就是说，这里并没有说，需要连续的三个数
// 三个数的动态变化时，先固定一个，然后另外两个进行左右夹逼
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
// 实现排序
sort(nums.begin(), nums.end());
int res=nums[0]+nums[1]+nums[nums.size()-1]-target; // 这是一个参考值
// 下面是实现夹逼的方法
for (unsigned int i=0; i<nums.size(); i++) {
int l = i+1, r = nums.size()-1;
while (l<r) {
int s = (nums[i]+nums[l]+nums[r])-target;
if (s>0){ // 当s 大于0 时，得向0靠拢
if(abs(res)>s) res=s;
r--;
}
else if (s<0){ // 当s 小于0 时，得向0靠拢
if(abs(res)>abs(s)) res=s;
l++;
}
else {//0 和 -1 或者 1 都会到这里来
if(s==0) return target;
}
}
}
return target+res;
}
};
M Combination Sum ii
[给一个候选的数字集合C和一个目标值，找到C中所有的唯一组合，使得组合的数字和为T]
[C中的每一个数字都只能被用一次]
[其实这个题目更难一点，因为不知道有多少种可能]
class Solution {
private:
vector<vector<int>> res;
public:
void help(vector<int>& candidates,vector<int>& vec, int target, int left,int sum){
if(sum==target){
res.push_back(vec);
return;
}
for(int i=left;i<candidates.size();i++){
if(sum+candidates[i]>target) return;
int sign=0;
// 顺序执行的时候，已经将同样字符的情况考虑到了， 就不需要再提前再考虑了。
for(int j=left;j<i;j++){
if(candidates[j]==candidates[i]){
sign=1;
break;
}
}
// 如果没问题就直接运行
if(sign==0){
vec.push_back(candidates[i]);
help(candidates,vec,target, i+1, sum+candidates[i]);
vec.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
if(candidates.size()==0) return res;
vector<int> vec;
sort(candidates.begin(),candidates.end());
help(candidates,vec,target, 0, 0);
return res;
}
};
网友评论