583. Delete Operation for Two Strings

583. Delete Operation for Two Strings

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:

1. The length of given words won't exceed 500.
2. Characters in given words can only be lower-case letters.

--------------------
Solution #1
2个单词的长度和 －longest common subsequence * 2

class Solution {
    public int minDistance(String word1, String word2) {
        return word1.length() + word2.length() - 2 * lcs(word1,word2);
    }
    
    private int lcs(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = 1 + dp[i - 1][j - 1];
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        
        return dp[m][n];
    }
}

Solution #2 DP, ToDo
类似edit distance, 方程：
dp[x][y] = dp[x - 1][y - 1] if s1[x] == s2[y]
dp[x][y] = 1 + min(dp[x - 1][y], dp[x][y - 1) if s1[x] != s2[y]

523. 560, Continuous Subarray Sum, Subarray Sum Equals K

523. Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

-----------------
(sum - preSum) % k = 0
=>
sum % k = preSum % k

所以set里面要存的是sum % k,

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length < 2) return false; 
        if (checkZeros(nums)) return true;
        if (k == 0) return false;
        
        int sum = nums[0];
        Set<Integer> set = new HashSet<>();
        set.add(0);
        set.add(sum);
        
        for (int i = 1; i < nums.length; i++) {
            sum += nums[i];
            sum %= k;
            if (set.contains(sum)) {
                return true;
            }
            set.add(sum);
        }
        
        return false;
    }
    
    private boolean checkZeros(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == 0 && nums[i - 1] == 0) return true;
        }
        
        return false;
    }
}

560. Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

---------------

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        int sum = 0;
        int rt = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) rt += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        
        return rt;
    }
}

678. Valid Parenthesis String

678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

1. The string size will be in the range [1, 100].

------------------------
ref: https://leetcode.com/problems/valid-parenthesis-string/discuss/107577/Short-Java-O(n)-time-O(1)-space-one-pass

遇到'*'可以生成3种可能) = -1, "" = 0, ( = +1。 另一关键在于所有的可能性都是连续的 0, 1, 2,....
保持一个最小最大，如果最后最小能到0，说明可以获得合法的string

class Solution {
    public boolean checkValidString(String s) {
        int low = 0, hi = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                hi++;
                low++;
            }else if (c == ')') {
                if (low > 0) {
                    low--;
                }
                hi--;
            }else if (c == '*') {
                if (low > 0) {
                    low--;
                }
                hi++;
            }
            if (hi < 0) return false;
        }
        
        return low == 0;
    }
}

266. Palindrome Permutation

266. Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:

Input: "code"
Output: false

Example 2:

Input: "aab"
Output: true

Example 3:

Input: "carerac"
Output: true

------------------
2 pass.
可以用set来实现single pass，加加减减

class Solution {
    public boolean canPermutePalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        boolean odd = false;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() % 2 == 1) {
                if (odd) return false;
                odd = true;
            } 
        }
        
        return true;
    }
}

408. Valid Word Abbreviation

408. Valid Word Abbreviation

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

A string such as "word" contains only the following valid abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".

Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.

Example 1:

Given s = "internationalization", abbr = "i12iz4n":

Return true.

Example 2:

Given s = "apple", abbr = "a2e":

Return false.

--------------------
分三种情况：
1. 如果是数字，吃数字
2. 如果count == 0, 说明大家都指向字符。那就对比字符
3. 如果不是数字，j += count。 此时i, j都会指向字符或超出范围，两者对比会交给下一次的循环。

注意几个corner case：
1. 数字开头为0: a0b
2. 末尾是数字: ab1。 最后检测长度的时候加上count

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i = 0, j = 0;
        int count = 0;
        
        while (i < abbr.length() && j < word.length()) {
            char c = abbr.charAt(i);
            if (Character.isDigit(c)) {
                if (count == 0 && c <= '0') return false;
                count = Character.getNumericValue(c) + count * 10;
                i++;
            }else if (count == 0) {
                if (c != word.charAt(j)) return false;
                i++;
                j++;
            }else {
                j += count;
                count = 0;
            }
        }
        
        return i == abbr.length() && j + count == word.length();
    }
}

658. Find K Closest Elements

658. Find K Closest Elements

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 104
3. Absolute value of elements in the array and x will not exceed 104

----------------
Solution #1, O(logN + K)

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = findClosest(arr, x);
        int right = left + 1;
        int n = arr.length;
        if (left == -1) {
            right = k;
        }else if (left == n) {
            right = n;
            left = n - k - 1;
        }else {
            while (k > 0) {
                if (left >= 0 && right < n) {
                    if (x - arr[left] > arr[right] - x) {
                        right++;
                    }else {
                        left--;
                    }
                }else if (left >= 0) {
                    left--;
                }else {
                    right++;
                }

                k--;
            }
        }
        left++;
        right--;
        
        List<Integer> rt = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            rt.add(arr[i]);
        }
        
        return rt;
    }
    
    private int findClosest(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (mid < arr.length - 1 && arr[mid] <= x && arr[mid + 1] > x) return mid;
            if (arr[mid] > x) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

Solution #2, O(logN + K)，ref：https://leetcode.com/problems/find-k-closest-elements/discuss/106419/O(log-n)-Java-1-line-O(log(n)-+-k)-Ruby
二分查找subarray的起点，用反证法可以证明此算法的正确性

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length - k;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - arr[mid] <= arr[mid + k] - x) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        
        List<Integer> rt = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            rt.add(arr[left + i]);
        }
        
        return rt;
    }
}

716. Max Stack

716. Max Stack

Design a max stack that supports push, pop, top, peekMax and popMax.

1. push(x) -- Push element x onto stack.
2. pop() -- Remove the element on top of the stack and return it.
3. top() -- Get the element on the top.
4. peekMax() -- Retrieve the maximum element in the stack.
5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:

MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

Note:

1. -1e7 <= x <= 1e7
2. Number of operations won't exceed 10000.
3. The last four operations won't be called when stack is empty.

-------------------------
Solution #1
priority queue搞不定，只能treemap。 O(logN)

class MaxStack {
    
    class Node {
        public Node next;
        public Node pre;
        public int val;
        public Node(int val) {
            this.val = val;
            next = null;
            pre = null;
        }
    }
    
    class DoublyLinkedList {
        private Node head;
        private Node tail;
        
        public DoublyLinkedList() {
            head = new Node(0);
            tail = new Node(0);
            head.next = tail;
            tail.pre = head;
        }
        
        public void addToEnd(Node node) {
            node.pre = tail.pre;
            node.pre.next = node;
            node.next = tail;
            tail.pre = node;
        }
        
        public void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;            
        }
        
        public int getLast() {
            return tail.pre.val;
        }
        
        public int removeLast() {
            int tmp = getLast();
            remove(tail.pre);
            
            return tmp;
        }
    }

    private DoublyLinkedList dll;
    private TreeMap<Integer, LinkedList<Node>> map;
    
    /** initialize your data structure here. */
    public MaxStack() {
        dll = new DoublyLinkedList();
        map = new TreeMap<>();
    }
    
    public void push(int x) {
        Node node = new Node(x);
        if (!map.containsKey(x)) {
            map.put(x, new LinkedList<Node>());
        }
        map.get(x).add(node);
        dll.addToEnd(node);
    }
    
    public int pop() {
        int last = dll.removeLast();
        map.get(last).pollLast();
        if (map.get(last).isEmpty()) {
            map.remove(last);
        }
        
        return last;
    }
    
    public int top() {
        return dll.getLast();
    }
    
    public int peekMax() {
        return map.lastKey();
    }
    
    public int popMax() {
        int max = map.lastKey();
        dll.remove(map.get(max).pollLast());
        
        if (map.get(max).isEmpty()) {
            map.remove(max);   
        }
        
        return max;
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */

Solution #2, 2个stack，ref：https://leetcode.com/problems/max-stack/solution/

329. Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

---------------------------
Solution #1, typical DFS, 没啥好说的

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] inter = new int[m][n];
        int longest = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                longest = Math.max(longest, dfs(matrix, i, j, inter, Integer.MAX_VALUE));
            }
        }
        
        return longest;
    }
    
    private int dfs(int[][] matrix, int row, int col, int[][] inter, int pre) {
        if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length 
           || matrix[row][col] >= pre) return 0;
        
        if (inter[row][col] > 0) return inter[row][col];
        
        int longest = dfs(matrix, row + 1, col, inter, matrix[row][col]);
        longest = Math.max(longest, dfs(matrix, row - 1, col, inter, matrix[row][col]));
        longest = Math.max(longest, dfs(matrix, row, col + 1, inter, matrix[row][col]));
        longest = Math.max(longest, dfs(matrix, row, col - 1, inter, matrix[row][col]));
        inter[row][col] = longest + 1;
        
        return longest + 1;
    }
}

Solution #2, iterative。也是典型的BFS。ToDo, 有空可以写一下
找到所有的起点，一起塞进Queue（或List），同时记录步数

430. Flatten a Multilevel Doubly Linked List

430. Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

Input:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

Explanation for the above example:

Given the following multilevel doubly linked list:

We should return the following flattened doubly linked list:

-------------------------
Solution #1, recursive

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    public Node flatten(Node head) {
        if (head == null) return null;
        Node cp = head;
        rec(cp);
        
        return head;
    }
    
    private Node rec(Node head) {
        if (head.next == null && head.child == null) return head;
        
        if (head.child == null) {
            return rec(head.next);
        }
        
        Node savedNext = head.next;
        head.next = head.child;
        head.child.prev = head;

        Node last = rec(head.child);
        head.child = null;
        last.next = savedNext;
        if (savedNext != null) {
            savedNext.prev = last;
        }
        savedNext = last;
        return rec(savedNext);
    }
}

Solution #2, iterative. 如果有child，就把child整个list并回主list(暂时先放过child的child)，然后再从child开始走。每次都减少一层
O(n), 因为每个node最多被走了2次

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    public Node flatten(Node head) {
        Node itr = head;
        
        while (itr != null) {
            if (itr.child != null) {
                Node savedNext = itr.next;
                itr.next = itr.child;
                itr.child.prev = itr;
                itr.child = null;
                
                Node itrInner = itr.next;
                while (itrInner.next != null) {
                    itrInner = itrInner.next;
                }
                
                itrInner.next = savedNext;
                if (savedNext != null) savedNext.prev = itrInner;
            }
            
            itr = itr.next;
        }
        
        return head;
    }
}

568. Maximum Vacation Days

568. Maximum Vacation Days

LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.

Rules and restrictions:

1. You can only travel among N cities, represented by indexes from 0 to N-1. Initially, you are in the city indexed 0 on Monday.
2. The cities are connected by flights. The flights are represented as a N*N matrix (not necessary symmetrical), called flightsrepresenting the airline status from the city i to the city j. If there is no flight from the city i to the city j, flights[i][j] = 0; Otherwise, flights[i][j] = 1. Also, flights[i][i] = 0 for all i.
3. You totally have K weeks (each week has 7 days) to travel. You can only take flights at most once per day and can only take flights on each week's Monday morning. Since flight time is so short, we don't consider the impact of flight time.
4. For each city, you can only have restricted vacation days in different weeks, given an N*K matrix called days representing this relationship. For the value of days[i][j], it represents the maximum days you could take vacation in the city i in the week j.

You're given the flights matrix and days matrix, and you need to output the maximum vacation days you could take during K weeks.

Example 1:

Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation: 
Ans = 6 + 3 + 3 = 12. 

One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day. 
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.) 
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.

Example 2:

Input:flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]
Output: 3
Explanation: 
Ans = 1 + 1 + 1 = 3. 

Since there is no flights enable you to move to another city, you have to stay at city 0 for the whole 3 weeks. 
For each week, you only have one day to play and six days to work. 
So the maximum number of vacation days is 3.

Example 3:

Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]
Output: 21
Explanation:
Ans = 7 + 7 + 7 = 21

One of the best strategies is:
1st week : stay at city 0, and play 7 days. 
2nd week : fly from city 0 to city 1 on Monday, and play 7 days.
3rd week : fly from city 1 to city 2 on Monday, and play 7 days.

Note:

1. N and K are positive integers, which are in the range of [1, 100].
2. In the matrix flights, all the values are integers in the range of [0, 1].
3. In the matrix days, all the values are integers in the range [0, 7].
4. You could stay at a city beyond the number of vacation days, but you should work on the extra days, which won't be counted as vacation days.
5. If you fly from the city A to the city B and take the vacation on that day, the deduction towards vacation days will count towards the vacation days of city B in that week.
6. We don't consider the impact of flight hours towards the calculation of vacation days.

--------------------------------
典型的DP，这次直接给iterative的解法了。
dp[i][k] (0<= i <= N - 1, 0 <= k <= K - 1) 表示从城市i出发，在第k周的周一能得到的最大值
因为dp[i][k]仅依赖于dp[i][k + 1], 所以一维dp就够了
O(K * N ^ 2)

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int N = flights.length, K = days[0].length;
        int[] dp = new int[N];
        
        for (int k = K - 1; k >= 0; k--) {
            int[] tmp = new int[N];
            
            for (int i = 0; i < N; i++) {
                tmp[i] = days[i][k] + dp[i];
                for (int j = 0; j < N; j++) {
                    if (flights[i][j] == 0) continue;
                    tmp[i] = Math.max(tmp[i], days[j][k] + dp[j]);
                }
            }
            dp = tmp;
        }
        
        return dp[0];
    }
}

674. Longest Continuous Increasing Subsequence

674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. 

Example 2:

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1. 

Note: Length of the array will not exceed 10,000.

------------------------

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) return 0;
        
        int len = 1;
        int start = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] <= nums[i - 1]) {
                start = i;
            }
            
            len = Math.max(len, i - start + 1);
        }
        
        return len;
    }
}

446. Arithmetic Slices II - Subsequence

446. Arithmetic Slices II - Subsequence

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.

A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

----------------------------
递归，超时

class Solution {
    
    public int numberOfArithmeticSlices(int[] A) {
        
        return dfs(A, 0, new ArrayList<Integer>());
    }
    
    private int dfs(int[] A, int i, List<Integer> cur) {
        int count = 0;
        if (cur.size() > 2) {
            if ((long)cur.get(cur.size() - 1) - (long)cur.get(cur.size() - 2) ==
                    (long)cur.get(cur.size() - 2) - (long)cur.get(cur.size() - 3)) {
                count++;
            }else {
                return 0;
            }
        }
        
        for (; i < A.length; i++) {
            List<Integer> t = new ArrayList<>(cur);
            t.add(A[i]);
            count += dfs(A, i + 1, t);
        }
        
        return count;
    }
}

Solution #2, memoization。 OA超时，都是超时的个例在test run可以过

class Solution {
    
    public int numberOfArithmeticSlices(int[] A) {
        
        return dfs(A, 0, new ArrayList<Integer>(), new HashMap<String, Integer>());
    }
    
    private int dfs(int[] A, int i, List<Integer> cur, Map<String, Integer> dp) {
        int count = 0;
        int n = cur.size();
        if (n > 2) {
            if ((long)cur.get(n - 1) - (long)cur.get(n - 2) == (long)cur.get(n - 2) - (long)cur.get(n - 3)) count++;
        }
        
        for (; i < A.length; i++) {
            if (n > 1) {
                if ((long)cur.get(n - 1) - (long)cur.get(n - 2) == (long)A[i] - (long)cur.get(n - 1)) {
                    int diff = A[i] - cur.get(n - 1);
                    String key = diff + "" + i;
                    
                    if (dp.containsKey(key)) {
                        count += dp.get(key);
                    }else {
                        List<Integer> t = new ArrayList<>(cur);
                        t.add(A[i]);
                        int tmp = dfs(A, i + 1, t, dp);
                        dp.put(key, tmp);
                        count += tmp;    
                    }
                }
            }else {
                List<Integer> t = new ArrayList<>(cur);
                t.add(A[i]);
                count += dfs(A, i + 1, t, dp);
            }
            
        }
        
        return count;
    }
}

dp[i]存的是以A[i]为末尾的subsequence的所有满足条件的diff的长度。
算法的思路是拿A[i]依次与[0, i]凑
ref: https://leetcode.com/problems/arithmetic-slices-ii-subsequence/discuss/92822/Detailed-explanation-for-Java-O(n2)-solution

Followup, 如果修改长度为4怎么做？
额外设计数据机构，对每一个i要记录长度和count, 而且对不同长度的count要分开计算

class Solution {
    
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        Map<Integer, Integer>[] dp = new Map[n];
        int rt = 0;
        
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<Integer, Integer>();
            
            for (int j = 0; j < i; j++) {
                long diff = (long)A[i] - A[j];
                if (diff <= Integer.MIN_VALUE || diff > Integer.MAX_VALUE) continue;
                
                int di = (int) diff;
                int c1 = dp[i].getOrDefault(di, 0);
                int c2 = dp[j].getOrDefault(di, 0);
                rt += c2;
                dp[i].put(di, c1 + c2 + 1);
            }
        }
        
        return rt;
    }
}

Partial的follow up，不一定对，暂时先放在这里

class Solution {
    class Cus{
        public int length;
        public int count;
        public Cus() {
            length = 1;
            count = 0;
        }
    }
    
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        Map<Integer, Cus>[] dp = new Map[n];
        int rt = 0;
        
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<Integer, Integer>();
            
            for (int j = 0; j < i; j++) {
                long diff = (long)A[i] - A[j];
                if (diff <= Integer.MIN_VALUE || diff > Integer.MAX_VALUE) continue;
                
                int di = (int) diff;
                Cus c1 = null;
                if (dp[i].containsKey(di)) {
                    c1 = dp[i].get(di);
                }else {
                    c1 = new Pair();
                }
                
                Cus c2 = null;
                if (dp[j].containsKey(di)) {
                    c2 = dp[j].get(di);
                }else {
                    c2 = new Pair();
                }
                
                c2.length++;
                if (c2.length > 2) {
                    rt += c2.count;
                }
                
                c1.length = c2
                
                int c1 = dp[i].getOrDefault(di, 0);
                int c2 = dp[j].getOrDefault(di, 0);
                rt += c2;
                dp[i].put(di, c1 + c2 + 1);
            }
        }
        
        return rt;
    }
}

688. Knight Probability in Chessboard

688. Knight Probability in Chessboard

On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).

A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.

Example:

Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

Note:

N will be between 1 and 25.

K will be between 0 and 100.

The knight always initially starts on the board.

-----------------------
典型的DP，按套路一路推理

Solution #1 超时

class Solution {
    
    public double knightProbability(int N, int K, int r, int c) {
        int total = 1;
        for (int i = 0; i < K; i++) {
            total *= 8;
        }
       
        return dfs(N, K, r, c) / total;
    }
    
    public double dfs(int N, int K, int r, int c) {
        if (r < 0 || r >= N || c < 0 || c >= N) {
            return 0;
        }

        if (K == 0) {
            return 1;
        }
        
        return  dfs(N, K - 1, r - 2, c - 1) +
            + dfs(N, K - 1, r - 2, c + 1)
            + dfs(N, K - 1, r - 1, c - 2)
            + dfs(N, K - 1, r - 1, c + 2)
            + dfs(N, K - 1, r + 1, c - 2)
            + dfs(N, K - 1, r + 1, c + 2)
            + dfs(N, K - 1, r + 2, c - 1)
            + dfs(N, K - 1, r + 2, c + 1);
    }
}

Solution #2 Memoization
O(N^2 * K) 时间

class Solution {
    private int[] dr = {-2, -2, -1, -1, 1, 1, 2, 2};
    private int[] dc = {-1, 1, -2, 2, -2, 2, -1, 1};
         
    public double knightProbability(int N, int K, int r, int c) {
        
        double[][][] dp = new double[N][N][K];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                Arrays.fill(dp[i][j], -1);
        }
        double a = dfs(N, K, r, c, dp);
        return  a / Math.pow(8, K);
    }
    
    public double dfs(int N, int K, int r, int c, double[][][] dp) {
        if (r < 0 || r >= N || c < 0 || c >= N) {
            return 0;
        }
        
        if (K == 0) {
            return 1;
        }
        if (dp[r][c][K - 1] != -1) return dp[r][c][K - 1];

        double total = 0;
        for (int i = 0; i < 8; i++) {
            total += dfs(N, K - 1, r + dr[i], c + dc[i], dp);
        }
        
        dp[r][c][K - 1] = total;
        return total;
    }
}

Solution #3 DP, 思路同上。
因为[k]仅依赖于[k - 1], 所以用2个2维数组可以交替使用，不用3维
O(N^2 * K) 时间，O(N^2) 空间

class Solution {
    private int[] dr = {-2, -2, -1, -1, 1, 1, 2, 2};
    private int[] dc = {-1, 1, -2, 2, -2, 2, -1, 1};
         
    public double knightProbability(int N, int K, int r, int c) {
        
        double[][] dp1 = new double[N][N];
        double[][] dp2 = new double[N][N];    
        dp1[r][c] = 1;
        
        for (int k = 0; k < K; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (dp1[i][j] > 0) {
                        for (int d = 0; d < 8; d++) {
                            helper(N, i, j, i + dr[d], j + dc[d], dp1, dp2);   
                        }                
                        dp1[i][j] = 0;
                    }
                }
            }
            double[][] tmp = dp1;
            dp1 = dp2;
            dp2 = tmp;
        }
        
        double total = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) total += dp1[i][j];
        }
        
        return  total / Math.pow(8, K);
    }
    
    public void helper(int N, int r1, int c1, int r2, int c2, double[][] dp1, double[][] dp2) {
        
        if (r2 < 0 || r2 >= N || c2 < 0 || c2 >= N) {
            return ;
        }
        dp2[r2][c2] += dp1[r1][c1];
    }
}

360. Sort Transformed Array

360. Sort Transformed Array

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]

---------------------
一元二次方程
咋看之下有4种情况 a > 0, a < 0, a == 0 && b > 0, a ==0 && b < 0, 其实代码一整合就只有2种：a >= 0和a < 0

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] rt = new int[n];
        int left = 0, right = n - 1;
        int itr = a >= 0 ? n - 1 : 0;
        
        while (left <= right) {
            if (a >= 0) {
                if (f(nums[left], a, b, c) > f(nums[right], a, b, c)) {
                    rt[itr] = f(nums[left], a, b, c);
                    left++;
                }else {
                     rt[itr] = f(nums[right], a, b, c);
                    right--;
                }          
                itr--;
            }else {
                if (f(nums[left], a, b, c) < f(nums[right], a, b, c)) {
                    rt[itr] = f(nums[left], a, b, c);
                    left++;
                }else {
                     rt[itr] = f(nums[right], a, b, c);
                    right--;
                }          
                itr++;
            }
        }
        
        return rt;
    }
    
    private int f(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}