lcp355

按分隔符拆分字符串

方法一：模拟

class Solution {
    public List<String> splitWordsBySeparator(List<String> words, char separator) {
        List<String> res = new LinkedList<>();
        for (String word : words) {
            StringBuilder sb = new StringBuilder();
            boolean add = false;
            for (int i = 0; i < word.length(); ++i) {
                char ch = word.charAt(i);
                if (ch == separator) {
                    if (sb.length() > 0) {
                        res.add(sb.toString());
                        sb.setLength(0);
                    }
                    add = !add;
                }
                else if (ch != ' ')
                    sb.append(ch);
                if (i == word.length() - 1 && sb.length() > 0)
                    res.add(sb.toString());
            }
        }
        return res;
    }
}

合并后数组中的最大元素

方法一：贪心

不要直接用数组元素累加，会超出整型范围

class Solution {
    public long maxArrayValue(int[] nums) {
        int n = nums.length;
        long max = 0, pre = nums[n - 1];
        max = Math.max(max, nums[n - 1]);
        for (int i = n - 1; i >= 1; --i) {
            if (pre >= nums[i - 1]) {
                pre += nums[i - 1];
            }
            else {
                pre = nums[i - 1];
            }
            max = Math.max(max, pre);
        }
        return max;
    }
}

长度递增组的最大数目

方法一：排序 + 二分

思路

贫富差距，富人压榨穷人，穷人不能向富人索取

class Solution {
    public int maxIncreasingGroups(List<Integer> usageLimits) {
        Collections.sort(usageLimits, Collections.reverseOrder());
        int n = usageLimits.size(), left = 0, right = n;
        while (left <= right) {
            int mid= (left + right) >> 1;
            if (check(mid, usageLimits))
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }

    private boolean check(int mid, List<Integer> usageLimits) {
        int gap = 0;
        for (int x : usageLimits) {
            gap = Math.min(0, gap + x - mid);
            if (mid > 0)
                --mid;
        }
        return gap >= 0;
    }
}

6942. 树中可以形成回文的路径数

方法一：异或

视频讲解

1. 可以排列的回文串等价于至多一个字母出现奇数次，其余字母出现偶数次
2. 
3. 

class Solution {
    public long countPalindromePaths(List<Integer> parent, String s) {
        int n = parent.size();
        for (int i = 0; i < n; ++i)
            graph.put(i, new HashMap<>());
        for (int i = 1; i < parent.size(); ++i)
            graph.get(parent.get(i)).put(i, 1 << (s.charAt(i) - 'a' ));
        dfs(0, 0);
        return res;
    }

    private void dfs(int node, int xorVal) {
        res += xorCount.getOrDefault(xorVal, 0);
        for (int i = 0; i < 26; ++i)
            res += xorCount.getOrDefault(xorVal ^ (1 << i), 0);
        xorCount.put(xorVal, xorCount.getOrDefault(xorVal, 0) + 1);
        Map<Integer, Integer> nexts = graph.get(node);
        for (int next : nexts.keySet())
            dfs(next, xorVal ^ graph.get(node).get(next));
    }

    long res = 0;
    // 第二个map key: 下标, val: 字符 - 'a'
    Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
    // key: xor的值，val: xor的值出现的次数
    Map<Integer, Integer> xorCount = new HashMap<>();
}