8/10, Google Tag

Group Shifted Strings

挺简单的，和 group anagram 异曲同工。

唯一需要注意的就是 "az" 和 "ba" 同组，说明字母表是环形的。两个字母之间的差如果为负数，就把 diff 加上 26. "az" diff = -25 + 26 = 1; "ba" diff = 1;

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> ans = new ArrayList<List<String>>();
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for(String s:strings){
            StringBuilder sb = new StringBuilder();
            for(int i=1;i<s.length();i++){
                int x = (s.charAt(i)-s.charAt(i-1)+26)%26;
                sb.append(x+",");
            }
            if(s.length()<=0) sb.append(s.length());
            String key = sb.toString();
            if(!map.containsKey(key))
                map.put(key, new ArrayList<String>());
            System.out.println(s+" "+key);
            map.get(key).add(s);
        }

        for(String key : map.keySet()){
            Collections.sort(map.get(key));
            ans.add(map.get(key));
        }
        return ans;
    }
}

Perfect Squares

仔细观察一下这题:

• 我们要凑出来一个和正好是 n 的选择组合；

• 能选的元素是固定数量的 perfect square (有的会超)

• 一个元素可以选多次；

这就是背包啊！两种枚举方式，向后推进，dp[i+j*j] = Math.min(dp[i+j*j], dp[i]+1); 向前查询，dp[i] = Math.min(dp[i], dp[i-j*j]+1);

public int numSquares(int n){
        int sq = (int) Math.sqrt(n);
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            for(int j=1;i-j*j>=0;j++){
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }

public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i=0;i<=n;i++)
            dp[i] = 10000;
        dp[0] = 0;
        for(int i=0;i<=n;i++){
            for(int j=1;i+j*j<=n;j++){
                dp[i+j*j] = Math.min(dp[i+j*j], dp[i]+1);
            }
        }
        return dp[n];
    }

这道题如果空间有限， 还有BFS的解法。

一开始看错了，以为是相乘，搞了一堆因式分解数因数的。。还往数论上想了半天。

后来发现 BFS 就能 AC.

前两次提交都在大数上 MLE，说明 BFS 剪枝不到位。

• 扫合理 moves 的时候，先从大的扫；

• 用个 hashset 存一下已经访问过的 sum 值，避免重复；

以上两招都可以很简便的减少内存和计算时间开销。

public class Solution {
    public int numSquares(int n) {
        // All perfect squares less than n
        List<Integer> moves = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            if(i * i <= n) moves.add(i * i);
            else break;
        }
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        int lvl = 0;
        queue.offer(0);
        while(!queue.isEmpty()){
            int size = queue.size();
            lvl ++;
            for(int i = 0; i < size; i++){
                int sum = queue.poll();
                for(int j = moves.size() - 1; j >= 0; j--){
                    int next = moves.get(j);

                    if(sum + next > n || visited.contains(sum + next)){
                        continue;
                    } else if(sum + next == n){
                        return lvl;
                    } else {
                        visited.add(sum + next);
                        queue.offer(sum + next);
                    }
                }
            }

        }
        return -1;
    }
}

Next Permutation

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length <= 1) return;

        int start = nums.length - 2;
        while(start >= 0 && nums[start] >= nums[start + 1]) start--;

        if(start >= 0){
            int end = start + 1;
            while(end < nums.length && nums[start] < nums[end]) end++;
            end--;
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
        }

        reverse(nums, start + 1);
    }

    private void reverse(int[] nums, int index){
        int end = nums.length - 1;
        while(index < end){
            int temp = nums[index];
            nums[index] = nums[end];
            nums[end] = temp;

            index++;
            end--;
        }
    }
}

Strobogrammatic Number II

注意数字开始不能为0， 需要添加n》3的判断条件。

    public List<String> findStrobogrammatic(int n) {
        List<String> org;
        if(n%2==0){
            org = new ArrayList<String>(Arrays.asList(""));
        }
        else
            org = new ArrayList<String>(Arrays.asList("0","1","8"));
        if(n<2) return org;

        while(n>1){
            ArrayList<String> l = new ArrayList<String>();
            for(String s : org){
                if(n>3)
                    l.add("0" + s + "0");
                l.add("1" + s + "1");
                l.add("6" + s + "9");
                l.add("8" + s + "8");
                l.add("9" + s + "6");
            }
            org = l;
            n=n-2;
        }
        return org;
    }

为什么一个这么简单的 DFS 能超过 89% ..

注意：index == 0 并且 i == 0 的时候要跳过，免得在起始位置填上 0 .

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> list = new ArrayList<>();
        char[] num1 = {'0','1','8','6','9'};
        char[] num2 = {'0','1','8','9','6'};
        char[] number = new char[n];

        dfs(list, number, num1, num2, 0);

        return list;
    }

    private void dfs(List<String> list, char[] number, char[] num1, char[] num2, int index){
        int left = index;
        int right = number.length - index - 1;

        if(left > right){
            list.add(new String(number));
            return;
        }
        // We can fill in 0,1,8 only
        if(left == right){
            for(int i = 0; i < 3; i++){
                number[left] = num1[i];
                dfs(list, number, num1, num2, index + 1);
            }
        } else {
            for(int i = 0; i < num1.length; i++){
                if(index == 0 && i == 0) continue;
                number[left] = num1[i];
                number[right] = num2[i];
                dfs(list, number, num1, num2, index + 1);
            }
        }
    }
}

Strobogrammatic Number III

Google 面经里的 follow-up 是，给定一个上限 n ，输出所有上限范围内的数。

办法土了点，遍历所有 lowLen ~ highLen 区间的长度，生成所有可能的结果，考虑到区间可能是大数，我们就改一下，自己写一个 String compare 函数好了。

后来发现有点多余，可以直接用内置的 str1.compareTo(str2).

public class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int len1 = low.length();
        int len2 = high.length();
        int count = 0;
        for(int i=len1+1;i<len2;i++){
            List<String>list = generate(i);
            count+=list.size();
        }
        for(String s:generate(len1)){
            if(compare(s,low)!=-1 && compare(s,high)!=1) {count++;}
        }

        if(len1==len2) return count;

        for(String s:generate(len2)){
            if(compare(s,low)!=-1 && compare(s,high)!=1) count++;
        }
        return count;
    }

    public List<String> generate(int n){
        ArrayList<String> ans=new ArrayList<String>();
        if(n%2==0){
            ans = new ArrayList<String>(Arrays.asList(""));
        }
        else if(n%2==1){
            ans = new ArrayList<String>(Arrays.asList("0", "1", "8"));
        }
        while(n>1){
            ArrayList<String> next = new ArrayList<String>();
            for(String s : ans){
                if(n>3)
                    next.add("0"+s+"0");
                next.add("1"+s+"1");
                next.add("6"+s+"9");
                next.add("9"+s+"6");
                next.add("8"+s+"8");
            }
            n=n-2;
            ans = next;
        }
        return ans;
    }

    public int compare(String s1, String s2){
        if(s1.length()>s2.length()) return 1;
        else if(s1.length()<s2.length()) return -1;
        for(int i=0;i<s1.length();i++){
            int digit1 = s1.charAt(i) - '0';
            int digit2 = s2.charAt(i) - '0';
            if(digit1 != digit2) return (digit1 > digit2) ? 1: -1;
        }
        return 0;
    }
}

简单写法

public class Solution {

    public int strobogrammaticInRange(String low, String high) {
        List<String> org = new ArrayList<String>();
        for(int i=low.length();i<=high.length();i++){
            org.addAll(helper(i));
        }

        int count =0;
        for(String s:org){
            if((s.length()==low.length() && s.compareTo(low)<0) || (s.length()==high.length() && s.compareTo(high)>0)) continue;
            count++;
        }
        return count;

    }

    public List<String> helper(int n){
                List<String> org;
        if(n%2==0){
            org = new ArrayList<String>(Arrays.asList(""));
        }
        else
            org = new ArrayList<String>(Arrays.asList("0","1","8"));
        if(n<2) return org;

        while(n>1){
            ArrayList<String> l = new ArrayList<String>();
            for(String s : org){
                if(n>3)
                    l.add("0" + s + "0");
                l.add("1" + s + "1");
                l.add("6" + s + "9");
                l.add("8" + s + "8");
                l.add("9" + s + "6");
            }
            org = l;
            n=n-2;
        }
        return org;

    }

}

Sort Transformed Array

这题比较简洁的写法如下，明天学习一个。

这种写法的核心是只看 a 的 “正负”，无所谓 0.

• If a > 0; the smallest number must be at two ends of orgin array;

• If a < 0; the largest number must be at two ends of orgin array;

• 换句话说，a 的符号可以直接确定 two pointer 两端一定有一个 “最大/最小” 的值，每次 O(1) 计算一下就好，也能处理直线的情况。

public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] ans = new int[nums.length];
        int i = 0; int j=nums.length-1; 
        int index = a>0?nums.length-1:0;
        while(i<=j){
            if(a>0){
                ans[index--]=quad(a, b, c, nums[i])>quad(a,b,c,nums[j])?quad(a, b, c, nums[i++]):quad(a, b, c, nums[j--]);
            }
            else
                ans[index++]=quad(a, b, c, nums[i])<quad(a,b,c,nums[j])?quad(a, b, c, nums[i++]):quad(a, b, c, nums[j--]);
        }
        return ans;
    }

    public int quad(int a, int b, int c, int x){
        return a*x*x+b*x+c;
    }

}