当前位置：网站首页>Niuke network programming problem - [wy22 Fibonacci series] and [replace spaces] detailed explanation

Niuke network programming problem - [wy22 Fibonacci series] and [replace spaces] detailed explanation

2022-07-29 05:35:00 【Gancheng なつき】

꧁ Hello, everybody ！ It is a great honor to have your visit , Let's have a long way to go in programming ！꧂
* Blog column ：【 Niuke. Com 】*
Introduction to this article ： Explain the test questions of niuke.com in detail -【WY22 Fibonacci The sequence 】 And 【 Replace blank space 】！
Get to know the author ： Aspire to be a great programmer , Xiaobai, who is currently a sophomore in College .
Inspirational terms ： The tediousness of programming , Let's study together and become interesting ！

Text begins

Catalog

Preface

【WY22 Fibonacci The sequence 】

【 Replace blank space 】

Preface

After a period of study C Advanced language content , Ushered in a test , It's a pity that I still haven't come up with a solution to the last two programming problems , And write the complete code ！ After listening to the teacher's explanation , And my understanding , You should master the ideas and methods of solving problems , Now I will share the content of these two problems, the solution and the source code ！

【WY22 Fibonacci The sequence 】

Topic explanation

describe
Fibonacci Sequence is defined like this ：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
therefore ,Fibonacci A sequence of numbers is like this ：0, 1, 1, 2, 3, 5, 8, 13, ..., stay Fibonacci The numbers in a sequence are called Fibonacci Count . To give you one N, You want it to be a Fibonacci Count , At each step you can put the current number X Turn into X-1 perhaps X+1, Now I'll give you a number N How many steps does it take at least to change into Fibonacci Count .
Input description ：
The input is a positive integer N(1 ≤ N ≤ 1,000,000)
Output description ：
Output a minimum number of steps to Fibonacci Count "
Example 1
Input ：
15
Copy output ：
2

This is a campus recruitment question from Niuke , We should all be familiar with Fibonacci numbers , And this problem is how to input a number X , become X-1 perhaps X+1, Make yourself a Fibonacci number , And it takes at least a few steps to become .

Niuke topic link ：https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=122&tqId=33668&ru=/exam/oj

Their thinking

Let's initialize the first two numbers of Fibonacci number , Then there is Fibonacci number c Just replace it , such as ：

int a=0;
int b=1;
int c=a+b;
Find the Fibonacci number in the following with the method of circulation
while(1)
{
c=a+b;
a=b;
b=c;
}
Form like this .

Let's assume that the number we enter is N, And this number falls on 【a,b】 Between , When N==b when , We should go back to 0, When N<b when , We use it | N-a |（ The absolute value ） And | N-b |（ The absolute value ） Compare , Who's the one who's the one who's the one who's the one who's the one who's the one who's the one who's the one who's the one ！

The illustration ：

Source code

#include<stdio.h>
#include<math.h>
int main()
{
    int N=0;
    scanf("%d",&N);// The number you input 
    int a=0;
    int b=1;
    int c=a+b;// Definition c
    while(1)
    {
        if(N==b)// This number is directly Fibonacci number hour 
        {
            printf("0\n");
            break;
        }
        else if(N<b)
        {
           if(abs(a-N)>abs(b-N)) // Be careful  abs It's absolute , A reference header file is required 
           {
               printf("%d\n",abs(b-N));// Output small 
           }
            else
            {
                printf("%d\n",abs(a-N));//
            }
            break;
        }
        c=a+b;// Find the Fibonacci number behind 
        a=b;
        b=c;
    }
    return 0;
}

【 Replace blank space 】

Topic explanation

describe
Please implement a function , Put a string s Replace each space in with “%20”.
for example , When the string is We Are Happy. The replaced string is We%20Are%20Happy.
Data range :0 \le len(s) \le 1000 \0≤len(s)≤1000 . Ensure that the characters in the string are capitalized English letters 、 One of lowercase letters and spaces .
Example 1
Input ：
"We Are Happy"
Copy the return value ：
"We%20Are%20Happy"
Copy
Example 2
Input ：
" "
Copy the return value ：
"%20"

Niuke topic link ：https://www.nowcoder.com/questionTerminal/4060ac7e3e404ad1a894ef3e17650423

Their thinking

Ideas ： Let's go through it from the beginning , See how many spaces there are , Every time a space is encountered, the string +2 once , Suppose two subscripts , One for end1 At the end of the original string , The other subscript is end2 Put at the end of the lengthened string , Every time when end1-- When , When it's not a space ,str[end2]=str[end1], Replace , When end1-- When you encounter a space , send
str[end2--]='0';// meanwhile -- once
str[end2--]='2';
str[end2--]='%';
end1--;
When there is no space in front ,end1 Meeting ==end2, This is the condition for the cycle to stop ！

The illustration ：

Source code

class Solution {
public:
	void replaceSpace(char *str,int length) {
        // Go through it first   see   The number of spaces 
        char* ps=str;
        int count=0;
        while(*ps!='\0')
        {
            if(*ps==' ')
            count++;
            ps++;
        }
        int end1=length-1;// Define the subscript at the end of the original 
        int end2=length+count*2-1;// End subscript after lengthening 
        while(end1!=end2)
        {
            if(str[end1]!=' ')
            {
                str[end2--]=str[end1--];
            }
            else{
                
               str[end2--]='0';
                str[end2--]='2';
                str[end2--]='%';
                end1--;
            }
        }
	}
};