# **109-2 程式設計III 寒假作業**
344. Reverse String
code

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
code

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
code

/**
 * 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
code

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

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
code

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
code

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
code

/**
 * 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
code

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
code

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
code

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
code

/**
 * 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
code

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
code

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;
}