剑指offer刷题（一）

一.二维数组的查找

题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

public class Solution {
    public static void main(String[] args) {
        int[][] array = new int[][]{{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
        boolean res = Find(7, array);
        System.out.println(res);
    }

    //第一种方法
    public static boolean Find(int target, int [][] array) {
        if(array==null){
            return false;
        }
        //列数
        int colSize = array[0].length;
        //行数
        int rowSize = array.length;
        //首先在第一行依次的往后查找
        for(int i = 0 ; i < colSize; i++){
            if(array[0][i]>target){
                return false;
            }
            System.out.println("第"+(i+1)+"列");
            //每一列的最后一个值为最大值
            for(int j = 0 ;j < rowSize; j++){
                System.out.println(array[j][i]);
                if(array[rowSize-1][i]<target){
                    break;
                }
                //二分查找
                int min = 0;
                int max = rowSize-1;
                while(min <= max){
                    int mid = (min+max)/2;
                    int curNum = array[mid][i];
                    if(curNum == target){
                        return true;
                    }else if(curNum > target){
                        max = mid - 1;
                    }else{
                        min = mid + 1;
                    }
                }
            }
        }
        return false;
    }

    //第二种方法
    public boolean Find2(int target, int [][] array) {
        if(array==null){
            return false;
        }
        //列数
        int colSize = array[0].length;
        //行数
        int rowSize = array.length;

        int rowNum = rowSize-1;
        int colNum = 0;

        while(colNum<colSize && rowNum>=0){
            if(target == array[rowNum][colNum]){
                return true;
            }else if(target>array[rowNum][colNum]){
                colNum++;
            }else {
                rowNum--;
            }
        }
        return false;
    }
}

二.替换空格

题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public class Solution2 {
    //第一种方法 直接调API替换
    public String replaceSpace(StringBuffer str) {
        if (str==null || str.toString().equals(""))return str.toString();
        for (int i = 0;i<str.length();i++){
            if (str.charAt(i)==' '){
                str.replace(i,i+1, "%20");
            }
        }

        return str.toString();
    }


    //第二种方法 倒着插入
    public String replaceSpace2(StringBuffer str) {
        int spacenum = 0;//spacenum为计算空格数
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' ')
                spacenum++;
        }
        int indexold = str.length()-1; //indexold为为替换前的str下标
        int newlength = str.length() + spacenum*2;//计算空格转换成%20之后的str长度
        int indexnew = newlength-1;//indexold为为把空格替换为%20后的str下标
        str.setLength(newlength);//使str的长度扩大到转换成%20之后的长度,防止下标越界
        for(;indexold>=0 && indexold<newlength-1;--indexold){
            if(str.charAt(indexold) == ' '){  //
                str.setCharAt(indexnew--, '0');
                str.setCharAt(indexnew--, '2');
                str.setCharAt(indexnew--, '%');
            }else{
                str.setCharAt(indexnew--, str.charAt(indexold));
            }
        }
        return str.toString();
    }
}

三.从头到尾打印链表

题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

public class Solution3 {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      //第一种方法 普通插入方法
        ArrayList<Integer> list = new ArrayList<>();
        while(listNode!=null){
            list.add(0, listNode.val);
            listNode=listNode.next;
        }
        return list;

    }

    //第二种方法  stack
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {

        Stack<Integer> stack=new Stack<Integer>();
        while(listNode!=null){
            stack.push(listNode.val);
            listNode=listNode.next;
        }

        ArrayList<Integer> list=new ArrayList<Integer>();
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }

    //第三种方法  递归
    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {

        ArrayList<Integer> list=new ArrayList<Integer>();
        addListNodeVal(list , listNode);
        return list;
    }

    private void addListNodeVal(ArrayList<Integer> list , ListNode listNode) {
        if(listNode!=null){
            if(listNode.next!=null){
                addListNodeVal(list,listNode.next);
            }
            list.add(listNode.val);
        }
    }

    class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}