[C++知识库]LeetBook初级算法（C语言）——数组篇

一、删除排序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

注意：

• 数组可能为空，所以需要判断，若为空直接返回0
• 返回数组长度比数组最后一位的下标大一

int removeDuplicates(int* nums, int numsSize){
    
     if (nums == NULL || numsSize == 0)
        return 0;
    int* output;
    int length = 0;  
    output = &nums[0];
    for(int i=1;i<numsSize;i++){
        if(nums[i]!=output[length]){
            length++;
            output[length]=nums[i];
        }
    }
    nums = output;
    return length+1;
}

二、买卖股票的最佳时机 II

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
注意

• 由于是当前数字与后一位数字进行比较，所以要考虑数组越界问题

int maxProfit(int* prices, int pricesSize){
    int flag=0;//表示现在是否持有股票，当flag=0时，只能进行买操作，当flag=1时，只能进行卖操作
    int sum=0;

    if(pricesSize <2 || prices ==NULL)
        return 0;

    for(int i=0;i+1<pricesSize;i++){
        if(flag==0){//买
            if(prices[i]<=prices[i+1]){
                sum = sum - prices[i];
                flag = 1;
            }
        }else{//卖
            if(prices[i]>prices[i+1]){
                sum = sum + prices[i];
                flag = 0;
            }    
        }
    }

    if(flag=1&&prices[pricesSize-2]<=prices[pricesSize-1])
        sum = sum + prices[pricesSize-1];

    return sum;

}

三、旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
注意
需要新开空间进行复制，不能直接使用指针。

void rotate(int* nums, int numsSize, int k){

    int temp[numsSize];
    for(int i=0;i<numsSize;i++){
        temp[i]=nums[i];
    }
    k=k%numsSize;
    for(int i=0;i<numsSize;i++){
        nums[(i + k) % numsSize] = temp[i];
    }
}

四、存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，返回 false 。

这道题用C来写巨麻烦，用其他语言来写则会简单很多，在考虑要不要换语言……

思路就是排序+判断就可以了。
Python如下：

class Solution(object):
    def containsDuplicate(self, nums):
        return len(nums)!=len(set(nums))//set函数进行去重操作，所以只需要比较两个列表长度就可以了

C语言（作者：julian-14）：

int compare(void *a, void *b)
{
    int *ap = (int *)a;
    int *bp = (int *)b;

    return *ap - *bp;
}

bool containsDuplicate(int *nums, int numsSize)
{
    if (nums == NULL || numsSize == 0) {
        return true;
    }

    qsort(nums, numsSize, sizeof(int), compare);

    int i;
    for (i = 1; i < numsSize; i++) {
        if (nums[i] == nums[i - 1]) {
            return true;
        }
    }

    return false;
}

五、只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

比较简单，排序以后，每个元素一定与相邻的一个元素相同，否则他就只出现一次。

int cmp(const void*a, const void*b) {
    return *(int*)a - *(int*)b;
}
int singleNumber(int* nums, int numsSize){

    qsort(nums, numsSize, sizeof(int), cmp);

    if(numsSize<2)
        return nums[0];
    if(nums[0]!=nums[1])
        return nums[0];
    else if(nums[numsSize-1]!=nums[numsSize-2])
        return nums[numsSize-1];
    else{
        for(int i = 1;i<numsSize-1;i++){
            if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]){
                return nums[i];
            }
        }
    }
    return 0;//不返回值不能通过，可忽略
}

六、两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

int cmp(const void* _a, const void* _b) {
    int *a = _a, *b = (int*)_b;
    return *a == *b ? 0 : *a > *b ? 1 : -1;
}

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size,
               int* returnSize) {
    qsort(nums1, nums1Size, sizeof(int), cmp);
    qsort(nums2, nums2Size, sizeof(int), cmp);
    *returnSize = 0;
    int* intersection = (int*)malloc(sizeof(int) * fmin(nums1Size, nums2Size));
    int index1 = 0, index2 = 0;
    while (index1 < nums1Size && index2 < nums2Size) {
        if (nums1[index1] < nums2[index2]) {
            index1++;
        } else if (nums1[index1] > nums2[index2]) {
            index2++;
        } else {
            intersection[(*returnSize)++] = nums1[index1];
            index1++;
            index2++;
        }
    }
    return intersection;
}

七、加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize){
    int *result = malloc(sizeof(int)*(digitsSize+1));
    memset(result,0,sizeof(int)*(digitsSize+1));
    digits[digitsSize-1]+=1;
    for(int i=digitsSize-1;i-1>-1;i--){
        if(digits[i]==10){
            result[i]=0;
            digits[i-1]+=1;
        }else{
            result[i]=digits[i];
        }
    }
    if(digits[0]==10){
        for(int i=digitsSize;i>0;i--){
            result[i]=result[i-1];
        }
        result[0]=1;
        *returnSize=digitsSize+1;
    }else{
        result[0]=digits[0];
        *returnSize=digitsSize;
    }

    return result;
}

八、移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

void moveZeroes(int* nums, int numsSize){

    if (nums == NULL || numsSize == 0)
        return;
    int index = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != 0)
            nums[index++] = nums[i];
    }
    while (index < numsSize) {
        nums[index++] = 0;
    }
}

呜呜呜，受不了C语言了，准备转Python。