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

• 第三题：栈与队列的互相转换
• 第五题：接雨水问题
• • 代码
• 第七题：判断是否为为旋转字符串
• • 代码
• 第七题加题： 咖啡杯问题
• • 代码

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

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

队列是先进先出，栈是先进后出；使用队列实现栈的先进后出，使用栈实现队列的先进先出

• 思路
  1）两个栈实现一个队列，来数据一直放进栈1，当需要弹出数据的时候，将栈1的数据全部弹出放在栈2里边，然后弹出栈2的栈尾元素；接着来元素的时候，将元素放进栈1，接着如果需要弹出元素，判断栈2是否为空，如果不是空就弹出栈2 的栈尾元素，如果栈2空了，就将栈1中的元素弹出压进栈2；

  2） 两个丢列实现一个栈，来数据放进队列1中，如果需要弹出元素，将从队列头部弹出元素进入队列2；当队列1只有一个元素是弹出，之后队列1为空，如果这时候来新元素，进进入队列1，以后弹出元素还是队列1进对队列2；如果连序弹出，就需要两个队列反复的调转；新元素来的时候始终进入空队列；

附加：常规情况下，二叉树的层序遍历(宽度优先遍历)只能使用队列，深度优先遍历只能使用栈；但是如果实现了队列和栈之间的相互转换也可以使用栈完成二叉树的层序遍历，使用队列完成二叉树的深度遍历；

技巧：单调栈结构
技巧：双指针结构

• 思路1
  思路1:额外空间复杂度O(N)
  1）使用单调栈记录位置i左右两侧第一个大于位置高的位置索引。
  2） 使用每个位置得到的两个位置索引得到此位置的雨水量
  3） 求所有位置雨水的总和

• 思路2：额外空间复杂度O(1)
  使用两个变量max_L和max_R记录两个指针从左右两边开始遍历，遍历过的元素中的元素最大值；
  从值小的一端地方开始遍历，并根据遍历到的元素更新对应的变量；假如说从右侧开始遍历，然后随着遍历的进行，更新变量max_R;当max_R变得小于等于max_L的时候就可以计算此时可以得到的雨水量了；根据max_L - Arr[i]为高度；两个索引差为宽；然后换头开始遍历，知道两个指针碰上

• code

#include
#include
#include
using namespace std;



class PROBLEM05_1
{
public:
	int get_res(vector Arr)
	{
		int Len = Arr.size();
		int maxR = Arr[0];
		int maxL = Arr[Len - 1];
		int L = 1;
		int R = Len - 1;
		int ans = 0;
		while (L != R)
		{
			//从左往右遍历
			if (maxR > maxL)
			{
				if (Arr[L] < maxL)
				{
					ans += maxL - Arr[L];
				}
				else
					maxL = Arr[L];
				L++;
			}
			//从右往左遍历
			else
			{
				if (Arr[R] < maxR)
				{
					ans += maxR - Arr[R];
				}
				else
					maxR = Arr[R];
				R--;
			}
		}
		return ans;
	}
};


class PROBLEM05_2
{
public:
	stack st;//储存数组元素的索引
	vector  L_Arr;//元素i左边第一个大于自身的元素的索引
	vector  R_Arr;//元素i右边第一个大于自身的元素的索引
	int ans = 0;
	int get_res(vector Arr)
	{
		st.push(0);
		L_Arr.resize(Arr.size());
		R_Arr.resize(Arr.size());
		for (int i = 1; i < Arr.size(); i++)
		{
			if (Arr[st.top()] > Arr[i])
				st.push(i);
			else
			{
				while (Arr[st.top()] <= Arr[i])
				{
					int temp = st.top();
					R_Arr[temp] = i;
					st.pop();
					if (st.empty())
						break;
					L_Arr[temp] = st.top();
				}
				st.push(i);
			}
		}

		while (!st.empty())
		{
			int temp = st.top();
			st.pop();
			if (st.empty())
				break;
			L_Arr[temp] = st.top();
		}
		for (int i = 1; i < Arr.size()-1; i++)
		{
			if (L_Arr[i] == 0 && R_Arr[i] == 0)
				continue;
			else
			{
				ans += (R_Arr[i] - L_Arr[i] - 1) * (min(Arr[L_Arr[i]], Arr[R_Arr[i]]) - Arr[R_Arr[i] - 1]);
			}
		}
		return ans;
	}
};

int main()
{
	vector Arr = {3,1,2,5,2,4};
	PROBLEM05_1 P1;
	int res = P1.get_res(Arr);
	cout << res << endl;
	PROBLEM05_2 P2;
	int res2 = P2.get_res(Arr);
	cout << res2 << endl;
	return 0;
}

技巧：KMP前缀表

• 思路
  如果a和b互为旋转字符串，那么两个b一定是a+a的字串；就可以看作b是否为a的字串问题；使用KMP求出b与a+a匹配到的第一个字符位置；如果返回一个正儿八经的位置，那么就是旋转字符串

• code

#include
#include
#include

using namespace std;

class PROBLEM07
{
public:
	string s;
	string m;
	vector nexts;
	PROBLEM07(string str, string match)
	{
		s = str;
		m = match;
		nexts.resize(m.size());
	}

	//产生匹配字符串的nexts数组
	void get_nexts()
	{
		nexts[0] = -1;
		nexts[1] = 0;
		s = s + s;
		if (m.size() < 2)
			return;
		int curidx = 2;
		int cm = nexts[curidx - 1];
		while (curidx < m.size())
		{
			if (m[curidx - 1] == m[cm])
			{
				nexts[curidx++] = ++cm;
			}
			else if (cm > 0)
				cm = nexts[cm];
			else
				nexts[curidx++] = 0;
		}
		return;
	}
	//返回b在字符串在a+a字符串中的第一个位置
	int get_index()
	{
		int i = 0;
		int j = 0;
		while (i < s.size() && j < m.size())
		{
			if (s[i] == m[j])
			{
				i++;
				j++;
			}
			else if (j == 0)
				i++;
			else
				j = nexts[j];
		}
		return j == m.size() ? i - j : -1;
	}

	bool get_res()
	{
		get_nexts();
		int ans = get_index();
		return ans == -1 ? false : true;

	}
};

int main()
{
	string a = "1ab2";
	string b = "ab12";

	if (a.size() != b.size())
		return false;
	if (a.size() == 1 && b.size() == 1 && a == b)
		return true;


	PROBLEM07 P(a,b);
	cout << P.get_res() << endl;
	return 0;
}

题目：
条件一：数组Arr=[3,2,7]代表3太咖啡机制作一杯咖啡的时间
条件二：N代表有N个人排队喝咖啡，一人一杯，来的人三个咖啡机后边都可以排队
条件三：a代表洗咖啡杯的机器洗一个杯子需要的时间(只有一个洗咖啡杯机器，一次只洗一个杯子)
条件四：b代表一个咖啡杯不适用机器清洗，自然挥发变干净的时间
条件五：店里的咖啡杯超过N个

问:从第一个人去泡咖啡开始，到杯子全部变干净至少耗时多久

• 思路
  1） 使用一个小根堆储存三个数据对，数据对的第一个元素表示需要过多久咖啡机空闲，第二个元素表示咖啡机做一杯咖啡的时间；每来一个人，就选取排在堆首的咖啡机，因为可以最快的拿到咖啡；然后根据选择的咖啡机更新数据对，然后堆内部根据等待时间+效率时间排序，将最小的排在堆首；N个人选择完以后，就可以得到一个储存每个人最快拿到咖啡的时刻的数组Arr；
  2） 根据数组Arr和时间a和b来求最小时间；递归转动态规划，当前人拿到咖啡到最后一个杯子干净需要用时，结果为当前杯子用时a和用时b，加上下一个人到最后一个杯子干净时间的最小值

• code

#include
#include
#include
using namespace std;

class Node
{
public:
	int timestamp;
	int id;
	Node(int t, int i)
	{
		timestamp = t;
		id = i;
	}
	Node() {};
};

class PROBLEM07_add
{
public:
	vector eat_all;//表示每个人都拿到咖啡时候的时间
	
	static bool cmp(Node N1, Node N2)
	{
		return N2.timestamp + N2.id > N1.timestamp + N1.id;
	}

	//得到N个人每个人拿到咖啡时候的时间
	void get_eat_all(int N)
	{
		priority_queue, decltype(&cmp)> minheap(cmp);
		minheap.emplace(Node(0, 2));
		minheap.emplace(Node(0, 3));
		minheap.emplace(Node(0, 7));

		for (int i = 0; i < N; i++)
		{
			Node cur = minheap.top();
			eat_all.push_back(cur.timestamp + cur.id);
			minheap.pop();
			minheap.emplace(Node(cur.timestamp+cur.id,cur.id));
		}
		return;
	}	

	//返回最短的时间,递归暴力处理方法
	//Arr是每个人拿到咖啡需要等待的时间
	//a表示使用机器洗杯子一个需要用时
	//b表示使用挥发洗杯子用时
	//idx表示从idx个人的杯子开始到最后一个杯子干净需要的最小用时
	//wirtim洗当下第一个杯子需要等待的时长
	int process1(vector Arr, int a, int b, int idx, int witim)
	{
		
		if (idx == Arr.size() - 1)
		{
			return min(max(Arr[idx], witim) + a, Arr[idx] + b);
		}
		//选择使用咖啡机洗当前的首个杯子，一个杯子需要耗时a
		int use_time = max(Arr[idx],witim) + a;
		int next_time = process1(Arr, a, b, idx + 1, use_time);
		int a_t = max(use_time, next_time);

		//选择使用挥发洗当前的首个杯子，一个杯子耗时b
		int use_time1 = Arr[idx] + b;
		int next_time2 = process1(Arr, a, b, idx + 1, witim);
		int b_t = max(use_time1, next_time2);

		return min(a_t, b_t);
	}
	void main_1(vector Arr, int a, int b)
	{
		int ans =  process1(eat_all, a, b, 0, 0);
		cout << ans << endl;
		return;
	}


	//暴力递归改为动态规划
	//dp[0][0]表示从第1个人的拿到碗的时间开始，起始等待时间为0时，到洗完为止的时间
	int process2(vector Arr,int a,int b)
	{
		int N = Arr.size();
		int raw = N;
		int col = Arr[N - 2] + (N - 1) * a;
		vector> dp(raw, vector(col, 0));
		//根据上边暴力递归方法的basecase截至条件写出第N行的数据
		for(int j = 0;j= 0; i--)
		{
			int newcol = Arr[i] + (i + 1) * a;
			for (int j = 0; j < newcol; j++)
			{
				int wash = max(Arr[i], j) + a;
				dp[i][j] = min(max(wash, dp[i + 1][j]), max(Arr[i] + b, dp[i + 1][j]));
			}
		}
		return dp[0][0];
	}

	void main_2(vector Arr, int a, int b)
	{
		int ans = process2(eat_all, a, b);
		cout << ans << endl;
		return;
	}


};

int main()
{
	int N = 10;
	int a = 4;
	int b = 5;
	PROBLEM07_add P;
	P.get_eat_all(N);
	P.main_1(P.eat_all,a,b);
	P.main_2(P.eat_all, a, b);
	return 0;
}