力扣练习—— 66砖墙

  [3,1,2],

  [1,3,2],

  [2,4],

  [3,1,2],

  [1,3,1,1]]
1
2
3
4
5
6
7
8
9

vector nums;

int num;

stringstream sstream(str);

while(sstream >> num)

{

    nums.push_back(num);

}

return nums;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector > wall;

vector v;

string aLine;

int n,k,data;

cin>>n;

getchar();

for(int i=0; i

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29

}
2.输入说明
首先输入砖墙的行数n，

然后输入n行，每行包含若干整数，表示砖的宽度，整数之间用空格分隔。

每一行砖块的宽度之和应该相等，并且不能超过 INT_MAX。

每一行砖块的数量在 [1,10000] 范围内， 墙的高度n在 [1,10000] 范围内， 总的砖块数量不超过 20,000。

3.输出说明
输出一个整数，表示穿过的最少的砖块数量
4.范例
输入
6
1 2 2 1
3 1 2
1 3 2
2 4
3 1 2
1 3 1 1
输出
2
5.代码

#include
#include
#include
#include
#include
#include
#include
#include 

using namespace std;



vector<int> string2int(string str)

{

	vector<int> nums;

	int num;

	stringstream sstream(str);

	while (sstream >> num)

	{
		nums.push_back(num);
	}

	return nums;

}

int leastBricks(vector<vector<int> > wall)
{
	//墙的总高度-穿过的砖墙 边缘 数= 穿过的 最少 墙体 数
    //使用map记砖块右边缘和最左边的距离，因为墙体两侧的边缘是不算的，所以砖块只要遍历到倒数第二块即可
	unordered_map<int, int>map;
	for (auto vec : wall)//依次遍历每一行
	{
		int sum = 0;
		for (int i = 0; i < vec.size() - 1; i++)//只需要访问到倒数第二块砖块

		{
			sum += vec[i];
			map[sum]++;
		}
	}
	//遍历map，寻找出现次数最多的那个砖块右边缘位置
	int ans = 0;
	for (auto m : map)
	{
		ans = max(ans, m.second);
	}
	return wall.size() - ans;//ans记录总共有多少砖块没有被穿过(就是只穿过边缘)，而墙体总高度是确定的，因此相减得到穿过的最小砖块数量
}

int main()

{

	vector<vector<int> > wall;

	vector<int> v;

	string aLine;

	int n, k, data;

	cin >> n;

	getchar();

	for (int i = 0; i < n; i++)

	{

		getline(cin, aLine);

		v = string2int(aLine);

		wall.push_back(v);
	}

	int res = leastBricks(wall);

	cout << res << endl;

	return 0;

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93