1.在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同）癌蓖，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序份名。請(qǐng)完成一個(gè)函數(shù)碟联，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)妓美，判斷數(shù)組中是否含有該整數(shù)。
方法一：普通方法鲤孵，全部遍歷一遍
public class Solution {
????public boolean Find(int target,?int[][] array)?
?????????????for(int i=0;i<array.length;i++){
?????????????????for(int j=0;j<array[0].length;j++){
?????????????????????if(target==array[i][j])
????????????????????????return true;
?????????????????}
?????????????}
?????????????return false;
????}
}
方法二：利用題目要求從左下角開始遍歷壶栋，若是比左下角數(shù)字大則在右邊查找，否則向上查找
public class Solution {
? ? public boolean Find(int target, int [][] array){
? ? ? ? int row = array.length-1;
? ? ? ? int col = 0;
? ? ? ? while(col<array[0].length&&row>=0){
? ? ? ? ? ? if(target==array[row][col]){
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? ? ? else if(target>array[row][col]){
? ? ? ? ? ? ? ? col++;
? ? ? ? ? ? }
? ? ? ? ? ? else{
? ? ? ? ? ? ? ? row--;
? ? ? ? ? ? }
? ? ? ? }
? ? ? return false;
? ? }
}
方法三：二分查找
public class Solution {
? ? public boolean Find(int target, int [][] array){
? ? ? ? for(int i=0;i<array.length;i++){
? ? ? ? ? ? int left = 0;
? ? ? ? ? ? int right = array[i].length-1;
? ? ? ? ? ? while(left<=right){
? ? ? ? ? ? ? ? int flag = (left+right)/2;
? ? ? ? ? ? ? ? if(target>array[i][flag]){
? ? ? ? ? ? ? ? ? ? left=flag+1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else if(target<array[i][flag])
? ? ? ? ? ? ? ? ? ? right=flag-1;
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return false;
? ? }
}
2.請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)普监，將一個(gè)字符串中的每個(gè)空格替換成“%20”贵试。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy凯正。
方法一：將StringBuffer轉(zhuǎn)為String類型再使用replace方法
public class Solution {
? ? public String replaceSpace(StringBuffer str) {
? ? return str.toString().replaceAll("\\s","%20");
? ? }
}
方法二：遍歷加入到新的StringBuffer對(duì)象中
public class Solution {
? ? public String replaceSpace(StringBuffer str) {
? ? String s = str.toString();
? ? ? ? char[] s1 = s.toCharArray();
? ? ? ? StringBuffer s2 = new StringBuffer();
? ? ? ? for(int i=0;i<s1.length;i++){
? ? ? ? ? ? if(s1[i]==' '){
? ? ? ? ? ? ? ? s2.append("%20");
? ? ? ? ? ? }
? ? ? ? ? ? else{
? ? ? ? ? ? ? ? s2.append(s1[i]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return s2.toString();
? ? }
}
方法三：遍歷在原對(duì)象中操作
public class Solution {
? ? public String replaceSpace(StringBuffer str) {
? ? ? ? for(int i=0;i<str.length();i++){
? ? ? ? ? ? if(str.charAt(i)==' '){
? ? ? ? ? ? ? ? str.deleteCharAt(i);
? ? ? ? ? ? ? ? str.insert(i,"%20");
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return str.toString();
? ? }
}
3.輸入一個(gè)鏈表毙玻，按鏈表值從尾到頭的順序返回一個(gè)ArrayList。
方法一:利用遞歸將鏈表中的數(shù)據(jù)從尾到頭加入到新的鏈表
import java.util.ArrayList;
public class Solution {
? ? public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
? ? ? ? ArrayList arraylist = new ArrayList();
? ? ? ? if(listNode!=null){
? ? ? ? ? ? this.printListFromTailToHead(listNode.next);
? ? ? ? ? ? arraylist.add(listNode.val);
? ? ? ? }
? ? ? ? return arraylist;?
? ? }
}
方法二：
import java.util.ArrayList;
public class Solution {
? ? public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
? ? ? ? ArrayList<Integer> arraylist = new ArrayList<Integer>();
? ? ? ? ListNode pre=null;
? ? ? ? ListNode next=null;
? ? ? ? while(listNode!=null){
? ? ? ? ? ? next=listNode.next;
? ? ? ? ? ? listNode.next = pre;
? ? ? ? ? ? pre=listNode;
? ? ? ? ? ? listNode= next;
? ? ? ? }
? ? ? ? while(pre!=null){
? ? ? ? ? ? arraylist.add(pre.val);
? ? ? ? ? ? pre=pre.next;
? ? ? ? }
? ? ? ? return arraylist;
? ? }
}
4.大家都知道斐波那契數(shù)列廊散，現(xiàn)在要求輸入一個(gè)整數(shù)n淆珊，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始，第0項(xiàng)為0）奸汇。
n<=39
方法一：遞歸
public class Solution {
? ? public int Fibonacci(int n) {
? ? ? ? if(n<=0) return 0;
? ? ? ? if(n==1||n==2)
? ? ? ? ? ? return 1;
? ? ? ? return Fibonacci(n-1)+Fibonacci(n-2);
? ? }
}
