最大子序列和：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
int maxSubArray(int* nums, int numsSize){ int i = 0; int sum=nums[0]; int summax = nums[0]; for(i = 1; i < numsSize;i++) { if((nums[i]>sum)&&(sum<0)) { sum = nums[i]; } else{ sum+=nums[i]; } // printf("sum=%d,nums[i]=%d\n",sum,nums[i]); if(summax < sum){ summax=sum; } } return summax; }
报数序列：
是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
示例 1:
输入: 1
输出: "1"
示例 2:
输入: 4
输出: "1211"
#define Len 4500 char * countAndSay(int n){ char *pre, *num; int i=1; int len=0; int m=0; char flag; int index=0; pre = (char *)malloc(sizeof(char) * Len);//保存当前字符串 num = (char *)malloc(sizeof(char) * Len);//保存上一层字符串 if(n==1) return "1"; else { num=countAndSay(n-1);//求出上一层字符串 len=strlen(num);//求出上一层字符串长度 flag=num[0];//标记字符为第一个字符 m=1;//记录标记字符的个数 while(i<len)//向后遍历 { if(num[i]==flag)//如果当前字符和标记字符一样 m+=1;//个数加一 else//如果当前字符和标记字符不一样 { pre[index++]=m+'0';//将此次遍历结果写入结果字符串中 pre[index++]=flag; m=1;//修改个数 flag=num[i];//修改标记字符为当前字符 } i+=1; } pre[index++]=m+'0';//将最后一次遍历结果写入字符串中 pre[index++]=flag; pre[index]='\0'; return pre; } }
搜索插入位置：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
int searchInsert(int* nums, int numsSize, int target){
int left=0;
int right=numsSize-1; int mid; while(left<=right){//二分法 mid=left+((right-left)>>1); if(nums[mid]==target) return mid; else if(nums[mid]>target) right=mid-1;//注意+-1 else if(nums[mid]<target) left=mid+1; } if(target<nums[mid]) return mid;//此时target位于mid附近 else return mid+1; }
实现 strStr() 函数：
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
int strStr(char * haystack, char * needle){ int a=strlen(haystack); int b=strlen(needle); char *p=NULL;//定义一个新指针 if(b==0) return 0;//这里多考虑a,b同时或不同时为0的情况 p=haystack; for(int i=0;i<=a-b;++i){//注意a-b if(haystack[i]==needle[0]){ if(!strncmp(p,needle,b)) return i;//注意strcmp在这里不可以使用，他只有两个参数 } ++p; } return -1; }
两数之和：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
int* twoSum(int* nums, int numsSize, int target, int* returnSize){//参数：原始数组，原始数组长度，比较值，返回数组长度 int* res=(int*)malloc(sizeof(int)*2); *returnSize=0; int i,j; for(i=0;i<numsSize-1;i++) { for(j=i+1;j<numsSize;j++)//依次往后比较 { if(nums[i]+nums[j]==target) { res[0]=i; res[1]=j; *returnSize=2; return res; } } } return res; }
存在重复元素：
输入: [1,2,3,1]输出: true
输入: [1,2,3,4]输出: false
void swap(int *a, int *b)//自己编写交换函数 { int temp; temp = *a; *a = *b; *b = temp; } void quickSort(int arr[] ,int start, int end)//自己编写归并排序 { int arrBase, arrMiddle; int tempStart = start, tempEnd = end; //对于这种递归的函数，内部必须要有一个函数返回的条件 if(tempStart >= tempEnd) return; //拷贝一个基准值作为后面比较的参数 arrBase = arr[start]; while(start < end) { while(start < end && arr[end] > arrBase) end--; if(start < end) { swap(&arr[start], &arr[end]); start++; } while(start < end && arr[start] < arrBase) start++; if(start < end) { swap(&arr[start], &arr[end]); end--; } } arr[start] = arrBase; arrMiddle = start; //分治方法进行递归 quickSort(arr,tempStart,arrMiddle-1); quickSort(arr,arrMiddle+1,tempEnd); } int comp(const void *a,const void *b){//自己编写比较函数 return (*(int*)a > *(int*)b); } bool containsDuplicate(int* nums, int numsSize){ qsort(nums, numsSize, sizeof(int), comp);//把原始数组的值，按顺序排序 for(int k=0;k<numsSize-1;k++){//判断，相邻元素有相等，则返回true。 if(nums[k]==nums[k+1]){ return true; } } return false; }
两数相加：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ //链表结构 struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { //初始化空头 struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode)); head->next =NULL; struct ListNode* tail; tail = head; struct ListNode* p1 = l1; struct ListNode* p2 = l2; int carry = 0; //进位 if(p1==NULL) return p2;
if(p2==NULL) return p1;
//循环，直到跳出两个链表 //当两条链表一样长时只需这一次处理，但是当不一样长时，只能处理一样长的大小 while (p1 != NULL && p2 != NULL) { //当前结点的和，注意加上进位 int sum = p1->val + p2->val + carry; //当前结点和大于等于10时 if (sum >= 10) { sum -= 10; //当前结点的值-10，变为个位 carry = 1; //大于10，进位1 } else { carry = 0; } //初始化结点,尾添加, 必须先将尾指针移动到新的尾结点上再赋值，因为不这么做的话，第一个结点无法正确赋值(因为这时候尾指针还没有真正移到第一个结点上，此时指向的还是头结点) tail->next = (struct ListNode*)malloc(sizeof(struct ListNode)); tail = tail->next; tail->val = sum; p1 = p1->next; p2 = p2->next; } //当两条链表不一样长时，其中一者为NULL了，另一者还没完，这时候用p1指向没完的那一条链表，继续遍历 if (p1 == NULL) { p1 = p2; } else if (p2 = NULL) { p1 = p1; } //遍历剩余部分 while (p1 != NULL) { int sum = p1->val + carry; //带上进制计算当前结点和 if (sum >= 10) { sum -= 10; carry = 1; } else { carry = 0; } //继续朝合并的链表中添加结点 tail->next = (struct ListNode*)malloc(sizeof(struct ListNode)); tail = tail->next; tail->val = sum; p1 = p1->next; } //如果最后一位还有进制，再申请一个结点存1 if (carry == 1) { tail->next = (struct ListNode*)malloc(sizeof(struct ListNode)); tail = tail->next; tail->val = 1; } tail->next = NULL; //尾指针赋空，结尾 //因为我们不能返回头结点，所以要把头结点释放了，但是要头指针移到第一个结点 struct ListNode* pTemp = head; head = head->next; free(pTemp); return head; }
整数反转：
输入: 123 输出: 321
输入: -123 输出: -321
输入: 120 输出: 21
int reverse(int x) { int temp; int i; long c=0;//定义为long型 for(i=0;i<10;++i){ temp=x%10;//取出最后一位包括负数情况 x=x/10; c=c*10+temp; if(c>0x7fffffff||c<(signed int)0x80000000){//判断整型数据是否溢出 return 0; } if(x==0) break; } return c; }
罗马数转整数：
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
int romanToInt(char * s){ int len=strlen(s); if(len==0) return 0; int num=0; for(int i=0;i<len;++i){ switch(s[i]){//判断每一位字符 case 'M':num+=1000;break; case 'D':num+=500;break; case 'C':num+=100;if(i<len-1) if(s[i+1]=='D'||s[i+1]=='M') num-=200;break;//特殊情况，特殊处理，第一个if保证罗马数不是个位数字 case 'L':num+=50;break; case 'X':num+=10;if(i<len-1) if(s[i+1]=='L'||s[i+1]=='C') num-=20;break; case 'V':num+=5;break; case 'I':num+=1;if(i<len-1) if(s[i+1]=='V'||s[i+1]=='X') num-=2;break; } } return num; }
查找字符串数组中的最长公共前缀
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
char * longestCommonPrefix(char ** strs, int strsSize){ if(strsSize==0){ char *a=(char *)malloc(1); a[0]='\0'; return a; } if(strsSize==1){ return strs[0]; }
//首先判断两种特殊情况 int is = 1 , temp ; int i=0; for(;is;++i){ temp = strs[0][i]; for(int j=0;j<strsSize;++j){ if((!strs[j][i])||strs[j][i]!=temp){ is = 0; break; } } } strs[0][i-1]='\0'; return strs[0]; }
有效的括号：
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
bool isValid(char * s){ if ( s == NULL || s[0] == '\0' ) return true;//判断为空情况 char *aus = (char *) malloc (strlen(s) + 1); int top = 0; for(int i=0;i<strlen(s);++i){ if(s[i]=='('||s[i]=='{'||s[i]=='[') aus[top++]=s[i];//模拟入栈操作 else{ if(--top<0) return false;//模拟出栈操作 if(s[i]==')'&&aus[top]!='(') return false; if(s[i]==']'&&aus[top]!='[') return false; if(s[i]=='}'&&aus[top]!='{') return false; } } return !top;//初值为0，入栈多少次，出栈就多少次，最后依然为0。 }
回文数判断：
是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
bool isPalindrome(int x){ if(x<0) return false; if(x==0) return true; int a; long b=0,y=x;//定义为long型 while(y>=1){ a=y%10; y=y/10; b=b*10+a; } if(x==b) return true; return false; }
合并两个有序链表：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ //链表结构 struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ if(l1==NULL) return l2; if(l2==NULL) return l1;//首先判断为空指针情况 struct ListNode* l; struct ListNode* j; if(l1->val<l2->val){ l=l1; l1=l1->next; } else{ l=l2; l2=l2->next; }//先定义一个首节点 j=l; while(l1&&l2){ if(l1->val<l2->val){ j->next=l1;//注意指针的值比较和赋值的区别 l1=l1->next; } else{ j->next=l2; l2=l2->next; } j=j->next;//指针后移操作 } if(l1){//有剩余情况 j->next=l1; } if(l2){ j->next=l2; } return l; }
删除排序数组的重复项：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
int removeDuplicates(int* nums, int numsSize){ if(numsSize==0||numsSize==1) return numsSize; int len=0; for(int i=0;i<numsSize-1;++i){ if(nums[i]!=nums[i+1]){//有序数组相邻比较 nums[len++]=nums[i]; } } nums[len++]=nums[numsSize-1]; return len; }
移除元素：
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
int removeElement(int* nums, int numsSize, int val){ if(numsSize==0) return numsSize;//判断为空情况 int *left=nums;//使用左右双指针 int *right=nums+numsSize-1; while(left<right){ while(*left!=val&&left<right) left++;//左指针移到等于val的地方 while(*right==val&&left<right) right--;//右指针移到不等于val的地方 *left=*right;//右指针值覆盖左指针 right--;//右指针左移 } return left-nums+(*left!=val);//返回长度 }