LeetCode 131-135

131. 分割回文串

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> temp = new ArrayList<>();

    private boolean isPar(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }

    public void dfs(int begin, String s) {
        if (begin == s.length()) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = begin; i < s.length(); i++) {
            String sub = s.substring(begin, i + 1);
            if (isPar(sub) == true) {
                temp.add(sub);
                dfs(i + 1, s);
                temp.remove(temp.size() - 1);
            }
        }
    }

    public List<List<String>> partition(String s) {
        dfs(0, s);
        return res;
    }
}

132. 分割回文串 II

dp[i]代表s的前i个字符分割回文串的最少次数。
边界：
前i个字符最多分割i次可以变成回文子串。
转移方程：
如果前i个字符是回文串，那么dp[i] = 0。
如果前i个字符不是回文串，那么j从0遍历到i-1，如果从j到i是回文串，那么dp[i] 就等于dp[j] +1。遍历结束后，dp[i]取所有dp[j]+1的最小值。

class Solution {
    private boolean isPar(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }

    public int minCut(String s) {
        int len = s.length();
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            dp[i] = i;
        }
        for (int i = 1; i < len; i++) {
            if (isPar(s, 0, i)) {
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (isPar(s, j + 1, i)) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[len - 1];
    }
}

优化：
可以先预处理

133. 克隆图

class Solution {
    Map<Node, Node> map = new HashMap<>();

    public Node dfs(Node node) {
        if (map.containsKey(node)) {
            return map.get(node);
        }
        Node clone = new Node(node.val, new ArrayList<>());
        map.put(node, clone);
        for (Node n : node.neighbors) {
            clone.neighbors.add(dfs(n));
        }
        return clone;
    }

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        return dfs(node);
    }
}

134. 加油站

由于题目保证答案唯一了。我们可以用totalGas来判断是否能绕行一周，遍历的时候累加gas[i] - cost[i]，如果最后totalGas大于等于0，那么肯定可以绕行一周。
用curGas来判断起点，不断累加curGas，如果某个位置curGas小于0了，那么起点肯定不是这里，此时起点start加1，注意要把curGas置0。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, curGas = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i] - cost[i];
            curGas += gas[i] - cost[i];
            if (curGas < 0) {
                start = i + 1;
                curGas = 0;
            }
        }
        if (totalGas < 0) {
            return -1;
        } else {
            return start;
        }
    }
}

135. 分发糖果

left[i]代表满足比左边的人糖果数多的最少糖果数，right[i]代表满足比右边的人糖果数多的最少糖果数。left right都初始化为1。
先从左往右遍历，保证如果右边的评分比左边高，那么右边的糖果数等于左边的糖果数加1。
再从右往左遍历，保证如果左边的评分比右边高，那么左边的糖果树等于右边的糖果树加1。
最终每个孩子必须既要满足左规则，又要满足右规则，所以分得的糖果数为left和right较大值。

class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] left = new int[len], right = new int[len];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        int res = 0;
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        for (int i = 0; i < len; i++) {
            res += Math.max(left[i], right[i]);
        }
        return res;
    }
}