【C++ 算法进阶】算法提升九

step num （贪心）

题目

我们现在给定一个正整数 680 每次模十相加 即680 + 68 + 6 = 754

则我们称754是680的step num

现在给你一个数字 要求你求出这个数字是谁的step num

题目分析

这道题我们要使用贪心来解 我们通过观察可以得到step num是递增的 （公式可以验证 一个三次函数）

那么这样的话 我们只需要从1开始到给定的数字 一直验算 就能找出这个唯一的答案

代码

int process(int num) {
	int i = 1;
	while (i < num)
	{
		int n = i;
		int stepnum = 0;
		while (n)
		{
			stepnum += n;
			n /= 10;
		}

		if (stepnum == num)
		{
			break;
		}

		i++;
	}

	return i;
}

int main() {
	cout << process(754) << endl;
	return 0;
}

开灯问题 （较为复杂的动态规划 从左到右模型）

题目

给定一个数组 arr arr里面的每个元素代表一盏灯 它只会有两种状态 1或者0 1表示灯开着 0表示灯关着

每一盏灯有一个按钮 当我们点击这个按钮的时候这盏灯 它前面一盏灯 它后面一盏灯都会改变状态 （1变0 0变1）

现在有如下两个问题

题目分析

我们首先看问题一

假设灯排列成一条直线的时候 我们想一下 如果一盏灯只能改变一个位置的值的时候我们是不是只需要使用一个变量就能完成整个遍历函数

如果一盏灯能改变两个位置呢？ 是不是就需要两个变量了

如果一盏灯能改变三个位置呢？

所以说我们这里使用三个变量来描述这个函数 当然这里很显然是一个从左到右的尝试模型

我们的尝试函数可以这样设置

// nextIndex表示遍历的下个位置 curStatus表示当前灯的状态  preStatus表示当前位置前一盏灯的状态
// 我们传入这几个参数之后让这个函数返回我们能够让灯全亮最小的操作数 如果没有则返回-1
int process(vector<int>& arr, int nextIndex, int curStatus, int preStatus) {

}

这个我们需要注意的是 如果nextIndex传入1 那么我们这个函数存在bug 就是prestaus没办法判断 那么这样子的话我们就可以将0位置特殊处理 nextindex从2开始传递

代码详解

// nextIndex表示遍历的下个位置 curStatus表示当前灯的状态  preStatus表示当前位置前一盏灯的状态
// 我们传入这几个参数之后让这个函数返回我们能够让灯全亮最小的操作数 如果没有则返回-1
int process(vector<int>& arr, int nextIndex, int curStatus, int preStatus) {
	if (nextIndex == arr.size())
	{
		if (curStatus == preStatus)
		{
			return curStatus == 1 ? 0 : 1;
		}
		else
		{
			return -1; 
		}
	}


	// 开始讨论一般情况
	if (preStatus == 0) //当前位置必须要开
	{
		curStatus ^= 1;
		int cur = arr[nextIndex] ^ 1;
		int next = process(arr, nextIndex + 1, cur, curStatus);
		if (next == -1){
			return -1;
		}
		else {
			return 1 + next;
		}
	}
	else
	{
		return process(arr, nextIndex + 1, arr[nextIndex], curStatus);
	}
}


int main() {
	vector<int> arr = { 1,1 ,1 , 0 ,0 ,0 , 0 , 0, 0};

	int p1 = 1 + process(arr, 2, arr[1] ^ 1, arr[0] ^ 1);
	int p2 = process(arr, 2, arr[1], arr[0]);
	return 0;
}

题目分析

有环问题相比于无环问题更加特殊一点 特殊的点在于 初始状态和末尾状态我们需要记录下来 并且2位置 N-1位置也会改变我们的函数参数

这里我们解决的方式是这样

既然我们知道前面有且之后12位置 能改变我们的函数参数 那么我们就把12的情况全排列出来 之后函数里面就只要考虑末尾N-1位置的数就行了

int process(vector<int>& arr, int nextIndex, int curStatus, int preStatus , int startStatus , int endStatus) {
	if (nextIndex == arr.size())
	{
		if (curStatus == preStatus == startStatus)
		{
			return curStatus == 1 ? 0 : 1;
		}
		else
		{
			return -1;
		}
	}


	// 开始讨论一般情况
	if (nextIndex != arr.size() - 1)
	{
		if (preStatus == 0) //当前位置必须要开
		{
			curStatus ^= 1;
			int cur = arr[nextIndex] ^ 1;
			int next = process(arr, nextIndex + 1, cur, curStatus , startStatus , endStatus);
			if (next == -1) {
				return -1;
			}
			else {
				return 1 + next;
			}
		}
		else
		{
			return process(arr, nextIndex + 1, arr[nextIndex], curStatus, startStatus, endStatus);
		}
	}
	else // N-2位置的情况特殊考虑
	{
		// N-2位置会改变endstatus的情况
		if (preStatus == 0)
		{
			curStatus ^= 1;
			int cur = arr[nextIndex] ^ 1; // 这里改变了endstatus的状态
			int next = process(arr, nextIndex + 1, cur, curStatus, startStatus, endStatus ^ 1);
			if (next == -1) {
				return -1;
			}
			else {
				return 1 + next;
			}
			
		}
		else
		{
			return process(arr, nextIndex + 1, arr[nextIndex], curStatus, startStatus, endStatus);
		}
	}
}

最长递增子序列问题 （动态规划 + 优化）

题目

本题为LC原题目 题目如下

题目分析

本题如果不做优化的话其实就是一道非常简单的动态规划问题

我们可以设置一个数组dp 该数组的dp[i]的含义是 表示以i位置结尾的递增子序列的最大值

那么只要我们将所有的dp都计算出来 我们就能计算出最终的答案了

计算的方式也很简单 首先dp[0]肯定是1

之后计算普遍位置的时候我们只需要往前找小于自己的数 然后看他们的dp值 找出其中最大的dp值加一即可

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size() , 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); i++) {
            int lnmax = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                  lnmax = max(lnmax , dp[j]);  
                }
            }
            dp[i] = lnmax + 1;
        }

        int ans = 1;
        for (int i = 0; i < dp.size(); i++) {
            ans = max(ans , dp[i]);
        }
        return ans;
    }
};

优化

我们在遍历填写dp值的时候每次都需要遍历数组才能得出最终答案

也就是说 我们的dp数组并没有给我们的解答提供一些便利

那么有没有什么办法在填写dp数组的时候不用再遍历整个数组呢？

这里提供一种思路

我们首先创建一个和原来dp数组同样大小的arr数组

其中arr[i] 表示最长递增子序列长度为i+1的结尾的最小值

有了这个数组我们只需要在这个数组上二分查找小于当前数且最接近当前数的值 之后修改它的下一个值就好

这样子我们就将遍历的时间复杂度从N 降低到了 logN

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> arr;
        arr.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            int L = 0;
            int R = arr.size() - 1;
            int m = 0;
            while (L <= R) {
                m = (L + R) / 2;
                if (arr[m] < nums[i]) {
                    L = m + 1;
                } else {
                    R = m - 1;
                }
            } 
            if (nums[i] <= arr[m]) {
                arr[m] = nums[i];
            }else {
                if (arr.size() - 1 > m + 1) {
                    arr[m+1] = nums[i];
                }else{
                    arr.push_back(nums[i]);
                }
            }
        }

        return arr.size();
    }
};

重点在于这段代码

   while (L <= R) {
                m = (L + R) / 2;
                if (arr[m] < nums[i]) {
                    L = m + 1;
                } else {
                    R = m - 1;
                }
            } 
            if (nums[i] <= arr[m]) {
                arr[m] = nums[i];
            }else {
                if (arr.size() - 1 > m + 1) {
                    arr[m+1] = nums[i];
                }else{
                    arr.push_back(nums[i]);
                }

我们首先用二分法在arr数组中找到大于等于 nums[i] 且后一位数小于 nums[i]的位置

之后判断是否等于nums[i] 如果等于可以不操作 也可以修改

接着我们判断数组的大小 如果数组很大则不需要扩容 我们直接修改下一位数字即可

如果数组很小则我们直接将nums[i] 插入到后一位即可