LeetCode 136-140

136. 只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }
}

137. 只出现一次的数字 II

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) == 1) {
                return key;
            }
        }
        return -1;
    }
}

138. 复制带随机指针的链表

先拷贝val值，原结点到新结点映射到map中，然后再更新next和random。

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

139. 单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()];
        if (set.contains(String.valueOf(s.charAt(0)))) {
            dp[0] = true;
        }
        for (int i = 1; i < s.length(); i++) {
            if (set.contains(s.substring(0, i + 1))) {
                dp[i] = true;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && set.contains(s.substring(j + 1, i + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length() - 1];
    }
}

140. 单词拆分 II

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

    public void dfs(int begin, String s) {
        if (begin == s.length()) {
            StringBuilder sb = new StringBuilder();
            for (String str : temp) {
                sb.append(str + " ");
            }
            sb.deleteCharAt(sb.length() - 1);
            res.add(sb.toString());
            return;
        }

        for (int i = begin; i < s.length(); i++) {
            String sub = s.substring(begin, i + 1);
            if (set.contains(sub) && wordBreak2(s.substring(i + 1))) {
                temp.add(sub);
                dfs(i + 1, s);
                temp.remove(temp.size() - 1);
            }
        }
    }

    public boolean wordBreak2(String s) {
        if ("".equals(s)) {
            return true;
        }
        boolean[] dp = new boolean[s.length()];
        if (set.contains(String.valueOf(s.charAt(0)))) {
            dp[0] = true;
        }
        for (int i = 1; i < s.length(); i++) {
            if (set.contains(s.substring(0, i + 1))) {
                dp[i] = true;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && set.contains(s.substring(j + 1, i + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length() - 1];
    }

    public List<String> wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        dfs(0, s);
        return res;
    }
}