# 8/10, Google Tag

## [Group Shifted Strings](https://leetcode.com/problems/group-shifted-strings/)

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

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

```java
public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> rst = new ArrayList<>();
        // Key : diff1,diff2... single character is "" 
        // Value : list of strings grouped together
        HashMap<String, List<String>> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 0 ; i < strings.length; i++){
            String str = strings[i];
            sb.setLength(0);
            for(int j = 0; j < str.length() - 1; j++){
                int diff = str.charAt(j) - str.charAt(j + 1);
                if(diff < 0) diff += 26;
                sb.append(diff);
                sb.append(',');
            }
            String key = sb.toString();
            if(!map.containsKey(key)) map.put(key, new ArrayList<String>());
            map.get(key).add(str);
        }

        Iterator<String> iter = map.keySet().iterator();
        while(iter.hasNext()){
            rst.add(map.get(iter.next()));
        }

        return rst;
    }
}
```

## [Perfect Squares](https://leetcode.com/problems/perfect-squares/)

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

后来发现 BFS 就能 AC.

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

* **扫合理 moves 的时候，先从大的扫；**
* **用个 hashset 存一下已经访问过的 sum 值，避免重复；**

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

```java
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;
    }
}
```

### 再仔细观察一下这题:

* **我们要凑出来一个和正好是 n 的选择组合；**
* **能选的元素是固定数量的 perfect square (有的会超)**
* **一个元素可以选多次；**

### 这就是背包啊！

```java
public class Solution {
    public int numSquares(int n) {
        // All perfect squares less than n
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 1);
        dp[0] = 0;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j * j <= n; j++){
                if(i - j * j >= 0) dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
}
```

## [Next Permutation](https://leetcode.com/problems/next-permutation/)

### 流程：

* **start 从倒数第二个数起，往左扫，寻找到第一个 nums\[start] < nums\[start + 1] 的位置；**
* **从 start 往后找，找到第一个比 nums\[start] 小的前一个数 (也就是最小的大于等于 nums\[start] 的数)**
* **交换 start , end**
* **把 start + 1 后面的区间翻转，over.**

### 1: 右往左，找下落；

### 2：左往右，找 threshold (换过来的数，怎么说也得比 nums\[start] 大)

### 3：交换，反转。

```java
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](https://leetcode.com/problems/strobogrammatic-number-ii/)

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

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

```java
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](https://leetcode.com/problems/strobogrammatic-number-iii/)

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

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

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

超过 81.92% \~

```java
public class Solution {
    int count = 0;
    public int strobogrammaticInRange(String low, String high) {
        int lowLen = low.length();
        int highLen = high.length();

        char[] num1 = {'0','1','8','6','9'};
        char[] num2 = {'0','1','8','9','6'};

        for(int i = lowLen; i <= highLen; i++){
            char[] number = new char[i];
            dfs(number, num1, num2, 0, low, high);
        }

        return count;
    }

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

        if(left > right){
            String num = new String(number);
            if(compare(low, num) <= 0 && compare(num, high) <= 0) count++;
            return;
        } else if(left == right){
            for(int i = 0; i < 3; i++){
                number[left] = num1[i];
                dfs(number, num1, num2, index + 1, low, high);
            }
        } else {
            for(int i = 0; i < 5; i++){
                if(index == 0 && i == 0) continue;
                number[left] = num1[i];
                number[right] = num2[i];
                dfs(number, num1, num2, index + 1, low, high);
            }
        }
    }

    // -1 : str1 is bigger
    // 1 : str 2 is bigger
    // 0 : equal
    private int compare(String str1, String str2){
        if(str1.length() > str2.length()) return 1;
        else if(str1.length() < str2.length()) return -1;
        else {
            for(int i = 0; i < str1.length(); i++){
                int digit1 = str1.charAt(i) - '0';
                int digit2 = str2.charAt(i) - '0';

                if(digit1 != digit2) return (digit1 > digit2) ? 1: -1;
            }
        }
        // Equal
        return 0;
    }

}
```

## [ Sort Transformed Array](https://leetcode.com/problems/sort-transformed-array/)

我很喜欢这题，挺有创意\~

* **注意点 1 : a = 0 的时候是直线，不能无脑按照抛物线的方式处理；**
* **注意点 2 : 对称轴 -b / 2 \* a 的时候括号顺序是 (double) -b / (2 \* a)**

第一次 AC 的代码\~ 太粗糙，得改改。

```java
public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] rst = new int[nums.length];

        // Is a straight line
        if(a == 0){
            if(b > 0){
                for(int i = 0; i < nums.length; i++){
                    rst[i] = a * nums[i] * nums[i] + b * nums[i] + c;
                }
            } else {
                for(int i = 0; i < nums.length; i++){
                    rst[nums.length - i - 1] = a * nums[i] * nums[i] + b * nums[i] + c;
                }
            }
            return rst;
        }


        double symmetricAxis = -((double) b / (2*a));

        int left = 0;
        int right = nums.length - 1;
        int index = (a < 0) ? 0: nums.length - 1;
        int step = (a < 0) ? 1: -1;

        while(left <= right){
            double leftDis = Math.abs(nums[left] - symmetricAxis);
            double rightDis = Math.abs(nums[right] - symmetricAxis);

            if(leftDis > rightDis){
                rst[index] = a * nums[left] * nums[left] + b * nums[left] + c;
                left ++;
            } else {
                rst[index] = a * nums[right] * nums[right] + b * nums[right] + c;
                right --;
            }

            index += step;
        }

        return rst;
    }
}
```

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

### 这种写法的核心是只看 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) 计算一下就好，也能处理直线的情况。**

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/810-_google_tag.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.