目录
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：两数之和IV—输入BST
试题要求如下：
解答思路：
1、使用中序遍历把结果存在数组中；
2、用双指针(即下标)，来找对应结果是否存在 i指向最小，j指向最大。若i+j小于目标值，那么i++，i+j大于>目标值，则j--。
回答（C语言）：
-
#define Maxsize 10000
-
-
void inorder(struct TreeNode* root,int *nums,int* length);
-
-
bool findTarget(struct TreeNode* root, int k){
-
int i=0,j=-1; //j记录最大值的下标(即数组最后一个元素)，把其指针传给inorder函数
-
int* nums=(int*)malloc(Maxsize*sizeof(int));
-
-
inorder(root,nums,&j);
-
-
while(i<j) //循环判断数组中是否存在两数之和等于k的情况
-
{
-
if(nums[i]+nums[j]==k) return true;
-
else if(nums[i]+nums[j]<k) i++;
-
else j--;
-
}
-
return false;
-
}
-
-
void inorder(struct TreeNode* root,int *nums,int* length){ //递归中序遍历二叉搜索树，并且把结果存在数组中
-
if(root==NULL) return;
-
inorder(root->left,nums,length);
-
nums[++(*length)]=root->val;
-
inorder(root->right,nums,length);
-
}
运行效率如下所示：
第2题：柠檬水找零
试题要求如下：
回答（C语言）：
-
bool lemonadeChange(int*a, int n)
-
{
-
if (a == NULL || n <= 0) {
-
return false;
-
}
-
-
int s5 = 0, s10 = 0, s20 = 0;
-
-
for (int i = 0; i < n; i++) {
-
switch (a[i]) {
-
case 20: // 给20找15元
-
if (s10 > 0 && s5 > 0) {
-
s20++, s10--, s5--;
-
continue; // 找开了
-
}
-
if (s5 > 3) {
-
s20++, s5 -= 3;
-
continue; // 找开了
-
}
-
return false;
-
case 10: //给10元找5元
-
if (s5 > 0) {
-
s10++, s5--;
-
continue; // 找开了
-
}
-
return false;
-
case 5: // 给5元
-
s5++;
-
continue; // 不找钱
-
default: // 其他都失败
-
return false;
-
}
-
}
-
-
return true;
-
}
运行效率如下所示：
第3题：左叶子之和
试题要求如下：
回答（C语言）：
-
/**
-
* Definition for a binary tree node.
-
* struct TreeNode {
-
* int val;
-
* struct TreeNode *left;
-
* struct TreeNode *right;
-
* };
-
*/
-
-
int sumOfLeftLeaves(struct TreeNode* root){
-
if(!root) return 0;
-
-
int sum=0;
-
-
if(root->left){
-
if(!root->left->left&&!root->left->right){
-
sum+=root->left->val;
-
}
-
else{
-
sum+=sumOfLeftLeaves(root->left);
-
}
-
}
-
-
if(root->right){
-
sum+=sumOfLeftLeaves(root->right);
-
}
-
-
return sum;
-
}
运行效率如下所示：
第4题：第K个缺失的正整数
试题要求如下：
回答（C语言）：
-
int findKthPositive(int* arr, int arrSize, int k){
-
int i = 0, cnt=0, hash[10000] = {0};
-
-
for(i=0;i<arrSize;i++)
-
{
-
hash[arr[i]]++; //记录出现次数，arr[i]对应下标的hash表值hash[arr[i]]就不会为0
-
}
-
for(i=1;i<10000;i++){
-
if(hash[i]==0){
-
cnt++;
-
}
-
if(cnt==k){ //找到第k个为0的元素,它也就是第k个没有出现的元素，返回对应下标即可
-
break;
-
}
-
}
-
-
return i;
-
}
运行效率如下所示：
第5题：反转字符串2
试题要求如下：
回答（C语言）：
-
char * reverseStr(char * s, int k){
-
//每2k个翻转前k个
-
//不足2k但大于等于1k，翻转前k个字符剩下的不变
-
//小于k个字符，全部翻转
-
int len = strlen(s);
-
-
for(int i=0; i<len; i+=2*k){
-
int left = i;
-
int right = (i + k - 1 < len) ? i + k - 1 : len - 1;
-
-
while(left<right){
-
char c = s[left];
-
s[left++] = s[right];
-
s[right--] = c;
-
}
-
}
-
-
return s;
-
}
运行效率如下所示：
第6题：最小移动次数使数组元素相等
试题要求如下：
解题思路：
n - 1个数加1即1个数减1，因此只需算sum(nums) - numsSize * min。
回答（C语言）：
-
int minMoves(int* nums, int numsSize){
-
int ret = 0;
-
int min = nums[0];
-
for(int i = 0;i < numsSize;i++){
-
if(nums[i] < min){
-
min = nums[i];
-
}
-
}
-
for(int i = 0;i < numsSize;i++){
-
ret = ret + nums[i] - min;
-
}
-
return ret;
-
}
运行效率如下所示：
第7题：分发饼干
试题要求如下：
解题思路：
采用贪心算法的思路，此问题的贪心选择是“先把胃口最小的孩子满足，再满足之后的，如果当前胃口最小的孩子都没满足那么已经终止分配了”。
回答（C语言）：
-
int cmp(const void *a, const void *b) {
-
return (*(int*)a - *(int*)b);
-
}
-
-
int findContentChildren(int* g, int gSize, int* s, int sSize){
-
qsort(g, gSize, sizeof(int), cmp);
-
qsort(s, sSize, sizeof(int), cmp);
-
-
int i = 0, j = 0;
-
int count = 0;
-
-
while (i < gSize && j < sSize) {
-
if (g[i] <= s[j]) {
-
i++;
-
count++;
-
}
-
j++;
-
}
-
-
return count;
-
}
运行效率如下所示：
第8题：二叉树的最小深度
试题要求如下：
解题思路：
1、二叉树为空树，最小深度为0；
2、二叉树不为空树，两子树均不为空，获取左右子树的最小深度，取最小的那个加1；
3、二叉树不为空树，但两子树其中之一为空，最小深度为子树不为空的最小深度加1。
回答（C语言）：
-
/**
-
* Definition for a binary tree node.
-
* struct TreeNode {
-
* int val;
-
* struct TreeNode *left;
-
* struct TreeNode *right;
-
* };
-
*/
-
-
#define min(A, B) ((A) < (B) ? (A) : (B))
-
int minDepth(struct TreeNode* root){
-
if (root == NULL) {
-
return 0;
-
}
-
int left = minDepth(root->left);
-
int right = minDepth(root->right);
-
-
return (left && right) ? min(left, right) + 1 : left + right + 1;
-
}
运行效率如下所示：
第9题：消失的数字
试题要求如下：
回答（C语言）：
-
int missingNumber(int* nums, int numsSize){
-
int sum = 0;
-
-
for(int i = 0; i < numsSize; i++){
-
sum += nums[i];
-
}
-
-
return ((numsSize * (1 + numsSize))/2) - sum;
-
}
运行效率如下所示：
第10题：多数元素
试题要求如下：
解答思路：
摩尔投票法，通过一个计数变量s，来观察哪一个数最后不是0即为majority;相同加，不相同减，变为0后换下一个。
回答（C语言）：
-
int majorityElement(int* nums, int numsSize){
-
int s = 1;
-
int maj = nums[0];
-
-
for (int i = 1; i < numsSize; i++) {
-
if (maj == nums[i]){
-
s++;
-
}
-
else {
-
s--;
-
}
-
if (s == 0) {
-
maj = nums[i + 1];
-
}
-
}
-
-
return maj;
-
}
运行效率如下所示：
文章来源: handsome-man.blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：handsome-man.blog.csdn.net/article/details/108002140