[LeetCode]Replace spaces&&disappeared numbers&&split linked list&&product of arrays except itself

​🌠 author:@A Liang joy.
🎆Column:“A Liang loves to write questions”
🎇 Motto: Every outstanding person has a period of silence. That period is a time when a lot of hard work has not yielded results. We call it taking root.


replace spaces

Please implement a function to replace each space in the string s with “%20”.

Example 1:

enter:s = "We are happy."
Output:"We%20are%20happy."

limit:

  • The length of 0 <= s is <= 10000

Idea: First count the number of spaces in the string s, then calculate the total length of the new string based on this number, and finally replace the spaces from back to front.

char* replaceSpace(char* s)
{
    int len = strlen(s);
    int spaceCount = 0;//Count the number of spaces
    int i = 0;
    for(i = 0; i < len; i++)
    {
        if(s[i] == ' ')
        {
            spaceCount++;
        }
    }
    int newLen = len + 2 * spaceCount;//String length
    char* ret = (char*)malloc(sizeof(char)*(newLen + 1));//newLen + 1 is to put '
char* replaceSpace(char* s)
{
int len = strlen(s);
int spaceCount = 0;//Count the number of spaces
int i = 0;
for(i = 0; i < len; i++)
{
if(s[i] == ' ')
{
spaceCount++;
}
}
int newLen = len + 2 * spaceCount;//String length
char* ret = (char*)malloc(sizeof(char)*(newLen + 1));//newLen + 1 is to put '\0'
ret[newLen] = '\0';
int pos = newLen - 1;
//Replace spaces from back to front
for(i = len - 1; i >= 0; i--)
{
if(s[i] == ' ')
{
ret[pos--] = '0';
ret[pos--] = '2';
ret[pos--] = '%';
}
else
{
ret[pos--] = s[i];
}
}
return ret;
}
' ret[newLen] = '
char* replaceSpace(char* s)
{
int len = strlen(s);
int spaceCount = 0;//Count the number of spaces
int i = 0;
for(i = 0; i < len; i++)
{
if(s[i] == ' ')
{
spaceCount++;
}
}
int newLen = len + 2 * spaceCount;//String length
char* ret = (char*)malloc(sizeof(char)*(newLen + 1));//newLen + 1 is to put '\0'
ret[newLen] = '\0';
int pos = newLen - 1;
//Replace spaces from back to front
for(i = len - 1; i >= 0; i--)
{
if(s[i] == ' ')
{
ret[pos--] = '0';
ret[pos--] = '2';
ret[pos--] = '%';
}
else
{
ret[pos--] = s[i];
}
}
return ret;
}
'; int pos = newLen - 1; //Replace spaces from back to front for(i = len - 1; i >= 0; i--) { if(s[i] == ' ') { ret[pos--] = '0'; ret[pos--] = '2'; ret[pos--] = '%'; } else { ret[pos--] = s[i]; } } return ret; }

disappearing numbers

The array nums contains all integers from 0 to n, but one is missing. Please write code to find the missing integer. Is there any way you can do it in O(n) time?


Example 1:

enter:[3,0,1]
Output:2

Example 2:

enter:[9,6,4,2,3,5,7,0,1]
Output:8

Idea 1

First find the sum of 0 ~ noldSum, and then useforLoop to findnumssum of arraynumsSumoldSumandnumsSumThe difference is the missing number.

int missingNumber(int* nums, int numsSize)
{
    int i = 0;
    int numsSum = 0;
    int oddSum = numsSize * (numsSize + 1) / 2;
    for(i = 0; i < numsSize; i++)
    {
        numsSum += nums[i];
    }
    return oddSum - numsSum;
}

Idea 2

Define an integer variableret = 0,useforThe loop willretandnumsXOR in the array, and thenretXOR with numbers from 0 ~ n, nowretJust disappearing numbers. Because except for the disappearing number, which was XORed only once, the other numbers were XORed twice.

int missingNumber(int* nums, int numsSize)
{
    int i = 0;
    int ret = 0;
    for(i = 0; i < numsSize; i++)
    {
        ret ^= nums[i];
    }
    for(i = 0; i <= numsSize; i++)
    {
        ret ^= i;
    }
    return ret;
}

delimited linked list

Given the head node head of a linked list and a specific value x, please separate the linked list so that all nodes less than x appear before nodes greater than or equal to x.

You should preserve the initial relative position of each node in both partitions.

Example 1:


enter:head = [1,4,3,2,5,2], x = 3
Output:[1,2,2,4,3,5]

Example 2:

enter:head = [2,1], x = 2
Output:[1,2]

hint:

  • The number of nodes in the linked list is in the range [0, 200]
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

Idea: Define two sentinel positionssmallHeadandbigHead, in order to facilitate the subsequent connection of nodes. Define three more pointerssmallTailbigTailandcur,usewhileLoop through the linked list. whencur->val < xwhen, executesmallTail->next = cur and smallTail = cur; Otherwise, executebigTail->next = cur and bigTail = cur. After the loop ends, thebigTailorientedNULLsmallTail->nextimplementbigHead->next. Finally, just return the results.

struct ListNode* partition(struct ListNode* head, int x)
{
    if(head == NULL)
        return NULL;
    struct ListNode* smallHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* bigHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* smallTail = smallHead;
    struct ListNode* bigTail = bigHead;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val < x)
        {
            smallTail->next = cur;
            smallTail = cur;
        }
        else
        {
            bigTail->next = cur;
            bigTail = cur;
        }
        cur = cur->next;
    }
    bigTail->next = NULL;
    smallTail->next = bigHead->next;
    struct ListNode* ret = smallHead->next;
    free(smallHead);
    free(bigHead);
    return ret;
}

product of arrays other than itself

Given an integer array nums, return the array answer, where answer[i] is equal to the product of the remaining elements in nums except nums[i].


The question data ensures that the product of all prefix elements and suffixes of any element in the array nums is within the range of 32-bit integers.

Please do not use division and complete this problem within O(n) time complexity.

Example 1:

enter:nums = [1,2,3,4]
Output:[24,12,8,6]

Example 2:

enter:nums = [-1,1,0,-3,3]
Output:[0,0,9,0,0]

Idea: Definitionleftandright, use onceforLoop to perform the product, calculate the product of the data on the left and the data on the right of each position and put it into the return array. After the loop ends, the result is returned.

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* result=(int*)malloc(sizeof(int)*numsSize);
    int left=1,right=1;//left: Multiply from the left, right: Multiply from the right
    for(int i=0; i<numsSize; i++)// Finally, the left and right products of each element are multiplied to obtain the result
    {
        result[i]=1;
    }
    for(int i=0;i<numsSize;i++)
    {
        result[i] *= left;//Multiply the product of its left side
        left *= nums[i];//The product of the numbers on the left
        result[numsSize-1-i] *= right;//Multiply the product on the left
        right *= nums[numsSize-1-i];//The product of the numbers on the right
    }
    *returnSize=numsSize;
    return result;
}

Summarize

The above is the entire content of this blog. If you find it useful, you can support it by clicking three in a row! Thank you everyone!

Related Posts

Shenzhou Loongson GSC3290 adapted to Yutai YT8521S operating instructions

Infinitus Classification

LeetCode 884 Uncommon words in two sentences [String] HERODING’s road to LeetCode

The four major characteristics of C++MySQL database operation statements and transactions

c++ student information management system

Basic operations of sequential stack (super detailed)

Can’t understand the C language code about linked lists? An article allows you to grasp the secondary pointers and deeply understand the various forms of passing parameters in the function parameter list

Gas station – detailed explanation of the problem (violence – overall – greedy)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*