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

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

image.png

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

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

  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
展开全部 17 讨论