1.在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
方法一：普通方法，全部遍历一遍
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;
}
}
方法二：利用题目要求从左下角开始遍历，若是比左下角数字大则在右边查找，否则向上查找
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.请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
方法一：将StringBuffer转为String类型再使用replace方法
public class Solution {
public String replaceSpace(StringBuffer str) {
return str.toString().replaceAll("\\s","%20");
}
}
方法二：遍历加入到新的StringBuffer对象中
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();
}
}
方法三：遍历在原对象中操作
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.输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
方法一:利用递归将链表中的数据从尾到头加入到新的链表
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.大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为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);
}
}
