---
# System prepended metadata

title: Practice in C
tags: [linux2020, c language]

---

# Practice in C
###### tags: `linux2020` `c language`
## leetCode (EASY): 104. Maximum Depth of Binary Tree [[link]](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

**Note**: A leaf is a node with no children.

**Example**:

Given binary tree `[3,9,20,null,null,15,7]`,
```
    3
   / \
  9  20
    /  \
   15   7
```



My code right-behind have ***time limit exceeded*** problem which is really ***bad example*** for recursive funtion.
```cpp=
int countDepth(struct TreeNode* root){
    if((root->left != NULL)&&(root->right!=NULL)){ 
        if(countDepth(root->left) > countDepth(root->right)){//<--WHICH IS REALLY BAD
            return countDepth(root->left)+1; //<--WHICH IS REALLY BAD
        }
        else{
            return countDepth(root->right)+1; //<--WHICH IS REALLY BAD
        }
    }
    else if((root->left == NULL)&&(root->right!=NULL)){
        int sum = countDepth(root->right);
        return sum + 1;
    }
    else if((root->left != NULL)&&(root->right==NULL)){
        int sum = countDepth(root->left);
        return sum + 1;
    }
    else{
        return 0;
    }
}
```

You should always catch your return value(from function) when function are recursing itself. The **better answer** is like the code below:
```cpp=
int countDepth(struct TreeNode* root){
    if((root->left != NULL)&&(root->right!=NULL)){
        int left = countDepth(root->left);//<--WHICH IS GOOD EXAMPLE
        int right = countDepth(root->right);//<--WHICH IS GOOD EXAMPLE
        if(left > right){//<--WHICH IS GOOD EXAMPLE
            return left+1;//<--WHICH IS GOOD EXAMPLE
        }
        else{
            return right+1;//<--WHICH IS GOOD EXAMPLE
        }
    }
    else if((root->left == NULL)&&(root->right!=NULL)){
        int sum = countDepth(root->right);
        return sum + 1;
    }
    else if((root->left != NULL)&&(root->right==NULL)){
        int sum = countDepth(root->left);
        return sum + 1;
    }
    else{
        return 0;
    }
}
```
This movement can save lots of excuting time, make your program **run faster**. 

---
## C programing skill 0
### Call by address in C
```cpp=
void myfunc(int* value){
    *value = 777;
}

int main(){
    int num = 0;
    myfunc(&num);
    printf("%d",num);
    return 0;
}
```
Guess what? Yeee~ You got **777**. The part need to point out is that `&` mark can extract the pointer address for `num`.

---
## leetCode (MEDIUM): 338. Counting Bits [[link]](https://leetcode.com/problems/counting-bits/)
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

**Example 1**:
```
Input: 2
Output: [0,1,1]
```
**Example 2**:
```
Input: 5
Output: [0,1,1,2,1,2]
```
> When I solve this problem in **C language on LeetCode**, I encounting a ERROR：
> ``` ==29== ERROR：AddressSanitizer: heap-buffer-overflow on address...```
> The reason why this error heppend is the [rule of AddressSanitizer](https://blog.csdn.net/zhangpeterx/article/details/88775434). Thus, the best way to fix this error is change your ```<=```,```>=``` mark to ```<```,```>``` in all your for loop and carefully check your dynamic memory have any overflow or not. [Reference](https://blog.csdn.net/lym940928/article/details/89678727)

Anyway, my solution is：
```cpp=
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
int* decToBin(int num, int* mSize){
    int i=0;
    int *arr1 = malloc(sizeof(int)*num);
    while(num>0){
        arr1[i] = num%2;
        i = i + 1;
        num = num/2;
    }
    int *arr2 = malloc(sizeof(int)*i);
    int k = 0;
    for(;i>0;i--){
        arr2[k] = arr1[i-1];
        k=k+1;
    }
    *mSize = k;
    free(arr1);
    return arr2;
}

int countBinary(int* arr,int mSize){
    int i = 0;
    int count =0;
    for(;i<mSize;i++){
        if(arr[i]==1){
            count ++ ;
        }
    }
    return count;
}

int* countBits(int num, int* returnSize){
    *returnSize = num+1;
    int i = 0;
    int mySize=0;
    int *ansArray = malloc(sizeof(int)*(num+1));
    for(;i<(num+1);i++){
        int* myBinary = decToBin(i,&mySize);
        int countNum = countBinary(myBinary,mySize);
        ansArray[i] = countNum;
    }
    return ansArray;
}
```
As you can see, my code is very simple, but **it is little bit longer**, compare to those code which also have good performance from the Leetcode website like：
```cpp=
int* countBits(int num, int *returnSize){
    num++;
    *returnSize = num;
    int* arr = (int*)malloc(sizeof(int)*num);
    arr[0] = 0;
    for(int i = 1; i < num; i++){
        arr[i] = (i&1)? arr[i>>1]+1 : arr[i>>1]; 
    }
    return arr;
}
```
How can I improve my code like this one？ Learn the skill below：

---
## C programing skill 1
### Question mark in C
e.g. 
```cpp=
x == 3 ? x++ : x--;
```
Do you know what those code means? It actually means：
```cpp=
if (x == 3) {
	x++;
}
else {
	x--;
}
```
Assume that you already have the code below：
```cpp=
int* countBits(int num, int *returnSize){
    num++;
    *returnSize = num;
    int* arr = (int*)malloc(sizeof(int)*num);
    arr[0] = 0;
    for(int i = 1; i < num; i++){
        if(arr[i] == i&1){
            arr[i/2]+1;
        }
        else{
            arr[i/2];
        }
    }
    return arr;
}
```
You can use this question mark skill and turn it to：
```cpp=
int* countBits(int num, int *returnSize){
    num++;
    *returnSize = num;
    int* arr = (int*)malloc(sizeof(int)*num);
    arr[0] = 0;
    for(int i = 1; i < num; i++){
        arr[i] = (i&1)? arr[i>>1]+1 : arr[i>>1]; 
    }
    return arr;
}
```
Cool~ right?
### NULL pointer
```cpp=
int *testCase = 0;
printf("%p %s\n",testCase,testCase);
testCase = NULL;
printf("%p %s",testCase,testCase);
```
The output is：
```
0000000000000000 (null)  
0000000000000000 (null)  
```
Yes, for pointer, zero is equals to null.
### The length of array
```cpp=
char* ss = "0123456789";
sizeof(ss)// 結果 4 ＝＝＝》ss 是指向字元串常量的字元指針，sizeof 獲得的是一個指針的之所占的空間,應該是長整型的，所以是 4。
sizeof(*ss)// 結果 1 ＝＝＝》*ss 是第一個字元 其實就是獲得了字元串的第一位 '0' 所占的內存空間，是 char 類型的，占了 1 位
strlen(ss)//結果 10  ＝＝＝》 如果要獲得這個字元串的長度，則一定要使用 strlen。strlen 用來求字元串的長度；而 sizeof 是用來求指定變量或者變量類型等所占內存大小。
```
### Preparing fxxk hard by valgrind
```cpp=
int main(){
    char* inputArr = malloc(sizeof(char)*101);
    int len = strlen(inputArr); //the problem caused by strlen
    printf("The length of char array before input is :%d",len);
    printf("\nSister, you better wake up and input string : ");
    fgets(inputArr,100,stdin);
    //fputs(inputArr,stdout);
    len = strlen(inputArr);
    printf("\nThe length of char array after input is :%d\n",len);
    int i =0;
    for(;i<len;i++)
        printf(" %c",inputArr[i]);
    printf("Show again : %s",inputArr);
    free(inputArr);
    return 0;
}
```
**Result** : 
```
The length of char array before input is :0
Sister, you better wake up and input string : I hate myself for not putting enough effort in coding.

The length of char array after input is :55
 I   h a t e   m y s e l f   f o r   n o t   p u t t i n g   e n o u g h   e f f o r t   i n   c o d i n g . 
Show again : I hate myself for not putting enough effort in coding.
```
Sure, you can compile and run it as usual, but you heard that sound of memory leaking? I heard it this time. Then, I check my @#$% code with valgrind and get one error named **jump or move depends on uninitialised value(s)**. Great ! 
```
$ valgrind --leak-check=full --log-file=vglog --track-origins=yes ./a.out 
$ cat valgrind
```

```
==5737== Memcheck, a memory error detector
==5737== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5737== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5737== Command: ./a.out
==5737== Parent PID: 18796
==5737== 
==5737== Conditional jump or move depends on uninitialised value(s)
==5737==    at 0x4C32CF9: strlen (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5737==    by 0x10884B: main (in /home/huang/JserV/JserV_practice/arrayToTree/a.out)
==5737==  Uninitialised value was created by a heap allocation
==5737==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5737==    by 0x10883B: main (in /home/huang/JserV/JserV_practice/arrayToTree/a.out)
==5737== 
==5737== 
==5737== HEAP SUMMARY:
==5737==     in use at exit: 0 bytes in 0 blocks
==5737==   total heap usage: 3 allocs, 3 frees, 2,149 bytes allocated
==5737== 
==5737== All heap blocks were freed -- no leaks are possible
==5737== 
==5737== For counts of detected and suppressed errors, rerun with: -v
==5737== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
```
To slove this, I know the two ways I can choose.
1. Do not using **strlen** to the **NULL-string**. 
2. Using **calloc** instand of the **malloc**, because calloc set the initialised value (0) for every space you declared. 

**Result 1.**
```cpp=
int main(){
    char* inputArr = malloc(sizeof(char)*101);
    // int len = strlen(inputArr);
    // printf("\nThe length of char array is :%d",len);
    printf("\nSister, you better wake up and input string: ");
    fgets(inputArr,100,stdin);
    fputs(inputArr,stdout);
    int len = strlen(inputArr);
    printf("\nThe length of char array is :%d",len);
    int i =0;
    for(;i<len;i++)
        printf("\nwhat %c",inputArr[i]);
    printf("\n%s",inputArr);
    free(inputArr);
    return 0;
}
```
**Result 2.**
```cpp=
int main(){
    char* inputArr = calloc(101,sizeof(char));
    int len = strlen(inputArr);
    printf("\nThe length of char array is :%d",len);
    printf("\nSister, you better wake up and input string: ");
    fgets(inputArr,100,stdin);
    fputs(inputArr,stdout);
    len = strlen(inputArr);
    printf("\nThe length of char array is :%d",len);
    int i =0;
    for(;i<len;i++)
        printf("\nwhat %c",inputArr[i]);
    printf("\n%s",inputArr);
    free(inputArr);
    return 0;
}
```
```
         ---
         
==6041== All heap blocks were freed -- no leaks are possible
==6041== 
==6041== For counts of detected and suppressed errors, rerun with: -v
==6041== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
Yeah, 0 errors. World piece... peace of cake?  My english suck...
### The type size never remember in my tiny brain


| Type | 32-bits System| 64-bits System|
| -------- | -------- | -------- |
| int    | | 4 bytes |
| char   | | 1?
I told you I never remember.
> [name=Huang Yu Hsuan]  [time=Tue, Mar 3, 2020 1:14 AM]