C陣列字串相關, leetcode 26,27,344題

我是在看K&R的C語言書[1]時讀到過的。

從字串中移除某個字元, 利用i去尋訪整個字串，j當所有str !=C的index,
且不需要額外空間。 j一定跑的比i慢，所以不會有溢位的問題。

這個技巧稱作two Pointers

Time complextiy : O(n). 假設n 是陣列長度，i、j最多就是做n步。

void remove(char str[], char c)
{
int i;j;
for(i=0 , j=0 ;str[i] !='\0';i++)
    if(str[i] != c)
    str[j++]=str[i];
str[j]='\0';
}

接著，我們來看leetcode 上有什麼相關的面試問題。

26.Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and >..return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

這題目的題示是

• 數字是排序過了
• 要用in place的方試，不能使用額外空間

要從移除重覆的數字，那我們就用一開始說的方式，用i來尋訪整個字串，用current記住目前的數字，當current跟i不同時才把這值取起來。

int removeDuplicates(int* nums, int numsSize) {
    int i,current;

    /*空字串的話直接回0, leetcode線上有這個測項.XD*/
    if(numsSize == 0 )
        return 0;

    for(i=1, current=0; i < numsSize ; i++){
        if(nums[current] != nums[i])
            nums[++current]=nums[i];
    }

    return (current+1);
}

27.Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example: Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

這題是要從陣列中，移除某個數字，要用到的技巧跟從字串中移除個字元一樣，用i來尋訪整個陣列，用current記錄目前位置，當i所在的值不是要移除的val時，才放到current來。

int removeElement(int* nums, int numsSize, int val) {
    int i;
    int current=0;

    if(numsSize ==0)
        return 0;

    for(i=0, current=0; i < numsSize ; i++){

        if(nums[i] != val)
            nums[current++]=nums[i];

    }

     return current;
}

344.Reverse String

Write a function that takes a string as input and returns the string reversed. Example: Given s = "hello", return "olleh".

inplace的做法就是一個一個頭尾交換，沒啥特別的。

char* reverseString(char* s) {

     int len=0;
     int i=0,j=0;
     char tmp;

     len=strlen(s);
     if(len == 0)
        return s;

     for(i=0, j=(len-1) ; i < j ; i++, j--){
         tmp=s[i];
         s[i]=s[j];
         s[j]=tmp;
     }    

     return s;
}

reference:
[1]Kernighan; Dennis Ritchie (March 1988). The C Programming Language (2nd ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 0-13-110362-8.
[2]https://leetcode.com/problems/remove-duplicates-from-sorted-array/
[3]https://leetcode.com/problems/remove-element/