@TOC
一、错误的集合
1.题目描述
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
题目地址：645.错误的集合
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. 密码只能由大写字母，小写字母，数字构成；
- 密码不能以数字开头；
- 密码中至少出现大写字母，小写字母和数字这三种字符类型中的两种；
- 密码长度至少为8
现在小明受到了n个密码，他想请你写程序判断这些密码中哪些是合适的，哪些是不合法的。
输入描述：
输入一个数n，接下来有n(n≤100)行，每行一个字符串，表示一个密码，输入保证字符串中只出现大写字母，小写字母和数字，字符串长度不超过100。
输出描述：
输入n行，如果密码合法，输出YES，不合法输出NO
题目地址：OR141密码检查
2.解题思路
考察点为一些字符分类函数的使用
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旋转数组最小数字
2.解题思路
==二分查找==
排序数组的查找问题首先考虑二分法解决，其可将遍历的线性级别时间复杂度降至对数级别
1.数组可以分为两个有序的子数组。其中，左排序的数组的值大于右排序数组中的值。
如图：
2.声明left,right 分别指向数组的左右两端；
- 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的值。
如图:
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];
}
