左神算法中级班第八课[C++代码]

• 第三题：纯code递归[百度原题，难]
• • 代码
• 第四题：最长无重复字符串的长度
• • 代码
• 第五题：字符转换最小代价
• • 代码
• 第六题：最小字典序
• • 代码

声明：博客根据左神在毕站的讲课视频整理，代码是根据左神的java代码版本改写为c++版本
代码为自己动手改写，未经应用不能转载

github代码链接：
https://github.com/hjfenghj/zuoshen_middlecalss

递归，把把问题分为小问题

• 思路
  假设数组Arr=[a,b,c,…,z],然后a为位置1，z为位置26

f(i,len)表示从位置i的字符出发，长度len的字符串的种类数
g(len)表示长度为len的字符串种类数

所以给一个字符串str
首先计算长度小于str.size()的字符串有多少个；
然后根据str的首字符在Arr的位置k1，计算位置k以前的字符为起始，长度为str.size()的字符串个数；
然后根据字符串str的第二个字符位置k2，计算以位置k2以前的字符为起始，长度为str.size()-1的字符个数；依次类推

• code

#include
#include
#include

using namespace std;

class PROBLEM03
{
public:
	//以idx字符开始,长度为Len的字符串的数量，,idx表示字符在[a,...,Z]中的位置
	int f(int idx, int Len)
	{
		int sum = 0;
		if (Len == 1)
			return 1;

		for (int i = idx+1; i <= 26; i++)
		{
			sum += f(i, Len-1);
		}
		return sum;
	}
	//得到长度为len的字符串有几个
	int g(int len)
	{
		int sum = 0;
		for (int i = 1; i <= 26; i++)
			sum += f(i, len);
		return sum;
	}
	int process(string str)
	{
		int ans = 0;
		int L = str.size();
		for (int i = 1; i < L; i++)
		{
			ans += g(i);
		}

		int first = str[0] - 'a' + 1;
		for (int i = 1; i < first; i++)
			ans += f(i,L);


		int pre = first;
		for (int i = 1; i < L; i++)
		{
			int newL = str[i] - 'a' + 1;
			for (int j = pre + 1; j < newL; j++)
			{
				ans += f(j, L - i);
			}
			pre = newL;
		}
		return ans + 1;
	}
};

int main()
{
	string str = "ab";
	PROBLEM03 P;
	int ans = P.process(str);
	cout << ans << endl;
	return 0;
}

技巧：动态规划，类似于最长有效括号字符串

• 思路
  看代码了解思想把，很简单的思路，但是不好描述

• code

#include
#include
#include

动态规划，力扣72的变种

• code

#include
#include
#include

using namespace std;

class PROBLEM05
{
public:
	int ic;
	int dc;
	int rc;
	PROBLEM05(int i, int d, int r)
	{
		ic = i;
		dc = d;
		rc = r;
	}

	int get_res(string str1, string str2)
	{
		int L1 = str1.size();
		int L2 = str2.size();
		vector> dp(L1+1, vector(L2+1, 0));
		dp[0][0] = 0;

		for (int i = 1; i <= L2; i++)
			dp[0][i] = ic * i;
		for (int i = 1; i <= L1; i++)
			dp[i][0] = dc * i;

		for (int i = 1; i <= L1; i++)
		{
			for (int j = 1; j <= L2; j++)
			{
				
				//仿照力扣72题的思路，力扣72是求操作数；
				if (str1[i-1]-str2[j-1] == 0)
					dp[i][j] = min(dp[i - 1][j] + dc, min(dp[i][j - 1] + ic, dp[i - 1][j - 1]));
				else
					dp[i][j] = min(dp[i - 1][j] + dc, min(dp[i][j - 1] + ic, dp[i - 1][j - 1]+rc));
			}
		}
		return dp[L1][L2];
	}
};

int main()
{
	string s1 = "abd";
	string s2 = "add";
	PROBLEM05 P(5,3,2);
	int ans = P.get_res(s1,s2);
	cout << ans << endl;
	return 0;
}

• 思路
  1）遍历字符串，记录词频
  2）重新遍历，词频表实时显示剩余没遍历的字符中的词频，当词频表中某字符词频变为零的时候停止遍历，去遍历过的元素中ACSII最小的字符ch，并删除整个数组中的字符ch
  3）重复1和2

#include
#include
#include
#include