Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

C++:
01 class Solution {
02 public:
03     int romanToInt(string s) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int result=0;
07         int h=0;
08         int t=0;
09         int d=0;
10         int p=0;
11         while(s[p]!=)
12         {
13             if(s[p]==‘M’)
14             {
15                 result-=h;
16                 h=0;
17                 result+=1000;
18             }
19             else if(s[p]==‘D’)
20             {
21                 result-=h;
22                 h=0;
23                 result+=500;
24             }
25             else if(s[p]==‘C’)
26             {
27                 result-=t;
28                 t=0;
29                 h+=100;
30             }
31             else if(s[p]==‘L’)
32             {
33                 result-=t;
34                 t=0;
35                 result+=50;
36             }
37             else if(s[p]==‘X’)
38             {
39                 result-=d;
40                 d=0;
41                 t+=10;
42             }
43             else if(s[p]==‘V’)
44             {
45                 result-=d;
46                 d=0;
47                 result+=5;
48             }
49             else if(s[p]==‘I’)
50             {
51                 d++;
52             }
53             p++;
54         }
55         return result+h+t+d;
56     }
57 };
Posted in Number trick, String | Leave a comment

4Sum

Given an array S of n integers, are there elements abc, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d)
  • The solution set must not contain duplicate quadruplets.
    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)
C++:
01 bool compare(int i, int j)
02 {
03     return i<j;
04 }
05 class Solution {
06 public:
07     vector<vector<int> > fourSum(vector<int> &num, int target) {
08         // Start typing your C/C++ solution below
09         // DO NOT write int main() function
10         sort(num.begin(),num.end(),compare);
11         vector<vector<int>> result;
12         int n=num.size();
13         if(n<3) return result;
14         for(int i=0i<n3; )
15         {
16             for(int j=i+1j<n2;  )
17             {
18                 int p=j+1;
19                 int q=n1;
20                 while(p<q)
21                 {
22                     int t=num[i]+num[j]+num[p]+num[q]target;
23                     if(t==0)
24                     {
25                         vector<int> item;
26                         item.push_back(num[i]);
27                         item.push_back(num[j]);
28                         item.push_back(num[p]);
29                         item.push_back(num[q]);
30                         result.push_back(item);
31                         p++;
32                         while((p<q)&&(num[p]==num[p1]))    p++;
33                     }
34                     else if(t<0)
35                     {
36                         p++;
37                     }
38                     else
39                     {
40                         q;
41                     }
42                 }
43                 j++;
44                 while((j<n2)&&(num[j]==num[j1]))  j++;
45             }
46             i++;
47             while((i<n3)&&(num[i]==num[i1])) i++;
48         }
49     }
50 };
Posted in Array and linked list | Leave a comment

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
C++:
01 bool compare(int i,int j)
02 {
03     return i<j;
04 }
05 class Solution {
06 public:
07     int threeSumClosest(vector<int> &num, int target) {
08         // Start typing your C/C++ solution below
09         // DO NOT write int main() function
10         int n=num.size();
11         if(n<3) return 0;
12         sort(num.begin(),num.end(),compare);
13         int result=num[0]+num[1]+num[2];
14         int dist=resulttarget;
15         dist=dist<0?-dist:dist;
16         for(int i=0;i<n;i++)
17         {
18             int j=i+1;
19             int k=n1;
20             while(j<k)
21             {
22                 int d=num[i]+num[j]+num[k]target;
23                 if(d==0)    return target;
24                 if(d<0)
25                 {
26                     if(d<dist)
27                     {
28                         dist=-d;
29                         result=d+target;
30                     }
31                     j++;
32                 }
33                 else
34                 {
35                     if(d<dist)
36                     {
37                         dist=d;
38                         result=d+target;
39                     }
40                     k;
41                 }
42             }
43         }
44         return result;
45     }
46 };
Posted in Array and linked list | Leave a comment

3Sum

Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
  • The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)
C++:
01 bool compare(int i, int j)
02 {
03     return i<j;
04 }
05 class Solution {
06 public:
07     vector<vector<int> > threeSum(vector<int> &num) {
08         // Start typing your C/C++ solution below
09         // DO NOT write int main() function
10         sort(num.begin(), num.end(), compare);
11         vector<vector<int>> result;
12         int n=num.size();
13         for(int i=0;i<n2😉
14         {
15             int j=i+1;
16             int k=n1;
17             while(j<k)
18             {
19                 if(num[i]+num[j]+num[k]==0)
20                 {
21                     vector<int> item;
22                     item.push_back(num[i]);
23                     item.push_back(num[j]);
24                     item.push_back(num[k]);
25                     result.push_back(item);
26                     j++;
27                     while((j<k)&&(num[j]==num[j1]))
28                     {
29                         j++;
30                     }
31                 }
32                 else if(num[i]+num[j]+num[k]<0)
33                 {
34                     j++;
35                 }
36                 else
37                 {
38                     k;
39                 }
40             }
41             i++;
42             while((num[i]==num[i1])&&(i<n2))
43             {
44                 i++;
45             }
46         }
47         return result;
48     }
49 };
Posted in Array and linked list | Leave a comment

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S"barfoothefoobarman"
L["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

C++:
01 class Solution {
02 public:
03     vector<int> findSubstring(string S, vector<string> &L) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int i=0;
07         vector<int> result;
08         int n=L.size();
09         if(n==0)    return result;
10         int m=L[0].size();
11         int r=S.size();
12         vector<int> A;
13         map<string, int> B;
14         for(int j=0;j<n;j++)
15         {
16             if(B.find(L[j])==B.end())
17             {
18                 A.push_back(1);
19                 B[L[j]]=i++;
20             }
21             else
22             {
23                 A[B[L[j]]]++;
24             }
25         }
26         vector<int> C;
27         for(int j=0;j<rm+1;j++)
28         {
29             string tmp=S.substr(j,m);
30             if(B.find(tmp)==B.end())
31             {
32                 C.push_back(1);
33             }
34             else
35             {
36                 C.push_back(B[tmp]);
37             }
38         }
39         for(int p=0;p<rm+1;p++)
40         {
41             int cnt=0;
42             vector<int> D(A);
43             for(int q=p;q<rm+1;q=q+m)
44             {
45                 if(C[q]==-1)    break;
46                 int t=C[q];
47                 if(D[t]==0)     break;
48                 D[t];
49                 cnt++;
50             }
51             if(cnt==n)
52             {
53                 result.push_back(p);
54             }
55         }
56         return result;
57     }
58 };
Posted in Array and linked list, Hashtable and Map, String | Leave a comment

Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

C++:
01 class Solution {
02 public:
03     char *strStr(char *haystack, char *needle) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         if((needle==NULL)||(*needle==))
07             return haystack;
08         vector<int> A;
09         int k=0;
10         A.push_back(0);
11         char* p=needle+1;
12         while(*p!=)
13         {
14             while((k>0)&&(*(needle+k)!=*p))
15             {
16                 k=A[k1];
17             }
18             if(*(needle+k)==*p)
19             {
20                 k++;
21             }
22             A.push_back(k);
23             p++;
24         }
25         int n=A.size();
26         k=0;
27         p=haystack;
28         while(*p!=)
29         {
30             while((k>0)&&(*(needle+k)!=*p))
31             {
32                 k=A[k1];
33             }
34             if(*(needle+k)==*p)
35             {
36                 k++;
37             }
38             if(k==n)
39             {
40                 return pk+1;
41             }
42             p++;
43         }
44         return NULL;
45     }
46 };
Posted in Backtrack, String | Leave a comment

Longest Common Prefix

Write a function to find the longest common prefix string among an array of strings.

C++:
01 class Solution {
02 public:
03     string longestCommonPrefix(vector<string> &strs) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         string result;
07         if(strs.size()==0)  return result;
08         for(int i=0;;i++)
09         {
10             if(strs[0].size()<=i)
11             {
12                 return result;
13             }
14             char c=strs[0][i];
15             for(int j=1;j<strs.size();j++)
16             {
17 
18                 if((strs[j].size()<=i)||(strs[j][i]!=c))
19                 {
20                     return result;
21                 }
22             }
23             result+=c;
24         }
25     }
26 };
Posted in Array and linked list, String | Leave a comment