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

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

image.png

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

展开讨论
共 17 个讨论

来贴一个 5298. 口算难题 的题解

因为字母解码的过程中,数字与字母满足一一映射的关系,所以可能的映射关系最多只有 10!10! 种。如果给定一个字母-数字的映射关系,能 O(1)O(1) 检查是否满足题目中的方程,那么问题就解决了。

为了能够 O(1)O(1) 检查,考虑预处理每个字母对方程左式与右式的贡献,设方程左式等于 leftleft,右式等于 rightright
用题目的第一个样例 words = ["SEND","MORE"], result = "MONEY" 来举例。
我们知道 :

left=(1000S+100E+10N+D)+(1000M+100O+10R+E)right=10000M+1000O+100N+10E+Y\begin{aligned} left &= (1000\cdot S +100\cdot E + 10\cdot N + D) + (1000\cdot M +100\cdot O + 10\cdot R + E) \\ right &= 10000\cdot M + 1000\cdot O +100\cdot N + 10\cdot E + Y \end{aligned}

如果从字母贡献的角度来看,可以得到另一种等价的计算方法:

left=1000S+101E+10N+1D+1000M+100O+10R+0Yright=0S+10E+100N+0D+10000M+1000O+0R+1Y\begin{aligned} left &= 1000\cdot S +101\cdot E + 10\cdot N + 1\cdot D + 1000\cdot M +100\cdot O + 10\cdot R + 0\cdot Y \\ right &= 0\cdot S +10\cdot E + 100\cdot N + 0\cdot D + 10000\cdot M +1000\cdot O + 0\cdot R + 1\cdot Y \end{aligned}

如果我们可以预处理出每一个字母对于 left,rightleft, right 的贡献权值,那么一旦确定了一个字母对应的数值,就可以计算出它对于 left,rightleft, right 的贡献并加入其中。当确定完所有数字对应的数值之后,left,rightleft, right 也能随之确定了,就能直接 O(1)O(1) 检查了。

所以,先预处理出上段所介绍的贡献权值,然后使用一个 DFS 枚举字母与数字的对应关系,DFS 的过程中维护 left,rightleft, right 的值并在终点检查。

class Solution {
public:
    bool canZero[26];
    int left[15], right[15], numc;
    map<char, int> toIndex;
    bool vis[15];
    
    void calcWeight(const string &s, int arr[]){
        int n = s.length(), w = 1;
        for (int i = n - 1; i >= 0; i--){
            arr[toIndex[s[i]]] += w;
            w *= 10;
        }
    }
    
    bool dfs(int cur, int n, int l, int r){
        if (cur > n){
            // if (l == r) printf("%d\n", l);
            return l == r;
        }
        
        for (int i = 0; i <= 9; i++){
            if (canZero[cur] == false && i == 0) continue;
            if (vis[i]) continue;
            vis[i] = true;
            bool flag = dfs(cur + 1, n, l + i * left[cur], r + i * right[cur]);
            if (flag) return true;
            vis[i] = false;
        }
        return false;
    }
    
    bool isSolvable(vector<string>& words, string result) {
        numc = 0; toIndex.clear();
        for (auto w: words) for (auto c: w){
            if (toIndex[c] == 0) toIndex[c] = ++numc;
        }
        for (auto c: result){
            if (toIndex[c] == 0) toIndex[c] = ++numc;
        }
        
        for (int i = 0; i < 26; i++) canZero[i] = true;
        canZero[toIndex[result[0]]] = false;
        for (auto w: words) canZero[toIndex[w[0]]] = false;
        
        memset(left, 0, sizeof(left));
        memset(right, 0, sizeof(right));
        calcWeight(result, right);
        for (auto w: words) calcWeight(w, left);
        
        memset(vis, false, sizeof(vis));
        return dfs(1, numc, 0, 0);
    }
};
5

T4时限多少?

4

最后一题可以想到剪枝的地方:
1.前导不能为0
2.result里的字母对应的数字,可以由words里mod 10得到, 不必在[0,9]里面搜索。

3

额,竞争真激烈,做完 3 道题的人这么多,40 分钟做完 3 道,排到了快 500 名
最后一道题比赛结束 6 分钟后才通过,我用的剪枝是,最后一位数之和是否匹配,不匹配就不用往下继续看了
然后看了下做完 4 道题的人咋写的最后一道题,然后旧找到了一个最简洁的版本,这么写,我是真心服气的~

image.png

3

石锤T4标称/数据有误

题干中出现描述:
每个 words[i] 和 result 都会被解码成一个没有前导零的数字。

事实上,标程没有判断是否出现前导零的情况。

现提供测试数据如下:

["AB","CD","EF"]
"GHIJ"

如不允许前导零出现(即 G=0G=0 )则无解,然而期望结果为true

争议样例

另附16ms通过代码(允许出现前导零),如若删除注释部分则可以保持不出现前导零的情况:

class Solution {
    bool ok;
    bool vis[10];
    int n;
    int num[26];
    vector<char> lead;
    
    void dfs(int p,int pp,int jin,vector<string>& words, string& result){
        if (ok) return;
        if (p==n){
            if (jin!=0) return;
            ok=true;/*
            for (auto &i:lead){
                if (num[i-'A']==0){
                    ok=false;
                    return;
                }
            }*/
            for (int i=0;i<26;++i){
                if (num[i]!=-1){
                    cout<<char('A'+i)<<"="<<num[i]<<' ';
                }
            }
            cout<<endl;
            return;
        }
        int rl=jin,rr;
        for (int i=pp;i<words.size();++i){
            if (words[i].length()<=p) continue;
            if (num[words[i][p]-'A']!=-1){
                rl+=num[words[i][p]-'A'];
            }
            else{
                for (int j=0;j<10;++j){
                    if (vis[j]) continue;
                    vis[j]=true;
                    rl+=j;
                    num[words[i][p]-'A']=j;
                    dfs(p,i+1,rl,words,result);
                    vis[j]=false;
                    rl-=j;
                    num[words[i][p]-'A']=-1;
                }
                return;
            }
        }
        if (result.length()<=p){
            if (rl%10==0) dfs(p+1,0,rl/10,words,result);
        }
        else if (num[result[p]-'A']!=-1){
            rr=num[result[p]-'A'];
            if (rr==rl%10) dfs(p+1,0,rl/10,words,result);
        }
        else{
            if (vis[rl%10]) return;
            rr=rl%10;
            vis[rr]=true;
            num[result[p]-'A']=rr;
            dfs(p+1,0,rl/10,words,result);
            vis[rr]=false;
            num[result[p]-'A']=-1;
        }
    }
    
public:
    bool isSolvable(vector<string>& words, string& result) {
        memset(num,-1,sizeof(num));
        memset(vis,false,sizeof(vis));
        n=result.length();
        if (result.length()>1) lead.push_back(result[0]);
        for (auto &e:words){
            n=max(n,(int)e.length());
            reverse(e.begin(),e.end());
            if (e.length()>1) lead.push_back(e[0]);
        }
        reverse(result.begin(),result.end());
        ok=false;
        dfs(0,0,0,words,result);
        return ok;
    }
};

@LeetCode
不清楚如果以后的竞赛中出现题目/数据有误,竞赛积分会怎么算呢?另外,本场比赛大量用户T4出现特判数据的作弊情况(因为测试数据只有26个就一个个答案试过来最终通过题目)。不知道官方怎么看待这种现象?

2

[WeeklyContest]169 Q3 跳跃游戏 III

题目来源

这里有一个非负整数数组 arr,你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时,你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处。

注意,不管是什么情况下,你都无法跳到数组之外。

  • 1 <= arr.length <= 5 * 10^4
  • 0 <= arr[i] < arr.length
  • 0 <= start < arr.length

样例

输入:arr = [4,2,3,0,3,1,2], start = 5
输出:true
解释:
到达值为 0 的下标 3 有以下可能方案: 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 
输入:arr = [4,2,3,0,3,1,2], start = 0
输出:true 
解释:
到达值为 0 的下标 3 有以下可能方案: 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3
输入:arr = [3,0,2,1,2], start = 2
输出:false
解释:无法到达值为 0 的下标 1 处。 

算法1

(bfs) T:O(n) S:O(n)

  • 从start这个点出发,进行广度优先遍历,看看当前点idx对应的arr[idx]是不是等于0,若等于0就停止寻找;若找不到就往左走idx-arr[idx]或者往右走idx+arr[idx]。(越界了就不走)
  • 访问过一个节点就不用再访问了,用一个数组vis来标记

C++ 代码

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vector<bool> vis(n, false);
        
        queue<int> q;
        q.push(start);
        while (!q.empty()) {
            int idx = q.front(); q.pop();
            vis[idx] = true;
            if (arr[idx] == 0) return true;
            int left = idx - arr[idx], right = idx + arr[idx];
            if (left >= 0 && left < n && !vis[left]) q.push(left);
            if (right >= 0 && right < n && !vis[right]) q.push(right);
        }
        
        return false;
    }
};

算法2

(dfs) T:O(n) S:O(n)

  • 从start这个点出发,进行深度优先遍历,先看看左边能不能找到等于0的点,若找到了直接返回;若没找到再看看右边能不能找到等于0的点。都没找到就返回false

C++ 代码

class Solution {
public:
    vector<bool> vis;
    
    bool dfs(const vector<int>& arr, int idx) {
        if (arr[idx] == 0) return true;
        vis[idx] = true;
        int left = idx - arr[idx], right = idx + arr[idx];
        bool res = false;
        if (left >= 0 && left < arr.size() && !vis[left]) 
            res = dfs(arr, left);
        if (!res && right >= 0 && right < arr.size() && !vis[right]) 
            res = dfs(arr, right);
        return res;
    }
    
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vis.resize(n, false);
        return dfs(arr, start);
    }
};
1

就说说最后一道题吧,我用的是模拟方法,首先

  1. 看清楚题意,表达式中使用的不同字符数最大为 10,那么可以想象暴力每个字符的数组的复杂读为O(10×9×8...1)=O(3,628,800)O(10\times9\times8...1)=O(3,628,800),这个量级暴力每个字符对应的数字完全没问题
  2. 2 <= words.length <= 5,1 <= words[i].length, results.length <= 7这两个代表了整个字符长度撑死了也就5×7+7=425\times7+7=42,如果能O(1)O(1)内计算这个和等结果,那么总复杂度也就是O(42×3,628,800)=O(1亿5千万)O(42 \times3,628,800 ) = O(1亿5千万)的级别
  3. 要注意人家说得很清楚不能为前导0,这个地方要稍微得剪枝,然后如果得到正确的结果了,那么其实已经可以回溯了。
  4. 这里还有个优化的地方,就是建立映射,要知道最多10个不同的字符,那么首先建立一个c数组,表示对应字母所在的id,第一次碰见的字符,就用top给他一个标识,这样就可以避免使用set集合这些操作,直接用数组模拟。
import java.util.HashSet;
import java.util.Set;

public class test8 {

    boolean ans;

    int sum(String s,int c[],int[] aim)
    {
        int ans = 0;
        for(int i = 0; i < s.length();i++)
        {
            int x = s.charAt(i) - 'A';
            ans = ans * 10 + aim[c[x]];
        }
        return ans;
    }


    void find(int deep,int max,int c[],int[] aim,boolean flag[],boolean numFlag[],String[] words, String result)
    {
        if(deep == max)
        {
            int LeftSum = 0;
            int RightSum = 0;

            for(int i = 0;i < words.length;i++) LeftSum += sum(words[i],c,aim);
            RightSum += sum(result,c,aim);

            if(LeftSum == RightSum) ans = true;
            return ;
        }


        for(int i = 0;i <= 9;i++)
        {
            if(numFlag[i]) continue; //别人已经读取过这个数字
            if(i == 0 && flag[deep] == false) continue; //这个字母不能为前导0

            numFlag[i] = true;
            aim[deep] = i;
            find(deep + 1,max,c,aim,flag,numFlag,words,result);
            numFlag[i] = false;

            if(ans) return;
        }

        return;
    }

    public boolean isSolvable(String[] words, String result) {

        ans = false;
        final int N = 26;
        int top = 0;
        int c[] = new int[N]; // 用来表示字符对应的数字
        boolean flag[] = new boolean[10]; // 是否可以为前导0
        int aim []  = new int[10]; // 目标数字
        boolean numFlag[] = new boolean[10]; //标识哪些数字已经被使用

        for(int i = 0;i <= 9;i++)
        {
            numFlag[i] = false; //所有空闲数字
            flag[i] = true;
        }
        for(int i = 0;i < N;i++) c[i] = -1;

        for(int i = 0;i < words.length;i++)
        {
            for(int j = 0;j < words[i].length();j++)
            {
                int x = words[i].charAt(j) - 'A';

                if(c[x] == -1)
                {
                    c[x] = top;
                    top++;
                }

                if(j == 0)
                {
                    flag[c[x]] = false;
                }

            }
        }

        for(int j = 0; j < result.length();j++)
        {
            int x = result.charAt(j) - 'A';
            if(c[x] == -1)
            {
                c[x] = top;
                top++;
            }

            if(j == 0)
            {
                flag[c[x]] = false;
            }
        }

        find(0,top,c,aim,flag,numFlag,words,result);
        return ans;
    }

    public static void main(String[] args) {

        test8 of = new test8();
        String[] words = {"LEET","CODE"};
        String result = "POINT";

        System.out.println(of.isSolvable(words,result));
    }
}
1

感觉这难度分布差距太大了...
昨晚的双周赛,难度偏简单...
早上的前3题,就是看谁写的快和网络好...
第4题...直接就放弃了,看到就觉得是 和24点游戏差不多的暴力深搜,
感觉很排斥这种题...静不下心来写...
突然从简单提到超难,过山车一样..
坐等大佬们写出简单明了的题解~

1

和为零的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

Kotlin提交报一个Json的编译Error,多提交几次 就正常了... 且报的Error并没有算到WA里,没有罚时
是服务器的问题?