剑指offer

据说做完剑指offer就可以找到好工作呢。

前10题已经做过就不写了。

11、二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解：

public class Solution {
public int NumberOf1(int n) {
    int count = 0;
    if(n<0){count++; n = n & 0x7fffffff;}//因为负数在计算机中是以补码表示的，这里把负数转为正数，并count记1.
    while(n>0){ 
        int x = n%2;
        if(x ==1){
            count++;
        }
        n /= 2;
    }
    return count;
}
}

看到别人的最优解，很精彩：

public static int NumberOf1(int n) {
    int count = 0;
    while (n != 0) {
        ++count;
        n = (n - 1) & n;
    }
    return count;
}

12、整数的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解：

public double Power(double base, int exponent) {
    double number=1;
    int count = exponent;
    if(exponent < 0 )count = -exponent;
    for(int i=0;i<count;i++){
        number *= base;
    }
    if(exponent < 0){
        number = 1/number;
    }
    return number;
}

13、调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解:

public class Solution {
public void reOrderArray(int [] array) {
    int []ji = new int [array.length];
    int []ou = new int [array.length];
    int jiIndex = 0;
    int ouIndex = 0;
    for(int i=0;i<array.length;i++){
        if(array[i]%2 == 1){
            ji[jiIndex] = array[i];
            jiIndex++;
        }else{
            ou[ouIndex] = array[i];
            ouIndex++;        
        }
    }
    for(int i=0;i<array.length;i++){
        if(i<jiIndex){
            array[i] = ji[i];
        }else{
            array[i] = ou[i-jiIndex];
        }
    }
}
}

14、链表中倒数第K个节点

输入一个链表，输出该链表中倒数第k个结点。

 /*
public class ListNode {
    int val;
    ListNode next = null;

ListNode(int val) {
    this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
    int count = 1;
    ListNode index =head;
    if(head == null)return head;
    while(index.next != null){index = index.next; count++;}
    if(count-k<0)return null;
    for(int i = 0;i < count-k; i++){
        head = head.next;
    }
    return head;
}
}

15、反转链表

输入一个链表，反转链表后，输出链表的所有元素。

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
    this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
    ListNode lastLast = null;
    ListNode last = null;
    ListNode self = head ;
    if(head == null)return null;
    while(self.next != null){
        if(last != null)lastLast = last;
        last = self ;
        self = self.next ;
        last.next = lastLast ;
    }
    self.next = last;
    return self;
}
} 

16、合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
    this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newListHead = new ListNode(0);
        ListNode newListIndex = newListHead;
        while(list1!=null | list2 !=null){
            if(list1 == null){newListIndex.next = list2;break;}
            if(list2 == null){newListIndex.next = list1;break;}
            if(list1.val < list2.val){
                newListIndex.next = list1;list1 = list1.next;newListIndex = newListIndex.next;
            }else{
                newListIndex.next = list2;list2 = list2.next;newListIndex = newListIndex.next;
            }
            
        }
        return newListHead.next;
}
}

17、树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

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

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

}

}
*/
public class Solution {
public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if(root1 == null ||root2 == null)return false;
    if(duibi(root1,root2)==true)return true;
    if (root1.left != null){if(HasSubtree(root1.left,root2)==true)return true;}
    if (root1.right != null){
        if(HasSubtree(root1.right,root2)==true)return true;}
    return false;
}

public static boolean duibi(TreeNode root1, TreeNode root2) {
  if(root2==null) return true;
    if(root1==null && root2!=null) return false;        
    if(root1.val==root2.val){
        return duibi(root1.left, root2.left) && duibi(root1.right, root2.right);
    }
    return false;
}
}

18、二叉树的镜像

二叉树的镜像定义：源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5

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

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

}

}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null)return;
    Mirror(root.left);
    Mirror(root.right);
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
}
}

19、顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 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 test1 {
public static ArrayList<Integer> printMatrix(int [][] matrix) {
    ArrayList<Integer> list =new ArrayList<Integer>();
    if(matrix==null)return null;
    int count = matrix.length*matrix[0].length;
    int fangxiang =1;//1右,2下,3左,4上
    int minX=-1,maxX=matrix[0].length,minY=0,maxY=matrix.length;
    int x=0,y=0;
    for(int i=0;i<count;){
        switch(fangxiang){
        case 1:
            if(x+1==maxX){
                fangxiang=2;
                maxX--;
            }else{
                list.add(matrix[y][x]);
                i++;
                x++;
            }
            break;
        case 2:
            if(y+1==maxY){
                fangxiang=3;
                maxY--;
            }else{
                list.add(matrix[y][x]);
                i++;
                y++;
            }
            break;
        case 3:
            
            if(x-1==minX){
                fangxiang=4;
                minX++;
            }else{
                list.add(matrix[y][x]);
                i++;
                x--;
            }
            break;
        case 4:
            if(y-1==minY){
                fangxiang=1;
                minY++;
            }else{
                list.add(matrix[y][x]);
                i++;
                y--;
            }
            break;
        }
    }
       return list;
}
}

20、包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

import java.util.Stack;
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list= new ArrayList();  
public void push(int node) {
    list.add(node);
}

public void pop() {
    list.remove(list.size()-1);
}

public int top() {
    return list.get(list.size()-1);
}

public int min() {
    int min = Integer.MAX_VALUE;
    if(list.size()>0){
        min = list.get(0);
        for(int i=0;i<list.size();i++){
            if(min>list.get(i))min = list.get(i);
        }
    }
    return min;
}
}

21、栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

 import java.util.ArrayList;

public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
    ArrayList<Integer> list= new ArrayList(); 
    int pushIndex = 0;
     int popIndex = 0;
     while(popIndex<popA.length){
         
         if(list.size()==0||list.get(list.size()-1)!=popA[popIndex]){
             if(pushIndex == pushA.length)return false;
             list.add(pushA[pushIndex]);
             pushIndex++;
         }else{
             list.remove(list.size()-1);
             popIndex++;
         };
         
         
     }
     return true;
}
}

22、从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

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

}

}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<TreeNode> treeList = new ArrayList<TreeNode>();
        ArrayList<TreeNode> nextTreeList = new ArrayList<TreeNode>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root == null)return list;                                          
        treeList.add(root);
        while(treeList.size()>0){
            for(int i=0;i<treeList.size();i++){
                list.add(treeList.get(i).val);
                if(treeList.get(i).left!=null)
                nextTreeList.add(treeList.get(i).left); 
                if(treeList.get(i).right!=null)
                    nextTreeList.add(treeList.get(i).right);
            }
            treeList = nextTreeList;
            nextTreeList = new ArrayList<TreeNode>();
            
            
        }
        return list;
}
}