剑指offer【持续更新中】

1、数组的查找

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

public class Solution {
    public boolean Find(int target, int [][] array) {
    	//分出行和列
        int hang=array.length;
        int lie=array[0].length;
        //如果行或列为零的话，肯定不存在
        if(hang==0 || lie==0){
            return false;
        }
        //对每一行的数据进行比对，使用二分法查找
        for(int i=0;i<hang;i++) {
        	//注意一下边界的关系
        	int start=0;
            int end=lie-1;
        	while(start<=end) {
        		int mid=(start+end)/2;
        		if(array[i][mid]==target) {
        			return true;
        		}else if(array[i][mid]>target) {
        			end=mid-1;
        		}else if(array[i][mid]<target) {
        			start=mid+1;
        		}
        	}
        }
        //如果都找遍了，但是还没有结果，说明不存在
        return false;
    }
}

2、替换空格

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

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	int len=str.length();
    	for(int i=0;i<len;) {
    		char c=str.charAt(i);
    		if(c==' ') {
    			str.deleteCharAt(i);
    			str.insert(i, "%20");
    			len=str.length();
    			i+=3;
    		}else {
    			i+=1;
    		}
    	}
    	return str.toString();
    }
}

3、从尾到头打印链表

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

方法一：使用栈作为中间存储

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode==null || listNode.next==null){
            return new ArrayList<Integer>();
        }
        Stack<Integer> stack=new Stack<Integer>();
        while(listNode.next!=null) {
			stack.push(listNode.val);
            listNode=listNode.next;
		}
        stack.push(listNode.val);
        ArrayList<Integer> list=new ArrayList<Integer>();
        while(!stack.isEmpty()) {
        	list.add(stack.pop());
        }
        return list;
    }
}

方法二：使用dfs反转链表

/**
*    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) {

		if(listNode==null || listNode.next==null){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> list = new ArrayList<>();
        listNode = reverse(listNode);
        while(listNode!=null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
    
    //反转整个链表
	public ListNode reverse(ListNode head) {
		if(head.next == null) {
			return head;
		}
		ListNode last = reverse(head.next);
		head.next.next = head;
		head.next = null;
		return last;
	}
}

反转链表参考这位大佬的，从反转全部链表到部分反转链表，讲的很透彻：题解