第4题：寻找两个正序数组的中位数
给定两个大小分别是m和n的正序（从小到大）数组nums1和nums2.请你找出并返回这两个正序数组的中位数。 算法的时间复杂度应该为O(log(m+n))。
来源：LeetCode
链接：4. 寻找两个正序数组的中位数 - 力扣（LeetCode） (leetcode-cn.com)
示例
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
思路
按序合并两个数组，找到中位数。
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题：最长回文子串
给你一个字符串s，找到s中最长的回文子串。
来源：LeetCode
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
示例
输入：s = "babad"
输出："bab"
思路
遍历字符串，对每个字符先向右合并相同的字符，在判断左右的字符是否相同。
注意 ：字符串的最后包含'\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字形变换
将一个给定字符串s根据给定的行数numRows，以从上往下、从左到右进行Z字形排列。
来源：LeetCode
链接：6. Z 字形变换 - 力扣（LeetCode） (leetcode-cn.com)
示例：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
思路
观察寻找每行字符排列的规律。
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题：整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer
示例
输入：x=123
输出：321
输入：-123
输出：-321
思路
用数组存储x。
int reverse(int x){ //整数范围：-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题：字符串转换整数（atoi）
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
来源：力扣（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题：回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，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题：正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 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题：盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
思路
使用两个指针，从两端开始遍历，每次移动值较小的指针。
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;
}
