lcp339

最长平衡子字符串

方法二：一次遍历

class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        int n = s.length(), pre = 0, cur = 0, res = 0;
        for (int i = 0; i < n; ++i) {
            ++cur;
            char ch = s.charAt(i);
            if (i == n - 1 || s.charAt(i + 1) != ch) { // 分界点
                if (ch == '1')
                    res = Math.max(res, Math.min(pre, cur) * 2);
                pre = cur;
                cur = 0;
            }
        }
        return res;
    }
}

方法一：模拟

class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        if (s.equals(""))
            return 0;
        int res = 0, n = s.length();
        for (int i = 0; i < s.length(); ++i) {
            int cnt0 =  0, cnt1 = 0;
            char pre = '2'; // pre =
            for (int j = i; j < n; ++j) {
                char ch = s.charAt(j);
                if (ch == '0') {
                    if (pre == '1')
                        break;
                    ++cnt0;
                }
                else { // ch == '1'
                    if (pre == '0' || pre == '1' )
                        ++cnt1;
                    if (cnt1 == cnt0) {
                        res = Math.max(res, cnt0 + cnt1);
                        break;
                    }
                }
                pre = ch;

            }
        }
        return res;
    }
}

转换二维数组

方法一：哈希数组

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        int[] cnt = new int[201];
        int max = -1;
        for (int x : nums) {
            cnt[x]++;
            max = Math.max(max, cnt[x]);
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int k = 0; k < max; ++k) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < cnt.length; ++i) {
                if (cnt[i] > 0) {
                    --cnt[i];
                    list.add(i);
                }
            }
            res.add(list);
        }
        return res;
    }
}

老鼠和奶酪

方法一：贪心 + 排序

贪心

\(10^{10}\)复杂度，dp会超时

思路：

1. 如果老鼠1不吃奶酪，全部给老鼠2吃，那么分数为s = sum(reward2)。
2. 如果老鼠1吃了第i颗奶酪，那么分数为s + reward1[i] - reward2[i]
3. 求一个diff数组，并且排序，老鼠1吃diff[i]最大的k个奶酪

class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int sum = 0, n = reward1.length;
        int[] diff = new int[n];
        for (int i = 0; i < n; ++i) {
            sum += reward2[i];
            diff[i] = reward1[i] - reward2[i];
        }
        Arrays.sort(diff);
        for (int i = n - 1; i >= n - k; --i)
            sum += diff[i];
        return sum;
    }
}

2612. 最少翻转操作数

方法一：