238. Product of Array Except Self -M

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

A:

从前向后走一遍，计算之前的乘积
再从后向前走一遍，计算之后的乘积，

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n,1);
        // two round, forward, and backward
        for(int i =1;i<n;++i)
            res[i] = res[i-1] * nums[i-1];
        int back = 1;
        for(int i = n-1; i>=0; --i)
        {
            res[i] *= back;
            back *= nums[i];
        }
        return res;
    }
};

用2个帮助数组

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int pre[] = new int[n];
        int after[] = new int[n];
        pre[0] = 1;
        for(int i =1;i<n;i++)
            pre[i] = pre[i-1]*nums[i-1];
        after[n-1] = 1;
        for(int i=n-2;i>=0;i--)
            after[i] = after[i+1] * nums[i+1];
        int[] result = new int[n];
        for(int i =0;i<n;i++)
            result[i] = pre[i] * after[i];
        return result;
    }
}

Follow up:
为节省空间，用result数组和给的nums数组代替pre   after 数组。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n];
        pre[0] = 1;
        for(int i =1;i<n;i++)
            pre[i] = pre[i-1]*nums[i-1];
        for(int i=n-2;i>0;i--)
            nums[i] = nums[i+1] * nums[i];
        for(int i =0;i<n-1;i++)
            pre[i] = pre[i] * nums[i+1];
        return pre;
    }
}

Mistakes:

237. Delete Node in a Linked List (M)

Q:

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:

• The value of the given node should not exist in the linked list.
• The number of nodes in the linked list should decrease by one.
• All the values before node should be in the same order.
• All the values after node should be in the same order.

Custom testing:

• For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
• We will build the linked list and pass the node to your function.
• The output will be the entire list after calling your function.

 

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

 

Constraints:

• The number of the nodes in the given list is in the range [2, 1000].
• -1000 <= Node.val <= 1000
• The value of each node in the list is unique.
• The node to be deleted is in the list and is not a tail node.

A:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* pre = node;
        while(pre->next != NULL && pre->next->next != NULL){
            pre->val = pre->next->val;
            pre = pre->next;
        }
        pre->val = pre->next->val;
        pre->next = NULL;
    }
};

Mistakes:
最新一次代码，好几年不写了。
应该update node的value before node move next

236. Lowest Common Ancestor of a Binary Tree

Q:
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
A:


Google 面试题   哎，惨痛～～～～～～～～～～

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root==p || root==q)
            return root;
        auto L = lowestCommonAncestor(root->left, p, q);
        auto R = lowestCommonAncestor(root->right, p, q);
        if(L&R)
            return root;
        return L?L:R;
    }
};

Mistakes:

Lowest Common Ancestor of a Binary Search Tree

Q:
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
A:

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > q.val)
            return lowestCommonAncestor(root,q,p);
        return helper(root,p,q);
    }
    private TreeNode helper(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val<p.val)
            return helper(root.right,p,q);
        else if(root.val > q.val)
            return helper(root.left,p,q);
        return root;
    }
}

其实这道题，无关Binary Search Tree ---虽然利用起来，效率会高一些些

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null)
            return right;
        if(right ==null)
            return left;
        return root;
    }
}

Mistakes:

Palindrome Linked List

Q:
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
A:
----------------------首先就是空间换时间。 重新生成一个倒置的List ----------------------

public class Solution {
    public boolean isPalindrome(ListNode head) {
        int len=0;
        ListNode header = new ListNode(0);
        ListNode runner = head;
        while(runner != null){
            ListNode tmp = new ListNode(runner.val);
            tmp.next = header.next;
            header.next = tmp;
            runner = runner.next;
        }
        runner = head;
        header = header.next;
        while(runner!=null){
            if(runner.val != header.val)
                return false;
            runner = runner.next;
            header = header.next;
        }
        return true;
    }
}

************* O(1) space + O(n) time **********************
进一步的思考就是：  既然常规办法不能奏效， 就考虑修改List的内容（结构）
得到的方法，就是把前一半逆向插入到后一半 ， 然后再比较
%%%%%%其实也可以取下前一半，逆序，再比较，这样写起来更简单些%%%%%

public class Solution {
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode header = new ListNode(0);
        header.next = head;
        ListNode tail = header;
        while(tail.next != null){
            len++;
            tail = tail.next;
        }
        // add the first half to the tail of the 
        for(int i =0;i<len/2;i++){
            // detach
            ListNode tmp = header.next;
            header.next = tmp.next;
            // append to tail
            tmp.next = tail.next;
            tail.next = tmp;
        }
        // do comparesion.
        ListNode front = header.next;
        if(len %2 ==1){
            front = front.next;
        }
        tail = tail.next;
        while(tail!=null){
            if(tail.val != front.val)
                return false;
            tail = tail.next;
            front = front.next;
        }
        return true;
    }
}

Mistakes:

Number of Digit One ~~~~~~~~~

Q:
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
A:
就是每一位计算有多少个。
分为高一位 有多少个导致现在重复的。  和现在位有多少个1

public class Solution {
    public int countDigitOne(int n) {
        long num1s = 0;
        for(int i =0;i<32;i++){// for each digit
            long div = (long)Math.pow(10,i);
            if(div > n)
                break;
            num1s +=  n/(div*10)* div + helper(n%(div*10),div); // number of repeats  + at this position
        }
        return (int)num1s;
    }
    private long helper(long x,long powerOf10){// get the number of 1s at x's first digit (x/powerOf10 < 10)
        long res = x/powerOf10;
        if(res==0)
            return 0;
        if(res >1)
            return powerOf10;
        return x - res * powerOf10 + 1; // for case x = 10,
    }
}

 这里的关键点是： 如何分解这个答案：  我们的分解方式是：
1： 从低到高，每一位计算
2： 对数字位 i(i = 0 to 31);
     2.1 ）看高于它的数字位， 会导致有多少个重复1（在i位上）的。
     2.2） 看改位置：会有多少个重复的1 出现。    也就是 hepler函数。（这里又分为： 该位是否 为  1.    看1 的位置重复完了没有。   ）
 


Mistakes:
1:  刚开始 计算高位重复的，给减了一

Power of Two

Q:
Given an integer, write a function to determine if it is a power of two.
A:

public class Solution {
    public boolean isPowerOfTwo(int n) {
        return n>0 && (n & (n-1))==0;
    }
}

Mistakes:

232. Implement Queue using Stacks -E

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Accepted

A:
  -----use two stack to simulate ----------

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        sin.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(sout.empty())
        {
            while(not sin.empty())
            {
                int v = sin.top();
                sin.pop();
                sout.push(v);
            }
        }
        int v = sout.top();
        sout.pop();
        return v;
    }
    
    /** Get the front element. */
    int peek() {
        if(sout.empty())
        {
            while(not sin.empty())
            {
                int v = sin.top();
                sin.pop();
                sout.push(v);
            }
        }
        return sout.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return sin.empty() && sout.empty();
    }
private:
    stack<int> sin;
    stack<int> sout;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

The Skyline Problem

Q:
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

A:
 -----------------------------    divide and conquer  -----------------------







Mistakes:

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

A:

走2遍，第一遍算 *  / ，  然后计算  +  -

class Solution {
public:
    int calculate(string s) {
        vector<string> myList;
        int left = 0, right = 0;
        while(left<s.length() )
        {
            if(s[left] ==' ')
            {
                left++;
            }else if(s[left] == '+' || s[left] == '-' || s[left] == '*' || s[left] == '/'){
                string tmp(1,s[left]); // !!!!!!!!!!!!!!!!!!!!! this is the way from char to string
                myList.push_back(tmp);
                ++left;
            }else{ // left is digit
                right = left+1; // next probing place
                while(right<s.length() && s[right]>='0' && s[right] <='9' )
                {
                    right++;
                }
                myList.push_back(s.substr(left, right - left));
                left = right;
            }
        }
        vector<string> myList2;
        for(int i =0;i< myList.size();++i)
        {
            string tmp = myList[i];
            if(tmp == "/" || tmp == "*")
            {
                string strA = myList2.back();
                myList2.pop_back();
                string strB = myList[i+1];
                long a = stol(strA);
                long b = stol(strB);
                long aa = ( tmp=="*" )? (a*b) :(a/b);
                myList2.push_back(to_string(aa));
                i++;                    
            }else{
                myList2.push_back(tmp);
            }
        }
        // check for + and -
        long res = stol(myList2[0]);
        for(int i =1;i< myList2.size();i+=2)
        {
            string op = myList2[i];
            string ob2 = myList2[i+1];            
            if(op == "+")
            {
                res += stol(ob2);
            }else{
                res -= stol(ob2);
            }
        }
        return int(res);
    }
};

Mistakes:
1：  一开始都用int来保存，但是  "0-2147483648"   是不行的。 因此要用long类型

Basic Calculator

Q:
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

A:
下面的是递归的思路。但是，这样写是不行的。
自己考虑下，有哪两个错误。 (答案在最后一行)

public class Solution {
    public int calculate(String s) {
        s = s.trim();
        if(s.length()==0)
            return 0;
        // detach parentheses  ( )
        int i = s.indexOf('(');
        if(i>=0){
            int j = s.lastIndexOf(')');
            s = s.substring(0,i)+ calculate(s.substring(i+1, j))+s.substring(j+1);
        }
        int end = 0; // always start from 0
        while(end<s.length() && Character.isDigit(s.charAt(end)) ){
            end++;
        }
        int a = Integer.parseInt(s.substring(0,end));
        s = s.substring(end).trim();
        if(s.length()==0 )
            return a;
        if(s.charAt(0)=='+')
            return a+calculate(s.substring(1));
        else
            return a - calculate(s.substring(1));
    }
}
 

还是需要用Stack

下面的解法是用的2个Stack的思路 ------

public class Solution { 
    public int calculate(String s) {
        Stack<Integer> numStack = new Stack();
        numStack.push(0); // in case that s is empty
        Stack<Character> opStack = new Stack();
        for(int i =0;i<s.length();i++){
            int end = i;
            while(end<s.length() && (Character.isDigit(s.charAt(end)) || s.charAt(end)==' ')){
                end++;
            }
            String str = s.substring(i,end).trim();
            if(str.length()>0){ // just find a number
                int val = Integer.parseInt(str);
                numStack.push(val);
                check(numStack,opStack);
            }
            if(end<s.length()){
                char ch = s.charAt(end);
                opStack.push(ch);
                if(ch == ')')
                    check(numStack,opStack);
            }
            i = end;
        }
        return numStack.pop();
    }
    private void check(Stack<Integer> numStack,Stack<Character> opStack ){
        if(opStack.isEmpty())
            return;
        if(opStack.peek() ==')'){
            opStack.pop();// first on opStack is ')'
            opStack.pop();// first on opStack is '('
            check(numStack,opStack );
            return;
        }
        // just added a number
        if( opStack.peek()!='(') {
            int b = numStack.pop(), a = numStack.pop();
            char ch = opStack.pop();
            if (ch == '+')
                numStack.push(a + b);
            else
                numStack.push(a - b);
        }
    }
}

 

**************错误就是出在每次都要substring上。  下面是更改的代码***************

别人的代码

public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(1);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = c - '0';
                int j = i + 1;
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    num = 10 * num + (s.charAt(j) - '0');
                    j++;
                }
                res += stack.pop() * num;
                i = j - 1;
            } else if (c == '+' || c == '(') {
                stack.push(stack.peek());
            } else if (c == '-') {
                stack.push(-1 * stack.peek());
            } else if (c == ')') {
                stack.pop();
            }
        }
        return res;
    }
}

Mistakes:
1：  自己的解法有个最需要注意的问题就是：   pop完了（）两个运算符之后，要再 调用check（），因为我们相当于重新加入了一个运算数了



————————————————————————————————————
第一个解法，会造成某个数字是负数。再代入的话，就破坏原题目的简洁了
另外，  可能有多个括号并列的情况存在。 

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

A: 

思路参考 maximal rectangle。  仍然搞了个 height 的一位数组。  复杂的O(n*m)

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if(m==0)
            return 0;
        int n = matrix[0].size();
        int maxEdge = 0; // the edge length of the result square
        vector<int> height(n,0);
        for(int i =0;i<m;++i)
        {
            for(int j =0;j<n;++j)
                height[j]  = matrix[i][j] =='0'? 0:++height[j];
            // calculate square at current height
            int left = 0, right =0;
            for(int right = 0;right < n;++right)
            {
                if(height[right]<=maxEdge)
                {
                    left = right+1; // cannot be this one, check from next position
                }else{
                    if(maxEdge < right - left +1)
                    {
                        maxEdge++;//break since for each row, maxEdge increase by at most 1
                        break; 
                    }
                }
            }
            
        }
        return maxEdge*maxEdge;
    }
};

Mistakes:
1:   因为每次maxLen会更改。因此，下一次比较的时候，maxLen就已经不一样了。 ----》 需要加上break语句。

hackRand problem

Q:  检测一个2D数组  其 x，y坐标的k范围内是否存在重复

import java.util.*;

public class Main {
    public static void main(String args[] ) throws Exception {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if(n<=0){System.out.print("NO"); return;}
        String str  = sc.nextLine();
        // change str into line
        List<Integer[]> list = new LinkedList();

        int[][] Arr = new int[n][n];

        for(int i =0;i<n;i++) {
            String strArr[] = sc.nextLine().split("\\s+");
            for (int j = 0; j < strArr.length; j++)
                Arr[i][j] = Integer.parseInt(strArr[j]);
        }

        int k = sc.nextInt();
        int m = Arr[0].length;


        Map<Integer,Integer> map = new HashMap();

        //  each position as a center, and find it int the circle/ use k as radius
        for(int i =0;i<n;i++) {
            map.clear();
            // set-up the circle into the map
            for(int row=0; row < Math.min(n,i+k+1);row++){
                for(int col = 0;col<Math.min(n,k+1);col++){
                    if(row == i && col == 0)
                        continue;
                    int key = Arr[row][col];
                    addMap(map, key);
                }
            }
            // mvoe for each i-th position
            for (int j = 0; j < Arr[0].length; j++) {   // not, current i,j is not included
                int val = Arr[i][j];
                if(map.containsKey(val)){
                    System.out.println("YES");
                    return;
                }
                map.put(val,1);
                // remove most left column and add most left row
                if(j+ 1< m)
                    delMap(map,Arr[i][j+1]);
                if( j - k >=0 ){ // delete this 2k column
                    for(int row=Math.max(0,i-k); row < Math.min(n,i+k+1);row++){
                        delMap(map, Arr[row][j-k]);
                    }
                }
                if( j + k +1 < m ){ // add this 2k column
                    for(int row=Math.max(0,i-k); row < Math.min(n,i+k+1);row++){
                        addMap(map, Arr[row][j + k + 1]);
                    }
                }

            }
        }

        System.out.println("NO");
    }

    private static void addMap(Map<Integer,Integer> map, int val){
        int count = 0;
        if(map.containsKey(val))
            count = map.get(val);
        map.put(val,count+1);
    }
    private static void delMap(Map<Integer,Integer> map, int val){
        if(map.containsKey(val)) {
            int count = map.get(val);
            if(count==1){
                map.remove(val);
            }else
                map.put(val, count - 1);
        }
    }

}

Majority Element II

Q:
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
The algorithm should run in linear time and in O(1) space.
A:
最多2个结果。那么每次删除3个即可。   (这道题目有问题，OJ是要求大于等于 ⌊ n/3 ⌋ )
***********下面这个方法思路是有问题的 *********************

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new LinkedList();
        int n1 = 0,n2 = 0;
        int c1 = 0,c2=0;// count of n1,n2,n3
        for(int i = 0;i<nums.length;i++){
            int val = nums[i];
            if(c1==0){ // if first value is not found
                n1 = val;
                c1=1;
            }else if( c2 ==0){ // if second value is not found
                n2 = val;
                c2=1;
            }else{ // already found two different values
                if(val == n1){
                    c1++;
                }else if(val == n2){
                    c2++;
                }else{ // not equals to previous two val
                    c1--;
                    c2--;
                }
            }
        }
        // now check two possible value, n1 and n2;
        if(c1>0)
            checkValue(list, nums,n1);
        if(c2>0 && n1 != n2) // for po
            checkValue(list, nums,n2);
        return list;
    }
    private void checkValue(List<Integer> list, int[] nums, int value){
        int count = 0;
        for(int i =0;i<nums.length;i++){
            if(nums[i] == value)
                count++;
        }
        if(count > nums.length/3)
            list.add(value);
    }
}

**************这个是正确的解法*******************

public class Solution { 
    public List<Integer> majorityElement(int[] nums) {
        int a = 0,b=0, aCount = 0, bCount = 0;
        for(int val : nums){
            if(aCount==0 || val == a){
                aCount++;
                a = val;
            }else if(bCount==0 || val == b){
                bCount++;
                b = val;
            }else{// found both a, b and c different
                bCount--;
                aCount--;
                if(aCount==0){ // since we always check aCount/a firstly
                    aCount = bCount;
                    a = b;
                    bCount =0;
                }
            }
        }
        List<Integer> res = new LinkedList();
        if(aCount > 0 && isMoreThanThird(nums,a))
            res.add(a);
        if(bCount > 0 && isMoreThanThird(nums,b))
            res.add(b);
        return res ;
    }
    private boolean isMoreThanThird(int[] nums, int a){
        int count = 0;
        for(int x : nums)
            if( x == a)
                count++;
        return count > nums.length/3;
    }
}

Mistakes:
1：  在于for loop中各个 检测语句， 不产生重复。  (因此，当检查c2==0的时候，前面要检查是否已经是n1的值了。
2:  最后n2的时候，要有个if语句