传送门：第25场双周赛

拥有最多糖果的孩子

解题思路

由题意可得，模拟即可。当 当前数 加上 额外糖果数 大于等于数组中 最大的糖果数 则为true，反之false。

代码

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int ex) {
        List<Boolean> res = new ArrayList<>();
        int max = candies[0];
        
        // 遍历数组得到最大的糖果数
        for (int x : candies) {
            if (x > max) {
                max = x;
            }
        }
        
        // 三元运算符可省略
        for (int x : candies) {
            res.add(x + ex >= max ? true : false);
        }
        
        return res;
    }
}

运行结果

改变一个整数能得到的最大差值

解题思路

题意为你有两次替换数字的机会，每次替换的位数和替换数可以相同，且需要将数字中所有等于该位的数字全部替换，求改变后的最大差值。

最小数要求：不能为0，不能含前导0（代表最高位不能为0，eg：001、0、012345）。

再看解题实例，我们不难发现，最大的替换一定是将数字替换成9，而最小数除了首位数字只能替换成1，其他位都应该选择替换成0。

由于需要将相同的数字全部替换，且题目数字范围不大，所以直接转换为String，并使用replace函数替换。

代码

class Solution {
    public int maxDiff(int num) {
        // 标志位，因为是全部替换，且数字在0-9之间，所以替换（遇到）过的数位，就不需要去重复操作了
        boolean[] hash = new boolean[10];
        // int转String
        String s_num = Integer.toString(num);
        List<Integer> arr = new ArrayList<>();
        
        // 遍历数字
        for (char ch : s_num.toCharArray()) {
            int bit = ch - ‘0‘;
            // 若当前位没有遇到过
            if (!hash[bit]) {
                hash[bit] = true;
                // 替换得到最大值
                String s_max = s_num.replace(ch, ‘9‘);
                arr.add(Integer.parseInt(s_max));
                // 替换得到最小值
                String s_min = s_num.replace(ch, ‘0‘);
                // 如果最小值含有前导0
                if (s_min.startsWith("0")) {
                    // 则改为替换成1
                    s_min = s_num.replace(ch, ‘1‘);
                }
                // 将字符串转回整数
                arr.add(Integer.parseInt(s_min));
            }
        }
        
        // 升序排序
        arr.sort(new Comparator<>() {
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        });
        
        // 最大值减去最小值即为答案
        return arr.get(arr.size() - 1) - arr.get(0);
    }
}

运行结果

检查一个字符串是否可以打破另一个字符串

解题思路

题目看起来非常复杂，说什么某一个字符串排列能打破另一个字符串的排列即为可以打破，返回true，反之返回false。

当时拿到这题是懵的，全排列？？dfs回溯??？我好像忘了怎么去写了。。。

仔细观察，害，那还要去求什么全排列啊，直接暴力sort *2，然后遍历看有没有打破的??喙不就可以了！（其实还是有点怕WA，但是感觉推论应该是对的，所以，干就好了！??）

代码

class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();

        // 排序数组，默认是字典序a -> z
        Arrays.sort(cs1);
        Arrays.sort(cs2);

        boolean flag1 = false;
        boolean flag2 = false;
        // 看看s1能不能打破s2
        for (int i = 0; i < cs1.length; i++) {
            if (cs1[i] > cs2[i]) {
                flag1 = true;
                break;
            }
        }

        // 看看s2能不能打破s1
        for (int i = 0; i < cs2.length; i++) {
            if (cs1[i] < cs2[i]) {
                flag2 = true;
                break;
            }
        }

        // 返回值的含义为：如果存在可以打破的情况，就返回true
        return !(flag1 && flag2);
    }
}

运行结果

每个人戴不同帽子的方案数

解题思路

哇，T4看起来不难！数据量好像不大，我要开始爆搜了！！！（提交??——运行中??.....(5s后??)——TLE??）

采用了回溯法，属于DFS。（其实严格来说还是暴力）

TLE代码

class Solution {
    private int res;
    private boolean[] used;
    
    public int numberWays(List<List<Integer>> hats) {
        res = 0;
        // 标志位，回溯用
        used = new boolean[45];
        int len = hats.size();
        
        // 从第一个人开始搜
        dfs(hats, 0, len);
        
        return res;
    }
    
    private void dfs(List<List<Integer>> hats, int depth, int end) {
        // end ——— 到达最后一个人，即获得一个解
        if (depth == end) {
            res++;
            return;
        }
        
        // select —— 回溯模板。。。
        List<Integer> arr = hats.get(depth);
        for (int i = 0; i < arr.size(); i++) {
            if (used[arr.get(i)]) {
                continue;
            }
            used[arr.get(i)] = true;
            dfs(hats, depth + 1, end);
            used[arr.get(i)] = false;
        }    
    }
}

TLE现场??

总结

T4不会DP，我太菜了??！

记LeetCode第25场双周赛——菜鸡本菜🤓

原文：https://www.cnblogs.com/detachmliu/p/12821897.html