Joyce' Blog
0%

发表于 更新于

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

题解

动态规划：dp[i]=max(dp[i-1]+nums[i],nums[i])

1
2
3
4
5
6
7
8
9
10
int maxSubArray(vector<int>& nums) {
	int res = nums[0];
	int dp = nums[0];
	for (int i = 1; i < nums.size(); i++)
	{
		dp = max(dp + nums[i], nums[i]);
		res = dp > res ? dp : res;
	}
	return res;
}

动态规划让我觉得自己是渣渣。

题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

题解

按着顺序遍历，思路比较循规蹈矩。

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
vector<int> spiralOrder(vector<vector<int>>& matrix) {
	int m = matrix.size();
	if (!m)return {};
	int n = matrix[0].size();
	if (!n)return {};
	vector<int> res = {};

	int i = 0, j = 0;
	int base_i = 0, base_j = 0;

	while (true)
	{
		while (j < n)
		{
			res.push_back(matrix[i][j]);
			j++;
		}
		j = n - 1;
		base_i++;
		if (base_i == m)break;
		i = base_i;
		while (i < m)
		{
			res.push_back(matrix[i][j]);
			i++;
		}
		i = m - 1;
		n--;
		if (n == base_j)break;
		j = n - 1;
		while (j >= base_j)
		{
			res.push_back(matrix[i][j]);
			j--;
		}
		j = base_j;
		m--;
		if (base_i == m)break;
		i = m - 1;
		while (i >= base_i)
		{
			res.push_back(matrix[i][j]);
			i--;
		}
		i = base_i;
		base_j++;
		if (base_j == n)break;
		j = base_j;
	}
	return res;
}

发表于 更新于

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

题解

还是2的幂次比较好用。

1
2
3
4
5
6
7
8
9
10
double myPow(double x, int n) {
	if (x == 1)return 1;
	double res = 1;
	for (int i = n; i != 0; i /= 2)
	{
		if (i % 2)res *= x;
		x *= x;
	}
	return n < 0 ? 1 / res : res;
}

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

题解

终究躲不过。

n=1时返回1，n皇后问题当n大于等于4才有讨论意义，而且不只有一个解决方案；递归回溯找到每一种解决方案；

行数要记得往下移，不要走回头路，不然会死循环。

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
bool *heng, *shu, *pie, *na;
vector<string> model;

void dfs(vector<vector<string>>& res,int count,int n,int row)
{

	if(count==n){
		res.push_back(model);
		return;
	}
	for (int i = row; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (heng[i])
			{
				if (shu[j] && pie[i + j] && na[n - 1 - i + j])
				{
					model[i][j] = 'Q';
					heng[i] = false; shu[j] = false; pie[i + j] = false; na[n - 1 - i + j] = false;
					dfs(res, count + 1, n,i+1);
					model[i][j] = '.';
					heng[i] = true; shu[j] = true; pie[i + j] = true; na[n - 1 - i + j] = true;
				}
			}
			else
				break;
		}
	}
}
vector<vector<string>> solveNQueens(int n) {
	if (n == 1)return {{"Q"}};
	if (n < 4)return{};
	vector<vector<string>> res;

	string s = "";
	for (int i = 0; i < n; i++)
		s = s + '.';
	for (int i = 0; i < n; i++)
		model.push_back(s);
	heng = new bool[n];
	shu = new bool[n];
	int t = 2 * n - 1;
	pie = new bool[t];
	na = new bool[t];
	for (int i = 0; i < n; i++)
	{
		heng[i] = true; shu[i] = true;
	}
	for (int i = 0; i < t; i++)
	{
		pie[i] = true; na[i] = true;
	}
	dfs(res, 0, n, 0);
	return res;
}

执行用时 :108 ms, 在所有 C++ 提交中击败了6.45%的用户

内存消耗 :9.7 MB, 在所有 C++ 提交中击败了98.99%的用户

时间复杂度太差了，再剪剪枝。

本地没错，交到网上就报错：Heap-buffer-overflow。最后发现是斜线数量没注意。LeetCode对数组越界检查的比较严。

还是位运算效率最高。明天学吧。

题目描述

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

题解

棋盘上棋子的位置信息用一个一维数组来表示就好了，下标表示行数，值表示列数。如果两个格子处在同一斜线上，他们的横纵坐标满足：abs(row1-row2)=abs(col1-col2)。

非递归方法的一个重要问题时何时回溯及如何回溯的问题。程序首先对N行中的每一行进行探测，寻找该行中可以放置皇后的位置，具体方法是对该行的每一列进行探测，看是否可以放置皇后，如果可以，则在该列放置一个皇后，然后继续探测下一行的皇后位置。如果已经探测完所有的列都没有找到可以放置皇后的列，此时就应该回溯，把上一行皇后的位置往后移一列，如果上一行皇后移动后也找不到位置，则继续回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也无法找到可以放置皇后的位置，则说明已经找到所有的解程序终止。如果该行已经是最后一行，则探测完该行后，如果找到放置皇后的位置，则说明找到一个结果，打印出来。但是此时并不能再此处结束程序，因为我们要找的是所有N皇后问题所有的解，此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。

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
int totalNQueens(int n) {
	int* a;
	a = new int[n];
	for (int i = 0; i < n; i++)
		a[i] = -20;
	int res = 0;

	int i = 0, j = 0;
	while (i < n)
	{
		while (j < n)
		{
			bool valid = true;
			for (int k = 0; k < n; k++)
			{
				if (j == a[k] || abs(i - k) == abs(j - a[k]))
				{
					valid = false;
					break;
				}
			}

			if (valid)
			{
				a[i] = j;
				j = 0;
				break;
			}
			++j;
		}
		if (a[i] == -20)
		{
			if (i == 0)
				break;
			--i;
			j = a[i] + 1;
			a[i] = -20;
			continue;
		}
		if (i == n - 1)
		{
			res++;
			j = a[i] + 1;
			a[i] = -20;
			continue;

		}
		i++;
	}
	return res;
}

需要注意初始化a[i]的值时，a[i]的绝对值要比n大，否则在判断该位置是否有效的abs函数处会出现错误。

参考：https://blog.csdn.net/sinat_34166518/article/details/80096219

发表于 更新于

题目描述

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

题解

1
2
3
4
5
6
7
8
9
10
void rotate(vector<vector<int>>& matrix) {
	//转置和水平翻转两个步骤
	int vsize = matrix.size();
	for (int i = 0; i < vsize; i++)
		for (int j = 0; j < i; j++)
			swap(matrix[i][j], matrix[j][i]);
	for (int i = 0; i < vsize; i++)
		for (int j = 0; j < vsize / 2; j++)
			swap(matrix[i][j],matrix[i][vsize - 1 - j]);
}

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :9.3 MB, 在所有 C++ 提交中击败了5.11%的用户

好的吧。

题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

题解

我只能说，质数相乘这种想法是真的牛逼。

按常规想法，每个字符串内部排序然后再做比较，有一些慢啊。排序再比较那这个题有啥意思呢？？

算了，我写排序吧。毕竟质数这种想法，我是想不出来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<string>> groupAnagrams(vector<string>& strs) {
	vector<vector<string>> res;
	map<string, int> m;
	string tmp;
	int count = 0;
	map<string, int>::iterator it;
	for (int i = 0; i < strs.size(); i++)
	{
		tmp = strs[i];
		sort(tmp.begin(), tmp.end());
		it = m.find(tmp);
		if (it != m.end())
			res[it->second].push_back(strs[i]);
		else
		{
			m[tmp] = count;
			res.push_back({ strs[i] });
			count++;
		}
	}
	return res;
}

啊啊啊啊，LeetCode这个傻逼的同步操作，真是气死我了啊啊啊，新整个表就叫同步了吗啊？？？

OK，Fine.

执行用时 :44 ms, 在所有 C++ 提交中击败了89.71%的用户

内存消耗 :17 MB, 在所有 C++ 提交中击败了97.03%的用户

这个数据可以抚慰我心了。

发表于

与学习无关。只是想低调的记录一下 有一丝高兴的心情啦啦啦~

向日葵

奈留

我的兑换券

发表于 更新于

题目描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

题解

还是要回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> permute(vector<int>& nums) {
	vector<vector<int>> res;
	int vsize = nums.size();
	if (!vsize)return {};
	if (vsize == 1)return { nums };
	for (int i=0;i<vsize;i++)
	{
		int t = nums[i];
		nums.erase(nums.begin() + i);
		for (auto it : permute(nums))
		{
			it.push_back(t);
			res.push_back(it);
		}
		nums.insert(nums.begin() + i, t);
	}
	return res;
}

言简意赅我觉得不错。就是效率不咋地。

题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

题解

用set去重似乎有点傻。另外nums是无序的，得先排个序。

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
vector<vector<int>> permute(vector<int>& nums) {
	vector<vector<int>> res;
	int vsize = nums.size();
	if (vsize <= 1)return { nums };
	if (vsize == 2 && nums[0] == nums[1])return { nums };
	//对相同的部分跳过不做排列
	for (int i=0;i<vsize;i++)
	{
		int t = nums[i];
		if (i < vsize - 1 && nums[i + 1] == t)
			continue;
		nums.erase(nums.begin() + i);
		for (auto it : permute(nums))
		{
			it.push_back(t);
			res.push_back(it);
		}
		nums.insert(nums.begin() + i, t);
	}
	return res;
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
	//nums是有序的吗？？
	sort(nums.begin(),nums.end());
	return permute(nums);
}

啊啊啊啊啊我能说什么！虽然效率不是那么高，但是居然第一次！这么快！一次过！啊哈哈哈哈！！

主要的思路还是基于上一题的回溯，只不过这一题有重复数字，对于重复的数字，在排列时只要跳过他们就好啦，因为划去其中一个，然后进行排列，再把这个数字加进去，这个过程相同的数字之间只需要进行一次就好啦。还需要处理的一个地方是，当nums中只有两个相同元素时，就不用再进行排列，直接返回nums。

如果不改变思路的话，这个效率恐怕是提不上去的，递归用的空间略多。

发表于

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

题解

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int jump(vector<int>& nums) {
	//贪心算法
	if (nums.size() == 1)return 0;
	int reach = 0, nextreach = nums[0], steps = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		int t = nums[i] + i;
		if (t > nextreach)nextreach = t;//尽量走得远
		if (nextreach >= nums.size() - 1) return steps+1;
		if (i == reach)
		{
			reach = nextreach;//可跳
			steps++;
		}
	}
	return steps;
}

图的广度优先遍历可以找到某节点到所有节点最少步数，图的深度优先遍历可以找到无环图的拓扑结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int jump(vector<int>& nums) {
	//bfs
	int steps = 0;
	int start = 0, end = 0;
	int max;
	while (end < nums.size() - 1)
	{
		max = end;
		for (int i = start; i <= end; i++)
		{
			int t = i + nums[i];
			if (max < t) max = t;
		}
		start = end + 1;//往前走一步
		end = max;
		steps++;
	}
	return steps;
}

为什么大家的代码这么简洁。

我是渣渣。

发表于 更新于

题目描述

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

题解

或许，你需要来个动态规划？

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
bool isMatch(string s, string p) {
	int len1 = s.length();
	int len2 = p.length();
	bool** value = new bool*[len1+1];
	for (int i = 0; i <= len1; i++)
	{
		value[i] = new bool[len2 + 1];
		value[i][0] = false;
	}
	value[0][0] = true;
	for (int i = 1; i <= len2; i++)
	{
		switch (p[i-1])
		{
		case '*':
			value[0][i] = value[0][i - 1];
			for (int j = 1; j <= len1; j++)
				value[j][i] = value[j - 1][i] || value[j][i - 1];
			break;
		case '?':
			value[0][i] = false;
			for (int j = 1; j <= len1; j++)
				value[j][i] = value[j - 1][i - 1];
			break;
		default:
			value[0][i] = false;
			for (int j = 1; j <= len1; j++)
				value[j][i] = value[j - 1][i - 1] && p[i - 1] == s[j - 1];
			break;
		}
	}
	return value[len1][len2];
}

我要挂一个过分的例子

“abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb”
“**aa****ba\a*bb\aa*ab****aaaaaaa\**a*aaaa**bbabb*b*b**aaaaaaaaa*a*******ba*bbb***a*ba*bb*bb\abbb”

他害我写的递归超时了。

还是怪我，动态规划学得不到位。

发表于

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

说明：

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

题解

num1的第j位和num2的第i-j位相乘再求和(j从len1-1到0，i从len1+len2-2到0)，会得到ans的第i位及i-1位的进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string multiply(string num1, string num2) {
	if (num1 == "0" || num2 == "0")return "0";
	int len1 = num1.length();
	int len2 = num2.length();
	int i = len1 + len2 - 2;
	string res = "";
	int c = 0, x = 0;
	while (i >= 0)
	{
		x = c;//c表示上一次的进位
		for (int j = i < len1 ? i : (len1 - 1); i - j < len2 && j >= 0; j--)
			x += ((num1[j] - '0')*(num2[i - j] - '0'));
		c = x / 10;
		x = x % 10;
		res = char('0' + x) + res;
		i--;
	}
	if(c)res = char('0' + c) + res;
	return res;
}

发表于 更新于

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

题解

几乎一次过，受宠若惊啊哈哈哈哈

感觉没啥难的地方啊，就看图写代码

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
int trap(vector<int>& height) {
	int res = 0;
	int vsize = height.size();
	if (vsize < 3)return 0;
	while (height[0] <= height[1])
	{
		height.erase(height.begin());
		vsize--;
		if (vsize < 3)return 0;
	}
	while (height[vsize - 1] <= height[vsize - 2])
	{
		height.erase(height.end() - 1);
		vsize--;
		if (vsize < 3)return 0;
	}
	int t1 = 0;
	int t2 = t1 + 1;
	while (t2<vsize)
	{
		int h_sum = 0;
		while (t2 < vsize&&height[t2] < height[t1])
		{
			h_sum += height[t2];
			t2++;
		}
		if (t2 < vsize)
		{
			if (t2 - t2>1)
				res = res + height[t1] * (t2 - t1 - 1) - h_sum;
			t1 = t2;
		}
		t2++;
	}
	int limit = t1;
	t1 = vsize - 1;
	t2 = t1 - 1;
	while (t2 >= limit)
	{
		int h_sum = 0;
		while (t2 >= limit && height[t2] < height[t1])
		{
			h_sum += height[t2];
			t2--;
		}
		if (t2 >= limit)
		{
			if(t1 - t2>1)
				res = res + height[t1] * (t1 - t2 - 1) - h_sum;
			t1 = t2;
		}
		t2--;
	}
	return res;
}

发表于 更新于

题目描述

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

题解

数值信息转移到位置信息上

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
int firstMissingPositive(vector<int>& nums) {
	int pos = 0;
	int len = nums.size();
	//第一趟，清理0和负数
	while (pos < len)
	{
		if (nums[pos] <= 0)
			nums[pos] = len + 2;
		++pos;
	}
	//第二趟，处理绝对值在1-len之间的数字。（在处理过程中会再次出现负数）
	pos = 0;
	while (pos < len)
	{
		int t = abs(nums[pos]);
		if (t<=len)
			nums[t - 1] = -abs(nums[t - 1]);//用负号表示pos+1已经出现过
		++pos;
	}
	//数值信息转移到位置信息上
	//第三趟，找到第一个还是正数的位置pos，返回pos+1
	pos = 0;
	while (pos < len)
	{
		if (nums[pos]>0)
			return pos + 1;
		++pos;
	}
	return len + 1;
}

若没有时间的限制，可以直接排序后遍历查找。

若没有空间的限制，可以创建辅助空间后记录。