special column

• special column
  • Fundamentals of c language
  • Data structure and algorithm
    • Blog
    • classification
      • data structure
      • algorithm
  • leetcode summary
• Wrong question
  • Interview question 10.02 Modified phrase
  • Roman numeral to integer

Fundamentals of c language

• Two dimensional array

• Usage of sizeof

• Macro definition: Max & min

Data structure and algorithm

Blog

• Use of integer to character conversion in leetcode

• Summary of library functions in C language

• structural morphology

• mathematics

• character string

• Classification of leetcode simple questions

• One dimensional array

classification

data structure

• Linked List

• Tree tree

• Stack & queue

• Hash Table hash table

• Array & matrix array

• String string

• Graph

• Bit operation

• bags

• sets

algorithm

• Two pointer
• Sorting sorting
• Greedy greedy
• Binary Search two points
• Divide and Conquer
• Searching search
• Dynamic programming
• Math math

leetcode summary

• leetcode string type classification and description

TIPS

qsort and memset parameter positions

qsort(str，len，sizeof(int)，cmp)

memset (str, 0, len * sizeof(int)) in bytes

Summary of problem brushing methods

https://zhuanlan.zhihu.com/p/96883783

The algorithm is not to spell IQ, but can be learned through deliberate practice

The difficulty should be gradual

Problem solving:

1. Understand the topic (5 minutes)

2. Analyze and deduce the solution (don't think about how to realize the code and reduce the mental burden)

3. Convert ideas into code (pay attention to algorithm encapsulation)

Huyou topic classification

https://www.zhihu.com/question/280279208

Question brushing method:

• The first time: you can think first, then look at the reference answer brush, and brush it in combination with other people's questions. Think, summarize and master the type, thinking mode and optimal solution of this problem.

• The second time: think first, recall the optimal solution, compare it with the solutions you have written before, and summarize the problems and methods.

• The third time: improve the speed of problem brushing, take out a problem, you can know its investigation focus and problem-solving method, and write the solution in a short time.

Regular summary:

• Summarize according to the topic type: for a class of problems, summarize which problem-solving methods are available, which method is the best, and why.
• Summary key points: if you can't brush some questions many times, you should focus on them, think more about solutions, and constantly practice and strengthen them

Pay attention to optimization

1. Original title

2. Your first solution

3. Online good solution

4. What you can improve

5. Further streamline and optimize your own code until the code is simple (this is a very key step. When you reach this step, you will find that the improvement of your ability is far more than simply solving the problem)

6. The thought gained (or the place learned can be algorithms, data structures or Java features - such as Stream, etc.)

Each topic goes through at least one such iteration. After several times, I have a deeper understanding of each topic. I am confident that I can write the optimal solution for most of the topics, and even the code is optimized (at least more concise than the highest answer in the forum reply).

Wrong question

1. Interview question 10.02 Modified phrase

https://leetcode-cn.com/problems/group-anagrams-lcci/

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
bool ArrayComp(int* x, int* y) {
    for(int i = 0; i < 26; i++) {
        if (x[i] != y[i]) {
            return false;
        }
    }
    return true;
}
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes){
    int len = strlen(strs[0]);
    char*** res = (char***)malloc(sizeof(char**) * strsSize);//You can have no modified phrases
    for (int i = 0; i < strsSize; i++) {
        res[i] = (char**)malloc(sizeof(char*) * strsSize);
        for (int j = 0; j < strsSize; j++) {
            res[i][j] = (char*)malloc(sizeof(char) * len);//len is wrong. The length of each string is not necessarily 3
        }
    }

    //Create a 26 bit dictionary for each string to store the number of occurrences of letters
    char **alpha = (char**)malloc(sizeof(char*) * strsSize);
    for(int i = 0; i < len; i++) {
        alpha[i] = (char*)malloc(sizeof(char) * len);//The data type is wrong. It should be int
        memset(strs[i], sizeof(char) * len, 0);//Length of 26 letters
    }
    memset(alpha, sizeof(char*) * strsSize, 0);

    for (int i = 0; i < strsSize; i++) {
        for (int j = 0; j < strlen(strs[i]); j++) {
            alpha[i][strs[i][j] - 'a']++;
        }
    }

    int comResult;
    //Compare the dictionary order array of each string and output the sequence number of congruence
    for (int i = 0; i < strsSize; i++) {
        if (alpha[i])
        for(int j = i + 1; j < strsSize; j++) {
           comResult = ArrayComp(alpha[i], alpha[j]);
           if (comResult) {
               res[i] = strs[i];
           } 
        }
    }
}

• *returnSize and * * returnColumnSizes

*returnSize represents the line, which can be brought into the sub function through the pointer and then brought out

If it is of type int directly, it will be changed as a local variable, the sub function will end, and the stack will be destroyed (associative swap function)

Therefore, the entry in the main function is & returnSize, and the sub function parameter * returnSize

**returnColumnSizes represents columns. The number of columns corresponding to each row is not fixed, so it needs to be stored in a one-dimensional array. If it is only a one-dimensional array, the assignment in the sub function does not take effect and cannot be brought out. Therefore, it needs to take the address into the parameter like the row, and the address of the one-dimensional array is a secondary pointer.

Reference materials:

https://www.jianshu.com/p/613584a38a08

https://leetcode-cn.com/circle/discuss/V3ozv1/

https://blog.csdn.net/AuthurWhywat/article/details/105510874

Equivalent expression:

Allocate column pointer space

    //returnColumnSizes[0] = malloc(sizeof(int) * strsSize);
    //Equivalent writing: one is from the perspective of array (row pointer) and the other is from the perspective of pointer (address of one-dimensional array), which represents the first address of one-dimensional array name
    *returnColumnSizes = malloc(sizeof(int) * strsSize);

Number of columns written to each row

        //returnColumnSizes[0][*returnSize] = n;// How many columns are there in row * returnsize?
        (*returnColumnSizes)[*returnSize] = n;  //The number of columns is a one-dimensional array, which is declared as a two-dimensional array. Like the number of rows, the one-dimensional array is brought out by taking the address of the one-dimensional array

2. Roman numeral to integer

Hash table: (classic question type: number of letters, key value conversion)

1. Number of letters

   https://leetcode-cn.com/problems/roman-to-integer/submissions/

       while (s[i] != '\0') {
           hashtable[s[i] - 'a']++;
           i++;
       }
   //The for loop is also OK
   

   If it does not meet the meaning of the question, you can write return -1 at the end; Once you encounter a problem that meets the meaning of the question, you can directly return it in the for loop.

2. Key value conversion

• Using the alphabet

https://leetcode-cn.com/problems/roman-to-integer/solution/c-jie-fa-mei-shi-yao-jiu-na-yang-by-ning-junzhi/

    int hashmap[26] ={0};
        hashmap['I'-'A'] = 1;
        hashmap['V'-'A'] = 5;
        hashmap['X'-'A'] = 10;
        hashmap['L'-'A'] = 50;
        hashmap['C'-'A'] = 100;
        hashmap['D'-'A'] = 500;
        hashmap['M'-'A'] = 1000;

• Using two arrays to construct hash table

https://leetcode-cn.com/problems/roman-to-integer/solution/cyu-yan-by-song-hua-niang-jiu/
<<<<<<< HEAD

int ReverseNum(char s)
{
    int i = 0;
    char romanTable[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
    int value[] = {1, 5, 10, 50, 100, 500, 1000};

    while(s != romanTable[i]) {
        i++;
    }

    return value[i];
}

3,8. String to integer (atoi)

https://leetcode-cn.com/problems/string-to-integer-atoi/submissions/

Calculation of the power of 10

The calculation of the power of 10 in C language uses pow(10, x) instead of ^. This is the usage in VB. There will be errors in C language, indicating XOR

Formatted output of different data types

Length range of different data types:

https://blog.csdn.net/lyl0625/article/details/7350045#:~:text=%E5%88%9B%E4%BD%9C%E4%B8%AD%E5%BF%83-,%E5%9C%A8C%E8%AF%AD%E8%A8%80%E4%B8%AD%EF%BC%8Cdouble%E3%80%81long%E3%80%81unsigned%E3%80%81int,%E6%89%80%E5%8D%A0%E5%AD%97%E8%8A%82%E6%95%B0&text=1byte%20%3D%208bit%20%E4%B8%80%E4%B8%AA%E5%AD%97%E8%8A%82,4%E4%B8%AA%E5%AD%97%E8%8A%82long

-65536 ~ 65535, why negative numbers are 1 more than positive numbers?

Since 0 does not have the term - 0, a negative number will be one more than a positive number

https://blog.csdn.net/zggzgw/article/details/53710822

If int and long have the same length in an operating system, use% d

If not, int uses% d, long uses% ld, and longlong uses% lld

About integer array initialization and character array initialization

https://blog.csdn.net/Lucien_zhou/article/details/66529426

In C language, characters are stored according to their corresponding ASCII code. One character is one byte. Character constants can be output with "% d". See the corresponding ASCII code

int a[10] = {0}; // Initialize to integer 0
char a[10] = {0}; // ASCII code 0, corresponding to '\ 0'

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
                   
int main() {
    char str[10] = {48};
    char a[10] = {0};
    printf("%c~", str[0]); // Character '0', corresponding to ascii code 48
    printf("%d-", str[1]); // 48
    printf("%d-", a[1]);	// 0
    printf("%c~", a[0]);	// '\ 0' does not display empty characters, corresponding to NULL
    system("pause");
    return 0;
}

"2 * 10 ^ 19" 2 * 10 ^ 19 is installed with long type and becomes - 9223372036854775808

How to judge overflow

long sum;
(int) sum != sum;

1. Just convert sum to int type to see if there is any change. If there is any change, it means overflow. If sum > int is used_ Max will have an impact, because adding more than long will overflow, bring signed numbers and affect judgment. https://zhuanlan.zhihu.com/p/56203662

2. If you want to use sum > int_ Max needs to be declared as a long type inside the loop. Once it is greater than int type, it returns, instead of converting the whole number like method 1

Optimization:

1. Use the method of pure pointer (do it and be familiar with the relationship between pointer and array)

https://leetcode-cn.com/problems/string-to-integer-atoi/solution/chun-c-by-hua-jia-wang-tie-nan-2/

1. Make boundary judgment inside the loop

https://leetcode-cn.com/problems/string-to-integer-atoi/solution/shuang-100yi-li-jie-si-lu-by-yi-ke-da-ba-zzzp/

https://leetcode-cn.com/problems/implement-strstr/

4,136. Figures that appear only once

int singleNumber(int* nums, int numsSize){
    int hashmap[100000] = {0};
    for (int i = 0; i < numsSize; i++) {
        hashmap[nums[i] + 10000]++;
    }
    for (int j = 0; j < 100000; j++) {
        if (hashmap[j] == 1) {
            return (j - 10000);
        }
    }
    return -1;
}

Error prone point: negative numbers should be considered for non empty integer arrays, and int is a signed number

Improvement points: the number of 100000 is used opportunistically, which is a waste of space

Knowledge points:

1. strlen can only be used for character arrays. The parameter must be char *, which is only used for strings

   https://www.cnblogs.com/zpcdbky/p/5857656.html

2. Find array length

   Main function: sizeof(arr)/sizeof(arr[0])

   Subfunction: the input parameter group name is a pointer. Use the above method to get 1

Optimization:

1. Bit operation, aba = b

5,1249. Remove invalid parentheses

Stack + double pointer

Stack: array, an array that records the position of parentheses. The length is the number of left parentheses

The while writing method of double pointer is used for skip assignment

    while (p1 < len) {
        if (s[p1] != -1) {
            s[p2++] = s[p1++];
        } else {
            p1++;
        }
    }

6,121. The best time to buy and sell stocks

math. The function in H needs to be in c file include < math h>

Returns the larger of two floating-point parameters

result = fmax(max - min, result);

It can also be used for int type size comparison and implicit conversion from low precision to high precision

7,16. Sum of the nearest three

Absolute value: abs

memset related knowledge: values are assigned in bytes

In the array assignment:

char a5[3] = {1}	// After this line of code, the values of array a5 are 1, 0 and 0 respectively

If the number of elements specified during initialization is less than the size of the array, the remaining elements will be initialized to 0

Assignment using memset

memset(a5, 1, 3);

memset operates on bytes, so the following code will not get the results we expect.

int a6[3];
memset(a6, 1, 3 * sizeof(int));    //In 32-bit machines, the values of a6[0]~a6[2] are 16843009.

The reasons are as follows: https://blog.csdn.net/my_offer/article/details/6936242

Assign values to arrays using memcpy

https://blog.csdn.net/Hollay/article/details/88565249

1. Structure

2. Memory copy

3. Assign values one by one

#include<string.h>
int a[20],b[20];
memcpy(a,b,sizeof(a));//Make array a equal to array b

The timeout may be caused by too much printing. You can remove the circular printing