Skip to content

Commit 957a801

Browse files
mhcoderwlmhcoderwl
committed
要提交的变更：
 新文件: 2.1.12.cpp 新文件: 2.1.13.cpp 新文件: 2.1.15.cpp 新文件: 2.1.16.cpp 新文件: 2.1.17.cpp 新文件: 2.1.18.cpp 新文件: 2.1.20.cpp 新文件: 2.1.21.cpp 新文件: 2.1.22.cpp 新文件: 2.1.23.cpp 新文件: 2.1.24.cpp 新文件: 2.1.8.cpp 新文件: 2.2.1.cpp 新文件: 2.2.10.cpp 新文件: 2.2.11.cpp 新文件: 2.2.12.cpp 新文件: 2.2.13.cpp 新文件: 2.2.14.cpp 新文件: 2.2.2.cpp 新文件: 2.2.3.cpp 新文件: 2.2.4.cpp 新文件: 2.2.5.cpp 新文件: 2.2.6.cpp
1 parent 9f25119 commit 957a801

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

79 files changed

+3009
-0
lines changed

‎2.1.12.cpp

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*找到下一个比之前打的序列*/
2+
3+
4+
#include<algorithm>
5+
#include<iostream>
6+
#include<map>
7+
#include<vector>
8+
#include<iterator>
9+
using namespace std;
10+
class Solution{
11+
public:
12+
void nextPermutation(vector<int>& nums){
13+
nextpermutation(nums.begin(),nums.end());
14+
}
15+
template<typename BidiIt>
16+
bool next_permutation(BidiIt first,BidiIt last){
17+
const auto rfirst=reverse_iterator<BidiIt>(first);
18+
const auto rlast=reverse_iterator<BidiIt>(last);
19+
auto pivot=next(rfirst);
20+
while(pivot!=rlast&&pivot>=*prev(pivot))
21+
pivot++;
22+
if(pivot==rlast){
23+
reverse(nums);
24+
return false;
25+
}
26+
swap(*pivot,*change);
27+
reverse(rfirst,pivot);
28+
return true;
29+
}
30+
};

‎2.1.13.cpp

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
/*[1,2,3,..,n]n个数,找到第k个排列.(按数值从小到大的顺序)*/
2+
3+
#include<algorithm>
4+
#include<iostream>
5+
#include<vector>
6+
#include<map>
7+
#include<iterator>
8+
using namespace std;
9+
class Solution{
10+
public:
11+
vector<int> kth_permutation(int n,int k){
12+
vector<int> result;
13+
for(int i=1;i<=n;i++)
14+
result.push_back(i);
15+
for(int j=1;j<k;j++)
16+
next_permutation(result.begin(),result.end());
17+
return result;
18+
}
19+
template<typename BidiIt>
20+
bool next_permutation(BidiIt first,BidiIt last){
21+
const auto rfirst=reverse_iterator<BidiIt>(last);
22+
const auto rlast=reverse_iterator<BidiIt>(first);
23+
auto pivot=next(rfirst);
24+
while(pivot!=rlast&&*pivot>=*prev(pivot))
25+
pivot++;
26+
if(pivot==rlast){
27+
reverse(rfirst,rlast);
28+
return false;
29+
}
30+
auto change=find_if(rfirst,pivot,bind1st(less<int>(),*pivot));
31+
swap(*pivot,*change);
32+
reverse(rfirst,pivot);
33+
return true;
34+
}
35+
};

‎2.1.15.cpp

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
/*给定一个柱状图,计算这些柱子之间的空隙的面积.柱子的宽度为1.
2+
例如:输入{0,1,0,2,1,0,1},返回2.
3+
*/
4+
5+
#include<iostream>
6+
#include<vector>
7+
#include<algorithm>
8+
using namespace std;
9+
class Solution{
10+
public:
11+
int trap(const vector<int>& elevation){
12+
const int n=elevation.size();
13+
vector<int> max_left(n,0);
14+
vector<int> max_right(n,0);
15+
for(int i=1;i<n;i++){
16+
max_left[i]=max(max_left[i-1],elevation[i-1]);
17+
max_right[n-1-i]=max(max_right[n-i],elevation[n-i]);
18+
}
19+
int sum=0;
20+
for(int i=1;i<n;i++){
21+
int height=min(max_left[i],max_right[i]);
22+
if(height>elevation[i])
23+
sum+=height-elevation[i];
24+
}
25+
return sum;
26+
}
27+
};
28+
int main(){
29+
vector<int> a={0,1,0,2,1,0,1};
30+
Solution s;
31+
cout<<s.trap(a)<<endl;
32+
}
33+

‎2.1.16.cpp

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/*给定一个n*n的矩阵,求矩阵旋转90度后的矩阵.要求原址.
2+
思路:中线折叠一次,然后对角线折叠.
3+
*/
4+
5+
#include<iostream>
6+
#include<vector>
7+
#include<algorithm>
8+
using namespace std;
9+
typedef vector<vector<int> > matrix;
10+
class Solution{
11+
public:
12+
matrix& rotation(matrix& image){
13+
int rows=image.size();
14+
int cols=image[0].size();
15+
for(int i=0;i<rows/2;i++)
16+
for(int j=0;j<cols;j++){
17+
swap(image[i][j],image[rows-1-i][j]);
18+
}
19+
for(int i=0;i<rows;i++)
20+
for(int j=i+1;j<cols;j++){
21+
swap(image[i][j],image[j][i]);
22+
}
23+
return image;
24+
}
25+
};
26+
27+
int main(){
28+
matrix a={{1,2,3},{4,5,6},{7,8,9}};
29+
Solution s;
30+
s.rotation(a);
31+
for(auto i:a){
32+
for(auto j:i)
33+
cout<<j<<",";
34+
cout<<endl;
35+
}
36+
}
37+

‎2.1.17.cpp

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#include<iostream>
2+
#include<vector>
3+
#include<algorithm>
4+
using namespace std;
5+
class Solution{
6+
public:
7+
void plus_one(vector<int>& nums){
8+
auto bits=nums.rbegin();
9+
while(bits!=nums.rend() && (*bits)==9){
10+
*bits=0;
11+
bits++;
12+
}
13+
if(bits==nums.rend()){
14+
nums.insert(bits.base(),1);
15+
}else (*bits)++;
16+
}
17+
};
18+
int main(){
19+
vector<int> a={9,9};
20+
Solution s;
21+
s.plus_one(a);
22+
for(auto num:a)
23+
cout<<num;
24+
cout<<endl;
25+
}
26+
27+

‎2.1.18.cpp

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
#include<iostream>
2+
#include<vector>
3+
#include<algorithm>
4+
using namespace std;
5+
class Solution{
6+
public:
7+
int climbstairs(int n){
8+
int s1=1,s2=2,s3=0;
9+
for(int i=2;i<n;i++){
10+
s3=s1+s2;
11+
s1=s2;
12+
s2=s3;
13+
}
14+
return s3;
15+
}
16+
};
17+
18+
int main(){
19+
Solution s;
20+
cout<<s.climbstairs(5);
21+
cout<<endl;
22+
}
23+
24+
25+

‎2.1.20.cpp

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
/*给一个矩阵,将每个值为零的元素的行和列上元素设0,最好空间复杂度O(1).
2+
* 我的想法是维护两个数组用来存放需要设为0的行和列.空间复杂度O(m+n).
3+
* O(1)需要复用第一行和第一列.*/
4+
5+
#include<iostream>
6+
#include<vector>
7+
#include<algorithm>
8+
using namespace std;
9+
class Solution{
10+
public:
11+
void setzeroes(vector<vector<int> >& matrix){
12+
int m=matrix.size();
13+
int n=matrix[0].size();
14+
bool rows_zero=false;
15+
bool cols_zero=false;
16+
for(int i=0;i<m;i++)
17+
if(matrix[i][0]==0){
18+
rows_zero=true;
19+
break;
20+
}
21+
for(int i=0;i<n;i++)
22+
if(matrix[0][i]==0){
23+
cols_zero=true;
24+
break;
25+
}
26+
for(int i=1;i<m;i++)
27+
for(int j=1;j<n;j++)
28+
if(matrix[i][j]==0){
29+
matrix[0][j]=0;
30+
matrix[i][0]=0;
31+
}
32+
for(int i=1;i<m;i++)
33+
if(matrix[i][0]==0)
34+
fill(matrix[i].begin(),matrix[i].end(),0);
35+
for(int j=1;j<n;j++)
36+
if(matrix[0][j]==0)
37+
for(int i=0;i<m;i++)
38+
matrix[i][j]=0;
39+
if(rows_zero==true)
40+
for(int i=0;i<m;i++)
41+
matrix[i][0]=0;
42+
if(cols_zero==true)
43+
fill(matrix[0].begin(),matrix[0].end(),0);
44+
}
45+
};
46+
47+
int main(){
48+
vector<vector<int> > a={{1,0,1},{2,3,4},{4,5,0}};
49+
Solution s;
50+
s.setzeroes(a);
51+
for(auto i:a){
52+
for(auto j:i)
53+
cout<<j<<" ";
54+
cout<<endl;
55+
}
56+
}
57+
58+

‎2.1.21.cpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
/*N个加油站组成一个圈,返回能走一圈的加油站序号,输入耗油数组和加油数组.
2+
* 时间复杂度O(N)*/
3+
#include<iostream>
4+
#include<vector>
5+
using namespace std;
6+
class Solution{
7+
public:
8+
int cancomplete(vector<int>& gas,vector<int>& cost,int n){
9+
int sum=0;
10+
int total=0;
11+
int index=0;
12+
for(int i=0;i<n;i++){
13+
sum+=gas[i]-cost[i];
14+
total+=gas[i]-cost[i];
15+
if(sum<0){
16+
index=i;
17+
sum=0;
18+
}
19+
}
20+
return total>=0?index:-1;
21+
}
22+
};
23+

‎2.1.22.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/*给N个孩子发糖,每个孩子都有一个比值,比值比邻居高的孩子要比那个孩子糖多,每个孩子至少一个,最少要发多少个糖*/
2+
3+
#include<iostream>
4+
#include<vector>
5+
#include<algorithm>
6+
using namespace std;
7+
//从左到右扫一遍,每个比之前大的多,然后从右到左扫一遍,保证每个比之前大的多.
8+
class Solution{
9+
public:
10+
int send_candy(vector<int>& child){
11+
size_t n=child.size();
12+
vector<int> num(n,0);
13+
for(int i=1;i<n;i++)
14+
if(child[i]>child[i-1])
15+
num[i]=num[i-1]+1;
16+
for(int i=n-2;i>=0;i--)
17+
if(child[i]>child[i+1])
18+
num[i]=max(num[i],num[i+1]+1);
19+
return accumulate(num.begin(),num.end(),n);
20+
}
21+
};
22+
23+
24+
int main(){
25+
vector<int> a={1,6,6,4,3,8,2,6,5};
26+
Solution s;
27+
cout<<s.send_candy(a)<<endl;
28+
}
29+

‎2.1.23.cpp

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
#include<iostream>
2+
#include<vector>
3+
#include<algorithm>
4+
using namespace std;
5+
class Solution{
6+
int find_single(vector<int>& nums){
7+

‎2.1.24.cpp

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/*一组整数每个数都出现三次除了莫一个数,找到这个数,要求原址,时间复杂度O(n)
2+
* 思路:每个数都出现三次,说明该数二进制每位的1的出现次数是3的整数倍,所以如果某一位的1的出现次数不为3的整数位,说明该位是那个数为1的部分.
3+
*/
4+
#include<iostream>
5+
#include<vector>
6+
#include<algorithm>
7+
using namespace std;
8+
class Solution{
9+
public:
10+
int single_number(vector<int>& nums){
11+
int bits=sizeof(int)*8;
12+
int result=0;
13+
vector<int> counts(bits,0);
14+
for(auto i:nums){
15+
for(int j=0;j<bits;j++){
16+
if((i>>j)%2!=0)
17+
counts[j]++;
18+
}
19+
}
20+
for(int i=0;i<bits;i++){
21+
if(counts[i]%3!=0)
22+
result+=(1<<i);
23+
}
24+
return result;
25+
}
26+
};
27+
int main(){
28+
Solution s;
29+
vector<int> a={3,3,3,4,5,4,4};
30+
cout<<s.single_number(a)<<endl;
31+
}

‎2.1.8.cpp

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
//给定一组数值,找到其中三个数,和为0,按顺序排列并且不能重复出现.
2+
//先排序,然后左右夹逼,时间复杂度O(n^2).
3+
#include<iostream>
4+
#include<map>
5+
#include<vector>
6+
#include<iterator>
7+
#include<algorithm>
8+
using namespace std;
9+
class solution{
10+
public:
11+
vector< vector<int> > threeSum(vector<int>& nums,int target){
12+
vector< vector<int> > result;
13+
if(nums.size()<3)return result;
14+
vector<int>::iterator last=nums.end();
15+
vector<int>::iterator first=nums.begin();
16+
for(vector<int>::iterator i=first;i<last-2;i++){
17+
vector<int>::iterator j=i+1;
18+
vector<int>::iterator k=last-1;
19+
while(j<k){
20+
if(*i+*j+*k<target){
21+
j++;
22+
//while(*j==*(j-1)&&j<k)j++;
23+
}else if(*i+*j+*k>target){
24+
k--;
25+
//while(*k==*(k+1)&&j<k)k--;
26+
}else{
27+
vector<int> list;
28+
list.push_back(*i);
29+
list.push_back(*j);
30+
list.push_back(*k);
31+
result.push_back(list);
32+
j++;
33+
k--;
34+
//while(*j==*(j-1)&&*k==*(k+1)&&j<k)j++;
35+
}
36+
}
37+
}
38+
sort(first,last);
39+
result.erase(unique(result.begin(),result.end()),result.end());
40+
return result;
41+
}
42+
};
43+
44+
45+

0 commit comments

Comments
 (0)