C语言刷题~Leetcode与牛客网简单题

前言

作者：小蜗牛向前冲

名言：我可以接收失败，但我不能接收放弃

 如果觉的博主的文章还不错的话，还请点赞，收藏，关注支持博主。如果发现有问题的地方欢迎*大家在评论区指正。

 为了提高自己编写代码的能力，特意开设刷题专题，记录自己刷题的思路和理解。欢迎*大家的指正。

1 复写零

 思路：

对于这道题目我们很容易想到，进行数组遍历，若发现某个元素为0，则从这个元素之后的元素整体向后移动1个元素的大小，但很快会发现这样效率不高。

下面我将用双指针的方法进行解题：

首先，我们用指针top标记数组的栈顶位置，用指针i标记现在需要放置元素位置，

其次，我们要找到原数组中对应放置在最后位置的元素位置，

最后，在数组最后从该位置元素往前来进行模拟放置即可。

//遍历二遍数组就可以完成任务
void duplicateZeros(int* arr, int arrSize)
{
	int top = 0;//用来标记数组
	int i = -1;//用来标记要放置元素的数组
	//开始第一遍遍历数组
	while (top < arrSize)
	{
		i++;
		if (0 == arr[i])
		{
			top += 2;//找到0top标记要向后跳2个元素
		}
		else
		{
			top++;
		}
	}
	int j = arrSize - 1;
	//判读top标记是否超出数组的范围
	if (top > arrSize)
	{
		arr[j] = 0;//新数组最后一个元素必定为0
		j--;
		i--;
	}
	//开始从后往前进行第二遍遍历
	while (j >= 0)
	{
		arr[j] = arr[i];
		j--;
		//若下个元素为0进行复写
		if (!arr[i])
		{
			arr[j] = arr[i];
			j--;
		}
		i--;//指向下个元素
	}
}

 2 小乐乐与进制转换

 要想将10进制数转转化为6进制数，可以用取余反序法解决。

思路：

将10机制数求余数，将余数存在数组中，在由数组倒序打印就可以了。

#include<stdio.h>

int main()
{
    int n = 0;
    int arr[10] = { 0 };//存放6进制的位数
    int i = 0;
    int j = 0;
    scanf("%d", &n);
    while (n)
    {
        arr[i] = n % 6;// 不断的求出6进制数的位数
        n = n / 6;
        i++;
    }
    //输出
    for (j = i - 1;j >= 0;j--)//注意指这里i要-1
    {
        printf("%d", arr[j]);
    }
    return 0;
}

 3 小乐乐求和

这题的解题思路很简单，用个循环就可以解决，唯一要n输入的范围是1<=n<10^9。

《C和指针》中写过：long与int：标准只规定long不小于int的长度，int不小于short的长度。

所以int于long的范围都可以认为是（-2^31~(2^31-1))，这将有可能不满足n的取值范围,于是我们应该用long long来定义n的取值范围。

#include<stdio.h>

int main()
{
    //输入
    long long n = 0;
    scanf("%llu", &n);
    long long i = 1;
    long long sum = 0;
    while (n >= i)
    {
        sum = sum + i;
        i++;
    }
    //输出
    printf("%llu", sum);//注意这里是以%llu打印
    return 0;
}

 4 小乐乐定闹钟

 这题主要考察了对%与/运算符的用法，我们主要注意时和分都由二位数组成，所以我们要注意进行前导0补齐（%02d）

#include <stdio.h>

int main()
{
    int h = 0;//小时
    int m = 0;//分钟
    int k = 0;//要睡觉的时间
    scanf("%d:%d %d", &h, &m, &k);
    h = ((m+k)/60+h)%24;
    m = (m+k)%60;
    printf("%02d:%02d\n", h, m);
    return 0;
}

5小乐乐与欧几里得

这里我们很容易想到暴力求解，但真的能够通过吗？

#include<stdio.h>

int main()
{
    long long n = 0;
    long long m = 0;
    //输入
    scanf("%lld%lld", &n, &m);
    long long max = n > m ? m : n;//假设m和n中较小数位最大公约数
    long long min = n > m ? n : m;//假设m和n中较大数位最小公倍数
    //求最大公约数和最小公倍数
    while (1)
    {
        if (0 == n % max && 0 == m % max)
        {
            break;//找到最大公约数
        }
        max--;
    }
    while (1)
    {
        if (0 == min % n && 0 == min% m)
        {
            break;//找到最小公倍数
        }
        min++;
    }
    printf("%lld", max + min);
    return 0;
}

这里我们发现，这种算法用时会很长导致解题失败。那么还有更好的算法吗？

下面将为大家介绍用辗转相除法解题

辗转相除法（求最大公约数）：如果有两个数n,m；且n>m,设n/m商q余c,则n和m的最大公约数也是m和c的最大公约数。这样辗转相除，直到余数为0时除式的商（也就相当于n/m时c那个位置的数字）即为最大公约数；

而最小公倍数 = (n*m)/(最大公约数)

这里我们要注意是在求最大公约数的时候，n和m是发生改变了的，所以我们提前存储好他们。

//辗转相除法
int main()
{
    long long n = 0;
    long long m = 0;
    long long tmp = 0;

    scanf("%lld %lld", &n, &m);
    int a = n;
    int b = m;
    while (tmp = a % b)
    {
        a = b;
        b = tmp;
    }
    printf("%lld\n", b + m * n / b);
    return 0;
}

 今天题就刷到这里了，希望大家能在评论积极分享自己的最优解。