算法日志——第二天

旧城等待， 2023-09-28 15:35 126阅读 0赞

![在这里插入图片描述][8d8c342904294f98af2ea2478ceaf829.gif_pic_center]

> 作者简介: 博主在读计科双非本科，目前大二，正在学习JAVA，数据库，操作系统，计算机网络，数据结构，JAVA Web等…  
> 个人主页：[熬夜磕代码丶][Link 1]  
> 作品专栏: [从0到1，学习算法][0_1]  
> 我变秃了，也变强了  
> 给大家介绍一款程序员必备刷题平台——牛客网  
> [点击注册一起刷题收获大厂offer吧][offer]

![在这里插入图片描述][5365138b33744ae1aefda5c00427aaf2.png]

#### 文章目录 ####

*  一、错误的集合
 *   *  1.题目描述
     *  2.解题思路
     *  3.代码实现
 *  二、密码检查
 *   *  1.题目描述
     *  2.解题思路
     *  3.代码实现
 *  三、旋转数组最小数字
 *   *  1.题目描述
     *  2.解题思路
     *  3.代码实现

--------------------

## 一、错误的集合 ##

### 1.题目描述 ###

> 集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。  
> 给定一个数组 nums 代表了集合 S 发生错误后的结果。  
> 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。  
> 集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

题目地址：[645.错误的集合][645.]  
![在这里插入图片描述][b564f8f9c4394bd2af18776bd1584dbd.png]  
![在这里插入图片描述][08eb80a398ad4142887f6265af79555b.png]

### 2.解题思路 ###

> 排序  
> 先使用qsort对数组进行排序，比较相邻元素，即可找到错误的集合  
> 寻找重复的数字比较简单，如果相邻两元素相等，则该元素为重复元素。  
> 寻找丢失数字相对复杂,有以下两种判断:  
> 1.如果丢失的数字大于1且小于numsSize，则一定存在相邻的两元素大于1，这两个元素之间的数字即为丢失的数字。  
> 2.如果丢失的为1或n，需另外判断。

### 3.代码实现 ###

int cmp_int(const void* e1, const void* e2)
    {
        
    	return *(int*)e1 - *(int*)e2;
    }
    int* findErrorNums(int* nums, int numsSize, int* returnSize)
    {
        
    	qsort(nums, numsSize, sizeof(int), cmp_int);
    	*returnSize = 2;
    	int prev = 0;
    	int i = 0;
    	for (i = 0; i < numsSize; i++)
    	{
        
    		int curr = nums[i];
    		if (curr == prev)
    		{
        
    			nums[0] = prev;
    		}
    		else if (curr - prev > 1)
    		{
        
    			nums[1] = prev + 1;
    		}
    		prev = curr;
    	}
    	if (nums[numsSize - 1] != numsSize)
    		nums[1] = numsSize;
    	return nums;
    }

## 二、密码检查 ##

### 1.题目描述 ###

> 小明同学最近开发了一个网站，在用户注册账户的时候，需要设置账户的密码，为了加强账户的安全性，小明对密码强度有一定要求：  
> 1. 密码只能由大写字母，小写字母，数字构成；  
> 2. 密码不能以数字开头；  
> 3. 密码中至少出现大写字母，小写字母和数字这三种字符类型中的两种；  
> 4. 密码长度至少为8  
> 现在小明受到了n个密码，他想请你写程序判断这些密码中哪些是合适的，哪些是不合法的。  
> 输入描述：  
> 输入一个数n，接下来有n(n≤100)行，每行一个字符串，表示一个密码，输入保证字符串中只出现大写字母，小写字母和数字，字符串长度不超过100。  
> 输出描述：  
> 输入n行，如果密码合法，输出YES，不合法输出NO

题目地址：[OR141密码检查][OR141]  
![在这里插入图片描述][da8b063a4fcd41ae813c7d8363b3d0e5.png]

### 2.解题思路 ###

> 考察点为一些字符分类函数的使用

![在这里插入图片描述][8019c699c8394eacb71ecdd5d4f307d5.png]

### 3.代码实现 ###

#include<stdio.h>
    #include<string.h>
    #include<ctype.h>
    int main()
    {
        
    	int n = 0;
    	scanf("%d", &n);
    	char arr[100];
    	int i = 0;
    	for (i = 0; i < n; i++)
    	{
        
    		int flag = 1;
    		scanf("%s", arr);
    		int sz = strlen(arr);
    		if (isdigit(arr[0]))
    		{
        
    			flag=0;
    		}
    		if (sz < 8)
    		{
        
    			flag = 0;
    		}
    		int j = 0;
    		int a = 0, b = 0, c = 0;
    		for (j = 0; j < sz; j++)
    		{
        
    			if (!isalnum(arr[j]))
    			{
        
    				break;
    			}
    			if (isdigit(arr[j]))
    			{
        
    				a=1;
    			}
    			if (islower(arr[j]))
    			{
        
    				b=1;
    			}
    			if (isupper(arr[j]))
    			{
        
    				c=1;
    			}
    		}
    		if (j != sz && a + b + c < 2)
    		{
        
    			flag = 0;
    		}
    		if (flag == 1)
    			printf("YES\n");
    		else
    			printf("NO\n");
    	}
    	return 0;
    }

## 三、旋转数组最小数字 ##

### 1.题目描述 ###

> 有一个长度为 n 的非降序数组，比如\[1,2,3,4,5\]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了\[3,4,5,1,2\]，或者\[4,5,1,2,3\]这样的。请问，给定这样一个旋转数组，求数组中的最小值。  
> 数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000  
> 要求：空间复杂度：O(1) ，时间复杂度：O(logn)

题目描述：[JZ11旋转数组最小数字][JZ11]  
![在这里插入图片描述][c524d04368af46758f4c2623b9ee1fe5.png]  
![在这里插入图片描述][77b5316ed4174d829d21d4df7edf3147.png]

### 2.解题思路 ###

> 二分查找  
> 排序数组的查找问题首先考虑二分法解决，其可将遍历的线性级别时间复杂度降至对数级别  
> 1.数组可以分为两个有序的子数组。其中，左排序的数组的值大于右排序数组中的值。  
> 如图：

![在这里插入图片描述][9fba61412d144e3cb572a8c5458cf2fc.png]

> 2.声明left,right 分别指向数组的左右两端；  
> 3. mid = (left+right) / 2 为二分的中间位置。  
> 4.midleft,right分为三种情况：  
> a. rotateArray\[mid\] > rotateArray\[right\]时， 那么 最小值一定在 \[mid+1,right\]区间中；  
> b.rotateArray\[mid\] < rotateArray\[right\]时，那么最小值一定在\[left,mid\]区间内。  
> c. rotateArray\[mid\] = rotateArray\[right\]时，无法判断最小值在哪个区间，所以此时只能缩小right的值。  
> 如图:

![在这里插入图片描述][90b97f3015bf43c4b564b167fb7cfb57.png]

### 3.代码实现 ###

int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
        
        if(rotateArrayLen==0)
        {
        
            return 0;
        }
        int left=0;
        int right=rotateArrayLen-1;
        while(left<=right)
        {
        
              if(rotateArray[left]<rotateArray[right])//left即为最小值
              {
        
                  return rotateArray[left];
              }
            int mid=left+(right-left)/2;
            if(rotateArray[mid]>rotateArray[right])//最小值在右侧
            {
        
                left=mid+1;
            }else  if(rotateArray[mid]<rotateArray[right])//最小值在左侧
            {
        
                right=mid;
            }else//相等，需要调整
            {
        
                right--;
            }
        }
            return rotateArray[left];
    }

[8d8c342904294f98af2ea2478ceaf829.gif_pic_center]: https://img-blog.csdnimg.cn/8d8c342904294f98af2ea2478ceaf829.gif#pic_center
[Link 1]: https://blog.csdn.net/buhuisuanfa?spm=1018.2226.3001.5343
[0_1]: https://blog.csdn.net/buhuisuanfa/category_11918328.html?spm=1001.2014.3001.5482
[offer]: https://www.nowcoder.com/link/pc_csdncpt_bhsf_jzsf
[5365138b33744ae1aefda5c00427aaf2.png]: https://img-blog.csdnimg.cn/5365138b33744ae1aefda5c00427aaf2.png
[645.]: https://leetcode.cn/problems/set-mismatch/
[b564f8f9c4394bd2af18776bd1584dbd.png]: https://img-blog.csdnimg.cn/b564f8f9c4394bd2af18776bd1584dbd.png
[08eb80a398ad4142887f6265af79555b.png]: https://img-blog.csdnimg.cn/08eb80a398ad4142887f6265af79555b.png
[OR141]: https://www.nowcoder.com/practice/f2fbd8f61c564ca0b5feaa63ab42dae5?tpId=182&&tqId=34867&rp=1&ru=/ta/exam-all&qru=/ta/exam-all/question-ranking
[da8b063a4fcd41ae813c7d8363b3d0e5.png]: https://img-blog.csdnimg.cn/da8b063a4fcd41ae813c7d8363b3d0e5.png
[8019c699c8394eacb71ecdd5d4f307d5.png]: https://img-blog.csdnimg.cn/8019c699c8394eacb71ecdd5d4f307d5.png
[JZ11]: https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=23269&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[c524d04368af46758f4c2623b9ee1fe5.png]: https://img-blog.csdnimg.cn/c524d04368af46758f4c2623b9ee1fe5.png
[77b5316ed4174d829d21d4df7edf3147.png]: https://img-blog.csdnimg.cn/77b5316ed4174d829d21d4df7edf3147.png
[9fba61412d144e3cb572a8c5458cf2fc.png]: https://img-blog.csdnimg.cn/9fba61412d144e3cb572a8c5458cf2fc.png
[90b97f3015bf43c4b564b167fb7cfb57.png]: https://img-blog.csdnimg.cn/90b97f3015bf43c4b564b167fb7cfb57.png