---
# System prepended metadata

title: '**109-2 程式設計III 寒假作業**'

---

# **109-2 程式設計III 寒假作業**
344. Reverse String
![](https://i.imgur.com/m7WbfAa.png)
![](https://i.imgur.com/jmn9t8Q.png)
code
```c
void reverseString(char* s, int sSize){
    int i,j;
    char temp;
    for(i=0,j=sSize-1;i<j;i++,j--){
        temp=s[i];
        s[i]=s[j];
        s[j]=temp;
    }
}
```

38. Count and Say
![](https://i.imgur.com/3qgal85.png)
![](https://i.imgur.com/qjslGYz.png)
code
```c
char * countAndSay(int n){
    char *str1,*str2;
	str1=(char*)malloc(sizeof(char)*99999);
	str2=(char*)malloc(sizeof(char)*99999);
	memset(str1,0,99999);
	memset(str2,0,99999);
	strcpy(str1,"1");
	for(int i=1;i<n;i++)
	{
		int count=1,i=0,j=0;
	while(str1[i+1]!='\0')
	{
		if(str1[i]==str1[i+1])
		{
			i++;
			count++;
		}
		else
		{
			str2[j++]=count+'0';
			str2[j++]=str1[i]; 
			i++;
			count=1;
		}
	}
	 
	str2[j++]=count+'0'; 
	str2[j++]=str1[i];
		strcpy(str1,str2);
	}
	free(str2);
	return str1; 
}
```

1. Two Sum
![](https://i.imgur.com/SRMg0al.png)
![](https://i.imgur.com/bU6V0tN.png)
code
```c
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i = 0, j = 0;
    int n = numsSize;
    int* result = NULL;
    for(i = 0; i < n; i++) {
        for(j = i + 1; j < n; j++) {
            if(target == nums[i] + nums[j]) {
                result = (int*)malloc(sizeof(int) * 2);
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    return result;
}
```

709. To Lower Case
![](https://i.imgur.com/NTOUntN.png)
![](https://i.imgur.com/eAsngWh.png)
code
```c
char * toLowerCase(char * str){
    for(int i=0;i<strlen(str);i++){
        if(str[i]>='A'&&str[i]<='Z'){
            str[i]=str[i]+32;
        }
    }
    return str;
}
```

704. Binary Search
![](https://i.imgur.com/YW6qM8w.png)
![](https://i.imgur.com/Z04X2QR.png)
code
```
int search(int* nums, int numsSize, int target){
    for(int i=0;i<numsSize;i++){
        if(nums[i]==target){
            return i;
        }
    }
    return -1;
}
```

13. Roman to Integer
![](https://i.imgur.com/fBwGz0u.png)
![](https://i.imgur.com/16am6ro.png)
code
```c
int romanToInt(char * s){
    int i,p = 0,numslen=0;
        int sum = 0;
        int* nums = (int*)malloc(30 * sizeof(int));

        while (s[p] != '\0')
        {
            if (s[p] == 'M')
                nums[p] = 1000;
            else if (s[p] == 'D')
                nums[p] = 500;
            else if (s[p] == 'C')
                nums[p] = 100;
            else if (s[p] == 'L')
                nums[p] = 50;
            else if (s[p] == 'X')
                nums[p] = 10;
            else if (s[p] == 'V')
                nums[p] = 5;
            else if (s[p] == 'I')
                nums[p] = 1;
            p++;
        }
        numslen=p;

        for (i = 0; i < numslen; i++)
        {
            if (nums[i + 1] > nums[i])
                sum -= nums[i];
            else
                sum += nums[i];
        }

        return sum;  
}
```

771. Jewels and Stones
![](https://i.imgur.com/1Bf5P94.png)
![](https://i.imgur.com/u8C9CqM.png)
code
```c
int numJewelsInStones(char * jewels, char * stones){    
    int sum;
    for(int i=0;i<strlen(stones);i++){
        for(int j=0;j<strlen(jewels);j++){
            if(jewels[j]==stones[i]){
                sum++;
            }
        }
    }
    return sum;
}
```

509. Fibonacci Number
![](https://i.imgur.com/YEKEODn.png)
![](https://i.imgur.com/3OlmTEP.png)
code
```c
int fib(int n){
    if (n <= 1) return n;
        int a = 0, b = 1;
        for (int i = 2; i <= n; ++i) {
            int sum = a + b;
            a = b;
            b = sum;
        }
        return b;
}
```

1480. Running Sum of 1d Array
![](https://i.imgur.com/jCzfQGi.png)
![](https://i.imgur.com/ghExdzY.png)
code
```c
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* runningSum(int* nums, int numsSize, int* returnSize){
    int *res = (int*)malloc(numsSize * sizeof(int));
    memset(res, 0, numsSize);

    *returnSize = numsSize;

    int i = 0;
    int j = 0;
    int sum = 0;

    for(i = 0;i < numsSize;i++){
        sum = 0;
        for(j = 0; j <= i;j++){
            sum += nums[j];
        }
        res[i] = sum;
    }
    
    return res;
}
```

1528. Shuffle String
![](https://i.imgur.com/kVHykep.png)
![](https://i.imgur.com/2R3mCnO.png)
code
```c
char * restoreString(char * s, int* indices, int indicesSize){
    char *res = (char*)malloc(sizeof(char) * indicesSize);

    int i = 0;
    
    for(i = 0; i < indicesSize;i++){
        res[indices[i]] = s[i];
    }

    for(i = 0;i < indicesSize;i++){
        s[i] = res[i];
    }
    return s;
}
```

263. Ugly Number
![](https://i.imgur.com/Tbka8g5.png)
![](https://i.imgur.com/SpGD3XD.png)
code
```c
bool isUgly(int num){
   if(num<1)
        return false;
    while(num>1)
    {
        if(num%2==0)
            num=num/2;
        else if(num%3==0)
            num=num/3;
        else if(num%5==0)
            num=num/5;
        else
            return false;
    }
    return true;

}
```

268. Missing Number
![](https://i.imgur.com/hwpG3tN.png)
![](https://i.imgur.com/uQboCdM.png)
code
```c
int missingNumber(int* nums, int numsSize){
    int i,j,k;
    int tem;
    for(i=0;i<numsSize-1;i++)
        for(j=i+1;j<numsSize;j++)
        {
            if(nums[j]<nums[i])
            {
                tem=nums[i];
                nums[i]=nums[j];
                nums[j]=tem;
            }
        }
    if(nums[0]!=0)
        return 0;
    int b=0;
    for(i=1;i<numsSize;i++)
    {
        if(nums[i]==b+1)
        {
            b=nums[i];
            continue;
        }
        else
            break;
    }
    if(i==numsSize)
        return nums[numsSize-1]+1;
    return nums[i]-1;
}
```

977. Squares of a Sorted Array
![](https://i.imgur.com/VO08hoj.png)
![](https://i.imgur.com/o5AIptp.png)
code
```c
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int *ret = malloc(sizeof(int) * numsSize);
    int neg_idx = -1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < 0)
            neg_idx++;
        nums[i] = nums[i] * nums[i];
    }

    int pos_idx = neg_idx + 1, ctr = 0;
    while (neg_idx >= 0 && pos_idx < numsSize) {
        if (nums[neg_idx] > nums[pos_idx])
            ret[ctr++] = nums[pos_idx++];
        else
            ret[ctr++] = nums[neg_idx--];
    }

    while (neg_idx >= 0)
        ret[ctr++] = nums[neg_idx--];

    while (pos_idx < numsSize)
        ret[ctr++] = nums[pos_idx++];

    return ret;
}
```

1051. Height Checker
![](https://i.imgur.com/pLpmX5m.png)
![](https://i.imgur.com/JO4Nh3Q.png)
code
```c
int heightChecker(int* heights, int heightsSize){
    int res=0,i=0;
    int count[101];
    memset(count,0,sizeof(count));
    
    for(int n=0;n<heightsSize;n++){
        count[heights[n]]++;
    }
    for(int j=0;j<101;j++){
        for(;count[j]>0;count[j]--){
            res+=heights[i++]!=j?1:0;
        }
    }
    return res;
}
```

1342. Number of Steps to Reduce a Number to Zero
![](https://i.imgur.com/1Aeb6zm.png)
![](https://i.imgur.com/xQR4zwG.png)
code
```c
int numberOfSteps (int num){
    int c=0;
    while(num>0){
        if(num%2!=0){
            num=num-1;
            c++;
        }
        else{
            num=num/2;
            c++;
        }
    }
    return c;
}
```


