开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【解题报告】《九日集训》诺亚方舟(第三天) -> 正文阅读

[数据结构与算法]【解题报告】《九日集训》诺亚方舟(第三天)

语言：C++

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

利用二分法+旋转排序数组的性质查找

旋转排序数组：较大->最大->最小->较小

用if…else…语句：

条件判断语句一：

nums[mid] >= nums[0] 代表mid及mid左是有序的，即mid在最大数即最大数的左侧

else 即mid在最小数即最小数的右侧

条件判断语句二：

nums[mid] > target && target >= nums[0] 划分了target的范围就在 [nums[0],nums[mid-1])之间

class Solution
{
public:
	int search(vector<int>& nums, int target)
	{
		int left = 0;
		int right = nums.size()-1;
		int mid; 
		while (left <= right)
		{
			mid = left + (right - left) / 2;
			if (nums[mid] == target)
			{
				return mid;
			}
			if (nums[mid] >= nums[0])//mid左有序
			{
				if (nums[mid] > target && target >= nums[0])//在有序的范围内
				{
					right = mid - 1;
				}
				else
				{
					left = mid + 1;
				}
			}
			else//mid右有序
			{
				if (nums[mid] < target && target < nums[0])
                //在有序的范围内，target <= nums[nums.size()-1]也可
				{
                    left = mid + 1;					
				}
				else
				{
					right = mid - 1;
				}
			}
		}
		return -1;
	}
};

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

法一

本题与33题的区别是：本题是非降序->有重复元素，可能出现nums[0]==nums[nums.size()-1]等的情况

与33题相比加上了条件语句：nums[left] == nums[mid] && nums[mid] == nums[right]，避免形如{1,0,1,1,1,1,1}的数组出现时不能确定到底是mid左有序，还是mid右有序

不同点：判断target范围是从target >= nums[0]变为了target >= nums[left]，在此刻可以看做：数组范围由[nums[0],nums[nums.size()-1]]变为了[nums[left],nums[right]],边界数据均被删去的情况，依旧是为了避免旋转数组重复数存在时的区间判断问题（也可在33题中这么做）

相较于法一，个人认为法二更容易理解、易写

class Solution 
{
public:
    bool search(vector<int>& nums, int target) 
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                return true;
            }
			if (nums[left] == nums[mid] && nums[mid] == nums[right])
			{
				left++;
				right--;
			}
			else if (nums[mid]>=nums[left])//mid左有序
            {
                if (nums[mid] > target && target >= nums[left])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                if (nums[mid] < target && target <= nums[right])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};

法二

简化：在二分之前“去掉”尾端重复元素

注意：left<=right-1（因为后续要执行right–）

二分代码和33题一样

class Solution
{
public:
    bool search(vector<int>& nums, int target)
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while (nums[left] == nums[right] && left <= right - 1)
        {
            right--;
        }
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                return true;
            }
            if (nums[mid] >= nums[0])//mid左有序
            {
                if (nums[mid] > target && target >= nums[0])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                if (nums[mid] < target && target < nums[0])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

先写一个投机取巧的解法

设置一个min，其他就按二分格式写，每次比较nums[mid]和min的值，最后return min；

class Solution 
{
public:
    int findMin(vector<int>& nums)
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        int min = INT_MAX;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            min = fmin(min, nums[mid]);
            if (nums[mid] > nums[right])//mid左边有序,最小值在mid右边
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return min;
    }
};

法二

普遍解法

我自己写二分习惯用left<=right,left=mid+1,right=mid-1,所以这道题两个两次，两次都错

class Solution
{
public:
	int findMin(vector<int>& nums)
	{
		int left = 0;
		int right = nums.size() - 1;
		int mid;
		while (left < right)
		{
			mid = left + (right - left) / 2;
			if (nums[mid] > nums[right])
			{
				left = mid + 1;
			}
			else
			{
				right = mid;
			}
		}
		return nums[left];
	}
};

最后贴上一个保存在自己笔记里的二分相关知识点

（本来忘记是谁总结的了，看到了“「二分」的本质是两段性”这句，是宫水三叶的总结的）

二分搜索

1.有序队列查值，用二分。

2.「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足，就可以用「二分」。

二分搜索有两种模板：

if ( left < right )时，缩减范围用left = mid + 1和right = mid
- right边界始终维护语义nums[right] >= target（以普通二分搜索举例），这条语义通过检测if ( nums[mid] >= target )来实现，所以right = mid而非right = mid - 1
- 循环退出后需要检测right维护的语义是否正确，即if ( nums[right] >= target )，因为right的位置可能一直没动处于右边界且该位置从未被检测过语义，因为我们设置的循环条件是if ( left < right )，如果设置成if ( left <= right )的话，最后left == right == mid可能致死循环
if ( left <= right)时，缩减范围用left = mid + 1和right = mid - 1
- 中间直接检测if ( nums[mid] == target ) return mid，如果从未执行该语句而推出循环则说明未搜索到target
- 条件检测用if ( left <= right )从而可以检测右边界的语义，从而就应该使用right = mid- 1而非right = mid

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**注意：**给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶

第一想法就是递归

climbStairs(int n)=climbStairs(n - 2) + climbStairs(n - 1);

不过超时了

class Solution
{
public:
	int climbStairs(int n)
	{
		if (n <= 0)
			return 0;
		if (n <= 2)
			return n;
		return climbStairs(n - 2) + climbStairs(n - 1);
	}
};

用数组迭代实现上述想法

class Solution 
{
public:
	int climbStairs(int n) 
	{
		if (n <= 2)
			return n;
		vector<int>arr(n);
		arr[0] = 1;
		arr[1] = 2;
		for (int i = 2; i < n; ++i)
		{
			arr[i] = arr[i - 1] + arr[i - 2];
		}
		return arr[n - 1];
	}
};

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

递归：效率很慢（因为该题0 <= n <= 30，所以编译可以通过）

可以说是70题是斐波那契数的一个变形

class Solution 
{
public:
    int fib(int n)
    {
        if (n < 0)
            return 0;
        if (n <= 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
};

数组迭代

class Solution
{
public:
	int fib(int n)
	{
		if (n <= 1)
			return n;
		vector<int>arr(n + 1);
		arr[0] = 0;
		arr[1] = 1;
		for (int i = 2; i <= n; i++)
		{
			arr[i] = arr[i - 1] + arr[i - 2];
		}
		return arr[n];
	}
};

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

迭代走一波

class Solution
{
public:
    int tribonacci(int n) 
    {
        if (n == 0)
            return 0;
        else if (n <= 2)
            return 1;
        vector<int>arr(n + 1);
        arr[0] = 0;
        arr[1] = arr[2] = 1;
        for (int i = 3; i <= n; ++i)
        {
            arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
        }
        return arr[n];
    }
};

2006. 差的绝对值为 K 的数对数目

给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。

|x| 的值定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。

示例 1：

输入：nums = [1,2,2,1], k = 1
输出：4
解释：差的绝对值为 1 的数对为：

[1,2,2,1]
[1,2,2,1]
[1,2,2,1]
[1,2,2,1]

按题意写

class Solution 
{
public:
    int countKDifference(vector<int>& nums, int k)
    {
        int tmp = 0;
        for (int i = 0; i < nums.size() - 1; i++)
        {
            for (int j = i + 1; j < nums.size(); j++)
            {
                if (abs(nums[i] - nums[j]) == k)
                {
                    tmp++;
                }
            }
        }
        return tmp;
    }
};

LCP 01. 猜数字

小A 和小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回小A 猜对了几次？

输入的guess数组为小A 每次的猜测，answer数组为小B 每次的选择。guess和answer的长度都等于3。

示例 1：

输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。

过分水的一道题

class Solution
{
public:
    int game(vector<int>& guess, vector<int>& answer) 
    {
        int tmp = 0;
        for (int i = 0; i < 3; i++)
        {
            if (guess[i] == answer[i])
            {
                tmp++;
            }
        }
        return tmp;
    }
};

LCP 06. 拿硬币

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

示例 1：

输入：[4,2,1]

输出：4

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

法一

总之就是尽量每次拿两枚，只在每堆原始个数为奇数个情况下有一次拿一枚的机会

所以可以直接利用int的特性（个数+1）/2

class Solution
{
public:
	int minCount(vector<int>& coins)
	{
		int tmp = 0;
		for (int i = 0; i < coins.size(); i++)
		{
			tmp += (coins[i] + 1) / 2;
		}
		return tmp;
	}
};

不过法一效率有点低，可以利用奇数的二进制&1==1的前提优化

法二

注意事项：注意&的优先级，要给coins[i] & 1加括号

class Solution
{
public:
	int minCount(vector<int>& coins)
	{
		int tmp = 0;
		for (int i = 0; i < coins.size(); i++)
		{
			tmp += coins[i] / 2 + (coins[i] & 1);
		}
		return tmp;
	}
};