NowCoder: 剑指Offer solutions.

Seperate the Odd and Even

	

public void reOrderArray(int [] array) {
    int top = -1;
    int p = 0;
    while (true){
        if( p>= array.length){
            break;
        }
        if((array[p]&1)!=0){
            int temp = array[p];
            for(int j = p -1; j>oddEnd; j --){
                array[j+1] = array[j];
            }
            array[top + 1] = temp;
            top ++;
        }
        p++;
    }
}

The last k elements from the end.

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
         ListNode[] out = new ListNode[1];
        FindKthToTail(head, k, out);
        return out[0];
    }
    
    private int FindKthToTail(ListNode head, int k, ListNode[] out){
        int count = 0;
        if(head != null){
            count =  1 + FindKthToTail(head.next, k, out);
        }
        if(count == k){
            out[0] = head;
        }
        return count;
    }
}

Reverse the linked list:

public class Solution {
    public ListNode ReverseList(ListNode head) {
		ListNode first = null;
        while(head!= null){
            ListNode next = head.next;
            head.next = first;
            first = head;
            head = next;
        }
        return first;
    }
}

Merge the list
  

public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = list1;
        
        while(list1!= null&&list2!= null){
            
            ListNode pre1 = null;
            while(list1!= null && list2!= null&& list1.val <= list2.val){
                pre1 = list1;
                list1 = list1.next; 
            }
            if(pre1!= null){
                pre1.next = list2;
            }
            ListNode pre2 = null;
            while(list1!= null && list2!= null && list2.val<list1.val){
                pre2 = list2;
                list2 = list2.next;
            }
            if(pre2!= null){
                pre2.next = list1;
            }
        }
        return head;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
   
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        
        boolean result = false;
        if (root2== null || root1 == null) {
            return false;
        }
        if (root1.val == root2.val) {
            if (root2.left == null) {
                result = true;
            } else if(root2.left!= null) {
                result =  HasSubtree(root1.left, root2.left);
            }
            if (result) {
                if (root2.right== null) {
                    return true;
                } else{
                    if(HasSubtree(root1.right, root2.right)) {
                    	return true;
                    }
                }
            }
        }
        if (HasSubtree(root1.left, root2) 
            || HasSubtree(root1.right, root2) ) {
            return true;
        }
        return false;
    }

题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

import java.util.ArrayList;
public class Solution {
    
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> result = new ArrayList<>();
        int xEndIndex = matrix[0].length-1;
        int yEndIndex = matrix.length -1;
        int[][] end = new int[][]{{xEndIndex,0},{xEndIndex,yEndIndex},{0,yEndIndex},{0,1}};
        int[][] inset = new int[][]{{-1, 1}, {-1, -1}, {1, -1}, {1, 1}};
        int[][] delta = new int[][]{
            {1, 0},{0, 1}, {-1, 0}, {0, -1}
        };
        int x = 0;
        int y = 0;
        int deltaIndex = 0;
        int count = matrix.length*matrix[0].length;
        while(count > 0){
            result.add(matrix[y][x]);
            if(x == end[deltaIndex][0] && y == end[deltaIndex][1]){
                if(deltaIndex < delta.length - 1){
                    deltaIndex ++;
                }else{
                   for(int i = 0; i < end.length; ++ i){
                        for(int j = 0; j < end[i].length; ++ j){
                            end[i][j] = end[i][j] + inset[i][j];
                        }
                   }
                   deltaIndex = 0;
                }
            }
        	x = x + delta[deltaIndex][0];
            y = y + delta[deltaIndex][1];
            count --;
        }
        return result;
    }
}

import java.util.Stack;



定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
complexity of min, pop, top and push is : O(1)

/**
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
*/
public class Solution {
	
    public static final int incresement = 32;
    
    private int maxSize = 0;
    
    private int top;
    
    private int[] stack;
    
    public void doPush(int node){
        top ++;
        stack[top] = node;
    }
    
    private void checkIncreaseStack(){
        if(stack == null){
            stack = new int[incresement];
            maxSize = incresement;
            top = -1;
        }else if(top==maxSize -1){
            //increase
            int newMaxSize = maxSize + incresement;
            int[] newStack = new int[newMaxSize];
            for(int i = 0; i < maxSize; ++ i){
                newStack[i] = stack[i];
            }
            stack  = newStack;
        }
    }
       
    public void push(int node) {
        
        checkIncreaseStack();
        
        int currentMin;
        if(top >=0){
            currentMin = stack[top];
            if(node < currentMin){
           		currentMin = node;
       		}
        }else{
            currentMin = node;
        }
        doPush(node);
        doPush(currentMin);
    }
    
    public void pop() {
        if (top>=2) {
           top = top - 2; 
        }else{
            throw new RuntimeException("error 1");
        }
    }
    
    public int top() {
       if(stack == null || top < 0){
            throw new RuntimeException("error 2");
        }
        return stack[top - 1];
    }
    
    public int min() {
        if(stack == null || top < 0){
            throw new RuntimeException("error 3");
        }
        return stack[top];
    }
}

Mirror of binary tree

import java.util.List;
import java.util.ArrayList;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        while(nodes.size() > 0){
            int size = nodes.size();
            for (int i = 0; i < size; ++ i){
                TreeNode node = nodes.remove(0);
                TreeNode left = node.left;
                node.left = node.right;
                node.right = left;
                if(node.left!= null){
                    nodes.add(node.left);
                }
                if(node.right!= null){
                    nodes.add(node.right);
                }
            }
        }
    }
}

import java.util.Stack;

/**
	输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序
	。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序
	，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，
	但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
*/
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
       
        Stack<Integer> stack = new Stack<>();
       
        int pPush = 0;
       
        int pPop = 0;
       
        while (pPush < pushA.length) {
           stack.push(pushA[pPush]);
           pPush ++;
           while (stack.size()> 0 
                  && pPop < popA.length 
                  && stack.peek()== popA[pPop]) {
              stack.pop();
              pPop ++;
           }
        }
        
        if(pPop != popA.length){
            return false;
        }else{
            return true;
        }
    }
}

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）

public class Solution {
    public int Sum_Solution(int n) {
        
        int result = 0;
        
        boolean kk = ((n==0) || result == (result = Sum_Solution(n - 1)));
            
        return n + result;

    }
}