Joyce' Blog
0%

发表于

题目描述

给定一个链表，判断链表中是否有环。你能用 O(1)（即，常量）内存解决此问题吗？

题解

用快慢指针的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool hasCycle(ListNode *head) {
	if (!head||!head->next)return false;
	ListNode *t1 = head, *t2 = head->next;
	while (t1 && t2&&t1!=t2)
	{
		t1 = t1->next;
		t2 = t2->next;
		if (t2)
			t2 = t2->next;
		else
			return false;
	}
	if (!t2)
		return false;
	return true;
}

发表于

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

题解

利用位运算和有限状态自动机。对32位每位分开看待，按位加，出现三次的对应位加起来一定是3的倍数，所以模3就三种情况：00, 01,10. 模3之后每一位剩下的就是只出现了一次的那个数。余数有两位，记为two, one。int共32位，用两个数twos, ones存放，使用位运算。主要就是用有限自动机，找出如何计算twos和ones了。最后的结果每一位只会是01或00，因此ones的值就是要找的数字。

1
2
3
4
5
6
7
8
9
int singleNumber(vector<int>& nums) {
	int ones = 0, twos = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		ones = ones ^ nums[i] & ~twos;
		twos = twos ^ nums[i] & ~ones;
	}
	return ones;
}

发表于

题目描述

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

题解

先向左看，如果a[i]>a[i-1]，则有c[i]=c[i-1]+1；否则c[i]=1。再向右看，如果a[i]>a[i+1], 则有c[i]=(c[i], c[i+1]+1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int candy(vector<int>& ratings) {
	int num = ratings.size();
	int* ca = new int[num];
	for (int i = 0; i < num; i++)
		ca[i] = 1;
	for (int i = 1; i < num; i++)
		if (ratings[i] > ratings[i - 1])
			ca[i] = ca[i - 1] + 1;
	for (int i = num - 2; i >= 0; i--)
		if (ratings[i] > ratings[i + 1])
			ca[i] = max(ca[i], ca[i + 1] + 1);
	int res = 0;
	for (int i = 0; i < num; i++)
		res += ca[i];
	return res;
}

还有波峰波谷一次遍历的方法。

发表于

题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

  • 如果题目有解，该答案即为唯一答案。
  • 输入数组均为非空数组，且长度相同。
  • 输入数组中的元素均为非负数。

题解

gas<cost的点一定不会是起点，根据这一点，筛选出可能是起点的编号，然后对每一个编号进行计算模拟行驶过程，若计算中出现负数，则考虑下一个；若结果为非负数，则直接返回。

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
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
	int vsize = gas.size();
	vector<int> lefts,prob;
	int sum = 0;
	for (int i = 0; i < vsize; i++)
	{
		int t = gas[i] - cost[i];
		sum += t;
		lefts.push_back(t);
		if (t >= 0)
			prob.push_back(i);
	}
	if (sum < 0)return -1;

	//处理有可能是起点的编号集合
	int num = prob.size();
	int start = prob[0];
	for (int i = 0; i < num; i++)
	{
		start = prob[i];
		int oil = 0;
		int k = 0;
		while (k<vsize)
		{
			oil += lefts[(start + k) % vsize];
			if (oil < 0)
				break;
			k++;
		}
		if (oil >= 0)return start;
	}
	return start;
}

效率低得可怜，但至少是自创。

还看到一个高效巧妙的方法：为了让总油量剩余值（黑色折线）任意部分都不小于0（都在X轴以上），需要向上移动黑色折线，直到所有点都在X轴或X轴以上。此时，处在X轴的点即为出发点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
{
	int vsize = gas.size();
	int spare = 0;
	int minSpare = INT_MAX;
	int minIndex = 0;
	for (int i = 0; i < vsize; i++)
	{
		spare += (gas[i] - cost[i]);
		if (spare < minSpare)
		{
			minSpare = spare;
			minIndex = i;
		}
	}
	if (spare < 0)return -1;
	return (minIndex + 1) % vsize;
}

发表于 更新于

题目描述

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

题解

  1. 使用 HashMap 存储所有访问过的节点和克隆节点。HashMap 的 key 存储原始图的节点，value 存储克隆图中的对应节点。visited 用于防止陷入死循环，和获得克隆图的节点。

  2. 将第一个节点添加到队列。克隆第一个节点添加到名为 visited 的 HashMap 中。

  3. BFS 遍历

    从队列首部取出一个节点。
    遍历该节点的所有邻接点。
    如果某个邻接点已被访问，则该邻接点一定在 visited 中，那么从 visited 获得该邻接点。
    否则，创建一个新的节点存储在 visited 中。
    将克隆的邻接点添加到克隆图对应节点(步骤1中得到的首部节点)的邻接表中。

作者：LeetCode
链接：https://leetcode-cn.com/problems/clone-graph/solution/ke-long-tu-by-leetcode/

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
#include<unordered_map>
Node* cloneGraph(Node* node) {
	if (!node)return NULL;
	unordered_map<Node*, Node*>visited;
	visited[node] = new Node(node->val);
	queue<Node*>que;
	que.push(node);

	Node* tmpNode;
	vector<Node*> tmpVec;
	while (!que.empty())
	{
		tmpNode=que.front();
		que.pop();
		tmpVec = tmpNode->neighbors;
		for (Node* n : tmpVec)
		{
			if (!visited.count(n))
			{
				Node* newNode = new Node(n->val);
				visited[n] = newNode;
				que.push(n);
			}
			visited[tmpNode]->neighbors.push_back(visited[n]);
		}
	}
	return visited[node];
}

发表于

题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

题解

使用动态规划的方法，可以利用上次的动态规划判断回文字符串的方法做优化。

dp[i]：前缀子串 s[0:i] （包括索引 i 处的字符）符合要求的最少分割次数

状态转移方程： dp[i] = min(dp[j] + 1 if s[j + 1: i] 是回文 for j in range(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
30
31
32
33
34
35
36
int minCut(string s) {
	int slen = s.length();
	bool **isPali = new bool*[slen];
	for (int i = 0; i < slen; i++)
		isPali[i] = new bool[slen];
	for (int i = 0; i < slen; i++)
		isPali[i][i] = 1;
	for (int i = 1; i < slen; i++)
		isPali[i][i - 1] = 1;
	for (int i = 1; i < slen; i++)
	{
		for (int j = 0; j < slen-i; j++)
		{
			isPali[j][i + j] = isPali[j + 1][i + j - 1] && (s[j] == s[i + j]);
		}
	}
	int* dp = new int[slen];
	for (int i = 0; i < slen; i++)
		dp[i] = i;
	for (int i = 1; i < slen; i++)
	{
		if (isPali[0][i])
		{
			dp[i] = 0;
			continue;
		}
		for (int j = 0; j < i; j++)
		{
			if (isPali[j + 1][i])
			{
				dp[i] = min(dp[j] + 1, dp[i]);
			}
		}
	}
	return dp[slen - 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
bool **dp;
int slen = 0;
void dfsHelper(string& s,int ps,int& tmp,int& res)
{
	if (tmp > res)return;
	if (ps >= slen)
	{
		res = tmp < res ? tmp : res;
		return;
	}
	for (int i = ps; i < slen; i++)
	{
		if (dp[ps][i])
		{
			tmp++;
			dfsHelper(s, i + 1, tmp, res);
			tmp--;
		}
	}
}
int minCut(string s) {
	slen = s.length();
	dp = new bool*[slen];
	for (int i = 0; i < slen; i++)
		dp[i] = new bool[slen];
	for (int i = 0; i < slen; i++)
		dp[i][i] = 1;
	for (int i = 1; i < slen; i++)
		dp[i][i - 1] = 1;
	for (int i = 1; i < slen; i++)
	{
		for (int j = 0; j < slen-i; j++)
		{
			dp[j][i + j] = dp[j + 1][i + j - 1] && (s[j] == s[i + j]);
		}
	}
	int res = slen, tmp = 0;
	dfsHelper(s,0, tmp, res);
	return res-1;
}

还是很菜啊……所以更不能一直躺着啊……

发表于

题目描述

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)

题解

从最小的开始往后找。为了去重并把搜索降到O(1)，使用unordered_set。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int longestConsecutive(vector<int>& nums) {
	unordered_set<int> s;
	s.insert(std::begin(nums), std::end(nums));
	int res = 0;
	for (int num : s)
	{
		if (!s.count(num - 1))
		{
			int cur = num;
			int len = 1;
			while (s.count(cur + 1))
			{
				cur++;
				len++;
			}
			res = len > res ? len : res;
		}
	}
	return res;
}

发表于 更新于

题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

题解

分两步。第一步对s使用dp方法确定回文子串。第二步使用回溯法进行分割。

第一步，dp[i][j]代表s(i,j)是否为回文（包含i和j）字符串，注意当ij之间的字符大于等于3个时，dp[i][j]=dp[i+1][j-1]&&s[i]\==s[j]，即i递减，j递增，又j>=i，即可确定i，j的递推方向。第二步，dfs(ps)，将对dp[ps][i] (ps<=i<n)中为true的，s(ps,i)放入组合，进行dfs，当ps==n时，当前组合放入结果。注意dfs的优化，模版类使用传址，复用变量（如字符串s的大小）使用全局变量。

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
int len; bool **dp;
void dfsHelper(string& s,int ps, vector<string>& tmp, vector<vector<string>>& res)
{
	if (ps >=len)
	{
		res.push_back(tmp);
		return;
	}
	for (int i = ps; i < len; i++)
	{
		if (dp[ps][i])
		{
			tmp.push_back(s.substr(ps, i - ps + 1));
			dfsHelper(s, i+1, tmp, res);
			tmp.pop_back();
		}
	}
}
vector<vector<string>> partition(string s) {
	len = s.length();
	dp =new bool*[len];
	for (int i = 0; i < len; i++)
		dp[i] = new bool[len];
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++)
			dp[i][j] = 0;
	for (int i = 0; i < len; i++)
		dp[i][i] = 1;
	for (int i = 1; i < len; i++)
		dp[i][i - 1] = 1;
	for (int i = 1; i < len; i++)
	{
		for (int j = 0; j < len - i; j++)
		{
			dp[j][j + i] = dp[j + 1][j + i - 1] && (s[j] == s[j + i]);
		}
	}
	vector<string> tmp = {};
	vector<vector<string>> res;
	dfsHelper(s, 0, tmp, res);
	return res;
}

发表于 更新于

题目描述

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

题解

（好像围棋啊……）

题目要求替换所有被包围的’O’，其实可以找出所有未被包围的’O’：绕着矩阵的最外圈转一圈，碰到’O’，就宽度优先搜索，经过的所有’O’都标记为’Y’，最后，将所有的’O’改为’X’，所有的’Y’改为’O’。

不过这样做最大的问题在于时间超限……神奇，解决方案是：每在边框上找到一个’O’，别急着bfs，把所有合适的点都入队之后，再对所有点bfs。这样居然会把时间超限变成用时击败98% ！

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
queue<pair<int, int>> q;
void bfsColor(vector<vector<char>>& board,int len,int width)
{
	while (!q.empty())
	{
		pair<int, int> tmp = q.front();
		q.pop();
		int i = tmp.first;
		int j = tmp.second;
		board[i][j] = 'Y';
		if ((i - 1 >= 0) && (board[i - 1][j] == 'O'))
			q.push(pair<int, int>(i - 1, j));
		if ((i + 1 < len) && (board[i + 1][j] == 'O'))
			q.push(pair<int, int>(i + 1, j));
		if ((j - 1 >= 0) && (board[i][j - 1] == 'O'))
			q.push(pair<int, int>(i, j - 1));
		if ((j + 1 < width) && (board[i][j + 1] == 'O'))
			q.push(pair<int, int>(i, j + 1));
	}
}
void solve(vector<vector<char>>& board) {
	int len = board.size();
	if (!len)return;
	int width = board[0].size();
	if (!width)return;
	for (int i = 0; i < len; i++)
	{
		if (board[i][0] == 'O')
			q.push(pair<int, int>(i, 0));
		if (board[i][width - 1] == 'O')
			q.push(pair<int, int>(i, width - 1));
	}
	for (int i = 0; i < width; i++)
	{
		if (board[0][i] == 'O')
			q.push(pair<int, int>(0, i));
		if (board[len - 1][i] == 'O')
			q.push(pair<int, int>(len - 1, i)); 
	}
	bfsColor(board,len, width);
	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < width; j++)
		{
			if (board[i][j] == 'O')
				board[i][j] = 'X';
			else if (board[i][j] == 'Y')
				board[i][j] = 'O';
		}
	}
}

发表于

题目描述

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶子节点生成的所有数字之和。

题解

1
2
3
4
5
6
7
8
9
10
11
int helper(TreeNode* root, int i)
{
	if (!root)return 0;
	int tmp = i * 10 + root->val;
	if (!root->left && !root->right)
		return tmp;
	return helper(root->left, tmp) + helper(root->right, tmp);
}
int sumNumbers(TreeNode* root) {
	return helper(root, 0);
}

我这是怎么了啊……