目录
力扣(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;
-
}
运行效率如下所示：
转载：https://blog.csdn.net/m0_38106923/article/details/106206894
查看评论