331. Verify Preorder Serialization of a Binary Tree

Q:

One way to serialize a binary tree is to use pre-oder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

A:
 *******就是建立一个stack，来模拟深度，如果是visiting left child, 则stack上放1， 否则放 -1.
******************
每次看见一个 # ，表示结束了一个分支。 ********
**********直接一遍秒过，还不错，Tiger，明天犒劳自己*********

public class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] A = preorder.split(",");
        Stack<Integer> stack = new Stack(); //1 for left, -1 if visiting right
        for(String cur : A){
            cur = cur.trim();
            if(! cur.equals("#")){
                stack.push(1);
            }else{
                while( ! stack.isEmpty() && stack.peek()<0){
                    stack.pop();
                }
                if( !stack.isEmpty()){
                    stack.pop();
                    stack.push(-1);
                }
            }
            
        }
        return stack.isEmpty();
    }
}

330. Patching Array ！！！！！！！！

Q:

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

A:

Sol 1 ： 挨个找，如果找不到，就加入。但是这样不能保证最优。
Sol 2:  保持found list，和non-found list， 找出加入一个数字，可以保证满足最多的（可是这样
但是这样，一是麻烦，而是不保证正确，三是LTE
Sol 3:

public class Solution {
    public int minPatches(int[] nums, int n) {
        int count = 0, i = 0;
        long findMaxRight = 1;// this maxRight has not been found yet
        while(findMaxRight <= n){
            if( i<nums.length && nums[i] <= findMaxRight ){
                findMaxRight += nums[i++];
            }else{
                findMaxRight = 2*findMaxRight;
                count++;
            }
        }
        return count;
    }
}

Mistakes:
1: findMaxRight is exclusive.   thus its initial value can be set to 1.    WTF
2:  use long , instead of int , to avoid overflow.

326. Power of Three

Q:

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

A：
递归：

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n>0 && (n==1 || (n%3==0 && isPowerOfThree(n/3)));
    }
}

************ 代数 计算 ******  取Log

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n>0 &&  n == Math.pow(3,  Math.round((Math.log(n)/Math.log(3)))   );
    }
}

328. Odd Even Linked List --M

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

 

Example 1:

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

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

 

Constraints:

• The number of nodes in the linked list is in the range [0, 104].
• -106 <= Node.val <= 106

A:

-------------------------就是一个个拆下来而已------------

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode() : val(0), next(nullptr) {}

* ListNode(int x) : val(x), next(nullptr) {}

* ListNode(int x, ListNode *next) : val(x), next(next) {}

* };

*/

class Solution {

public:

ListNode* oddEvenList(ListNode* head) {

ListNode oHeader, eHeader;

auto oTail = &oHeader, eTail = &eHeader;

while (head) {

oTail->next = head;

oTail = oTail->next;

head = head->next;

if (head) {

eTail->next = head;

head = head->next;

eTail = eTail->next;

eTail->next = nullptr;

}

}

oTail->next = eHeader.next;

return oHeader.next;

}

};

Mistakes:           
ListNode* header1(0);         这样是不行的，其实并没有真正的声明一个pointer

正确的方法：
 ListNode header1();
或者    ListNode* header1 = new ListNode(0); ----> declared on heap, need delete

329. Longest Increasing Path in a Matrix

Q:

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

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

 

Example 1:

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

Example 2:

Input: matrix = [[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.

Example 3:

Input: matrix = [[1]]
Output: 1

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

A:

   先试试简单的dfs，记录每个点。但是这样会超时。  d*******代码如下***********

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int res = 0;
        boolean A[][] = new boolean[m][n];
        for(int i =0;i<m;i++)
            for(int j =0;j<n;j++)
                res = Math.max(res,dfs(matrix,i,j,A,matrix[i][j]-1));
        return res;
    }
    private int dfs(int[][] matrix, int i ,int j, boolean A[][],int minValue){
        int m = matrix.length,  n = matrix[0].length;
        if(i<0 || i >=m || j < 0 || j >=n || A[i][j])
            return 0;
        if(matrix[i][j]<=minValue)
            return 0;
        A[i][j] = true;
        int l = dfs(matrix, i,j-1, A,matrix[i][j]);
        int r = dfs(matrix, i,j+1, A,matrix[i][j]);
        int u = dfs(matrix, i-1,j, A,matrix[i][j]);
        int d = dfs(matrix, i+1,j, A,matrix[i][j]);
        A[i][j] = false;
        return 1+ Math.max( Math.max(l,r),Math.max(u,d));
    }
}

************改进****************
每个位置记录下其最长的increasing position（starting from it) .  毕竟，我们每个点，如果再找，也只是从比其小的位置开始。

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> M(m, vector<int>(n,-1));// how many it can go up
        int res = 0;
        for(int i =0;i<m;i++)
            for(int j =0;j<n;j++)
                res = max(res, dfs(matrix,i,j,M));
        return res;
    }
private:
    int dfs(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& M){
        if(M[i][j]>0) // if already visited
            return M[i][j];
        
        int m = matrix.size(), n = matrix[0].size();
        M[i][j] = 1;
        if(i-1 >= 0 && matrix[i-1][j] > matrix[i][j]){
            M[i][j] = max(M[i][j], 1 + dfs(matrix, i-1,j,M));
        }
        if(i+1 < m && matrix[i+1][j] > matrix[i][j]){
            M[i][j] = max(M[i][j], 1 + dfs(matrix, i+1,j,M));
        }
        if(j-1 >= 0 && matrix[i][j-1] > matrix[i][j]){
            M[i][j] = max(M[i][j], 1 + dfs(matrix, i,j-1,M));
        }
        if(j+1 < n && matrix[i][j+1] > matrix[i][j]){
            M[i][j] = max(M[i][j], 1 + dfs(matrix, i,j+1,M));
        }
        return M[i][j];
    }
};

Mistakes:

TopCoder ： AB problem

Problem Statement

You are given two s: N and K. Lun the dog is interested in strings that satisfy the following conditions:

• The string has exactly N characters, each of which is either 'A' or 'B'.
• The string s has exactly K pairs (i, j) (0 <= i < j <= N-1) such that s[i] = 'A' and s[j] = 'B'.

If there exists a string that satisfies the conditions, find and return any such string. Otherwise, return an empty string.

Definition

Class:

AB

Method:

createString

Parameters:

int, int

Returns:

String

Method signature:

String createString(int N, int K)

(be sure your method is public)

Limits

Time limit (s):

2.000

Memory limit (MB):

256

Constraints

- N will be between 2 and 50, inclusive.

- K will be between 0 and N(N-1)/2, inclusive.

Examples

0)

3

2

Returns: "ABB"

This string has exactly two pairs (i, j) mentioned in the statement: (0, 1) and (0, 2).

1)

2

0

Returns: "BA"

Please note that there are valid test cases with K = 0.

2)

5

8

Returns: ""

Five characters is too short for this value of K.

3)

10

12

Returns: "BAABBABAAB"

Please note that this is an example of a solution; other valid solutions will also be accepted.

A:
就是递归（DFS），没想到什么太简单的解法。

import java.util.Arrays;

public class AB{
    boolean findRes = false;
    public String createString(int N, int K){
        char AB [] = new char[N];
        // for each potential number of B
        for(int nB = 0;nB<N;nB++) // number of B
            helper(AB,0,  nB, K);
        return findRes? new String(AB) : "";
        
    }
    private void helper(char[] AB, int start,  int nB, int K){
        int N = AB.length;
        if(findRes==true)
               return;
        if(K<0 || nB<0|| nB > (N-start))
            return;
        if(K==0 && nB == N-start){
            Arrays.fill(AB,start, N, 'B');
            findRes = true;
            return;
        }
           // try to fillin one position at AB[start]
        AB[start] = 'A';
        helper(AB,start+1,nB, K-nB);
        AB[start] = 'B';
        helper(AB,start+1,nB-1, K);
        
    }
}