剑指offer1-3题总结

1 二维数组中的查找

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

1 2 3
4 5 6
7 8 9

分析：
1 根据输入的二维数组的规律可知：（1）右上角的数字，左边的数字都比它小，下边的数字都比它大；（2）左下角的数字，右边的数字都比它大，上边的数字都比它小。
2 根据这个规律，可以确定左下或右上的一个数，基于这个数的规律，进行数字判别计算。

/**
     * 通过二维数组的规律
     * 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
     * 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
     * 要查找数字比左下角数字小时。上移
     * 从右上角开始查找，当要查找数字比右上角数字大时。下移
     * 要查找数字比右上角数字小时。左移
     * @param:
     * @return:
     * @date: 2018-3-12  
     */
    public static boolean Find1(int target, int [][] array) {
        int row = array.length-1;
        int col = 0;

        while(row>=0 && col<=array.length-1){
            if(target == array[row][col]){
                return true;
            }else if(target >= array[row][col]){
                col++;
            }else{
                row--;
            }
        }
        return false;
    }

2 替换空格

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

分析：
1 初始化新的数据结构存储结果；(重点)
2 遍历字符串，找到空格；
3 根据不同情况，将不同的数据填充到新的存储结构中；

public String replaceSpace(StringBuffer str) {
            StringBuilder sb = new StringBuilder(); 
            for(int i=0;i<str.length();i++){
               if(str.charAt(i) == ' '){//charAt比较不能用equals
                    sb.append("%20");   
                }else{
                    sb.append(str.charAt(i));
                }
            }
           return sb.toString();
        }

使用ascll码方式判断（更优）

回车，ASCII码13
换行，ASCII码10
空格，ASCII码32

    /**
     * 请实现一个函数，将一个字符串中的每个空格替换成“%20”。
     * 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
     * @param str
     * @return
     */
    public static String replaceSpace(StringBuffer str){
        StringBuffer resStr = new StringBuffer();
        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == 32){
                resStr.append("%20");
            }else{
                resStr.append(str.charAt(i));
            }
        }
        return resStr.toString();
    }

3 从尾到头打印链表

输入一个链表，从尾到头打印链表每个节点的值。

分析：
1 怎样创建链表？
2 怎样遍历链表？
3 将ArrayList从尾到头打印，要怎么实现？
4 堆栈和递归的特点。

链表结构如下：

class ListNode {
    int val;
    ListNode next = null;

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

创建链表的操作

static ListNode head;

static void addNode(ListNode node){
    ListNode temp = null;
    if(head == null){
        head = node;
        return;
    }
    temp  =  head;
    while(temp.next != null){
          temp = temp.next;
    }
    temp.next = node;
}

使用递归的特点实现

    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> resArrayList = new ArrayList<Integer>();
        if (listNode != null){
            printListFromTailToHead(listNode.next);
            resArrayList.add(listNode.val);
        }
        return resArrayList;
    }

使用堆栈的特性实现

public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      Stack<Integer> stack = new Stack<>();
      while(listNode.next != null){
          stack.push(listNode.val);
     }
     ArrayList<Integer> list = new ArrayList<>();
     while(!stack.isEmpty()){
           list.add(stack.pop());
    }
    return list;
}

P.S.
总之，看到一个问题，首先要搞懂题目，然后明白如何处理。