目录
第1题:相同的树
第2题:对称二叉树
第3题:二叉树的最大深度
第4题:二叉树的最小深度
第5题:路径总和
第6题:杨辉三角1
第7题:杨辉三角2
第8题:买卖股票的最佳时机1
第9题:买卖股票的最佳时机2
第10题:验证回文串
力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。
第1题:相同的树
试题要求如下:
回答(C语言):
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(!p && !q){ return true; } else if(!p || !q){ return false; } else { if(p->val != q->val){ return false; } else { return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } } }
第2题:对称二叉树
试题要求如下:
回答(C语言):
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isMirror(struct TreeNode* p, struct TreeNode* q) { if(!p && !q) return true; else if(!p || !q) return false; else{ if(p->val == q->val) return isMirror(p->left, q->right) && isMirror(p->right, q->left); else return false; } } bool isSymmetric(struct TreeNode* root){ return isMirror(root, root); }
第3题:二叉树的最大深度
试题要求如下:
回答(C语言):
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int maxDepth(struct TreeNode* root){ if(root == NULL){ return 0; } int left_length = maxDepth(root->left) + 1; int right_length = maxDepth(root->right) + 1; if( left_length >= right_length){ return left_length; }else{ return right_length; } }
第4题:二叉树的最小深度
试题要求如下:
回答(C语言):
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int minDepth(struct TreeNode* root){ if(root == NULL){ return 0; } int left_length = minDepth(root->left) + 1; int right_length = minDepth(root->right) + 1; if( root->left == NULL ){ return right_length; }else if( root->right == NULL ){ return left_length; }else if( left_length >= right_length ){ return right_length; }else{ return left_length; } }
第5题:路径总和
试题要求如下:
回答(C语言):
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool hasPathSum(struct TreeNode* root, int sum){ if(root == NULL) return 0; sum-=root->val; if(root->left == NULL && root->right == NULL) return sum==0?1:0; return hasPathSum(root->left,sum) || hasPathSum(root->right,sum); }
第6题:杨辉三角1
试题要求如下:
回答(C语言):
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ int** generate(int numRows, int* returnSize, int** returnColumnSizes){ //返回的是二维数组,所以需要保存每一行的信息 *returnSize = numRows; //returnColumnSizes储存杨辉三角每一行元素的个数 *returnColumnSizes = (int *)malloc(sizeof(int)*numRows); int** res = (int**)malloc(sizeof(int*)*numRows); for (int i = 0; i < numRows; i++) { (*returnColumnSizes)[i] = i+1; res[i] = (int*)malloc(sizeof(int)*(i+1)); res[i][0] = 1; res[i][i] = 1; for (int j = 1; j < i; j++) { res[i][j] = res[i-1][j] + res[i-1][j-1]; } } return res; }
第7题:杨辉三角2
试题要求如下:
回答(C语言):
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* getRow(int rowIndex, int* returnSize){ *returnSize = rowIndex + 1; int* p = (int*)malloc(sizeof(int) * (rowIndex + 1)); int i, j, k = 0; for(i = 0; i <= rowIndex; i++){ p[k++] = 1; for(j = i - 1; j >= 1; j--){ p[j] += p[j-1]; } } return p; }
第8题:买卖股票的最佳时机1
试题要求如下:
回答(C语言):
/** * i指向当前遍历的值,min指向当前遍历过的值中的最小值,max表示当前的最大利润。 * 当prices[i] < min,更新,否则判断prices[i] - min是否大于max,然后更新max */ int maxProfit(int* prices, int pricesSize){ if(pricesSize<=0) return 0; int min=prices[0],max = 0; for(int i = 0; i < pricesSize; i++){ if(prices[i] < min){ min = prices[i]; } else if(prices[i] - min > max){ max = prices[i] - min; } } return max; } 第9题:买卖股票的最佳时机2 试题要求如下: 回答(C语言): int maxProfit(int* prices, int pricesSize){ int profit=0; for(int i=0;i<pricesSize-1;i++) if(prices[i]<prices[i+1]) profit+=prices[i+1]-prices[i]; return profit; }
第10题:验证回文串
试题要求如下:
回答(C语言):
bool isPalindrome(char * s){ int i = 0; int len = strlen(s); int j = len - 1; while (i < j) { if ((int)isalnum(s[i]) == 0) { i++; continue; } if ((int)isalnum(s[j]) == 0) { j--; continue; } if (tolower(s[i]) != tolower(s[j])) { return false; } i++; j--; } return true; }