BT level order traversal -- Java

Question:

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Answer:
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null)return res;
       
        List<Integer> subres = new ArrayList<Integer>();
        int pushnum=0, popnum=1;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.add(root);
       
        while(!que.isEmpty()){
            TreeNode cur = que.peek();
            que.poll();
            popnum--;
            subres.add(cur.val);
           
            if(cur.left!=null){
                que.add(cur.left);
                pushnum++;
            }
            if(cur.right!=null){
                que.add(cur.right);
                pushnum++;
            }
           
            if(popnum==0){
                int tmp=pushnum;
                pushnum = popnum;
                popnum = tmp;
                res.add(subres);
            }
        }
        return res;
    }
}

2sum + 3sum + 4sum (hashmap solution) -- Java

1. 2 sum:

Question:

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Answer:

public class Solution {

    public int[] twoSum(int[] numbers, int target) {

        

        HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();

        int[] res = {-1,-1};

        

        for(int i=0; i<numbers.length; ++i) {

            int o = target - numbers[i];

            if(hmap.containsKey(o)) {

                int oindex = hmap.get(o);

                if(oindex != i) {

                    res[0] = i+1;

                    res[1] = oindex+1;

                    break;

                }

            }

            if(!hmap.containsKey(numbers[i])) {

                hmap.put(numbers[i], i);

            }

        }

        if(res[0]>res[1]){

            int tmp = res[0];

            res[0]=res[1];

            res[1]=tmp;

        }

        return res;

    }

}

2. 3sum:

Answer:

public class Solution {

    public List<List<Integer>> threeSum(int[] num) {

        int sz = num.length;

        HashMap<Integer, List<Integer>> m = new HashMap<Integer, List<Integer>>();

        List<List<Integer>> ret = new ArrayList<List<Integer>>();

        List<Integer> tri = new ArrayList<Integer>();

        for(int i=0; i<sz; ++i) {

            int val = num[i];

            if(m.containsKey(val)) {

                List<Integer> l = m.get(val);

                l.add(i);

            } 

            else {

                ArrayList<Integer> l = new ArrayList<Integer>();

                l.add(i);

                m.put(val, l);

            }

        }

        for(int i=0; i<sz; ++i) {

            for(int j=i+1; j<sz; ++j) {

                int o = 0 - num[i] - num[j];

                if(m.containsKey(o)) {

                    List<Integer> l = m.get(o);

                    for(int idx : l) {

                        if(idx > j){

                            tri.add(num[i]);

                            tri.add(num[j]);

                            tri.add(num[idx]);

                            if (ret.isEmpty() || !tri.equals(ret.get(ret.size() - 1))) {

                                ret.add(tri);

}

                        }

                    }

                }

            }

        }

        return ret;

    }

}

3.  4Sum:

Answer:

static List<List<Integer>> fourSum(int[] num, int target) {

HashMap<Integer, List<Integer>> hmap = new HashMap<Integer, List<Integer>>();

                List<List<Integer>> ret = new ArrayList<List<Integer>>();

                List<Integer> tup = new ArrayList<Integer>();

int sz = num.length;

for (int i = 0; i < sz; ++i) {

for (int j = i + 1; j < sz; ++j) {

                                                                                            //key: val, value: idx=i*sz+j;

int val = num[i] + num[j];

int idx = i * sz + j;                              // pair(i,j) <-> idx= i*sz +j;

                                if (hmap.containsKey(val)) {

hmap.get(val).add(idx);

} else {

List<Integer> l = new ArrayList<Integer>();

l.add(idx);

hmap.put(val, l);

}

}

}

for (int i = 0; i < sz; ++i) {

for (int j = i + 1; j < sz; ++j) {

int val = num[i] + num[j];

int o = target - val;

if (hmap.containsKey(o)) {

List<Integer> l = hmap.get(o);

for (int pos : l) {

    if (j < pos / sz) {                            //!important, to avoid duplicate!

tup.add(num[i]);

tup.add(num[j]);

tup.add(num[pos / sz]);

tup.add(num[pos % sz]);

if (ret.isEmpty() || !tup.equals(ret.get(ret.size() - 1))) {

ret.add(tup);

     }

}

}

}

}

return ret;

}

}

Selection Sort

void selection_sort(int *a, int len)
{
    register int i, j, min, t;
    for(i = 0; i < len - 1; i ++)
    {
        min = i;//最小值下标
        //查找最小值
        for(j = i + 1; j < len; j ++)
            if(a[min] > a[j])
                min = j;
        //交换
        if(min != i)
        {
            t = a[min];
            a[min] = a[i];
            a[i] = t;
        }
    }
}

Evaluate Reverse Polish Notation -- Leetcode

Question:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Answer:
对于逆波兰式，一般都是用栈来处理，依次处理字符串，

如果是数值，则push到栈里面

如果是操作符，则从栈中pop出来两个元素，计算出值以后，再push到栈里面，

则最后栈里面剩下的元素即为所求。

class Solution {
public:
      int evalRPN (vector<string> &tokens) {
            stack<int> operand;   
            for(int i =0; i< tokens.size(); i++)   
            {   
                 if ((tokens[i][0] == '-' && tokens[i].size()>1) //negative number  
                           || (tokens[i][0] >= '0' && tokens[i][0] <= '9')) //positive number  
                 {   
                      operand.push(atoi(tokens[i].c_str()));   
                      continue;  
                 }  
                 int op1 = operand.top();  
                 operand.pop();  
                 int op2 = operand.top();  
                 operand.pop();  
                 if(tokens[i] == "+") operand.push(op2+op1);  
                 if(tokens[i] == "-") operand.push(op2-op1);  
                 if(tokens[i] == "*") operand.push(op2*op1);  
                 if(tokens[i] == "/") operand.push(op2/op1);  
            }  
            return operand.top();  
      }

};

Sqrt(x) -- Leetcode

Implement int sqrt(int x).

Compute and return the square root of x.

1. 二分法：Binary Search.

public int mySqrt(int x) {
        if(x < 0)return -1;
        if(x == 0)return 0;
        int start = 1;
        int end = x / 2 + 1;
        
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(mid <= x/mid && (mid+1) > x/(mid+1)){
                return mid;
            }else if(mid > x/mid){
                end = mid - 1;
            }else{
                //mid <= x/mid && (mid+1) <= x/(mid+1)
                start = mid + 1;
            }
        }
        return end;

    }

2. 牛顿迭代法

   为了方便理解，就先以本题为例：

   计算x² = n的解，令f(x)=x²-n，相当于求解f(x)=0的解，如左图所示。

   首先取x₀，如果x₀不是解，做一个经过(x₀,f(x₀))这个点的切线，与x轴的交点为x₁。

   同样的道理，如果x₁不是解，做一个经过(x₁,f(x₁))这个点的切线，与x轴的交点为x₂。

   以此类推。

   以这样的方式得到的x_i会无限趋近于f(x)=0的解。

   判断x_i是否是f(x)=0的解有两种方法：

   一是直接计算f(x_i)的值判断是否为0，二是判断前后两个解x_i和x_i-1是否无限接近。

经过(x_i, f(x_i))这个点的切线方程为f(x) = f(x_i) + f’(x_i)(x - x_i)，其中f'(x)为f(x)的导数，本题中为2x。令切线方程等于0，即可求出x_i+1=x_i - f(x_i) / f'(x_i)。

继续化简，x_i+1=x_i - (x_i² - n) / (2x_i) = x_i - x_i / 2 + n / (2x_i) = x_i / 2 + n / 2x_i = (x_i + n/x_i) / 2。

有了迭代公式x_i+1= (x_i + n/x_i) / 2，程序就好写了。关于牛顿迭代法，可以参考wikipedia以及百度百科。

[cpp] view plaincopyprint?

1. int sqrt(int x) {  
2.         // Start typing your C/C++ solution below  
3.         // DO NOT write int main() function  
4.         if (x ==0)  
5.             return 0;  
6.         double pre;  
7.         double cur = 1;  
8.         do  
9.         {  
10.             pre = cur;  
11.             cur = x / (2 * pre) + pre / 2.0;  
12.         } while (abs(cur - pre) > 0.00001);  
13.         return int(cur);  
14.     }  

Reverse Words in a String -- Leetcode

Question:

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

click to show clarification.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

Answer:

class Solution {

public:

    void reverseWords(string &s) {

        string ss;

        string res;

        

        for(int i=0; s[i]!='\0';++i){

            if(s[i]!=' '){

               ss.append(s[i],1);

            }

                 //For invalid ' ', if there exists duplicate ' '.

            else if(s[i] == ' ' && s[i+1] == ' '){

                continue;

            }

                 //For effective ' ', if there exists duplicate ' '. For case: "aa bb   cc   ".

            else if(s[i] == ' ' && s[i+1] != ' ' && s[i+1] != '\0'){

                res.insert(0," ");

                res.insert(1,ss);

                ss.clear();

            }

                 //For last word.

            else if(s[i] == ' ' && s[i+1] == '\0'){

                res.insert(0,ss);

                ss.clear();

            }

        }

        s = res;

    }

};

vector implementation using array -- Java

public class ImpArrayList {
   private int[] m_data = null;
 
   private int m_cur_size = -1;
   private int m_total_size = -1;
 
   private static final int s_min_size = 8;

 
 
   public ImpArrayList(int sz) {
       if(sz < 0) {
           sz = 0;
       }
       m_total_size = sz*2;
       if(m_total_size < s_min_size) {
           m_total_size = s_min_size;
       }
       m_data = new int [m_total_size];
       m_cur_size = sz;
   }

   public ImpArrayList() {
       this(0);
   }

   public int get(int i) {
       return m_data[i];
   }

   public void set(int i, int v) {
       m_data[i] = v;
   }

   public void push_back(int v) {
       if(m_cur_size >= m_total_size) {
           m_total_size = m_total_size * 2;
           int [] tmp = new int [m_total_size];
           System.arraycopy(m_data, 0, tmp, 0, m_cur_size);
           m_data = tmp;
       }
       m_data[m_cur_size] = v;
       m_cur_size++;
   }

   public void pop_back() {
       m_cur_size--;
       if(m_cur_size < 0) {
           //should throw an exception
           m_cur_size = 0;
       }
   }

   public boolean empty() {
       return m_cur_size == 0;
   }

   //some other functions like resize ...
   public static void main(int argc, String[] argv){
   
   }
}

Sudoku Solver

class Solution {
public:
    bool solveSudoku(vector<vector<char> > &board) {
        for (int i = 0; i < 9; ++i){
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (int k = 0; k < 9; ++k) {
                        board[i][j] = '1' + k;
                        if (isValid(board, i, j) && solveSudoku(board))
                            return true;
                    }
                    board[i][j] = '.';
                    return false;
                }
            }
        }
        return true;
    }
private:
   
    bool isValid(const vector<vector<char> > &board, int x, int y) {
        int i, j;
        for (i = 0; i < 9; i++) // 检查 y 列
            if (i != x && board[i][y] == board[x][y])
                return false;
        for (j = 0; j < 9; j++) // 检查 x 行
            if (j != y && board[x][j] == board[x][y])
                return false;
        for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
            for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
                if ((i != x || j != y) && board[i][j] == board[x][y])
                    return false;
        return true;
    }
};

LRU Cache -- Java

public class LRUCache {
    class Node{
        int key;
        int value;
        Node prev;
        Node next;
     
        public Node(int k, int v){
            key = k;
            value = v;
            prev = null;
            next = null;
        }
        public void setValue(int v){
            value = v;
        }
    }
 
 
    int cap;
    HashMap<Integer,Node> hmap;
    Node head;
    Node tail;
 
    public LRUCache(int capacity) {
        if(capacity<0){
            capacity = 1;
        }
        cap = capacity;
        hmap = new HashMap<Integer, Node>();
        head = null;
        tail = null;
    }
 
    public int get(int key) {
        if(hmap.containsKey(key)){
            if(hmap.size()>1){
                dragKeyNode(hmap.get(key));                   //lru
            }
            return hmap.get(key).value;
        }
        else return -1;
    }
 
    public void set(int key, int value) {
        if(hmap.containsKey(key)){
            dragKeyNode(hmap.get(key));                       //lru
            hmap.get(key).setValue(value);
        }
        else{      
                 //to insert a new Node to the doubly linkedin list.
            Node insertNode = new Node(key,value);
         
            if(hmap.size() < cap){                                     //!important judge.
                attachKeyNode(insertNode);
            }
            else{                                                                 // cur size >=cap
                detachKeyNode();
                attachKeyNode(insertNode);
            }
            hmap.put(key,insertNode);          
        }
        return;
    }
 
   //drag an existed node from original inner pos in doubly linkedlist to the head new pos.

    public void dragKeyNode(Node p){          
        if(p==head)return;                                    //if p==head, nothing needed to do.
     
        Node pprev = p.prev;
        Node pnext = p.next;
     
        pprev.next = pnext;
        if(pnext!=null){
            pnext.prev = pprev;
        }
        else{                                                          //if p is currently tail node, modify tail!
            tail = pprev;
        }
        p.prev = null;
        p.next = null;
        attachKeyNode(p);    
        return;
    }
 
 
    public void attachKeyNode(Node p){
        if(head == null && tail == null){
            head = p;
            tail = p;
        }
        else{                                
            p.next = head;
            head.prev = p;
            head = p;
        }
        return;
    }
 
    public void detachKeyNode(){                  //cut off tail node.
        if(hmap.size() < 1)return;
     
        int key = tail.key;
        hmap.remove(key);                                 //!important, also need to delete tail node in hashmap.
     
        if(hmap.size()==0){
            head = null;
            tail = null;
        }
        else{
            Node pprev = tail.prev;
            pprev.next = null;
            tail.prev = null;
            tail = pprev;
        }
        return;
    }
}

Encoding and decoding string

Question:

Answer:
Method 1:  '+'  to split strings, '\' to transfered symbol.

import java.util.ArrayList;

public class Dumper {
    public static void main(String [] args) {

        String [] str_array = new String [] {
            "a+b", // a+b
            "c\\b", // c\b
        };

        System.out.println("Orig: ");
        for(String s : str_array) {
            System.out.println(s);
        }

        String str_serialized = Serialize(str_array);

        System.out.println("Serialized: " + str_serialized);

        String [] str_deserialized = Deserialize(str_serialized);

        System.out.println("Deserialized: ");
        for(String s : str_deserialized) {
            System.out.println(s);
        }
    }

    static String Serialize(String [] str_arr) {
        StringBuilder buf = new StringBuilder();

        for(String s : str_arr) {
            for(int i=0; i<s.length(); ++i) {
                char c = s.charAt(i);

                if(c == '+' || c == '\\') {
                    buf.append('\\');
                }
                buf.append(c);
            }
            buf.append('+');
        }

        return buf.toString();
    }

    static String [] Deserialize(String str) {
        ArrayList<String> str_arr = new ArrayList<String>();

        StringBuilder buf = new StringBuilder();

        for(int i=0; i<str.length(); ++i) {
            char c = str.charAt(i);

            if(c == '\\') {
                c = str.charAt(i+1);
                i++;
                buf.append(c);
            }
            else if(c == '+') {
                str_arr.add(buf.toString());
                buf = new StringBuilder();
            }
            else {
                buf.append(c);
            }
        }

        return str_arr.toArray(new String [0]);

    }
}

Print Matrix Diagonally

Given a 2D matrix, print all elements of the given matrix in diagonal order. For example, consider the following 5 X 4 input matrix.

    1     2     3     4
    5     6     7     8
    9    10    11    12
   13    14    15    16
   17    18    19    20  (5x4)

Diagonal printing of the above matrix is

    1
    5     2
    9     6     3
   13    10     7     4
   17    14    11     8
   18    15    12
   19    16
   20

Following is C++ code for diagonal printing.

The diagonal printing of a given matrix ‘matrix[ROW][COL]‘ always has ‘ROW + COL – 1′ lines in output

#include <stdio.h> #include <stdlib.h>   #define ROW 5 #define COL 4   int min(int a, int b) { return (a < b)? a: b; }   int min(int a, int b, int c) { return min(min(a, b), c);}   int max(int a, int b) { return (a > b)? a: b; }   void diagonalOrder(int matrix[][COL]) {     for (int line=1; line<=(ROW + COL -1); line++)     {         /* Get column index of the first element in this line of output. The index is 0 for first ROW lines and line - ROW for remaining            lines  */         int start_col =  max(0, line-ROW);           /* Get count of elements in this line. The count of elements is            equal to minimum of line number, COL-start_col and ROW */          int count = min(line, (COL-start_col), ROW);         for (int j=0; j<count; j++)             printf("%5d ", matrix[min(ROW, line)-j-1][start_col+j]);           /* Ptint elements of next diagonal on next line */         printf("\n");     } }   void printMatrix(int matrix[ROW][COL]) {     for (int i=0; i< ROW; i++)     {         for (int j=0; j<COL; j++)             printf("%5d ", matrix[i][j]);         printf("\n");     } }   int main() {     int M[ROW][COL] = {{1, 2, 3, 4},                        {5, 6, 7, 8},                        {9, 10, 11, 12},                        {13, 14, 15, 16},                        {17, 18, 19, 20},                       };     printf ("Given matrix is \n");     printMatrix(M);       printf ("\nDiagonal printing of matrix is \n");     diagonalOrder(M);     return 0; }