刷题13 数组

989. 数组形式的整数加法

整数的 数组形式  num 是按照从左到右的顺序表示其数字的数组。例如，对于 num = 1321 ，数组形式是 [1,3,2,1] 。

给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。

输入：num = [1,2,0,0], k = 34        输出：[1,2,3,4]
解释：1200 + 34 = 1234

int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
    int* res=malloc(sizeof(int)*100000);
    *returnSize=0;
    //从后向前进行加
    for(int i=numSize-1;i>=0||k>0;--i){
        if(i>=0){
            k+=num[i];
        }
        res[(*returnSize)++]=k%10;
        k/=10;
    }
    //翻转
    for(int i=0;i<(*returnSize)/2;++i){
        int tmp=res[i];
        res[i]=res[(*returnSize)-i-1];
        res[(*returnSize)-i-1]=tmp;
    }
    return res;
}

941. 有效的山脉数组 

 给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：arr.length >=3

• 在 0 < i < arr.length - 1 条件下，存在 i 使得：
  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

        线性扫描，进行模拟。 

bool validMountainArray(int* arr, int arrSize){
    int i=0;
    while(i+1<arrSize&&arr[i]<arr[i+1]){
        i++;
    }
    if(i==0||i==arrSize-1){
        return false;
    }
    while(i+1<arrSize&&arr[i]>arr[i+1]){
        i++;
    }
    return i==arrSize-1;
}

1207. 独一无二的出现次数 

 给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

int cmp(int* a,int* b){
    return *a-*b;
}
bool uniqueOccurrences(int* arr, int arrSize) {
    int flag[2002]={0};
    for(int i=0;i<arrSize;++i){
        if(arr[i]<0){
            //-1就放到下标为1001的位置
            flag[arr[i]+1002]++;
        }else{
            flag[arr[i]]++;
        }
    }
    qsort(flag,2002,sizeof(int),cmp);
    for(int i=0;i<2001;++i){
        if(flag[i]!=0){
            if(flag[i]==flag[i+1]){
                return false;
            }
        }
    }
    return true;
}

1437. 是否所有 1 都至少相隔 k 个元素 

 给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 True ；否则，返回 False 。

输入：nums = [1,0,0,0,1,0,0,1], k = 2
输出：true
解释：每个 1 都至少相隔 2 个元素。

        记录 上一个1出现的下标，除了第一个1之外，每次遇到一个1就判断与前一个1的距离。

bool kLengthApart(int* nums, int numsSize, int k) {
    int pre=-1;
    for(int i=0;i<numsSize;++i){
        if(nums[i]==1){
            if(pre!=-1&&i-pre-1<k){
                return false;
            }
            pre=i;
        }
    }
    return true;
}

2553. 分割数组中数字的数位 

 给你一个正整数数组 nums ，请你返回一个数组 answer ，你需要将 nums 中每个整数进行数位分割后，按照 nums 中出现的 相同顺序 放入答案数组中。对一个整数进行数位分割，指的是将整数各个数位按原本出现的顺序排列成数组。

比方说，整数 10921 ，分割它的各个数位得到 [1,0,9,2,1] 。

输入：nums = [13,25,83,77]
输出：[1,3,2,5,8,3,7,7]

void reverse(int* res,int l,int r){
    while(l<r){
        int tmp=res[l];
        res[l]=res[r];
        res[r]=tmp;
        l++;r--;
    }
    return;
}
int* separateDigits(int* nums, int numsSize, int* returnSize) {
    int* res=malloc(sizeof(int)*100000);
    int l=0;
    for(int i=0;i<numsSize;++i){
        if(nums[i]<10){
            res[l++]=nums[i];
        }else{
            int start=l;
            int num=nums[i];
            while(num){
                int cur=num%10;
                res[l++]=cur;
                num/=10;
            }
            reverse(res,start,l-1);
        }
    }
    *returnSize=l;
    return res;
}

2855. 使数组成为递增数组的最少右移次数 

 给你一个长度为 n 下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回让 nums 成为递增数组的 最少右移 次数，如果无法得到递增数组，返回 -1 。

一次 右移 指的是同时对所有下标进行操作，将下标为 i 的元素移动到下标 (i + 1) % n 处。

输入：nums = [3,4,5,1,2]        输出：2
解释：第一次右移后，nums = [2,3,4,5,1] 。第二次右移后，nums = [1,2,3,4,5] 。现在 nums 是递增数组了，所以答案为 2 。

        将数组分成两段，每一段都单调递增，并且前一段严格大于后一段。 

int minimumRightShifts(int* nums, int numsSize){
    int i=1;
    while(i<numsSize&&nums[i-1]<nums[i]){
        //找到第一个开始下降的点
        i++;
    }
    if(i==numsSize) return 0; //数列递增
    if(nums[0]<nums[numsSize-1]) return -1;//最后一个元素值大于第一个元素值
    int mid=i;
    i++;
    //判断mid之后的元素是否递增
    while(i<numsSize&&nums[i-1]<nums[i]) i++;
    if(i<numsSize) return -1;
    return numsSize-mid;
}

2869. 收集元素的最少操作次数 

 给你一个正整数数组 nums 和一个整数 k 。一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。请你返回收集元素 1, 2, ..., k 需要的 最少操作次数 。

输入：nums = [3,1,5,4,2], k = 2        输出：4
解释：4 次操作后，集合中的元素依次添加了 2 ，4 ，5 和 1 。此时集合中包含元素 1 和 2 ，所以答案为 4 。

int minOperations(int* nums, int numsSize, int k){
    int* ans=malloc(sizeof(int)*(k+1));
    for(int i=0;i<=k;++i) ans[i]=0;
    for(int i=0;i<numsSize;++i){
        //记录每个数字的下标位置
        if(nums[i]<=k){
            ans[nums[i]]=i;
        }
    }
    int mmin=INT_MAX;
    //找到符合要求的最小下标位置
    for(int i=1;i<=k;++i){
        if(ans[i]<mmin){
            mmin=ans[i];
        }
    }
    return numsSize-mmin;
}

2970. 统计移除递增子数组的数目 I 

 给你一个下标从 0 开始的 正 整数数组 nums 。

如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。

请你返回 nums 中 移除递增 子数组的总数目。注意 ，剩余元素为空的数组也视为是递增的。子数组 指的是一个数组中一段连续的元素序列。

输入：nums = [1,2,3,4]
输出：10
解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4] 和 [1,2,3,4]。移除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。

int incremovableSubarrayCount(int* nums, int numsSize) {
    int i=0;
    int n=numsSize;
    while(i<n-1&&nums[i]<nums[i+1]){
        i++;
    }
    if(i==n-1){
        //每个非空子数组都可以移除
        return n*(n+1)/2;
    }
    int ans=i+2;
    for(int j=n-1;j==n-1||nums[j]<nums[j+1];j--){
        while(i>=0&&nums[i]>=nums[j]){
            i--;
        }
        ans+=i+2;
    }
    return ans;
}