Algorithm Notes
  • Introduction
  • Search & Backtracking 搜索与回溯
    • Tree 与 BackTracking 的比较
    • Subsets, Combination 与 Permutation
    • Subsets & Combinations & Combination Sum
    • 枚举法
    • N 皇后 + 矩阵 Index Trick
    • Sudoku 数独 + 矩阵 Index Trick
    • Word Ladder I & II
    • Number of ways 类
    • DFS flood filling
    • Strobogrammatic 数生成
    • String 构造式 DFS + Backtracking
    • Word Pattern I & II
    • (G) Binary Watch
    • (FB) Phone Letter Combination
    • 常见搜索问题的迭代解法
  • String,字符串类
    • 多步翻转法
    • Substring 结构和遍历
    • Palindrome 问题
    • Palindrome Continued
    • String / LinkedList 大数运算
    • 序列化与压缩
    • 5/24 String 杂题
    • Knuth–Morris–Pratt 字符串匹配
    • Lempel–Ziv–Welch 字符串压缩算法
    • (G) Decode String
    • (G) UTF-8 Validation
  • Binary Tree,二叉树
    • 各种 Binary Tree 定义
    • LCA 类问题
    • 三序遍历,vertical order
    • Post order traversal 的应用
    • Min/Max/Balanced Depth
    • BST
    • 子树结构
    • Level Order traversal
    • Morris 遍历
    • 修改结构
    • 创建 / 序列化
    • 子树组合,BST query
    • 路径与路径和
    • NestedInteger 类
    • (FB) 从 Binary Tree Path 看如何递归转迭代
    • (FB) Binary Tree Path 比较路径大小
    • 比较好玩的 Binary Tree 概率题
  • Segment & Fenwick Tree,区间树
    • Segment Tree 基础操作
    • Segment Tree 的应用
    • Fenwick Tree (Binary Indexed Tree)
    • Range Sum Query 2D - Immutable
  • Union-Find,并查集
    • Union-Find,并查集基础
    • Union-Find, 并查集应用
  • Dynamic Programming, 动态规划
    • 6/20, 入门 House Robber
    • 7/12, Paint Fence / House
    • 6/24, 滚动数组
    • 6/24, 记忆化搜索
    • 6/24, 博弈类 DP
    • 博弈类DP, Flip Game
    • 6/25, 区间类DP
    • 6/27, subarray 划分类,股票
    • 7/2, 字符串类
    • Bomb Enemies
    • 8/2,背包问题
    • (G) Max Vacation
    • (11/4新增) AST 子树结构 DP
  • LinkedList,链表
    • 6/9, LinkedList,反转与删除
    • 6/11, LinkedList 杂题
    • (FB) 链表的递归与倒序打印
  • LinkedIn 面经,算法题
    • 6/17, LinkedIn 面经题
    • 6/28, LinkedIn 面经题
    • 7/6, LinkedIn 面经
    • Shortest Word Distance 类
    • DFA Parse Integer
  • Two Pointers,双指针
    • 3 Sum, 3 Sum Closest / Smaller, 4 Sum
    • 对撞型,灌水类
    • 对撞型,partition类
    • Wiggle Sort I & II
    • 双指针,窗口类
    • 双指针,窗口类
    • Heap,排序 matrix 中的 two pointers
  • Bit & Math,位运算与数学
    • Bit Manipulation,对于 '1' 位的操作
    • Math & Bit Manipulation, Power of X
    • 坐标系 & 数值计算类
    • Add Digits
    • 用 int 做字符串 signature
  • Interval 与 扫描线
    • Range Addition & LCS
    • 7/5, Interval 类,扫描线
  • Trie,字典树
    • 6/9, Trie, 字典树
  • 单调栈,LIS
    • 4/13 LIS
    • 栈, 单调栈
    • Largest Divisible Subset
  • Binary Search 类
    • Matrix Binary Search
    • Array Binary Search
    • Find Peak Element I & II
    • **Median of Two Sorted Arrays
  • Graph & Topological Sort,图 & 拓扑排序
    • 有向 / 无向 图的基本性质和操作
    • 拓扑排序, DFS 做法
    • 拓扑排序, BFS 做法
    • Course Schedule I & II
    • Alien Dictionary
    • Undirected Graph, BFS
    • Undirected Graph, DFS
    • 矩阵,BFS 最短距离探索
    • 欧拉回路,Hierholzer算法
    • AI, 迷宫生成
    • AI, 迷宫寻路算法
    • (G) Deep Copy 无向图成有向图
  • 括号与数学表达式的计算
  • Iterator 类
  • Majority Element,Moore's Voting
  • Matrix Inplace Operations
  • 常见数据结构设计
  • (G) Design / OOD 类算法题
  • 随机算法 & 数据结构
  • (FB) I/O Buffer
  • (FB) Simplify Path, H-Index I & II
  • (FB) Excel Sheet, Remove Duplicates
  • Integer 的构造,操作,序列化
  • Frequency 类问题
  • Missing Number 类,元素交换,数组环形跳转
  • 8/10, Google Tag
  • (FB) Rearrange String k Distance Apart
  • Abstract Algebra
    • Chap1 -- Why Abstract Algebra ?
    • Chap2 -- Operations
    • Chap3 -- The Definition of Groups
Powered by GitBook
On this page
  • Group Shifted Strings
  • Perfect Squares
  • 以上两招都可以很简便的减少内存和计算时间开销。
  • 再仔细观察一下这题:
  • 这就是背包啊!
  • Next Permutation
  • 流程:
  • 1: 右往左,找下落;
  • 2:左往右,找 threshold (换过来的数,怎么说也得比 nums[start] 大)
  • 3:交换,反转。
  • Strobogrammatic Number II
  • 注意:index == 0 并且 i == 0 的时候要跳过,免得在起始位置填上 0 .
  • Strobogrammatic Number III
  • 后来发现有点多余,可以直接用内置的 str1.compareTo(str2).
  • Sort Transformed Array
  • 这题比较简洁的写法如下,明天学习一个。
  • 这种写法的核心是只看 a 的 “正负”,无所谓 0.

Was this helpful?

8/10, Google Tag

PreviousMissing Number 类,元素交换,数组环形跳转Next(FB) Rearrange String k Distance Apart

Last updated 4 years ago

Was this helpful?

挺简单的,和 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>> 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;
    }
}

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

后来发现 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;
    }
}

再仔细观察一下这题:

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

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

  • 一个元素可以选多次;

这就是背包啊!

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];
    }
}

流程:

  • start 从倒数第二个数起,往左扫,寻找到第一个 nums[start] < nums[start + 1] 的位置;

  • 从 start 往后找,找到第一个比 nums[start] 小的前一个数 (也就是最小的大于等于 nums[start] 的数)

  • 交换 start , end

  • 把 start + 1 后面的区间翻转,over.

1: 右往左,找下落;

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

3:交换,反转。

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

为什么一个这么简单的 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);
            }
        }
    }
}

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

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

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

超过 81.92% ~

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

}

我很喜欢这题,挺有创意~

  • 注意点 1 : a = 0 的时候是直线,不能无脑按照抛物线的方式处理;

  • 注意点 2 : 对称轴 -b / 2 * a 的时候括号顺序是 (double) -b / (2 * a)

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

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) 计算一下就好,也能处理直线的情况。

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

Group Shifted Strings
Perfect Squares
Next Permutation
Strobogrammatic Number II
Strobogrammatic Number III
Sort Transformed Array