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

• 第一题：流水线打包问题[阿里原题]
• • 代码
• 第二题
• • 代码
• 第三题：打印螺旋矩阵
• • 代码
• 第四题
• • 代码
• 第五题：判读aim是否在矩阵中
• • 代码
• 第七题：topK问题
• • 代码
• 第七题加题:自定义堆解题
• • 代码

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

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

技巧分析: 以某个元素为分割点，求左右两侧信息的技巧

• 思路
  遍历数组，记录每个位置左右两侧(不包括此位置)的信息。这里需要记录左侧所有数据的平均值于全部数组平均值大小的关系；
  左侧的元素平均值记为L_avg,右侧的元素平均值记为R_avg,数组全部元素平均值记为avg；
  如果L_avg>avg，表示需要从左侧拿出物体放在此位置
  如果R_avg>avg, 表示需要从右侧拿出物体放在此位置
  所以一共右4中情况

1. L = L_avg - avg < 0 且 R = R_avg- avg < 0
   需要从此位置往两侧拿物体，因为每个位置每次只能搬动一个物体进行移动，所以位置i处需要调度abs(L) + abs®次才能到达均值
   2）L = L_avg - avg > 0 且 R = R_avg- avg > 0
   需要从两侧拿物体放在i位置上，可以同时进行，所以这里需要调度max(abs(L),abs®)轮
   3）L = L_avg - avg 与 R = R_avg- avg 异号，需要从一侧搬出物体放在位置i上，右需要从位置i上取出物体放在另一侧；因为考虑到位置i初始时可能为零的情况，第一轮不能同时完成，所以需要max(abs(L),abs®)轮次

• code

#include
#include

using namespace std;
 
int get_res(vector Arr)
{
	int ans = 0;
	int LeftSum = 0;//当前索引左侧元素和
	int AllSum = 0;
	for (int i = 0; i < Arr.size(); i++)
	{
		AllSum += Arr[i];
	}
	int avg = AllSum / Arr.size();
	int RightSum = AllSum - LeftSum; //当前索引左侧元素和,起始索引为-1

	for (int i = 0; i < Arr.size(); i++)
	{
		RightSum = RightSum - Arr[i] - LeftSum;
		if (i > 0)
			LeftSum = LeftSum + Arr[i - 1];
		int L = (i > 0) ? LeftSum - avg * (i - 1) : 0;
		int R = RightSum - avg * (Arr.size() - i - Arr[i]);
		if (R > 0 && L > 0)
			ans = max(ans, R + L);
		else
			ans = max(ans, max(abs(R), abs(L)));
	}
	return ans;
}

技巧：大局观，宏观意识

• 思路
  两个指针，都从位置【0,0】开始;一个指针往左移动，撞墙以后往下移动；一个指针往下移动，撞墙以后往右移动；当两个指针到达结束位置的时候返回

• code

#include
#include
using namespace std;

class PROBLEM02
{
public:
    vector ans;
    void process(vector> Arr,int a,int b,int c,int d,bool flag)
    {
        //从右上角角往左下角移动
        if (flag)
        {
            while (a != c+1)
                ans.push_back(Arr[a++][b--]);
        }
        //从左下角往右上角移动
        else
        {
            while (c != a - 1)
                ans.push_back(Arr[c--][d++]);
        }
        return;
    }

    void get_res(vector> Arr)
    {
        bool flag = true;
        int Lx = 0;
        int Ly = 0;
        int Dx = 0;
        int Dy = 0;
        while (Lx != Arr.size())
        {
            process(Arr, Lx, Ly, Dx, Dy, flag);

            //两个指针坐标迁移
            Lx = Ly == Arr[0].size() - 1 ? Lx+1 : Lx;
            Ly = Ly == Arr[0].size()-1 ? Ly : Ly+1;
            Dy = Dx == Arr.size() - 1 ? Dy+1 : Dy;
            Dx = Dx == Arr.size() - 1 ? Dx : Dx+1;

            flag = !flag;
        }
        return;
    }
};

int main()
{
    vector> Arr(4, vector(4, 0));
    for (int i = 0; i < 4; i++)
    {
        Arr[i] = vector{ 1 + i * 4,2 + i * 4,3 + i * 4,4 + i * 4 };
    }
    for (int i = 0; i < Arr.size(); i++)
    {
        for (int j = 0; j < Arr[0].size(); j++)
        {
            cout << Arr[i][j] << " ";
        }
        cout << endl;
    }
    cout << "==============" << endl;
    PROBLEM02 P;
    P.get_res(Arr);
    for (int i = 0; i < P.ans.size(); i++)
        cout << P.ans[i] << " ";
    return 0;
}

技巧：大局观，宏观意识
矩阵的子矩阵可以由左上角和右下角两个位置确定

• 思路1
  螺旋举着的打印时一圈一圈的打印，也就是每次打印一个子矩阵的外圈；所以使用两个指针，一个指针从左上角开始，一个指针从右下角开始；打印确定的矩阵的外圈；

• 思路2
  常规思路

• code

#include
#include

using namespace std;

class PROBLEM03_1
{
public:
	vector ans;
	//(a,b)左上角点,(c,d)右下角点
	void process(vector> Arr,int a,int b,int c,int d)
	{
		//同行
		if (a == c){
			while (b <= d){
				ans.push_back(Arr[a][b]);
				b++;
			}
		}
		//同列
		if (b == d){
			while (a <= c){
				ans.push_back(Arr[a][b]);
				a++;
			}
		}
		//其他情况
		for (int j = b; j < d;j++)
			ans.push_back(Arr[a][j]);
		for (int i = a; i < c; i++)
			ans.push_back(Arr[i][d]);
		for (int j = d; j > b; j--)
			ans.push_back(Arr[c][j]);
		for (int i = c; i > a; i--)
			ans.push_back(Arr[i][b]);	
		return;
	}
	void get_res(vector> Arr)
	{
		int a = 0;
		int b = 0;
		int c = Arr.size()-1;
		int d = Arr[0].size()-1;
		while (a <= c && b <= d)
		{
			process(Arr, a++, b++, c--, d--);
		}
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << " ";
		cout << endl;
		return;
	}
};


class PROBLEM_03_2
{
public:
	vector ans;
	void get_res(vector> Arr)
	{
		int i = 0;//实时记录目前打印到的位置
		int j = 0;

		int idx = 0;//记录现在是第几圈，0表示第一圈
		int flag = (min(Arr.size(), Arr[0].size()) + 1) / 2;//一共需要打印多少圈

		while (idx < flag)
		{
			//0+idx表示起始列，从左往右打印，递增列
			for (j = 0 + idx; j < Arr[0].size() - idx - 1; j++)
				ans.push_back(Arr[i][j]);
			//自上往下打印，递增行
			for (i = 0 + idx; i < Arr.size() - idx - 1; i++)
				ans.push_back(Arr[i][j]);
			//自右往左打印，递减列
			for (j; j >= 0 + idx + 1; j--)
				ans.push_back(Arr[i][j]);
			//自下网上打印，递减行
			for (i; i >= 0 + idx + 1; i--)
				ans.push_back(Arr[i][j]);
			//更新起始位置和圈数
			i++;
			idx++;
		}
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << " ";
		return;
	}
};

技巧：大局观，宏观意识

• 思路
  每次都是四个点的互换(写为固定的函数)，根据每一圈的边长，确定每个外圈需要调用互换函数的次数；左上角和右下角两个点确定一个矩形；

class PROBLEM04
{
public:
	void get_res(vector>& Arr)
	{
		int flag = (min(Arr[0].size(), Arr.size()) + 1)/2;
		int count = 0;//层数
		int idx1 = 0;
		int idy1 = 0;
		int idx2 = Arr.size()-1;
		int idy2 = Arr[0].size()-1;
		while (count < flag)
		{
			int a = idx1 + count;
			int b = idy1 + count;
			int c = idx2 - count;
			int d = idy2 - count;
			for (int offset = 0; (offset+a) < Arr.size() - count - 1; offset++)
			{
				int temp = 0;
				temp = Arr[a][b + offset];
				Arr[a][b + offset] = Arr[c - offset][b];
				Arr[c - offset][b] = Arr[c][d - offset];
				Arr[c][d - offset] = Arr[a + offset][d];
				Arr[a + offset][d] = temp;
			}
			count++;
		}

		for (int i = 0; i < Arr.size(); i++)
		{
			for (int j = 0; j < Arr[0].size(); j++)
			{
				cout << Arr[i][j] << " ";
			}
			cout << endl;
		}
	}
};

技巧：遍历顺序的重要性

• 思路
  思路很简单，从左上角开始遍历，判断与target的大小关系，如果大于target，就往左遍历；如果小于target,就往下遍历；当找到目标的时候返回，或者越界的时候返回；

• code

class PROBLEM05
{
public:
	int flag = false;//是否找到的标志
	//返回行号,如果down一直没找到，返回-1
	int Down(vector> Arr, int i, int j, int target)
	{
		while (i < Arr.size())
		{
			if (Arr[i][j] > target)
				return i;
			else if (Arr[i][j] == target)
				flag = true;
			i++;
		}
		return -1;
	}
	//返回列,如果down一直没找到，返回-1
	int Left(vector> Arr, int i, int j, int target)
	{
		while (j >= 0)
		{
			if (Arr[i][j] < target)
				return j;
			else if (Arr[i][j] == target)
				flag = true;
			j--;
		}
		return -1;
	}
	bool process(vector> Arr, int aim)
	{
		int L1 = Arr.size();
		int L2 = Arr[0].size();
		//作为全局的变量,实时更新当前位置
		int idx_r = 0;
		int idx_c = L2 - 1;
		while (!flag && idx_r != -1 && idx_c != -1)
		{
			if (Arr[idx_r][idx_c] == aim)
				return true;
			//小于当前值往下搜素，遇到大于目标值返回
			else if (Arr[idx_r][idx_c] < aim)
				idx_r = Down(Arr, idx_r, idx_c, aim);
			//大于当前值往左搜索, 遇到小于当前值返回
			else
				idx_c = Left(Arr, idx_r, idx_c, aim);
		}
		return flag;
	}
};


class PROBLEM05_2
{
public:
	bool process(vector> Arr, int target)
	{
		int row = 1;
		int col = Arr[0].size()-1;
		while (row < Arr.size() && col > -1)
		{
			if (Arr[row][col] == target)
				return true;
			else if (Arr[row][col] > target)
				col--;
			else
				row++;
		}
		return false;
	}
};

小根堆的使用

• 思路
  哈希表记录字符出现的频率，然后构建小根堆，根据词频记录前K个；
  当小根堆长度达到K以后，根据堆顶元素的词频与待进入字符词频比较，如果待进入字符的词频到达小根堆的门槛，就把堆顶弹出，把待进入的字符压入小根堆，然后堆内部会重新进行排列，将目前词频最小的字符推在堆顶

class Node
{
public:
	string str;
	int times;
	Node(string s, int t)
	{
		str = s;
		times = t;
	}
};

class PROBLEM07
{
public:
	static bool compare(Node N1, Node N2)
	{
		return N2.times > N1.times;
	}

	vector get_res(vector S,int T)
	{
		//词频统计
		map M;
		for (auto str : S)
		{
			if (M.find(str) != M.end())
				M[str]++;
			else
				M[str] = 1;
		}
		//使用小根堆
		priority_queue,decltype(&compare)> PQ(compare);
		for (auto kv : M)
		{
			if (PQ.size() < T)
			{				
				PQ.emplace(Node(kv.first, kv.second));
			}
			else
			{
				if (PQ.top().times < kv.second)
				{
					PQ.pop();
					PQ.emplace(Node(kv.first, kv.second));
				}
			}
		}
		vector res;
		for (int i = 0; i < T;i++)
		{
			res.push_back(PQ.top().str);
			PQ.pop();
		}
		return res;
	}
};
int main()
{
	vector  S{ "a","b","c","f","s","a","b","c","r","a","b","f","f","f","f","f","s","s","s" };
	PROBLEM07 P;
	vector res = P.get_res(S, 2);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	return 0;
}

第七题中直接给定了所有字符，可以直接将不达标的字符删去，但是如果字符时源源不断地流来的话，因为不知道以后的数据是什么情况，就需要将原来不能进入小根堆的字符 以及其词频也储存起来；

设计投票系统，实时显示前K高的人

• 思路
  1）词频表
  2）堆位置表，可以看作是数组中的索引值(以中序遍历的方式遍历二叉树形成的数组)
  3）最小堆

来一个字符，通过词频表判断字符是否出现过，词频表中添加该字符，如果没出现过那么在堆里边的位置一定为-1；然后判断字符词频有没有达到堆顶门槛，如果达到了，就把堆顶元素与新元素互换，然后堆堆使用heapify方法将首节点往下沉，将最小词频字符拿到堆顶，并实时更新堆位置表；如果堆没有满，将新字符放在堆尾(在堆位置表数组中体现，然后堆该位置调用heapinsert方法，将最小词频字符浮在堆顶)

• code

#include
#include
#include
#include