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 a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on ...

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 newHeader(0, head);
        ListNode evenHeader(0);
        ListNode* tail = &newHeader;        
        ListNode* tailEven = &evenHeader;
        
        int idx = 0;
        while(tail->next){
            ++idx;
            if (idx & 1){
                tail = tail->next;
            }else{
                tailEven->next = tail->next;
                tailEven = tailEven->next;
                tail->next = tailEven->next;
                tailEven->next = nullptr;
            }
        }
        tail->next = evenHeader.next;
        return head;
    }
};

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

正确的方法：
 ListNode header1(0);
或者    ListNode* header1 = new ListNode(0);

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

267. Palindrome Permutation II ##################

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example 1:

Input: "aabb"
Output: ["abba", "baab"]

Example 2:

Input: "abc"
Output: []

A:

每次从一个seed开始， 左右两边加上可能的值。

然后dfs直到都用光。

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        if(s.length() == 0)
            return vector<string>();        
        unordered_map<char,int> M;
        for(auto c:s)
            M[c]++;
        int oddCount = 0;
        char oddCh = '0';
        for(auto iter=M.begin(); iter!=M.end(); iter++){
            if(iter->second %2){
                oddCount++;
                oddCh = iter->first;
            }
        }
        if(oddCount>=2)
            return vector<string>();
        string seed="";
        if(oddCount){
            seed += oddCh;
            M[oddCh]--;
            if(M[oddCh]==0){
                M.erase(oddCh);
            }
        }
        vector<string> res;
        dfs(seed, M,res);
        return res;
    }
private:
    void dfs(string &seed, unordered_map<char,int> &M, vector<string> & res){
        if(M.empty()){
            res.push_back(seed);
            return;
        }
        vector<char> chars; // save a copy, so that we dould not modify on M directly while looping it
        for(auto iter=M.begin();iter!= M.end();iter++){
            chars.push_back(iter->first);
        }
        for(auto ch : chars){
            string tmp(1,ch);
            string newSeed = tmp+ seed + tmp;
            M[ch]-=2;
            if(M[ch]==0)
                M.erase(ch);
            dfs(newSeed, M, res);
            M[ch]+=2; // put them back
        }
    }
};

Mistakes: