第4題：尋找兩個(gè)正序數(shù)組的中位數(shù)
給定兩個(gè)大小分別是m和n的正序（從小到大）數(shù)組nums1和nums2.請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的中位數(shù)。 算法的時(shí)間復(fù)雜度應(yīng)該為O(log(m+n))。
來源：LeetCode
鏈接：4. 尋找兩個(gè)正序數(shù)組的中位數(shù) - 力扣（LeetCode） (leetcode-cn.com)
示例
輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
思路
按序合并兩個(gè)數(shù)組，找到中位數(shù)。
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int mid = (nums1Size + nums2Size) /2;
int i, j, k;
double dos1, dos2;
j = 0;
k = 0;
for(i = 0; i <= mid; i++)
{
dos1 = dos2;
if(j < nums1Size && k < nums2Size)
{
if(nums1[j] < nums2[k])
{
dos2 = nums1[j];
j++;
continue;
}
else
{
dos2 = nums2[k];
k++;
continue;
}
}
if(j < nums1Size)
{
dos2 = nums1[j];
j++;
continue;
}
if(k < nums2Size)
{
dos2 = nums2[k];
k++;
continue;
}
}
if((nums1Size + nums2Size) % 2 == 0) return (dos1 + dos2)/2;
else return dos2;
}
第5題：最長回文子串
給你一個(gè)字符串s，找到s中最長的回文子串。
來源：LeetCode
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring/
示例
輸入：s = "babad"
輸出："bab"
思路
遍歷字符串，對(duì)每個(gè)字符先向右合并相同的字符，在判斷左右的字符是否相同。
注意 ：字符串的最后包含'\0'。
char * longestPalindrome(char * s){
int slen = strlen(s);
if(slen < 2)
{
return s;
}
int i, dos1, dos2, len, start,num;
len = 0;
start = 0;
for(i = 0; i < slen; i+= num)
{
dos1 = i - 1;
dos2 = i + 1;
num = 1;
while(dos2 < slen && s[i] == s[dos2])
{
dos2 ++;
num++;
}
while(dos1 >= 0 && dos2 < slen && s[dos1] == s[dos2])
{
dos1 --;
dos2 ++;
}
if(dos2 - dos1 -1 > len)
{
start = dos1 + 1;
len = dos2 - dos1 -1;
}
}
char *m;
m = (char *)malloc(len +1);
strncpy(m , s + start, len);
m[len] = '\0';
return m;
}
第6題：Z字形變換
將一個(gè)給定字符串s根據(jù)給定的行數(shù)numRows，以從上往下、從左到右進(jìn)行Z字形排列。
來源：LeetCode
鏈接：6. Z 字形變換 - 力扣（LeetCode） (leetcode-cn.com)
示例：
輸入：s = "PAYPALISHIRING", numRows = 3
輸出："PAHNAPLSIIGYIR"
思路
觀察尋找每行字符排列的規(guī)律。
char * convert(char * s, int numRows){
int i, j, k;
int slen = strlen(s);
if(numRows == 1) return s;
char *m = (char * )malloc ( slen + 1);
int len = 2*numRows - 2;
j = 0;
int dos;
for(i = 0; i < numRows; i++)
{
if(i == 0)
{
dos = 0;
while(dos < slen)
{
m[j] = s[dos];
j++;
dos += len;
}
}
else if(i == numRows - 1)
{
dos = numRows-1;
while(dos<slen)
{
m[j] = s[dos];
j++;
dos += len;
}
}
else
{
dos = i;
while(dos<slen)
{
m[j] = s[dos];
j++;
dos += len;
if(dos-2*i < slen)
{
m[j] = s[dos-2*i];
j++;
}
}
}
}
m[slen] = '\0';
return m;
}
第7題：整數(shù)反轉(zhuǎn)
給你一個(gè) 32 位的有符號(hào)整數(shù) x ，返回將 x 中的數(shù)字部分反轉(zhuǎn)后的結(jié)果。
如果反轉(zhuǎn)后整數(shù)超過 32 位的有符號(hào)整數(shù)的范圍 [?2^31, 2^31 ? 1] ，就返回 0。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-integer
示例
輸入：x=123
輸出：321
輸入：-123
輸出：-321
思路
用數(shù)組存儲(chǔ)x。
int reverse(int x){ //整數(shù)范圍：-2147483648 ~ 2147483647
int num;
if(x==0 || x == -2147483648) return 0;
int n1[10],n[10];
if(x < 0) num = - x;
else num = x;
int i, l,len = 1;
int dos = 0;
for(i = 0; i < 9; i++ )
{
len *=10;
if(num % len== num)
{
n1[i] = num % len;
l = len /10;
if(i == 0) n[i] = n1[i];
else n[i] = (n1[i] - n1[i-1]) /l;
dos++;
break;
}
n1[i] = num % len;
l = len /10;
if(i == 0) n[i] = n1[i];
else n[i] = (n1[i] - n1[i-1])/l;
dos++;
}
if(num % 1000000000 != num)
{
n[9] = num / 1000000000;
dos++;
}
if(dos < 10)
{
num = n[0];
for(i = 1; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else
{
if(n[0] > 2) return 0;
else if(n[0] < 2)
{
num = n[0];
for(i = 1; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else{
num = n[0];
if(n[1] > 1 ) return 0;
else if(n[1] < 1)
{
num = num *10 +n[1];
for(i = 2; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else{
num = num *10 +n[1];
if(n[2] > 4) return 0;
else if(n[2] < 4)
{
num = num *10 + n[2];
for(i = 3; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else{
num = num *10 + n[2];
if(n[3] > 7) return 0;
else if(n[3] < 7)
{
num = num *10 +n[3];
for(i = 4; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else
{
num = num *10 +n[3];
if(n[4] > 4) return 0;
else if(n[4] < 4)
{
num = num *10 + n[4];
for(i = 5; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else
{
num = num *10 + n[4];
if(n[5] > 8)
{
return 0;
}
else if(n[5] < 8)
{
num = num *10 + n[5];
for(i = 6; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else{
num = num *10 + n[5];
if(n[6]>3) return 0;
else if(n[6] < 3)
{
num = num *10 + n[6];
for(i = 7; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else
{
num = num *10 + n[6];
if(n[7] > 6) return 0;
else if(n[7] < 6)
{
num = num *10 + n[7];
for(i = 8; i < dos; i++)
{
num = num * 10 + n[i];
}
if(x > 0) return num;
else return -num;
}
else
{
num = num *10 + n[7];
if(n[8] >4) return 0;
else if(n[8] < 4)
{
num = num *10 + n[8];
num = num * 10 + n[9];
if(x > 0) return num;
else return -num;
}
else
{
num = num *10 + n[8];
if(x > 0)
{
if(n[9] > 7) return 0;
else num = num*10 +n[9];
return num;
}
else
{
if(n[9] > 8) return 0;
else num = num *10 + n[9];
return -num;
}
}
}
}
}
}
}
}
}
}
}
}
第8題：字符串轉(zhuǎn)換整數(shù)（atoi）
請(qǐng)你來實(shí)現(xiàn)一個(gè) myAtoi(string s) 函數(shù)，使其能將字符串轉(zhuǎn)換成一個(gè) 32 位有符號(hào)整數(shù)（類似 C/C++ 中的 atoi 函數(shù)）。
函數(shù) myAtoi(string s) 的算法如下：
讀入字符串并丟棄無用的前導(dǎo)空格
檢查下一個(gè)字符（假設(shè)還未到字符末尾）為正還是負(fù)號(hào)，讀取該字符（如果有）。 確定最終結(jié)果是負(fù)數(shù)還是正數(shù)。 如果兩者都不存在，則假定結(jié)果為正。
讀入下一個(gè)字符，直到到達(dá)下一個(gè)非數(shù)字字符或到達(dá)輸入的結(jié)尾。字符串的其余部分將被忽略。
將前面步驟讀入的這些數(shù)字轉(zhuǎn)換為整數(shù)（即，"123" -> 123， "0032" -> 32）。如果沒有讀入數(shù)字，則整數(shù)為 0 。必要時(shí)更改符號(hào)（從步驟 2 開始）。
如果整數(shù)數(shù)超過 32 位有符號(hào)整數(shù)范圍 [?231, 231 ? 1] ，需要截?cái)噙@個(gè)整數(shù)，使其保持在這個(gè)范圍內(nèi)。具體來說，小于 ?231 的整數(shù)應(yīng)該被固定為 ?231 ，大于 231 ? 1 的整數(shù)應(yīng)該被固定為 231 ? 1 。
返回整數(shù)作為最終結(jié)果。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/string-to-integer-atoi
示例
輸入：s=" -42"
輸出：-42
int myAtoi(char * s){
while(*s == ' ')
{
s++;
}
int flag = 1;
int num, sum;
int max = 2147483647;
int min = -2147483648;
if(*s == '-')
{
flag = -1;
s++;
}
else if(*s == '+') s++;
while(*s == '0') s++;
sum = 0;
num = 0;
int n;
while(*s >= '0' && *s <='9')
{
sum ++;
n = *s - '0';
if(sum == 10 && *(s+1) >= '0' && *(s+1) <='9')
{
if(flag == 1) return max;
else return min;
}
if(sum == 10 && (*(s+1) > '9' || *(s+1) <'0'))
{
if(flag == 1)
{
if(num > max/10) return max;
else if(num < max/10)
{
num = num *10 +n;
return num;
}
else
{
if(n < 7)
{
num = num *10 + n;
return num;
}
else return max;
}
}
else{
if(num > max/10) return min;
else if(num < max/10)
{
num = num *10 + n;
return -num;
}
else if(n<8)
{
num = num * 10 + n;
return -num;
}
else return min;
}
s++;
}
else{
num = num*10+ n;
s++;
}
}
if(flag == 1) return num;
else return -num;
}
第9題：回文數(shù)
給你一個(gè)整數(shù) x ，如果 x 是一個(gè)回文整數(shù)，返回 true ；否則，返回 false 。
回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。
例如，121 是回文，而 123 不是。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/palindrome-number
bool isPalindrome(int x){
int i,len,l;
int num[10],n[10];
len = 0;
int k = 1;
if(x < 0) return false;
if(x/1000000000 != 0)
{
num[9] = x/1000000000;
len++;
}
for(i = 0; i < 9; i++)
{
k *= 10;
n[i] = x % k;
l = k/10;
if(n[i] == x)
{
num[i] = x/l;
len++;
break;
}
len ++;
if(i == 0) num[i] = n[i];
else num[i] = n[i] - n[i-1];
num[i] = num[i] /l;
}
for(i = 0; i <= len/2; i++)
{
if(num[i] != num[len-i-1])
{
return false;
}
}
return true;
}
第10題：正則表達(dá)式匹配
給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p，請(qǐng)你來實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配。
'.' 匹配任意單個(gè)字符
'*' 匹配零個(gè)或多個(gè)前面的那一個(gè)元素
所謂匹配，是要涵蓋 整個(gè) 字符串 s的，而不是部分字符串。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/regular-expression-matching
bool isMatch(char * s, char * p){
if(!*p) return !*s;
bool match = *s && (*s == *p || *p == '.');
if(*(p+1) == '*')
{
return isMatch(s, p+2) || (match && isMatch(++s, p));
}
else
{
return match && isMatch(++s,++p);
}
}
第11題：盛最多水的容器
給定一個(gè)長度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲(chǔ)存的最大水量。
說明：你不能傾斜容器。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/container-with-most-water
思路
使用兩個(gè)指針，從兩端開始遍歷，每次移動(dòng)值較小的指針。
int maxArea(int* height, int heightSize){
int i,j,max,temp;
max = 0;
i = 0;
j = heightSize -1;
while(i<j)
{
temp = height[i] > height[j] ? height[j] :height[i];
temp = temp *(j - i);
if(temp > max) max =temp;
if(height[i] < height[j]) i++;
else j--;
}
return max;
}
