C language brush questions ~leetcode and simple questions of niuke.com

Preface

author ： Little snail rushes forward

quotes ： I can accept failure , But I can't accept giving up

  If you think the blogger's article is good , Please give the thumbs-up , Collection , Follow and support bloggers . If you find any problems, you are welcome * Please make corrections in the comments section .

  In order to improve their ability to write code , Specially set up topic brushing , Record your thoughts and understanding of writing questions . welcome * Everybody's correction .

1 Copy zero

  Ideas ：

It is easy for us to think of this topic , Array traversal , If an element is found to be 0, Then move backward from the whole element after this element 1 The size of an element , But it will soon be found that such efficiency is not high .

I'll use The double pointer method Solve the problem ：

First , We use pointers top Mark the stack top position of the array , With a pointer i The tag now needs to be placed at the element location ,

secondly , We need to find The position of the element corresponding to the last position in the original array ,

Last , At the end of the array, you can simulate the placement from the position element forward .

// You can complete the task by traversing the array twice 
void duplicateZeros(int* arr, int arrSize)
{
	int top = 0;// Used to mark an array 
	int i = -1;// The array used to mark the elements to be placed 
	// Start traversing the array for the first time 
	while (top < arrSize)
	{
		i++;
		if (0 == arr[i])
		{
			top += 2;// find 0top Mark to jump back 2 Elements 
		}
		else
		{
			top++;
		}
	}
	int j = arrSize - 1;
	// interpretation top Whether the tag is out of the range of the array 
	if (top > arrSize)
	{
		arr[j] = 0;// The last element of the new array must be 0
		j--;
		i--;
	}
	// Start the second traversal from back to front 
	while (j >= 0)
	{
		arr[j] = arr[i];
		j--;
		// If the next element is 0 Make a copy 
		if (!arr[i])
		{
			arr[j] = arr[i];
			j--;
		}
		i--;// Point to the next element 
	}
}

 2  Little Lele and hexadecimal conversion

  If you want to 10 The hexadecimal number is converted to 6 Hexadecimal number , It can be used The remainder reverse order method is used to solve .

Ideas ：

take 10 Find the remainder of the mechanism number , Save the remainder in the array , Just print in the reverse order of the array .

#include<stdio.h>

int main()
{
    int n = 0;
    int arr[10] = { 0 };// Deposit 6 The number of decimal digits 
    int i = 0;
    int j = 0;
    scanf("%d", &n);
    while (n)
    {
        arr[i] = n % 6;//  Constantly find 6 The number of decimal digits 
        n = n / 6;
        i++;
    }
    // Output 
    for (j = i - 1;j >= 0;j--)// Attention, point here i want -1
    {
        printf("%d", arr[j]);
    }
    return 0;
}

 3  Little Lele asks for peace

The idea of solving this problem is very simple , It can be solved with a cycle , The only thing n The input range is 1<=n<10^9.

《C And a pointer 》 It was written in ：long And int： The standard only stipulates long Not less than int The length of ,int Not less than short The length of .

therefore int On long The scope of can be regarded as （-2^31~(2^31-1)), This will probably not satisfy n Value range of , So we should use long long To define n Value range of .

#include<stdio.h>

int main()
{
    // Input 
    long long n = 0;
    scanf("%llu", &n);
    long long i = 1;
    long long sum = 0;
    while (n >= i)
    {
        sum = sum + i;
        i++;
    }
    // Output 
    printf("%llu", sum);// Note that here is %llu Print 
    return 0;
}

 4  Xiaolele sets the alarm clock

  This question mainly examines the right % And / Usage of operators , We mainly notice that both hours and minutes are composed of two digits , So we should pay attention to leading 0 A filling （%02d）

#include <stdio.h>

int main()
{
    int h = 0;// Hours 
    int m = 0;// minute 
    int k = 0;// Time to sleep 
    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 Little Lele and Euclid

It's easy to think of violent solutions here , But can it really pass ？

#include<stdio.h>

int main()
{
    long long n = 0;
    long long m = 0;
    // Input 
    scanf("%lld%lld", &n, &m);
    long long max = n > m ? m : n;// hypothesis m and n The greatest common divisor of the minor digits 
    long long min = n > m ? n : m;// hypothesis m and n The least common multiple of the larger digit in 
    // Find the greatest common divisor and the least common multiple 
    while (1)
    {
        if (0 == n % max && 0 == m % max)
        {
            break;// Find the greatest common divisor 
        }
        max--;
    }
    while (1)
    {
        if (0 == min % n && 0 == min% m)
        {
            break;// Find the least common multiple 
        }
        min++;
    }
    printf("%lld", max + min);
    return 0;
}

Here we find , This algorithm will take a long time to solve the problem . So is there a better algorithm ？

Next, we will introduce how to solve problems with the method of rolling and dividing

division （ Find the greatest common divisor ）： If there are two numbers n,m; And n>m, set up n/m merchant q more than c, be n and m The greatest common divisor of m and c Maximum common divisor of . This is how you divide , Until the remainder is 0 Quotient of time division （ Which is equivalent to n/m when c The number of that position ） That is to say greatest common divisor ;

And the least common multiple = (n*m)/( greatest common divisor )

Here we should pay attention to finding the greatest common divisor ,n and m It has changed , So we store them in advance .

// division 
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;
}

  That's all for today , I hope you can actively share your best solution in the comments .