[学习报告]《LeetCode零基础指南》

文章目录

• 一，排序API介绍
• 二，做题记录：
• • 1.LeetCode:912. 排序数组
  • 2.[LeetCode:169. 多数元素]
  • 3.LeetCode:217. 存在重复元素
  • 4.[LeetCode:164. 最大间距]
  • 5.[LeetCode:905. 按奇偶排序数组]
  • 6.[LeetCode:539. 最小时间差]
  • 7.[976. 三角形的最大周长]
  • 8.[881. 救生艇]
• 三，总结

一，排序API介绍

排序有几种十分经典的排序： 时间复杂度 O ( n 2 ) O(n^2) O(n2)的有冒泡排序，选择排序，插入排序， O ( n ∗ l o g n ) O(n*logn) O(n∗logn)的有希尔排序，归并排序，快速排序，堆排序，剩下的还有桶排序，基数排序，计数排序等等，许多语言都有内置的排序API，C语言中的为 q s o r t ( ) qsort() qsort(),他利用的是快速排序，C++的为 s o r t ( ) sort() sort()，他会根据数据量的大小来进行选择快速排序，或是插入排序等

C语言中的 q s o r t ( ) qsort() qsort();

int cmp(const void * e1,const void * e2){
	//参数定义为const void *类型的指针有两点意义
	//1.是这个函数的作用是排序肯定不会对数据进行修改所以用const限制
	//2.利用void* 的指针可以接受任何类型的地址利于我们排序
	return *(int*)e1-*(int*)e2;//返回值为负数第一个参数排在第二个之前
	//返回值为正数，第二个在第一个之前,为0无所谓
	//在这种返回值下为升序排序，若*e1>*e2，则e1位于e2之后
	//若*e1<*e2则e1在e2之前
}
int main(int * nums){
	qsort(nums,sizeof(nums)/sizeof(nums[0]),sizeof(int),cmp);
	//qsort()有四个参数，第一个为要排序的数组
	//第二个是要排序的个数
	//第三个是要排序的数据类型的字节数
	//第四个是回调回函，这是需要我们自己实现的，他是排序的规则
}

C++中的 s o r t ( ) sort() sort()

class solution{
public :
	void _sort(vector<int>& nums){
		sort(nums.begin(),nums.end(),___);
		//sort函数有三个参数，第一个为起始迭代器即是我们要排序的第一个元素
		//第二个是末尾迭代器，为我们要排序的最后一个元素的下一个位置是结束的标志
		//第三个可以是回调函数，可以是谓词，可以是lambada表达式，也可以对<进行重载
		//同时C++的库函数中为我们提供了greater<>()和less<>()对<进行了重载
		//当我们不输入第三个参数时，默认是升序排序
	}
};

二，做题记录： 1.LeetCode:912. 排序数组

题目链接

给你一个整数数组 nums，请你将该数组升序排列。

简单的排序数组，调用 q s o r t ( ) qsort() qsort()即可

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(int *a,int *b){
    return *a-*b;
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize=numsSize;
    int *ans=(int*)malloc(sizeof(int)*(*returnSize));
    for(int i=0;i<numsSize;i++){
    	ans[i]=nums[i];
    }
    qsort(ans,numsSize,sizeof(int),cmp);
    return ans;
}

2.[LeetCode:169. 多数元素]

题目链接

给定一个大小为 n 的数组，找到其中的多数元素。

多数元素是指在数组中出现次数 大于 n / 2 n/2 n/2 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

  这道题简单的方法就是利用一个辅助数组来进行计数，最后再遍历这个辅助数组看某个元素是不是多数元素，这里介绍一下进阶解法，也是十分简单，直接返回中间元素，因为排序后若存在多数元素则一定位于数组的中间位置上。

因为多数元素的定义是超过了数组长度一半的数，考虑两种极端情况前 n / 2 n/2 n/2个元素就是多数元素的值和后 n / 2 n/2 n/2是多数元素的值，其余的情况都是这两种情况不断向中间逼近。

int cmp(int *a,int *b){
    return *a-*b;
}
int majorityElement(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    return nums[numsSize/2];
}

3.LeetCode:217. 存在重复元素

题目链接

  给你一个整数数组 nums 。

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

示例 1：
输入：nums = [1,2,3,1]
输出：true
示例 2：
输入：nums = [1,2,3,4]
输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

  排序之后利用双指针进行判断即可（这里的指针并非指针变量，而是存储了数组下表信息的变量）当然也可以直接遍历判断相邻元素是否相等

int cmp(int *a,int *b){
    return *a-*b;
}
bool containsDuplicate(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int p1=0,p2=1;
    while(p2<numsSize){
        if(nums[p1++]==nums[p2++]){
            return true;
        }
    }
    return false;
}

4.[LeetCode:164. 最大间距]

题目链接

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。

如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

示例 1:
输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:
输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

提示:
1 <= nums.length <= 105
0 <= nums[i] <= 109

  根据题意进行模拟即可，先排序再在遍历数组的过程中维护间距最大值

int cmp(int *a,int *b){
    return *a-*b;
}
int max(int a,int b){
    return a>b?a:b;
}
int maximumGap(int* nums, int numsSize){
    if(numsSize<2){
        return 0;
    }
    qsort(nums,numsSize,sizeof(int),cmp);
    int ans=nums[1]-nums[0];
    for(int i=2;i<numsSize;i++){
        ans=max(nums[i]-nums[i-1],ans);
    }
    return ans;
}

5.[LeetCode:905. 按奇偶排序数组]

题目链接

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。

你可以返回满足此条件的任何数组作为答案。

示例：
输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。

  这道题有很多方法，比如利用两个辅助数组 o d d odd odd和 e v e n even even分别存储偶数和奇数元素，并依次放到原数组中，在这里介绍一种利用 c m p cmp cmp来自定义排序规则的方法，这也是以后对结构体进行排序的基础。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int check(int a){
    return a&1;//判断奇偶性
}
int cmp(int *a,int *b){
    return check(*a)-check(*b);
    //通过check函数来判断*a,*b的奇偶性
    //若都是奇数返回的是0，谁在前无所谓
    //若都是偶数返回的也都是0，谁在前无所谓
    //若*a是奇数，*b是偶数返回值为-1，*b在前
    //若*a是偶数,*b是奇数返回值是1，*a在前
}
int* sortArrayByParity(int* nums, int numsSize, int* returnSize){
    int *ans=(int *)malloc(sizeof(int)*numsSize);
    for(int i=0;i<numsSize;i++){
        ans[i]=nums[i];
    }
    qsort(ans,numsSize,sizeof(int),cmp);
    *returnSize=numsSize;
    return ans;
}

6.[LeetCode:539. 最小时间差]

题目链接

给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：
输入：timePoints = [“23:59”,“00:00”]
输出：1
示例 2：
输入：timePoints = [“00:00”,“23:59”,“00:00”]
输出：0
提示：
2 <= timePoints.length <= 2 * 104
timePoints[i] 格式为 “HH:MM”

介绍一种简单的方法即是将 t i m e P o i n t s timePoints timePoints数组中的每个元素转换为他对应的分钟数，之后进行排序，一是可以不用借助 a b s ( ) abs() abs()函数来维护ans，二是将数组进行升序排序之后只需要遍历一次就可以维护ans降低时间复杂度。

另外需要注意 00 : 00 00:00 00:00这个时间非常特殊，他换算成分钟后及可以看作0，也可以看作 24 ∗ 60 = 1440 24*60=1440 24∗60=1440,也即是说它可以同时充当一天当中的最小时间和最大时间，在计算的时候0不会影响结果，但是1440也许会影响结果，例如：
n u m [ 0 ] = 0 , n u m [ 1 ] = 23 : 59 , n u m [ 2 ] = 24 : 00 num[0]=0,num[1]=23:59,num[2]=24:00 num[0]=0,num[1]=23:59,num[2]=24:00，这样最小结果就是1而不是23*60+59-0;

int min(int a,int b){
    return a<b?a:b;
}
int cmp(int *a,int *b){
    return *a-*b;
}
int findMinDifference(char ** timePoints, int timePointsSize){
    int *tmp =(int*)malloc(sizeof(int)*timePointsSize);
    int hh,mm;
    for(int i=0;i<timePointsSize;i++){
        sscanf(timePoints[i],"%d:%d",&hh,&mm);
        tmp [i]=hh*60+mm;
    }
    qsort(tmp,timePointsSize,sizeof(int),cmp);
    int ans =10000000;
    for(int i=1;i<timePointsSize;i++){
        ans=min(ans,tmp[i]-tmp[i-1]);
    }
    ans=min(ans,tmp[0]-tmp[timePointsSize-1]+1440);
    return ans;
}

7.[976. 三角形的最大周长]

题目链接

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。

如果不能形成任何面积不为零的三角形，返回 0。

示例 1：
输入：nums = [2,1,2]
输出：5
示例 2：
输入：nums = [1,2,1]
输出：0
提示：
3 <= nums.length <= 104
1 <= nums[i] <= 106

十分简单的一题，先对 n u m s nums nums进行降序排序，接着遍历，先判断三边是否可以构成三角形，如果可以计算出周长直接返回按照降序排列的说三边若是符合条件一定是周长最大的三角形.

int cmp(int *a,int *b){
    return *b-*a;//降序排序
}
int largestPerimeter(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=0;i<numsSize-2;i++){
        if((nums[i+1]+nums[i+2])>nums[i]){
            return nums[i+1]+nums[i+2]+nums[i];
        }
    }
    return 0;
}

8.[881. 救生艇]

题目链接

给定数组 people 。

people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：
输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)
示例 2：
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：
输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)
提示：
1 <= people.length <= 5 * 1 0 4 10^4 104
1 <= people[i] <= limit <= 3 * 1 0 4 10^4 104

  这一题还是有一定的难度的，同时它的提示十分重要，首先他告诉了我们 p e o p l e [ i ] people[i] people[i]<= l i m i t limit limit,那么也就是说我们必须把所有人都送走，接下来这样考虑
1 ) 1) 1) 题目要求我们返回把所有人均送走的最小船数，并且每个船在两人的重量和小于 l i m i t limit limit时可以载走他们。

那么很自然的想到在载重不超过 l i m i t limit limit的情况下每条船要尽量找到两个重量之和最接近 l i m i t limit limit的人，使得空间得到充分利用。

2 ) 2) 2)这里我们利用贪心思想，因为要使两人的重量尽量靠近 l i m i t limit limit，首先对数组进行升序排序，接着使得数组最右侧的人和最左侧的人放到一组，也即是决定将目前还没有运走的人中最重的人和最轻的人尝试匹配到一组中去。

如果匹配不成功则为最重的人单独分配一艘船。

因为若是最重的人与最轻的人也无法匹配成功那么他与剩下的人也必定无法匹配成功，只能自己乘坐一艘船。

如果匹配成功的话，那么接着匹配次重和次轻的人，如此往复即可。

代码实现如下：

int cmp(int *a,int *b){
    return *a-*b;
}
int numRescueBoats(int* people, int peopleSize, int limit){
    qsort(people,peopleSize,sizeof(int),cmp);//排序
    int l=0,r=peopleSize-1;//双指针分别指向最轻和最重的人
    int ans=0;
    while(l<=r){
        if(people[l]+people[r]<=limit){
            l++;//如果匹配成功向下一组匹配
        }
        r--;
        ans++;//这里其实包含了两种情况
        //1：如果匹配成功r自然要指向体重次重的人，ans++，没有什么疑问
        //2：匹配不成功l不变，单独为people[r]分配一艘船ans++，
        //同时r要指向次重的人，这里为了提高代码的复用性把重复的代码提取了出来
    }
    return ans;
}

三，总结

本日的训练来自英雄哪里出来的九日集训专栏，感兴趣的可以自己去做一下：英雄哪里出来：LeetCode零基础指南-排序API那么本次的难度相比前几天上升了一些，同时运用到了双指针和排序算法，还有对于一些特定问题场景的处理