27. 移除元素
35. 搜索插入位置
53. 最大子序和
66. 加一
88. 合并两个有序数组
121. 买卖股票的最佳时机
167. 两数之和 II - 输入有序数组
169. 多数元素 思想太妙了
217. 存在重复元素
283. 移动零
303. 区域和检索 - 数组不可变
中等题
228. 汇总区间 说好的简单题呢？？？
500. 键盘行
题解
27. 移除元素
int removeElement(int* nums, int numsSize, int val){ int left = 0, right = numsSize; while (left < right) { if (nums[left] == val) {//找到一个等于val的值 把它换到后面 nums[left] = nums[right - 1]; right--;//右端减一 } else { left++; } } return left;//left最终指向所有不等于val值的右边一个值 }
35. 搜索插入位置 基础的二分
int searchInsert(int* nums, int numsSize, int target){ int low = 0,high = numsSize - 1; while(low <= high){ int mid = low + (high - low)/2;//根据中间值修改两个指针 if(nums[mid] > target) high = mid - 1; if(nums[mid] == target) return mid; if(nums[mid] < target) low = mid +1; } return low; }
53. 最大子序和
int maxSubArray(int* nums, int numsSize) { int qian = 0, maxAns = nums[0]; for (int i = 0; i < numsSize; i++) { qian = qian + nums[i]>nums[i]?qian + nums[i]:nums[i];//计算当前的最大前缀和 maxAns = maxAns>qian?maxAns:qian; } return maxAns; }
66. 加一
int* plusOne(int* digits, int digitsSize, int* returnSize){ int count9 = 0; for(int i = 0;i < digitsSize;i++) if(digits[i] == 9) count9++; if(count9 == digitsSize) *returnSize = digitsSize + 1;//判断返回数组是否发生变化 else *returnSize = digitsSize; int anssize = *returnSize,*ans = malloc(sizeof(int) * anssize); int jinwei = 1; for(int i = digitsSize-1;i >= 0;i--){ ans[--anssize] = (digits[i] + jinwei)%10; jinwei = (digits[i] + jinwei)/10; } if(anssize) ans[--anssize] = 1; return ans; }
88. 合并两个有序数组
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int size = m + n;//从后往前合并 不会产生覆盖的问题 int min = -1000000001; for(int i = m - 1,j = n - 1;i>=0||j>=0;){ if(i<0) nums1[--size] = nums2[j--]; else if(j<0||nums1[i] > nums2[j]) nums1[--size] = nums1[i--]; else nums1[--size] = nums2[j--]; } }
121. 买卖股票的最佳时机
int maxProfit(int* prices, int pricesSize){ int minprice = 1000000000, maxprofit = 0;//找到最低点买入 高点卖出 for (int i = 0;i<pricesSize;i++) { if((prices[i] - minprice) > maxprofit) maxprofit = (prices[i] - minprice); if(minprice > prices[i]) minprice = prices[i]; } return maxprofit; }
167. 两数之和 II - 输入有序数组
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){ int hash[2010];//创建hash表 memset(hash,-1,sizeof(hash));//初始为-1，记录位置 *returnSize = 2; int *ans = malloc(sizeof(int) * 2); for(int i = 0;i < numbersSize;i++) if(hash[target - numbers[i]+1000] != -1){ ans[0] = hash[target - numbers[i]+1000]; ans[1] = i + 1; return ans; } else hash[numbers[i] + 1000] = i + 1;//+1000保证映射到数组内 return 0; }
169. 多数元素 由于超过一半 每一那一个最多次数的元素和一个非最多元素抵消 最后剩下的只能是最多元素
int majorityElement(int* nums, int numsSize){ int maxnum = 0,maxtime = 0;//最多元素 以及最多元素当前的次数 for(int i = 0;i < numsSize;i++){ if(maxtime == 0){ maxnum = nums[i];//没有最多元素 选定当前元素为最多元素 maxtime++; } else if(nums[i] == maxnum) maxtime++;//还是最多元素 增加计数 else maxtime--;//不是最多计数 抵消一个? } return maxnum; }
217. 存在重复元素
int cmp(int *a,int *b){ return *a > *b; } bool containsDuplicate(int* nums, int numsSize){ qsort(nums,numsSize,sizeof(int),cmp);//排个序直接看被。。 for(int i = 1;i < numsSize;i++) if(nums[i] == nums[i-1]) return true; return false; }
283. 移动零
void moveZeroes(int* nums, int numsSize){ int i = 0; while(i<numsSize&&nums[i++] != 0); if(i == numsSize) return ; i--; for(int j = i + 1;j < numsSize;j++){ if(nums[j] != 0) nums[i++] = nums[j]; } for(;i<numsSize;i++) nums[i] = 0; }
303. 区域和检索 - 数组不可变
typedef struct { int sum[20000]; int size; } NumArray; NumArray* numArrayCreate(int* nums, int numsSize) { NumArray * ans= malloc(sizeof(NumArray)); ans->size = numsSize; ans->sum[0] = 0; for(int i = 0;i < numsSize;i++) ans->sum[i+1] = ans->sum[i] + nums[i]; return ans; } int numArraySumRange(NumArray* obj, int left, int right) { return obj->sum[right+1] - obj->sum[left]; } void numArrayFree(NumArray* obj) { free(obj); }
228. 汇总区间
void rever(char *s){ int len = strlen(s); for(int i = 0;i < len/2;i++){ s[i] = s[i] ^ s[len - 1 - i]; s[len - 1 - i] = s[i] ^ s[len - 1 - i]; s[i] = s[i] ^ s[len - 1 - i]; } } char *numtostr(int n){ char * ans = malloc(sizeof(char)*12); if(n==0){ ans[0] = '0',ans[1] = 0; return ans; } int anssize = 0,flag = 1; if(n > 0) flag = 0,n = -n;//转化为负数 while(n){ ans[anssize++] = '0' - n % 10;//处理数字 n/=10; } if(flag) ans[anssize++] = '-'; ans[anssize++] = 0; rever(ans); return ans; } char ** summaryRanges(int* nums, int numsSize, int* returnSize){ char** ans = malloc(sizeof(char*)*numsSize); char fuhao[3] = {"->"}; int anssize = 0; for(int i = 0;i<numsSize;i++){ int temp = i;i++; while(i<numsSize && (long long )nums[i]-(long long )nums[temp] == i - temp) i++; i--; if(i == temp) ans[anssize++] = numtostr(nums[temp]); else{ char * anstemp = malloc(sizeof(char)*25); anstemp[0] = 0; strcat(anstemp,numtostr(nums[temp])); strcat(anstemp,fuhao); strcat(anstemp,numtostr(nums[i])); ans[anssize++] = anstemp; } } *returnSize = anssize; return ans; }
500. 键盘行
char ** findWords(char ** words, int wordsSize, int* returnSize){ char **ans = malloc(sizeof(char*)*wordsSize); int anssize = 0; char s[3][20]={"qwertyuiop","asdfghjkl","zxcvbnm"}; bool hash[3][26]; for(int i = 0;i<3;i++){ memset(hash[i],0,sizeof(hash[i])); for(int j =0;j < strlen(s[i]);j++) hash[i][s[i][j] - 'a'] = true; } for(int i = 0;i<wordsSize;i++){ if(!words[i][0]) continue; int j =-1,k; while(++j >-1){ //寻找第几排 if(words[i][0]<='Z'){ if(hash[j][words[i][0] - 'A']) break; } else if(hash[j][words[i][0] - 'a']) break; } for(k = 1;words[i][k];k++) if(words[i][k] <='Z'){ if(!hash[j][words[i][k] - 'A']) break; } else if(!hash[j][words[i][k] - 'a']) break; printf("%d %d ",j,k); if(!words[i][k]) ans[anssize++] = words[i]; } *returnSize = anssize; return ans; }
