力扣(LeetCode)刷题，简单题(第13期)
【摘要】 目录
第1题：字符的最短距离
第2题：棒球比赛
第3题：判定是否互为字符重排
第4题：岛屿的周长
第5题：两个数组的交集
第6题：计算质数
第7题：旋转数组
第8题：二叉树的层平均数
第9题：修建二叉搜索树
第10题：分糖果
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题...
目录
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：字符的最短距离
试题要求如下：
解答思路：
从左向右遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 i - prev。
从右想做遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 prev - i。
这两个值取最小就是答案。
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
int* shortestToChar(char * S, char C, int* returnSize){
-
int tmp1,tmp2;
-
int len = strlen(S);
-
int* ret = (int *)malloc(len * sizeof(int));
-
-
for(int i = 0; i < len; i++)
-
{
-
tmp1 = 0;
-
for(int j = i; j >= 0; j--)
-
{
-
if (S[j] != C) {
-
if (j == 0) {
-
tmp1 = len;
-
} else {
-
tmp1++;
-
}
-
} else {
-
break;
-
}
-
}
-
-
tmp2 = 0;
-
for(int j = i; j < len; j++)
-
{
-
if (S[j] != C) {
-
if (j == len-1) {
-
tmp2 = len;
-
} else {
-
tmp2++;
-
}
-
} else {
-
break;
-
}
-
}
-
-
ret[i] = tmp1 < tmp2 ? tmp1 : tmp2;
-
}
-
-
*returnSize = len;
-
return ret;
-
}
运行效率如下所示：
第2题：棒球比赛
试题要求如下：
解答思路：
堆栈思想。
回答（C语言）：
-
int calPoints(char ** ops, int opsSize){
-
int arr[1000]={0};
-
int score = 0,i = 0,j = 0;
-
-
while(i < opsSize){
-
switch(ops[i][0]){
-
case 'C':
-
arr[j-1]=0;
-
j-=2;
-
break;
-
-
case 'D':
-
arr[j]=arr[j-1]*2;
-
break;
-
-
case '+':
-
arr[j]=arr[j-1]+arr[j-2];
-
break;
-
-
default:
-
//字符串类型转整数类型
-
arr[j]=atoi(ops[i]);
-
break;
-
}
-
-
j++;
-
i++;
-
}
-
-
for(int i=0;i<j;i++){
-
score+=arr[i];
-
}
-
-
return score;
-
}
运行效率如下所示：
第3题：判定是否互为字符重排
试题要求如下：
回答（C语言）：
-
bool CheckPermutation(char* s1, char* s2){
-
int i = 0,j = 0,s1Len = 0,s2Len = 0;
-
s1Len=strlen(s1);
-
s2Len=strlen(s2);
-
-
if(s1Len != s2Len){
-
return false;
-
}
-
-
char letter[26]={0};
-
-
for(i=0;i<s1Len;i++){
-
letter[s1[i]-'a']++;
-
}
-
-
for(i=0;i<s2Len;i++){
-
letter[s2[i]-'a']--;
-
}
-
-
for(i=0;i<26;i++){
-
if(letter[i]!=0){
-
return false;
-
}
-
}
-
-
return true;
-
}
运行效率如下所示：
第4题：岛屿的周长
试题要求如下：
解答思路：
每个岛+4周围四个方向有岛屿则-1。
回答（C语言）：
-
int islandPerimeter(int** grid, int gridSize, int* gridColSize){
-
int circle = 0;
-
-
for (int i = 0; i < gridSize; i++) {
-
for (int j = 0; j < (*gridColSize); j++) {
-
if (grid[i][j] == 1) {
-
circle +=4;
-
if (i > 0 && grid[i-1][j] == 1) {
-
circle--;
-
}
-
if ((i + 1) < gridSize && grid[i + 1][j] == 1){
-
circle--;
-
}
-
if (j > 0 && grid[i][j - 1] == 1) {
-
circle--;
-
}
-
if ((j + 1) < (*gridColSize) && grid[i][j + 1] == 1){
-
circle--;
-
}
-
}
-
}
-
}
-
-
return circle;
-
}
运行效率如下所示：
第5题：两个数组的交集
试题要求如下：
解答思路：
使用哈希表查询：对数组1进行映射，将数组元素作为下标，对散列表相应元素++；遍历数组2，同样将数组元素作为下标，判断该下标处元素是否有数值（在数组1中是否存在）。
回答（C语言）：
运行效率如下所示：
第6题：计算质数
试题要求如下：
解答思路：
质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
厄拉多塞筛法：
回答（C语言）：
-
int countPrimes(int n)
-
{
-
int *isPrime = (int*)malloc(sizeof(int) * n);
-
memset(isPrime, 0, sizeof(int) * n);
-
int cnt = 0;
-
-
for(int i = 2; i < n; i++){
-
if(isPrime[i] == 0){
-
cnt++;
-
for(int j = i + i; j < n; j += i){ //筛去i的倍数
-
isPrime[j] = 1;
-
}
-
}
-
}
-
-
return cnt;
-
}
运行效率如下所示：
第7题：旋转数组
试题要求如下：
解答思路：
使用反转数组的方法，例如k为3时：
原始数组 : 1 2 3 4 5 6 7
反转所有数字后 : 7 6 5 4 3 2 1
反转前 k 个数字后 : 5 6 7 4 3 2 1
反转后 n-k 个数字后 : 5 6 7 1 2 3 4 --> 结果
回答（C语言）：
-
static void reverse(int* nums, int numsSize, int start, int end)
-
{
-
int temp = 0;
-
-
while (start < end)
-
{
-
temp = nums[start];
-
nums[start] = nums[end];
-
nums[end] = temp;
-
start++, end--;
-
}
-
}
-
-
void rotate(int* nums, int numsSize, int k){
-
k = k % numsSize;
-
reverse(nums, numsSize, 0, numsSize - 1);
-
reverse(nums, numsSize, 0, k - 1);
-
reverse(nums, numsSize, k, numsSize - 1);
-
}
运行效率如下所示：
第8题：二叉树的层平均数
试题要求如下：
回答（C语言）：
-
/**
-
* Definition for a binary tree node.
-
* struct TreeNode {
-
* int val;
-
* struct TreeNode *left;
-
* struct TreeNode *right;
-
* };
-
*/
-
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
-
void helper(struct TreeNode* root, double* sum, double* count, int index, int* head){
-
if(root==NULL){
-
return;
-
}
-
sum[index] += root->val;
-
count[index]++;
-
(*head) = fmax(*head, index);
-
helper(root->left, sum, count, index+1, head);
-
helper(root->right, sum, count, index+1, head);
-
}
-
-
double* averageOfLevels(struct TreeNode* root, int* returnSize){
-
int NUM = 10000;
-
double* sum = (double*)calloc(NUM, sizeof(double));
-
double* count = (double*)calloc(NUM, sizeof(double));
-
-
int head = 0;
-
helper(root, sum, count, 0, &head);
-
double* ret = (double*)malloc((head+1)*sizeof(double));
-
for(int i=0; i<head+1; i++) {
-
ret[i] = sum[i]/count[i];
-
}
-
-
*returnSize = head+1;
-
-
return ret;
-
}
运行效率如下所示：
第9题：修建二叉搜索树
试题要求如下：
回答（C语言）：
-
/**
-
* Definition for a binary tree node.
-
* struct TreeNode {
-
* int val;
-
* struct TreeNode *left;
-
* struct TreeNode *right;
-
* };
-
*/
-
-
struct TreeNode* trimBST(struct TreeNode* root, int L, int R){
-
if (NULL == root)
-
{
-
return NULL;
-
}
-
-
if (root->val < L)
-
{
-
return trimBST(root->right, L, R);
-
}
-
-
if (R < root->val)
-
{
-
return trimBST(root->left, L, R);
-
}
-
-
root->left = trimBST(root->left, L, R);
-
root->right = trimBST(root->right, L, R);
-
-
return root;
-
}
运行效率如下所示：
第10题：分糖果
试题要求如下：
回答（C语言）：
-
int cmpfunc (const void * a, const void * b)
-
{
-
return ( *(int*)a - *(int*)b );
-
}
-
-
int distributeCandies(int* candies, int candiesSize){
-
int cou = 0;
-
-
qsort(candies, candiesSize, sizeof(int), cmpfunc);
-
-
for(int i = 0,j = 1;i < candiesSize-1;i++,j = i+1){
-
if(candies[i] != candies[j]){
-
cou++;
-
}
-
}
-
-
cou++;
-
-
if(cou < candiesSize/2){
-
return cou;
-
}
-
-
return candiesSize/2;
-
}
运行效率如下所示：
文章来源: blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/m0_38106923/article/details/106206894
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）