Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

C++:
01 double kSmall(int A[],int m,int B[],int n,int k)
02 {
03       if(m==0) return B[k1];
04       if(n==0) return A[k1];
05       int a_hi;
06       int b_hi;
07       int a_lo=0;
08       if(k==1)  return A[0]<B[0]?A[0]:B[0];
09       if(m>k1){
10           a_hi=k2;
11           b_hi=0;
12       }else{
13           a_hi=m1;
14           b_hi=k1m;
15       }
16       while(a_lo<=a_hi){
17           int a_mid=(a_hi+a_lo)/2;
18           int d=a_hia_mid;
19           if(d>nb_hi1)
20               d=nb_hi1;
21           int b_mid=b_hi+d;
22           a_mid=a_hid;
23           if(A[a_mid]<B[b_mid]){
24               if((a_mid==m1)||(B[b_mid]<=A[a_mid+1]))
25                   return B[b_mid];
26               a_lo=a_mid+1;
27           }else{
28               if((b_mid==n1)||(A[a_mid]<=B[b_mid+1]))
29                   return A[a_mid];
30               a_hi=a_mid1;
31               b_hi=b_mid+1;
32           }
33       }
34       if(a_hi<0)
35           return B[k1];
36       if(B[0]>A[a_hi])
37           return A[a_hi+1];
38  }
39 
40 class Solution {
41 public:
42     double findMedianSortedArrays(int A[], int m, int B[], int n) {
43         // Start typing your C/C++ solution below
44         // DO NOT write int main() function
45         int k=m+n;
46         if(k%2==1)
47         {
48             return kSmall(A, m, B, n, (k+1)/2);
49         }
50         else
51         {
52             double result=kSmall(A,m,B,n,k/2)
53                     +kSmall(A,m,B,n,k/2+1);
54             return result/2;
55         }
56     }
57 };
Posted in Array and linked list, Binary search | Leave a comment

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

C++:
01 class Solution {
02 public:
03     string longestPalindrome(string s) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int n=s.size();
07         int m=2*n1;
08         int length=0;
09         int first=0;
10         for(int i=0;i<m;i++)
11         {
12             if(i%2==0)
13             {
14                 int len=1;
15                 int t=i/2;
16                 if(len>length)
17                 {
18                     length=len;
19                     first=t;
20                 }
21                 int j=t1;
22                 int k=t+1;
23                 while((j>=0)&&(k<n))
24                 {
25                     if(s[j]!=s[k])
26                         break;
27                     len+=2;
28                     if(len>length)
29                     {
30                         length=len;
31                         first=j;
32                     }
33                     j;
34                     k++;
35                 }
36             }
37             else
38             {
39                 int len=0;
40                 int j=i/2;
41                 int k=j+1;
42                 while((j>=0)&&(k<n))
43                 {
44                     if(s[j]!=s[k])
45                         break;
46                     len+=2;
47                     if(len>length)
48                     {
49                         length=len;
50                         first=j;
51                     }
52                     j;
53                     k++;
54                 }
55             }
56         }
57         return s.substr(first,length);
58     }
59 };
Posted in Array and linked list, String | Leave a comment

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

C++:
01 class Solution {
02 public:
03     string convert(string s, int nRows) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function    
06         if(nRows==1)
07             return s;
08         int n=s.size();
09         string result;
10         for(int i=0;i<nRows;i++)
11         {
12             bool flag=false;
13             int prv=-1;
14             for(int j=i;j<n;)
15             {
16                 if(j!=prv)
17                 {
18                     result+=s[j];
19                     prv=j;
20                 }
21                 if(flag==false)
22                 {
23                     flag=true;
24                     j+=2*nRows2i*2;
25                 }
26                 else
27                 {
28                     flag=false;
29                     j+=2*i;
30                 }
31             }
32         }
33         return result;
34     }
35 };
Posted in Array and linked list, String | Leave a comment

String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

C++:
01 class Solution {
02 public:
03     int atoi(const char *str) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int result=0;
07         int sign=1;
08         int p=0;
09         int max=INT_MAX;
10         int min=INT_MIN;
11         while(str[p]==‘ ‘) p++;
12         if(str[p]==‘-‘)
13         {
14             sign=-1;
15             p++;
16         }
17         if(str[p]==‘+’)
18         {
19             p++;
20         }
21         while((str[p]>=‘0’)&&(str[p]<=‘9’))
22         {
23             if(result>max/10)
24             {
25                 return sign>0?INT_MAX:INT_MIN;
26             }
27             if(result*10>maxstr[p]+‘0’)
28             {
29                 return sign>0?INT_MAX:INT_MIN;
30             }
31             result=result*10+str[p++]‘0’;
32         }
33         return sign>0?result:result;
34     }
35 };
Posted in Number trick, String | Leave a comment

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true
C++:
01 bool isMatchHelp(const char *s, const char *p, int m, int n)
02 {
03      if((s[m]=='')&&(p[n]==''))  return true;
04      if(p[n]=='') return false;
05      if(p[n+1]=='*')
06      {
07          int t=m;
08          do
09          {
10              if(isMatchHelp(s,p,t,n+2))  return true;
11          }while(((s[t]==p[n])||(p[n]=='.'))&&(s[t++]!=''));
12      }
13      else
14      {
15          if(p[n]=='.')
16          {
17            return (s[m]!='')&&(isMatchHelp(s,p,m+1,n+1));
18          }
19          return (s[m]==p[n])&&(isMatchHelp(s,p,m+1,n+1));
20      }
21      return false;
22  }
23  class Solution {
24  public:
25      bool isMatch(const char *s, const char *p) {
26          // Start typing your C/C++ solution below
27          // DO NOT write int main() function    
28          return isMatchHelp(s,p,0,0);
29      }
30  };
Posted in Recursive, String | Leave a comment

Container With Most Water

Given n non-negative integers a1a2, …, an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

C++:
01 class Solution {
02 public:
03     int maxArea(vector<int> &height) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         vector<int> A;
07         int left=0;
08         int right=height.size()1;
09         while(left<right)
10         {
11             int lh=height[left];
12             int rh=height[right];
13             int h=lh<rh?lh:rh;
14             A.push_back(h*(rightleft));
15             if(lh<rh)
16                 left++;
17             else
18                 right;
19         }
20         int result=0;
21         for(int i=0;i<A.size();i++)
22         {
23             if(A[i]>result)
24                 result=A[i];
25         }
26         return result;
27     }
28 };
Posted in Array and linked list, Greedy algorithm | Leave a comment

Integer to Roman

Given an integer, convert it to a roman numeral.

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

C++:
01 class Solution {
02 public:
03     string intToRoman(int num) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function    
06         string s;
07         while(num!=0)
08         {
09             while(num>=1000)
10             {
11                 s+=‘M’;
12                 num-=1000;
13             }
14             if(num>=900)
15             {
16                 s+=‘C’;
17                 s+=‘M’;
18                 num-=900;
19             }
20             if(num>=500)
21             {
22                 s+=‘D’;
23                 num-=500;
24             }
25             if(num>=400)
26             {
27                 s+=‘C’;
28                 s+=‘D’;
29                 num-=400;
30             }
31             while(num>=100)
32             {
33                 s+=‘C’;
34                 num-=100;
35             }
36             if(num>=90)
37             {
38                 s+=‘X’;
39                 s+=‘C’;
40                 num-=90;
41             }
42             if(num>=50)
43             {
44                 s+=‘L’;
45                 num-=50;
46             }
47             if(num>=40)
48             {
49                 s+=‘X’;
50                 s+=‘L’;
51                 num-=40;
52             }
53             while(num>=10)
54             {
55                 s+=‘X’;
56                 num-=10;
57             }
58             if(num>=9)
59             {
60                 s+=‘I’;
61                 s+=‘X’;
62                 num-=9;
63             }
64             if(num>=5)
65             {
66                 s+=‘V’;
67                 num-=5;
68             }
69             if(num>=4)
70             {
71                 s+=‘I’;
72                 s+=‘V’;
73                 num-=4;
74             }
75             while(num>0)
76             {
77                 s+=‘I’;
78                 num;
79             }
80         }
81         return s;
82     }
83 };
Posted in Number trick, String | Leave a comment