Skip to content

Commit 8464eff

Browse files
mhcoderwlmhcoderwl
committed
2017.05.07
1 parent 27a32ea commit 8464eff

File tree

17 files changed

+463
-0
lines changed

17 files changed

+463
-0
lines changed

‎10.10.cpp

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
//

‎10.11.cpp

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
//给一个2维字母表,给定一个单词返回在表中是否能找到//
2+
//例如:ABCE
3+
// SFCS
4+
// ADEE
5+
// word="ABCCED" return true.
6+
#include<iostream>
7+
#include<string>
8+
#include<algorithm>
9+
using namespace std;
10+
class Solution{
11+
public:
12+
bool exist_word(vector<vector<char>> &board,const string& target){
13+
const int N=board.size();
14+
const int M=board[0].size();
15+
vector<vector<bool>> visited(N,vector<bool>(M,false));
16+
for(int i=0;i<N;i++)
17+
for(int j=0;j<M;j++)
18+
if(dfs(board,i,j,target,0,visited))
19+
return true;
20+
return false;
21+
}
22+
23+
bool dfs(vector<vector<char>>& board,int i,int j,const string& target,int step,vector<vector<bool>>& visited){
24+
if(step==target.length())
25+
return true;
26+
if(visited[i][j]==true)
27+
return false;
28+
if(i<0||j<0||i>=board.size()||j>=board[0].size())
29+
return false;
30+
if(board[i][j]!=target[step])
31+
return false;
32+
visited[i][j]=true;
33+
bool result=dfs(board,i+1,j,target,step+1,visited)||
34+
dfs(board,i,j+1,target,step+1,visited)||
35+
dfs(board,i,j-1,target,step+1,visited)||
36+
dfs(board,i-1,j,target,step+1,visited);
37+
visited[i][j]=false;
38+
return result;
39+
}
40+
};
41+
int main(){}
42+
43+

‎10.2.cpp

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,4 +16,36 @@ class Solution1{
1616
//深搜,加备忘录可以加速
1717
class Solution2{
1818
int uniquePaths(int m,int n){
19+
vector<vector<int>> buffer(m,vector<int>(n,0));
20+
buffer[0][0]=1;
21+
return dfs(m-1,n-1,buffer);
22+
}
23+
int dfs(int x,int y,vector<vector<int>>& buffer){
24+
if(x<0||y<0)return 0;
25+
if(buffer[x][y]>0){
26+
return buffer[x][y];
27+
}else {
28+
return buffer[x][y]=(dfs(x-1,y,buffer)+dfs(x,y-1,buffer));
29+
}
30+
}
31+
};
32+
//DP
33+
class Solution3{
34+
public:
35+
int uniquePaths(int m,int n){
36+
vector<vector<int>> result(m+1,vector<int>(n+1,0));
37+
for(int i=1;i<m+1;i++)
38+
for(int j=1;j<n+1;j++){
39+
if(j==1&&i==1)
40+
result[i][j]=1;
41+
else
42+
result[i][j]=result[i-1][j]+result[i][j-1];
1943

44+
}
45+
return result[m][n];
46+
}
47+
};
48+
int main(){
49+
Solution3 s;
50+
cout<<s.uniquePaths(2,2)<<endl;
51+
}

‎10.3.cpp

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
//给一个二维数组,从左上角到右下有多少种走法,中间为1的为路障不能走//
2+
#include<iostream>
3+
#include<vector>
4+
#include<algorithm>
5+
using namespace std;
6+
//DP
7+
class Solution{
8+
public:
9+
int uniquePaths(vector<vector<int>> obstacle){
10+
const int m=obstacle.size();
11+
const int n=obstacle[0].size();
12+
vector<vector<int>> result(m+1,vector<int>(n+1,0));
13+
for(int i=1;i<m+1;i++)
14+
for(int j=1;j<n+1;j++){
15+
if(obstacle[i-1][j-1]==1){
16+
result[i][j]=0;
17+
}else if(j==1&&i==1)
18+
result[i][j]=1;
19+
else
20+
result[i][j]=result[i-1][j]+result[i][j-1];
21+
}
22+
return result[m][n];
23+
}
24+
};
25+
26+
int main(){
27+
Solution s;
28+
vector<vector<int>> result(3,vector<int>(3,0));
29+
result[1][1]=1;
30+
cout<<s.uniquePaths(result)<<endl;
31+
}
32+

‎10.6.cpp

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
//给一个字符串包含若干数字,返回所有有效的IP组合,例如:"25525511135"返回"255.255.11.135""255.255.111.35"
2+
#include<iostream>
3+
#include<vector>
4+
#include<string>
5+
using namespace std;
6+
class Solution{
7+
vector<string> ValidIP(const string& s){
8+
vector<string>result;
9+
vector<string>cur;
10+
dfs(s,result,cur,0);
11+
return result;
12+
}
13+
14+
void dfs(string s,vector<string>& result,vector<string> &cur,int start){
15+
if(start==s.size()){
16+
result.push_back(cur[0]+"."+cur[1]+"."+cur[2]+"."+cur[3]+".");
17+
return;
18+
}
19+
if((4-cur.size())*3<(s.size()-start))
20+
return;
21+
if((4-cur.size())>(s.size()-start))
22+
return;
23+
int num=0;
24+
for(int i=0;i<3;i++){
25+
num=num*10+(s[i+start]-'0');
26+
if(num<0||num>255)continue;
27+
cur.push_back(s.substr(start,i+1));
28+
dfs(s,result,cur,start+i+1);
29+
cur.pop_back();
30+
if(num==0)break;
31+
}
32+
}
33+
};
34+
35+
int main(){}

‎10.7.cpp

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
//给一组数和一个目标数,找到所有组合(可重复使用)加起来等于目标数
2+
#include<iostream>
3+
#include<vector>
4+
#include<algorithm>
5+
using namespace std;
6+
class Solution{
7+
public:
8+
vector<vector<int>> cominationSum(vector<int> nums,int target){
9+
sort(nums.begin(),nums.end());
10+
vector<vector<int>> result;
11+
vector<int>cur;
12+
//dfs(nums,result,cur,0,0,target);
13+
dfs(nums,cur,result,target,0);
14+
return result;
15+
}
16+
17+
void dfs(vector<int> &nums,vector<vector<int>> &result,vector<int> &cur,int step,int sum,int target){
18+
if(sum==target){
19+
result.push_back(cur);
20+
return;
21+
}
22+
if(step==nums.size()||sum>target)
23+
return;
24+
dfs(nums,result,cur,step+1,sum,target);
25+
int count=0;
26+
while(sum<target){
27+
cur.push_back(nums[step]);
28+
sum+=nums[step];
29+
dfs(nums,result,cur,step+1,sum,target);
30+
count++;
31+
}
32+
for(;count>0;count--)
33+
cur.pop_back();
34+
}
35+
void dfs(vector<int>& nums,vector<int>& path,vector<vector<int>>& result,int gap,int start){
36+
if(gap==0){
37+
result.push_back(path);
38+
return;
39+
}
40+
int previous=-1;
41+
for(int i=start;i<nums.size();i++){
42+
if(previous==nums[i])continue;
43+
44+
if(gap<nums[i])return;
45+
previous=nums[i];
46+
path.push_back(nums[i]);
47+
dfs(nums,path,result,gap-nums[i],i+1);
48+
path.pop_back();
49+
}
50+
}
51+
};
52+
int main(){
53+
Solution s;
54+
vector<int> nums={10,1,2,7,6,1,5};
55+
int target=8;
56+
auto result=s.cominationSum(nums,target);
57+
for(auto i:result){
58+
for(auto j:i)
59+
cout<<j<<' ';
60+
cout<<endl;
61+
}
62+
}
63+

‎10.9.cpp

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
//给n对括号,组成有效括号串
2+
//例如:n=2,返回"()()""(())"
3+
#include<iostream>
4+
#include<string>
5+
#include<algorithm>
6+
using namespace std;
7+
class Solution{
8+
public:
9+
vector<string> generateParenthesis(int n){
10+
vector<string> result;
11+
string cur;
12+
dfs(result,cur,n,n);
13+
return result;
14+
}
15+
16+
void dfs(vector<string>& result,string& cur,int left_gap,int right_gap){
17+
if(left_gap>right_gap||left_gap<0||right_gap<0)
18+
return;
19+
if(left_gap==0){
20+
string s(cur);
21+
result.push_back(s.append(right_gap,')'));
22+
return;
23+
}
24+
cur.push_back('(');
25+
dfs(result,cur,left_gap-1,right_gap);
26+
cur.pop_back();
27+
cur.push_back(')');
28+
dfs(result,cur,left_gap,right_gap-1);
29+
cur.pop_back();
30+
}
31+
};
32+
33+
int main(){
34+
Solution s;
35+
auto result=s.generateParenthesis(3);
36+
for(auto i:result)
37+
cout<<i<<endl;
38+
}
39+
40+
41+
42+

‎11.1.cpp

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
//实现pow(x,n)
2+
#include<iostream>
3+
#include<vector>
4+
#include<algorithm>
5+
#include<limits.h>
6+
using namespace std;
7+
class Solution{
8+
public:
9+
double myPow(double x,int n){
10+
if(n<0)
11+
return 1/Power(x,-n);
12+
else return Power(x,n);
13+
}
14+
double Power(double x,int n){
15+
if(n==0)return 1;
16+
double v=Power(x,n/2);
17+
if(n%2==0)return v*v;
18+
else return v*v*x;
19+
}
20+
};
21+
int main(){
22+
Solution s;
23+
cout<<s.myPow(3,-3)<<endl;
24+
cout<<pow(3,-3)<<endl;
25+
}

‎11.2.cpp

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
//实现平方根函数sqrt(int x)//
2+
#include<iostream>
3+
#include<algorithm>
4+
using namespace std;
5+
class Solution{
6+
public:
7+
double mySqrt(int x){
8+
if(x<0)
9+
return -1;
10+
double start=1;
11+
double end=x;
12+
while(start!=end){
13+
double mid=start+(end-start)/2;
14+
if(abs(x/mid-mid)<0.00001)
15+
return mid;
16+
else if(x/mid>mid)
17+
start=mid;
18+
else end=mid;
19+
}
20+
}
21+
};
22+
23+
int main(){
24+
Solution s;
25+
cout<<s.mySqrt(5)<<endl;
26+
}

‎12.1.cpp

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
//给一个数组,每个数字代表能跳的最长距离,返回是否能跳到最后的位置
2+
#include<iostream>
3+
#include<vector>
4+
using namespace std;
5+
class Solution{
6+
public:
7+
int minSteps(vector<int> steps){
8+
const int len=steps.size();
9+
int min_step=0;
10+
for(int i=0;i<len-1;){
11+
int max_len=0;
12+
int next=0;
13+
for(int j=1;j<=steps[i];j++){
14+
int max_steps=j+steps[i+j];
15+
if(max_len<max_steps){
16+
max_len=max_steps;
17+
next=j;
18+
}
19+
}
20+
if(next==0)
21+
return -1;
22+
i+=next;
23+
min_step++;
24+
25+
}
26+
return min_step;
27+
}
28+
};
29+
int main(){
30+
Solution s;
31+
vector<int> steps={2,3,1,1,4};
32+
cout<<s.minSteps(steps)<<endl;
33+
}

‎12.3.cpp

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
//给一个股票每日价格,只能买卖一次,求最大利润
2+
#include<iostream>
3+
#include<vector>
4+
#include<algorithm>
5+
using namespace std;
6+
class Solution{
7+
int maxprofit(vector<int>& prices){
8+

‎12.5.cpp

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
//在一个字符串里找到最长不含重复字母的子串//
2+
//思路:从左往右扫描,遇到重复起始位置直接跳到重复的下一个字符//
3+
#include<iostream>
4+
#include<string>
5+
#include<algorithm>
6+
using namespace std;
7+
class Solution{
8+
public:
9+
int longestSubstring(string s){
10+
int max_len=0;
11+
int start=0;
12+
int last[255];
13+
fill_n(last,255,-1);
14+
for(int i=0;i<s.length();i++){
15+
if(last[s[i]]>=start){
16+
max_len=max(max_len,i-start);
17+
start=last[s[i]]+1;
18+
19+
}
20+
last[s[i]]=i;
21+
22+
}
23+
return max((int)s.size()-start,max_len);
24+
}
25+
};
26+
int main(){
27+
Solution s;
28+
string str="abbdd";
29+
cout<<s.longestSubstring(str)<<endl;
30+
}

‎12.6.cpp

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+

0 commit comments

Comments
 (0)