# 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]
Sign in with Wallet
Connect another wallet