劍指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;
	}
}

反轉鏈表參考這位大佬的，從反轉全部鏈表到部分反轉鏈表，講的很透徹：題解