7.2号刷题

第一题 293. Flip Game

题目描述

在一个String中，将连续两个 ++ 换成 –

算法

public class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> list = new ArrayList<>();
        if (s.isEmpty()) return list;

        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                String str = new String();
                str = s.substring(0, i) + "--" + s.substring(i + 2, s.length());
                list.add(str);
            }
        }
        return list;        
    }
}

学到的东西

substring这个函数如果越过边界的话，默认返回空，不需要做超过边界的处理

第二题 294. Flip Game II

题目描述

现在求第一个走的人是否能赢

算法

回溯

查看下一个选择的人是否能赢

public class canWin294 {
    public static boolean canWin2(String s) {
        if (s.isEmpty()) return false;

        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                String str = s.substring(0, i) + "--" + s.substring(i + 2, s.length());
                if (!canWin2(str)) return true;
            }
        }
        return false;
    }
}

动态规划

把之前的状态进行存储，减少时间消耗

public class Solution {
    public boolean canWin(String s) {
        if (s.isEmpty()) return false;
        Map<String, Boolean> map = new HashMap<>();
        return canWin(s, map);
    }
    
    public boolean canWin(String s, Map<String, Boolean> map) {
        if (map.containsKey(s)) return map.get(s);
        
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                String t = s.substring(0, i) + "--" + s.substring(i + 2, s.length());
                if (!canWin(t, map)) {
                    map.put(s, true);
                    return true;
                }
            }
        }
        map.put(s, false);
        return false;
    }
}

第三题 606. Construct String from Binary Tree

题目描述

将二叉树序列化为字符串，形式为”root(left)(right)”，空节点表示为”()”。所有不产生歧义的空括号可以省去。

算法

First Version

public class tree2str606 {
    public String tree2str(TreeNode t) {
        String s = "";
        return backtrack(s, t);
    }

    public String backtrack(String s, TreeNode root) {
        if (root == null) return s;
        s += root.val;

        if (root.left == null && root.right == null) return s;

        //only backtrack left part
        if (root.right == null) {
            s += "(";
            s = backtrack(s, root.left);
            s += ")";
        } else {
            s += "(";
            s = backtrack(s, root.left);
            s += ")(";
            s = backtrack(s, root.right);
            s += ")";
        }
        return s;
    }
}

Refactory

public class Solution {
    public String tree2str(TreeNode t) {
        StringBuilder sb = new StringBuilder();
        helper(sb, t);
        return sb.toString();
    }

    public void helper(StringBuilder sb, TreeNode root) {
        if (root != null) {
            sb.append(root.val);
            if (root.left != null || root.right != null) {
                sb.append("(");
                helper(sb, root.left);
                sb.append(")");
                if (root.right != null) {
                    sb.append("(");
                    helper(sb, root.right);
                    sb.append(")");
                }
            }
        }
    }
}

第四题 520. Detect Capital

题目描述

判断单词是否为首字母大写、全部大写或者全部小写

注意：输入单词非空并且只包含大写或者小写字母

算法

统计法

public class detectCapitalUse520 {
    public boolean detectCapitalUse2(String word) {
        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            if ('Z' - word.charAt(i) >= 0) count++;
        }
        return (count == 0 || count == word.length() || (count == 1 && 'Z' - word.charAt(0) >= 0));
    }
}

正则匹配

public class detectCapitalUse520 {
    public boolean detectCapitalUse(String word) {
        return word.matches("[A-Z]+|[a-z]+|[A-Z][a-z]+");
    }
}

第五题 383. Ransom Note

题目描述

给定两个字符串ransomNote和magazine，编写函数判断magazine中的字符是否可以完全包含ransomNote中的字符。

注意：可以假设字符串中只包含小写字母。

算法

public class canConstruct383 {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] store = new int[26];

        for (char c : magazine.toCharArray()) store['z' - c]++;

        for (char c : ransomNote.toCharArray()) {
            int index = 'z' - c;
            store[index]--;
            if (store[index] < 0) return false;
        }
        return true;
    }
}

第六题 539. Minimum Time Difference

题目描述

给定一组24小时制的时间，格式为“小时：分钟”，求任意两组时间中分钟数间隔的最小值。

注意：

1. 给定时间至少2个，至多20000个。
2. 给定时间是合法的，范围在00:00到23:59之间。

算法

利用bucket sort进行排序，然后找出最近的两个时间，时间复杂度O(n)

public class Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() >= 1440) return 0;
        boolean[] tag = new boolean[1440];
        int minNum = Integer.MAX_VALUE, maxNum = Integer.MIN_VALUE;
        
        for (String str : timePoints) {
            int hour = Integer.valueOf(str.split(":")[0]);
            int minute = Integer.valueOf(str.split(":")[1]);
            if (tag[hour * 60 + minute]) return 0;
            tag[hour * 60 + minute] = true;
            minNum = Math.min(minNum, hour * 60 + minute);
            maxNum = Math.max(maxNum, hour * 60 + minute);
        }
        
        int min = 1440 - (maxNum - minNum);
        int pre = -1;
        for (int i = 0; i < 1440; i++) {
            if (tag[i]) {
                if (pre != -1)
                    min = Math.min(min, i - pre);
                pre = i;
            }
        }
        return min;
    }
}

第七题 22. Generate Parentheses

题目描述

给定n个括号()，找出这些括号所有的搭配方式

算法

回溯，并计算左右括号的匹配情况

public class generateParenthesis22 {
    List<String> res;
    public List<String> generateParenthesis(int n) {
        res = new ArrayList<>();
        helper(new StringBuilder(), 0, 0, n);
        return res;
    }

    public void helper(StringBuilder sb, int left, int right, int n) {
        if (left == n && right == n) {
            res.add(sb.toString());
            return;
        }

        if (left < n) {
            helper(sb.append("("), left + 1, right, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right < left) {
            helper(sb.append(")"), left, right + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }

    }
}

第八题 17. Letter Combinations of a Phone Number

题目描述

对于8字键盘格，一个数字将会对应多个号码，找出数字对应的所有的字母组合可能性

算法

回溯

public class letterCombinations17 {
    List<String> res;
    String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        res = new ArrayList<>();
        if (digits.isEmpty()) return res;
        helper(new StringBuilder(), 0, digits);
        return res;
    }

    public void helper(StringBuilder sb, int length, String digits) {
        if (length == digits.length()) {
            res.add(sb.toString());
            return;
        }
        int number = Character.getNumericValue(digits.charAt(length));
        for (char c : mapping[number].toCharArray()) {
            sb.append(c);
            helper(sb, length + 1, digits);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

利用队列

public class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> ans = new LinkedList<>();
        if (digits.isEmpty()) return ans;
        String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ans.add("");
        
        for (int i = 0; i < digits.length(); i++) {
            int x = Character.getNumericValue(digits.charAt(i));
            while (ans.peek().length() == i) {
                String t = ans.poll();
                for (char c : mapping[x].toCharArray())
                    ans.add(t + c);
            }
        }
        return ans;        
    }
}

第九题 20. Valid Parentheses

题目描述

将所有左括号和右括号匹配

算法

利用Stack 判断是否所有括号都得到了相应的匹配

public class isValid20 {
    public boolean isValid(String s) {
        if (s.isEmpty()) return true;

        String open = "({[";
        List<Character> store = new ArrayList<>();
        for (char c : s.toCharArray()) {

            if (open.indexOf(c) >= 0) {
                store.add(c);

            } else {
                if (store.isEmpty()) return false;
                char last = store.get(store.size() - 1);

                if (last == '(' && c != ')') return false;
                else if (last == '{' && c != '}') return false;
                else if (last == '[' && c != ']') return false;

                store.remove(store.size() - 1);
            }
        }

        return store.isEmpty();
    }
}