数组

二维数组中的查找

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

该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。

124213_1560686367049_0ad9f7baf4084999a77a9b73562c9088.gif

public class Solution {
    public static boolean Find(int target, int [][] array) {
        for (int[] ints : array) {
            for (int j = array[0].length - 1; j >= 0; j--) {
                if (target == ints[j]) {
                    return true;
                } else if (target > ints[j]) {
                    break;
                }
            }
        }
        return false;
    }
}

第二道

......

数组笔记

1. 二维数组中，array.length指多少行，array[0].length指多少列

字符串

替换空格

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

在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。
令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。
从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。

124213_1560686383610_6980aef0debe4b4b8da58b1befbc1408.gif

public static String replaceSpace(StringBuffer str) {
        char c = ' ';
        int p1 = str.length() - 1;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == c) {
                str.append("aa");
            }
        }
        int p2 = str.length() - 1;
        while (p1 >= 0) {
            if (str.charAt(p1) == c) {
                str.setCharAt(p2--, '0');
                str.setCharAt(p2--, '2');
                str.setCharAt(p2--, '%');
            } else {
                str.setCharAt(p2--, str.charAt(p1));
            }
            p1--;
        }
        return str.toString();
    }

第二道

......

字符串笔记

1. StringBuffer会预留额外空间，因此length和capacity的值是不一样的，不要写错了

链表

从尾到头打印链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

递归法

124213_1560686400379_f5792051d9b24ca4a234a4a2de3d5a57.png

要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (listNode != null) {
            arrayList.addAll(printListFromTailToHead(listNode.next));
            arrayList.add(listNode.val);
        }
        return arrayList;
    }
}