Jiacheng Feng fjc-oai
fjc-oai
/ Palindrome Partitioning II .3.cpp
Created
November 28, 2014 19:24
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int minCut(string s) { | |
| vector<vector<bool>>isPal(s.size(),vector<bool>(s.size()+1,true)); | |
| for(int l=2;l<=s.size();l++) | |
| for(int i=0;i+l-1<s.size();i++) | |
| isPal[i][l]= s[i]==s[i+l-1] && isPal[i+1][l-2]; | |
| vector<int>f(s.size()+1,INT_MAX); | |
| f[0]=-1; | |
| for(int i=1;i<=s.size();i++) |
fjc-oai
/ Unique Binary Search Trees .3.cpp
Created
November 28, 2014 00:46
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int numTrees(int n) { | |
| vector<int>f(n+1,0); | |
| f[0]=1; | |
| for(int i=1;i<=n;i++){ | |
| for(int j=0;j<=i-1;j++) | |
| f[i]+=f[j]*f[i-1-j]; | |
| } | |
| return f[n]; |
fjc-oai
/ Word Break II .3.cpp
Created
November 28, 2014 00:33
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<string> wordBreak(string s, unordered_set<string> &dict) { | |
| vector<vector<int>>dp(s.size()+1,vector<int>()); | |
| dp[0].push_back(0); | |
| for(int i=1;i<=s.size();i++){ | |
| for(int j=1;j<=i;j++) | |
| if(!dp[j-1].empty() && dict.count(s.substr(j-1,i-j+1))!=0) | |
| dp[i].push_back(j); | |
| } |
fjc-oai
/ Max Points on a Line.3.cpp
Created
November 12, 2014 00:15
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for a point. | |
| * struct Point { | |
| * int x; | |
| * int y; | |
| * Point() : x(0), y(0) {} | |
| * Point(int a, int b) : x(a), y(b) {} | |
| * }; | |
| */ | |
| struct cmp{ |
fjc-oai
/ bitwise convertor.cpp
Created
November 5, 2014 03:53
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| string convert(string &decimal){ | |
| int p=decimal.size(); | |
| for(int i=0;i<decimal.size();i++) | |
| if(decimal[i]=='.'){ | |
| p=i; | |
| break; | |
| } | |
| int n1=atoi(decimal.substr(0,p).c_str()); | |
| double n2=atof(decimal.c_str())-n1; |
fjc-oai
/ Remove Nth Node From End of List .2.cpp
Created
November 3, 2014 18:45
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for singly-linked list. | |
| * struct ListNode { | |
| * int val; | |
| * ListNode *next; | |
| * ListNode(int x) : val(x), next(NULL) {} | |
| * }; | |
| */ | |
| class Solution { | |
| public: |
fjc-oai
/ Divide Two Integers.2.cpp
Created
October 29, 2014 05:05
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int divide(int dividend, int divisor) { | |
| int flag=1; int ret=0; | |
| if(dividend==0)return 0; | |
| if(divisor==INT_MIN)return dividend==INT_MIN?1:0; | |
| if(divisor<0){ | |
| divisor=-divisor; | |
| flag*=-1; | |
| } |
fjc-oai
/ Find Minimum in Rotated Sorted Array.2.2.cpp
Created
October 21, 2014 21:25
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int findMin(vector<int> &num) { | |
| int p=0,q=num.size()-1; | |
| while(p<=q){ | |
| int mid=p+(q-p)/2; | |
| if(p==mid)return min(num[p],num[q]); | |
| if(num[p]<num[q]) | |
| return num[p]; | |
| else{ |
fjc-oai
/ Find Minimum in Rotated Sorted Array.2.1.cpp
Created
October 21, 2014 21:25
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int findMin(vector<int> &num) { | |
| int p=0,q=num.size()-1; | |
| while(p<=q){ | |
| int mid=p+(q-p)/2; | |
| if( (mid==p || num[mid]<=num[mid-1]) && (mid==q || num[mid]<=num[mid+1])) | |
| return num[mid]; | |
| if(num[p]<num[q]) | |
| return num[p]; |
fjc-oai
/ N-Queens .2.cpp
Created
October 21, 2014 02:12
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<vector<string> > solveNQueens(int n) { | |
| vector<vector<string>>ret; | |
| vector<string>tmp(n,string(n,'.')); | |
| set<int>s1,s2,s3; | |
| dfs(ret,tmp,s1,s2,s3,n,0); | |
| return ret; | |
| } | |
| void dfs(vector<vector<string>>&ret,vector<string>&tmp,set<int>&s1,set<int>&s2,set<int>&s3,int n,int cur){ |
NewerOlder