7.21号刷题

第一题 89. Gray Code

题目描述

给定n表示可以有n个bit, 要求每次只能改变一个bit位，找出对于n个位所有可能的数字

算法

我们每次在最高位加1，同时利用之前的数字，不断迭代更新

public class grayCode89 {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);

        for (int i = 0; i < n; i++) {
            int size = res.size();
            for (int k = size - 1; k >= 0; k--)
                res.add(res.get(k) | 1 << i);
        }
        return res;
    }
}

第二题 139. Word Break

题目描述

给定一个字符串s和一个单词的字典dict，判断s是否可以分隔成由一个或多个字典中的单词组成的序列。

例如，给定s = “leetcode”, dict = [“leet”, “code”]

返回true，因为”leetcode”可以分隔成”leet code”。

算法

BFS

public class Solution {
    public boolean wordBreak(String s, List<String> wordDictSet) {
        Set<String> wordDict = new HashSet<>(wordDictSet);
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[s.length()];
        queue.offer(0);

        while (!queue.isEmpty()) {
            int start = queue.poll();
            if (!visited[start]) {
                for (int end = start + 1; end <= s.length(); end++) {
                    if (wordDict.contains(s.substring(start, end))) {
                        queue.offer(end);
                        if (end == s.length())
                            return true;
                    }
                }
                visited[start] = true;
            }
        }
        return false;
    }
}

DP

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

第三题 140. Word Break II

题目描述

给定一个字符串s与一组单词的字典dict，在s中添加空格构造句子，使得句中的每一个单词都是字典中的单词。

返回所有可能的句子。

例如给定s = “catsanddog”, dict = [“cat”, “cats”, “and”, “sand”, “dog”].

上例的一个可行解是：[“cats and dog”, “cat sand dog”]

算法

回溯

public class Solution {
    Map<Integer, List<String>> map = new HashMap<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        return backtrack(s, 0, new HashSet<>(wordDict));
    }

    public List<String> backtrack(String s, int start, Set<String> words) {
        if (map.containsKey(start)) {
            return map.get(start);
        }

        List<String> res = new ArrayList<>();
        if (start == s.length()) {
            res.add("");
        }
        
        for (int end = start + 1; end <= s.length(); end++) {
            if (words.contains(s.substring(start, end))) {
                List<String> list = backtrack(s, end, words);
                for (String str : list) {
                    String temp = s.substring(start, end) + (str.equals("") ? "" : " ") + str;
                    res.add(temp);
                }
            }
            
        }
        map.put(start, res);
        return res;
    }
}

第四题 93. Restore IP Addresses

题目描述

给定一串String，将String切成所有可能的IP地址

算法

首先，对于IP地址，注意几点：

1. IP地址需要分成4段
2. 每段的大小为0~255

按照这样的理解，我们即可以写出以下的算法

public class restoreIpAddresses93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        int len = s.length();
        for (int first = 1; first < 4 && first < len - 2; first++) {
            for (int second  = first + 1; second < first + 4 && second < len - 1; second++) {
                for (int third = second + 1; third < second + 4 && third < len; third++) {
                    String part1 = s.substring(0, first), part2 = s.substring(first, second),
                            part3 = s.substring(second, third), part4 = s.substring(third);
                    if (isValid(part1) && isValid(part2) && isValid(part3) && isValid(part4)) {
                        res.add(part1 + "." + part2 + "." + part3 + "." + part4);
                    }
                }
            }
        }
        return res;
    }

    public boolean isValid(String s) {
        if (s.length() > 3 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1) || Integer.valueOf(s) > 255)
            return false;
        return true;
    }
}

第五题 254. Factor Combinations

题目描述

将所有的质因数组合打印出来

算法

public class getFactors254 {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        if (n <= 1) return res;
        backtrack(res, new ArrayList<>(), 2, n);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> cur, int start, int num) {
        if (num <= 1) {
            if (cur.size() > 1)
                res.add(new ArrayList<>(cur));
            return;
        }
        for (int i = start; i <= num; i++) {
            if (num % i == 0) {
                cur.add(i);
                backtrack(res, cur, i, num / i);
                cur.remove(cur.size() - 1);
            }
        }
    }
}

第六题 215. Kth Largest Element in an Array

题目描述

从一个未经排序的数组中找出第k大的元素。注意是排序之后的第k大，而非第k个不重复的元素

测试样例如题目描述

可以假设k一定是有效的， 1 ≤ k ≤ 数组长度

算法

每次获得队列尾的数字，然后将所有比队列尾数字小的调整到其左边，其余在右边。这样，每次我们就可以知道第k个大的数字，通过这样的方法，可以在不进行排序的情况下，最终获得第k个最大的数字。

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quicksort(nums, 0, nums.length - 1, k);
    }

    public int quicksort(int[] nums, int start, int end, int k) {
        int low = start;
        int pivot = nums[end];
        for (int i = start; i < end; i++) {
            if (nums[i] <= pivot) {
                exchange(nums, low++, i);
            }
        }
        exchange(nums, low, end);
        if (low == nums.length - k) {
            return nums[low];
        }
        else if (low > nums.length - k) {
            return quicksort(nums, start, low - 1, k);
        }
        else {
            return quicksort(nums, low + 1, end, k);
        }

    }


    public void exchange(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

第七题 414. Third Maximum Number

题目描述

给定一个整数数组，返回数组中第3大的数，如果不存在，则返回最大的数字。时间复杂度应该是O(n)或者更少。

算法

public class Solution {
    public int thirdMax(int[] nums) {
        
        long largest = Long.MIN_VALUE, second  = Long.MIN_VALUE, res = Long.MIN_VALUE;
        for (int num : nums) {
            if (num == largest || num == second || num == res)
                continue;
            if (num > largest) {
                res = second;
                second = largest;
                largest = num;
            } else if (num > second) {
                res = second;
                second = num;
            } else if (num > res) {
                res = num;
            }
        }
        return res == Long.MIN_VALUE ? (int)largest : (int)res;
    }
}

第八题 14. Longest Common Prefix

题目描述

找出几个String共同的前缀

算法

注意这题和Trie的联系

Verticle Scan

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0)
            return "";

        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);

            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);
            }
        }
        return strs[0];
    }
}

Divide and Conquer

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0)
            return "";
        return DC(strs, 0, strs.length - 1);
    }
    
    public String DC(String[] strs, int start, int end) {
        if (start >= end)
            return strs[start];
        
        int mid = (start + end) / 2;
        String left = DC(strs, start, mid);
        String right = DC(strs, mid + 1, end);
        return commonPrefix(left, right);
    }
    
    public String commonPrefix(String first, String second) {
        if (first.length() > second.length()) {
            String temp = first;
            first = second;
            second = temp;
        }
        for (int i = 0; i < first.length(); i++) {
            if (first.charAt(i) != second.charAt(i))
                return first.substring(0, i);
        }
        return first;
    }
}

第九题 58. Length of Last Word

题目描述

找到最后一个空格之后的那个单词的长度

算法

public class lengthOfLastWord58 {
    public int lengthOfLastWord2(String s) {
        String[] strs = s.split(" ");
        if (strs.length == 0) return 0;
        return strs[strs.length - 1].length();
    }


    public int lengthOfLastWord(String s) {
        return s.trim().length() - s.trim().lastIndexOf(" ") - 1;
    }
}