# special column

## 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

• 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

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

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++) {
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
}

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
```

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/

```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:

-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

Added by johnska7 on Tue, 08 Mar 2022 00:52:57 +0200