讨论/题目交流/🏆 第 169 场力扣周赛/
🏆 第 169 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 和为零的N个唯一整数
4 分 - 两棵二叉搜索树中的所有元素
5 分 - 跳跃游戏 III
7 分 - 口算难题

展开讨论
力扣 (LeetCode)发起于 2019-12-29
最近编辑于 2019-12-29

和为零的N个唯一整数

思路

偶数个,就n/2,然后一正一负;奇数个就再挂个0。

答题

vector<int> sumZero(int n)
{
    vector<int> ans;
    for (int i = 0; i < n / 2; i++)
    {
        ans.push_back(i + 1);
        ans.push_back(- i - 1);
    }
    if (n % 2 == 1)
    {
        ans.push_back(0);
    }
    return ans;
}

两棵二叉搜索树中的所有元素

思路

  1. 中序遍历
  2. 排序

答题

void inordered(TreeNode* root, vector<int>& out)
{
	if (root == nullptr) return;
	if (root->left != nullptr)
	{
		inordered(root->left, out);
	}
	out.push_back(root->val);
	if (root->right != nullptr)
	{
		inordered(root->right, out);
	}
}

vector<int> getAllElements(TreeNode* root1, TreeNode* root2)
{
	vector<int> ans;
	inordered(root1, ans);
	inordered(root2, ans);
	sort(ans.begin(), ans.end());
	return ans;
}

跳跃游戏 III

【跳跃游戏 III】dfs

思路

  1. 从起点开始找一条路径到终点
  2. 使用dfs套路即可
  3. 方向为'i + arr[i]i - arr[i]`

答题

void dfs(vector<int>& arr, int i, vector<bool>& vi, bool& ans)
{
	if (ans) return;
	if (i < 0 || i >= arr.size()) return;
	if (vi[i]) return;
	vi[i] = true;
	if (arr[i] == 0)
	{
		ans = true;
		return;
	}
	dfs(arr, i + arr[i], vi, ans);
	dfs(arr, i - arr[i], vi, ans);
}

bool canReach(vector<int>& arr, int start) 
{
	bool ans = false;
	vector<bool> vi(arr.size(), false);
	dfs(arr, start, vi, ans);
	return ans;
}

口算难题

图片.png

【口算难题】列方程回溯剪枝

思路

  1. 模拟合并同类项

比如 SIX + SEVEN + SEVEN = TWENTY ,第 0 阶段的方程式为:X + 2N + inc - Y = 0

  1. 根据数位列出各个方程,有几位数字,就能列出几个方程

因为题目的单词长度最多 8 个字母,所以最多可以列 8 个方程

  1. 回溯时根据每个方程阶段性判断剪枝
    31. 进入个位的方程时,只对涉及的几个字母进行判断,这样就避免了很多无用计算,达到剪枝效果
    32. 升入十位后,只对新出现的字母判断,依旧是剪枝状态
    33. 如果通过就进入下一阶段,如果全部失败,就退回到上一阶段

举例说明

比如:
SEND + MORE == MONEY
0位:D + E + inc - Y = 0
1位:N + R + inc - (E) = 0
2位:(E) + O + inc - (N) = 0
3位:S + M + inc - (O) = 0
4位:inc - (M) = 0

inc 为进位,初始为 0
等于 0 的意思为,个位为 0 即可通过。十位作为进位进入下一阶段

  1. 第 0 阶段,先枚举 DEY 三个字母,方程为D+E-Y的结果,个位为 0 就好,十位就进位到下一阶段
  2. 然后第 1 阶段,因为 E 再上一个阶段确定了,这个阶段确定 NR ,判断的方程用N + R + 进位 - E
  3. 如果不符合了,就原路回溯回去。
  4. 一路到底就返回结果。

执行流程如果想不明白,可以打开输出的注释,在vs里打断点看看

实际操作

  1. 首先要把初始数据转换成分阶段的数据,因为单词最多 8 个字母,所以分成 8 个阶段,使用vector<vector<int>> equation(8, vector<int>(26, 0));来保存每个阶段有哪些字母,用了几个,是加还是减。
  2. 然后根据上面的数据,再找出每个阶段需要确定的字母,前个阶段确定过的字母,这个阶段不用改,只确定新增的。使用vector<vector<char>> chars(8, vector<char>());来保存。
  3. 还需要一些变量来保存查询中的状态。比如 0-9 这 10 个数字哪些使用过了ne,字母被确定了要当做哪个数字en,还有第一位不能为 0 的zeroFlag
  4. dfs中,neen回溯。然后lv是记录现在哪个阶段,idx是当前阶段确定第几个字母。

答题

// 检查当前阶段方程是否成立,以及更新进位inc
bool check(vector<vector<int>>& eq, int lv, vector<int>& en, int& inc)
{
	auto& cur_eq = eq[lv];
	int sum = inc;
	for (int i = 0; i < cur_eq.size(); i++)
	{
		sum += cur_eq[i] * en[i];
	}
	inc = sum / 10;
	return (sum % 10 == 0);
}

void dfs(vector<vector<int>>& eq, vector<vector<char>>& chars, int lv, int idx, int inc, vector<char>& ne, vector<int>& en, vector<bool>& zeroFlag, bool& ans)
{
	if (ans) return;
	if (idx == chars[lv].size())
	{
		//{	// 输出 log
		//	for (size_t i = 0; i < 26; i++)
		//	{
		//		if (en[i] == -1) continue;
		//		char c = i + 'A';
		//		cout << c << ": " << en[i] << "\t";
		//	}
		//	int temp = inc;
		//	string str = (check(eq, lv, en, temp)) ? "check success!" : "check failed";
		//	cout << str << endl;
		//}

		if (!check(eq, lv, en, inc)) return; // 检查方程
		ans = (lv == 7);
		if (ans) return;

		dfs(eq, chars, lv + 1, 0, inc, ne, en, zeroFlag, ans); // 检查成功,升阶段
	}

	if (idx < 0 || idx >= chars[lv].size()) return;
	char c = chars[lv][idx];
	for (int n = 0; n < 10; n++)
	{
		if (ne[n] != 'a') continue;
		if (n == 0 && zeroFlag[c - 'A']) continue;

		en[c - 'A'] = n; // 字母对应的数字
		ne[n] = c; // 数字对应的字母(作用相当于数字是否used)
		int tempInc = inc;

		dfs(eq, chars, lv, idx + 1, inc, ne, en, zeroFlag, ans);

		en[c - 'A'] = -1; // 回溯,把状态改回来
		ne[n] = 'a';
		inc = tempInc;
	}
}

bool isSolvable(vector<string>& words, string result)
{
	vector<char> ne(10, 'a');
	vector<int> en(26, -1);
	vector<bool> zeroFlag(26, false);
	vector<vector<int>> equation(8, vector<int>(26, 0));
	vector<vector<char>> chars(8, vector<char>());

	words.push_back(result);
	for (size_t j = 0; j < words.size(); j++)
	{
		auto w = words[j];
		zeroFlag[w[0] - 'A'] = true;
		size_t d = 0;
		for (size_t i = w.size() - 1; i < w.size(); i--)
		{
			equation[d++][w[i] - 'A'] += (j == words.size() - 1) ? -1 : 1;
		}
	}
	unordered_set<char> us;
	for (size_t d = 0; d < 8; d++)
	{
		for (int i = 0; i < equation[d].size(); i++)
		{
			if (equation[d][i] == 0) continue;
			char c = i + 'A';
			if (us.count(c) != 0) continue;
			chars[d].push_back(c);
			us.insert(c);
		}
	}

	bool ans = false;
	dfs(equation, chars, 0, 0, 0, ne, en, zeroFlag, ans);
	return ans;
}

致谢

比赛时依然没有做出来。T_T
下来也写了好久,改了好几次,还是太菜了。
经验不足,代码写的还是冗余了,有空再改改。

欢迎热烈的交流和点赞!

1
展开全部 17 讨论