枚举法，穷搜

Generate Parentheses
Restore IP Addresses
- Code
Palindrome Partitioning
Letter Combinations of a Phone Number
算24点 Snapchat
N-Queens

今天是11-6

比较简单的Backtracking，不需要剪枝和加cache，无脑往下搜就可以了。

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

每一步都有两种可能，加"("或者")"

限制是什么？左括弧先右括弧的数量 <= 左括弧，所以右括弧的剩余数量 > 左括弧的剩余数量

搜索的终止条件是：剩余的leftParenthesis 和 righParenthesis 都为0.

Restore IP Addresses

Given a string containing only digits, restore(还原) it by returning all possible valid IP address combinations.

就是在合适的位置加点。每一步有三种可能：选一位数，两位数，还有三位数。

限制是什么？ segment是否valid segment的个数不能大于4 第一位不能是0.

这道题的启发：

维护什么变量：需要一个标志现在截取位置的变量index，因为最后一个区间和第一个区间需要特殊处理，所以需要一个segment 变量。

每个区间最多3个数，所以循环只需要i < 4.

把判断区间的数字是否成立的功能独立成一个函数，方便操作。

Code

Code

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if(s == null || s.length() == 0) {
            return result;
        }

        helper(s, result, "", 0, 1);
        return result;
    }

    private void helper(String s, List<String> result, String cur, int i, int segment) {
        if(i >= s.length()) {
            return;
        }

        if(segment == 4) {
            if(valid(s.substring(i))) {
                result.add(cur + s.substring(i));
            }
            return;
        }

        // 错误写法
        //for(int j = 0; j < 4 && i + j <= s.length() ; j++) {
        //    String str = s.substring(i, i + j);
        //    if(!valid(str)) {
        //        continue;
        //    }
        //    helper(s, result, cur + str, i + j, segment + 1);
        //}
        for(int j = 1; j < 4 && i + j <= s.length(); j++) {
            String str = s.substring(i, i + j);
            if(valid(str)) {
                // 少考虑到第一个segment的情况
                if(segment == 1) {
                    helper(s, result, str, i + j, segment + 1);
                } else {
                    helper(s, result, cur + "." + str, i + j, segment + 1);
                }
            }
        }
    }

    private boolean valid(String s) {
        if(s == null || s.length > 3) {
            return false;
        }

        if(s.charAt(0) == '0' && s.length() > 1) {
            return false;
        }

        // if(Integer.valueOf(s) > 255 && s.length() > 1) {
        //    return false;
        //}
        //return true;

        int num = Integer.parseInt(s);
        if(num >= 0 && num <= 255) {
            return true;
        }
        return false;
    }
}

Palindrome Partitioning

枚举分割线，每个分割线都有s.length() - 1种可能性。每一步上需要考虑的字问题数量和当前字符串剩余长度相等

判断每种可能是否合法。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if(s == null || s.length() == 0) {
            return result;
        }

        List<String> path = new ArrayList<>();
        helper(s, result, path);
        return result;
    }

    private void helper(String s, List<List<String>> result, List<String> path) {
        if(s.length() == 0) {
            result.add(new ArrayList<>(path));
            return;
        }

        for(int i = 1; i <= s.length(); i++) {
            String str = s.substring(0, i);
            if(isValid(str)) {
                path.add(str);
                helper(s.substring(i), result, path);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isValid(String s) {
        int i = 0;
        int j = s.length() - 1;

        for(; i < j; i++, j--) {
            if(s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }

        return true;
    }
}

可以优化的地方就是每次递归的时候再去判断当前子串是否是 palindrome 太费时了，可以先做一步预处理，把每个子串是否是palindrome 用一个数组记录下来。加cache

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if(s == null || s.length() == 0) {
            return result;
        }
        List<String> path = new ArrayList<>();
        boolean[][] isValid = preProcessing(s);

        helper(s, result, path, isValid, 0);
        return result;
    }

    private boolean[][] preProcessing(String s) {
        int n = s.length();
        boolean[][] result = new boolean[n][n];

        for(int i = 0; i < n; i++) {
            result[i][i] = true;
        }

        for(int i = 0; i < n - 1; i++) {
            if(s.charAt(i) == s.charAt(i + 1)) {
                result[i][i + 1] = true;
            }
        }

        for(int len = 2; len < n; len++) {
            for(int i = 0; i + len < n; i++) {
                if(result[i + 1][i + len - 1] && s.charAt(i) == s.charAt(i + len)) {
                    result[i][i + len] = true;
                }
            }
        }
        return result;
    }

    private void helper(String s, List<List<String>> result, List<String> path, boolean[][] isValid, int index) {
        if(index == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        for(int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            if(isValid[index][i]) {
                path.add(str);
                helper(s, result, path, isValid, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }   
}

Letter Combinations of a Phone Number

把每个digit所代表的char 逐个加入一个stringbuilder

退出条件sb.length() == input.length()

two-level for-loop

for(int i = 0; i < s.length(); i++) {
    String str = map.get(s.charAt(i));
    for(int j = 0; j < str.length(); j++) {
        int len = sb.length();
        sb.append(str.charAt(j));
        dfs(s, result, sb, i + 1);
        sb.setLength(len);
    }
}

算24点 Snapchat

先把所以的排列组合找出来，然后再去给他们在不同的位置加符号。

Permutation的时间复杂度是O(n!)

public class twentyFour {

    public static void main(String[] args) {
        int[] nums = {4,4,10,10};
        System.out.println(get24(nums));
    }

    public static boolean get24(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        Arrays.sort(nums);
        return helper(nums, new ArrayList<>(), new boolean[nums.length]);
    }

    public static boolean helper(int[] nums, List<Integer> elem, boolean[] visited) {
        if(elem.size() == nums.length) {
            for(double num : diffWayToCompute(elem, 0, elem.size() - 1)) {
                if(num == 24.0) {
                    System.out.println(num);
                    return true;
                }
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if(visited[i] || i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            elem.add(nums[i]);
            visited[i] = true;
            if(helper(nums, elem, visited)) return true;
            elem.remove(elem.size() - 1);
            visited[i] = false;
        }

        return false;
    }

    public static List<Double> diffWayToCompute(List<Integer> list, int start, int end) {
        List<Double> result = new ArrayList<>();
        if(start == end) {
            result.add((double)list.get(start));
            return result;
        }

        for(int i = start; i < end; i++) {
            List<Double> left = diffWayToCompute(list, start, i);
            List<Double> right = diffWayToCompute(list, i + 1, end);
            for (Double a : left) {
                for (Double b : right) {
                    result.add(a + b);
                    result.add(a - b);
                    result.add(a * b);
                    if (b != 0) {
                        result.add(a / b);
                    }
                    System.out.println(a);
                    System.out.println(b);
                }
            }
        }
        return result;
    }
}

N-Queens

主要思想就是一句话：用一个循环递归处理子问题。

这种题目都是使用这个套路，就是用一个循环去枚举当前所有情况，然后把元素加入，递归，再把元素移除，这道题目中不用移除的原因是我们用一个一维数组去存皇后在对应行的哪一列，因为一行只能有一个皇后，如果二维数组，那么就需要把那一行那一列在递归结束后设回没有皇后，所以道理是一样的。

这道题最后一个细节就是怎么实现检查当前棋盘合法性的问题，因为除了刚加进来的那个皇后，前面都是合法的，我们只需要检查当前行和前面行是否冲突即可。检查是否同列很简单，检查对角线就是 行的差和列的差的绝对值不要相等 就可以。

穷搜法