# 109-2 程式設計III 寒假作業
**[509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)**
`code`

int fib(int n){
    if(n==0){
        return 0;
    }
    if(n==1){
        return 1;
    }
    return fib(n-1)+fib(n-2);
}

---

**[1688. Count of Matches in Tournament](https://leetcode.com/problems/count-of-matches-in-tournament/)**
`code`

int numberOfMatches(int n){
    int round = 0;
    while(n>1){
        round+=n/2;
        n = n%2+n/2;
    }
    return round;
}

---

**[1523. Count Odd Numbers in an Interval Range](https://leetcode.com/problems/count-odd-numbers-in-an-interval-range/)**
`code`

int countOdds(int low, int high){
    low%2==0?low++:low;
    high%2==0?high--:high;
    return (high-low)/2+1;
}

---

[1550. Three Consecutive Odds](https://leetcode.com/problems/three-consecutive-odds/)
`code`

bool threeConsecutiveOdds(int* arr, int arrSize){
    if(arrSize<3){
        return 0;
    }
    for(int i = 1;i<arrSize-1;i++){
        if(arr[i-1]%2==1&&arr[i]%2==1&&arr[i+1]%2==1){
            return 1;
        }
    }
    return 0;
}

---

[1480. Running Sum of 1d Array](https://leetcode.com/problems/running-sum-of-1d-array/)
`code`

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* runningSum(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int temp[numsSize];
    int i = 0;
    while(i!=numsSize){
        temp[i] = nums[i];
        int total = 0;
        for(int j = i;j>=0;j--){
            total+=temp[j];
        }
        nums[i] = total;
        i++;
    }
    return nums;
}

---

[1641. Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)
`code`

int countVowelStrings(int n){
    return (n+1)*(n+2)*(n+3)*(n+4)/24;
}

[1672. Richest Customer Wealth
](https://leetcode.com/problems/richest-customer-wealth/)
`code`

int maximumWealth(int** accounts, int accountsSize, int* accountsColSize){
    int total=0;
    int max = 0;
    for(int i = 0;i<accountsSize;i++){
        total=0;
        for(int j = 0;j<*accountsColSize;j++){
            total+=accounts[i][j];
        }
        if(total>max){
            max = total;
        }
    }
    return max;
}

---
[771. Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/)
`code`

int numJewelsInStones(char * jewels, char * stones){
    int total = 0;
    for(int i = 0;i<strlen(jewels);i++){
        for(int j = 0;j<strlen(stones);j++){
            if(jewels[i]==stones[j]){
                total++;
            }
        }
    }
    return total;
}

---
[1365. How Many Numbers Are Smaller Than the Current Number](https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/)
`code`

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int c[numsSize];
    for(int i = 0;i<numsSize;i++){
        c[i]=nums[i];
        nums[i]=0;
    }
    for(int i = 0;i<numsSize;i++){
        for(int j = 0;j<numsSize;j++){
            if(i!=j&&c[i]>c[j]){
                ++nums[i];
            }
        }
    }
    return nums;
}

---
[1528. Shuffle String](https://leetcode.com/problems/shuffle-string/)
`code`

char * restoreString(char * s, int* indices, int indicesSize){
    char copy[indicesSize];
    for(int i = 0;i<indicesSize;i++){
        copy[indices[i]]=s[i];
    }
    for(int i = 0;i<indicesSize;i++){
        s[i] = copy[i];
    }
    return s;
}

---
[709. To Lower Case](https://leetcode.com/problems/to-lower-case/)
`code`

char * toLowerCase(char * str){
    for(int i = 0;i<strlen(str);i++){
        str[i]=tolower(str[i]);
    }
    return str;
}

---
[13. Roman to Integer](https://leetcode.com/problems/roman-to-integer/)
`code`

int romanToInt(char * s){
    int len = strlen(s);
    int total = 0;
    for(int i = 0;i<len;i++){
        if(s[i]=='I'){
            total+=1;
        }
        else if(s[i]=='V'){
            total+=5;
            if(s[i-1]=='I'){
                total-=2;
            }
        }
        else if(s[i]=='X'){
            total+=10;
            if(s[i-1]=='I'){
                total-=2;
            }
        }
        else if(s[i]=='L'){
            total+=50;
            if(s[i-1]=='I'){
                total-=2;
            }
            else if(s[i-1]=='V'){
                total-=10;
            }
            else if(s[i-1]=='X'){
                total-=20;
            }
        }
        else if(s[i]=='C'){
            total+=100;
            if(s[i-1]=='X'){
                total-=20;
            }
            // else if(s[i-1]=='L'){
            //     total-=100;
            // }
        }
        else if(s[i]=='D'){
            total+=500;
            if(s[i-1]=='I'){
                total-=2;
            }
            else if(s[i-1]=='V'){
                total-=10;
            }
            else if(s[i-1]=='X'){
                total-=20;
            }
            else if(s[i-1]=='L'){
                total-=100;
            }
            else if(s[i-1]=='C'){
                total-=200;
            }
        }
        else if(s[i]=='M'){
            total+=1000;
            if(s[i-1]=='C'){
                total-=200;
            }
            // else if(s[i-1]=='D'){
            //     total-=1000;
            // }
        }
    }
    return total;
}

---
[7. Reverse Integer](https://leetcode.com/problems/reverse-integer/)
`code`

int reverse(int x){
    int x1 = 0;
    int a[31]={0};
    int count = 0;
    int temp;
    if(x>=2147483647){
        return 0;
    }
    else if(x<=-2147483648){
        return 0;
    }
    
    if(x>0){
        x1=x;
    }
    else{
        x1 = -x;
    }
    for(int i = 0;x1!=0;i++){
        a[i] = x1 % 10;
        x1/=10;
        count++;
    }
    for(int i = 0;i<count/2;i++){
        temp = a[i];
        a[i] = a[count-1-i];
        a[count-1-i] = temp;
    }
    x1=0;
    for(int i = 0;i<count;i++){
        x1 += a[i]*pow(10,i);
    }
    if(x1>=2147483647){
        return 0;
    }
    else if(x1<=-2147483648){
        return 0;
    }
    if(x>0){
        x = x1;
    }
    else{
        x = -x1;
    }
    return x;
}

---
[704. Binary Search](https://leetcode.com/problems/binary-search/)
`code`

int search(int* nums, int numsSize, int target){
    int low=0;
    int high = numsSize-1;
    while(low<=high){
        int middle=(low+high)/2;
        if(target==nums[middle]){
            return middle;
        }
        else if(target<nums[middle]){
            high=middle-1;
        }
        else{
            low=middle+1;
        }
    }
    return -1;
}

---
[344. Reverse String](https://leetcode.com/problems/reverse-string/)
`code

void reverseString(char* s, int sSize){
    char temp;
    for(int i = 0, j = sSize-1;i<j;i++,j--){
        temp = s[i];
        s[i]=s[j];
        s[j]=temp;
    }
}