初级算法（一）

写在前面

因为还在学习C++，所以本次刷题所使用的编程语言为C。下学期我们会开一门叫做《计算机算法》的专业课，我想先提前玩一玩算法，所以就通过leetcode平台去刷题了。在每道算法题解中，我会给出一种或多种解法(我的解法和其他人比较好的解法)。

删除排序数组中的重复项

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

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

说明

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按升序排列

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int removeDuplicates(int* nums, int numsSize){
    if(nums==NULL||numsSize==0)
    return 0;
//判断是否为空数组
    int left = 0;
    for(int right = 1;right < numsSize;right++){
        //if(nums[left]==nums[right])
        	//right++;
        //如果相同，左指针不动，右指针移动。因为for循环有右指针移动，故省去这步right++；
        if(nums[left]!=nums[right])
        {
            left++;
            nums[left]=nums[right];
        }
        //如果不相同，左指针移动，右指针将自己的值赋给左指针，再移动。
    }
    return ++left;
}

一些理解

题中说明了数组内部已经排序 好。所以如果有重复元素，那他们一定是相邻的。故使用双指针来解决问题。只需要遍历一遍数组即可。

存在重复元素

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

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

示例1

1
2
输入: [1,2,3,1]
输出: true

示例2

1
2
输入: [1,2,3,4]
输出: false

示例3

1
2
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int left = 0;
    for(int right = 1;right < nums.size();right++){
         if(nums[left]==nums[right])
            return true;
        if(nums[left]!=nums[right])
        {
            left++;
            nums[left]=nums[right];
        }
    }
    return false;
    }
};

通过

一些理解

此题查重思路同第1题相同。只是要先排序。注意在for循环中的两个if语句顺序不能写颠倒了。

更好的解法

我们知道set集合中的元素是不能有重复的，在添加的时候如果有重复的，会把之前的值给覆盖，并且返回false。我们遍历数组中的所有值，一个个添加到集合set中，在添加的时候如果返回false，就表示有重复的，直接返回true。

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        //因为集合set中不能有重复的元素，如果有重复的
        //元素添加，就会添加失败
        if (!set.add(num))
            return true;
    }
    return false;
}

拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：

1
2
3
输入：[4,2,1]

输出：4

解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

示例 2：

1
2
3
输入：[2,3,10]

输出：8

限制：

  • 1 <= n <= 4
  • 1 <= coins[i] <= 10

题解

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minCount(vector<int>& coins) {
        int ans=0;
        for(int i=0;i<coins.size();i++)
        {
            ans+=(coins[i]+1)/2;
        }
        return ans;
    }
};

一些理解

一枚硬币也要拿一次，两枚硬币也要拿一次。那么就权当拿两枚。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/
来源：力扣（LeetCode）