第一題：
在一個二維數(shù)組中会油，每一行都按照從左到右遞增的順序排序蛤高，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)籍茧，輸入這樣的一個二維數(shù)組和一個整數(shù)版述，判斷數(shù)組中是否含有該整數(shù)。
????這是非常簡單的一道題寞冯，最常規(guī)的一種方式就是兩個方向上掃描渴析，但是要保證其中一個掃描方向數(shù)字是遞增的，而另外一個方向上數(shù)字是遞減的吮龄。
????下面給出我的解法俭茧，從矩陣中的右上角開始，從右往左掃漓帚，當(dāng)橫向當(dāng)前數(shù)的下一個數(shù)小于目標(biāo)數(shù)的時候往下少母债，找到返回true，越界返回false尝抖。
public class Solution {
public boolean Find(int target, int [][] array) {
for(int i = array[0].length-1; i >= 0; i--) {
if(array[0][i] <= target) {
for(int j = 0; j < array.length; j++) {
if(array[j][i] == target) return true;
}
}
}
return false;
}
}
第二題
請實(shí)現(xiàn)一個函數(shù)毡们，將一個字符串中的空格替換成“%20”。例如昧辽，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy衙熔。
????這題不解釋了，太簡單搅荞，很多編程語言直接用字符串處理函數(shù)就能做了红氯，用正則也能做，當(dāng)然咕痛，題目本身可能并不希望你這么干痢甘。
public class Solution {
public String replaceSpace(StringBuffer str) {
char[] arr = str.toString().toCharArray();
int len = arr.length;
int blankCount = 0;
for(int i = 0; i < len; i++) {
if(arr[i] == ' ')
blankCount++;
}
int[] res = new int[len+blankCount];
int j = 0;
for(int i = 0; i < len; i++) {
if(arr[i] == ' ') {
res[j++] = '%';
res[j++] = '2';
res[j++] = '0';
} else {
arr[j++] = arr[i];
}
}
StringBuffer sb = new StringBuffer();
for(int i = 0; i < res.length; i++) {
sb.append(res[i]);
}
return sb.toString();
}
}
第三題
輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點(diǎn)的值茉贡。
????最簡單的思路就是用棧倒序輸出塞栅。
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
while(listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while(!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}
第四題
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹腔丧。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字构蹬。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回悔据。
????總算來了個比較有意思的題目庄敛。給你前序和中序，讓你重構(gòu)二叉樹返回科汗。我們直接按題目中給的例子來講藻烤。
????前序遍歷是{1,2,4,7,3,5,6,8}，也就是說 {1}這個數(shù)字就是根盖喷。而中序遍歷是{4,7,2,1,5,3,8,6}沐悦，從而可以劃出兩個子集{4,7,2,1} {5,3,8,6}分別為組成以{1}為根的左右子樹。
????依照這個邏輯下去叹谁，就可以得出整棵樹的結(jié)構(gòu)了兴猩。這顯然就是一些重復(fù)步驟期吓，用遞歸去做是最好的方式。再進(jìn)一步思考倾芝，我們只需要知道前序和中序遍歷的邊界下標(biāo)讨勤，就能在遞歸過程中計算出我們要得到的數(shù)據(jù)。接下來晨另，讓我們直接看代碼潭千。
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return rebuilder(pre, in, 0, pre.length-1, 0, in.length-1);
}
public TreeNode rebuilder(int[] pre, int[] in, int prel, int prer, int inl, int inr) {
if(prel > prer) return null;
TreeNode node = new TreeNode(pre[prel]);
for(int i = inl; i <= inr; i++) {
if(in[i] == pre[prel]) {
node.left = rebuilder(pre, in, prel+1, prel+i-inl, inl, i-1);
node.right = rebuilder(pre, in, prel+i-inl+1, prer, i+1, inr);
break;
}
}
return node;
}
}
第五題
用兩個棧來實(shí)現(xiàn)一個隊(duì)列，完成隊(duì)列的Push和Pop操作借尿。 隊(duì)列中的元素為int類型刨晴。
????也是非常簡單的一題。要用兩個棧模擬隊(duì)列路翻，我們只需要保持兩個原則狈癞。第一，當(dāng)你要push一個元素到其中一個棧時候茂契，另外一個棧必須為空蝶桶。第二，當(dāng)你要pop一個元素的時候账嚎，必須把棧中的所有元素傾倒到另外一個空棧莫瞬，然后再pop數(shù)據(jù)出去儡蔓。
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
while(!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
stack1.push(node);
}
public int pop() {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
第六題
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾郭蕉，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)喂江，輸出旋轉(zhuǎn)數(shù)組的最小元素召锈。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1获询。 NOTE：給出的所有元素都大于0涨岁，若數(shù)組大小為0，請返回0吉嚣。
????咋看之下梢薪，這題似乎掃描一遍數(shù)組就行了。沒錯尝哆，確實(shí)如此秉撇，但是題目本身是希望你用二分去做的，不然給你非遞減這個特性就沒有意義了。題目說琐馆，非遞減數(shù)列做旋轉(zhuǎn)规阀，旋轉(zhuǎn)之后其實(shí)主要有兩種情況，一種就是旋轉(zhuǎn)后和旋轉(zhuǎn)前一樣瘦麸，一種是旋轉(zhuǎn)后和選擇前發(fā)生了變化（這里暫時忽略數(shù)列中過的數(shù)全部相等的情況）谁撼，第一種情況，數(shù)列的最后一個數(shù)一定是大于第一個數(shù)的滋饲。第二種情況厉碟，最小的數(shù)一定在數(shù)列中。而這個數(shù)列也會分成兩個遞增的子數(shù)列了赌，且兩個子序列相連的邊界數(shù)字一定是遞減的墨榄，比如：{3,4,5} {1, 2}兩個遞增數(shù)列，5和1這兩個邊界是下降的勿她，從而我們可以得到二分的條件袄秩，假設(shè)：當(dāng)前位置為i，那么當(dāng)a[i-1] > a[i]時逢并， i就是最小的數(shù)之剧。
public class Solution {
public int minNumberInRotateArray(int [] array) {
return binarySearch(array, 0, array.length-1);
}
/**
大體上就是一個二分搜索，注意搜索條件即可
*/
public int binarySearch(int[] arr, int l, int r) {
if (arr[0] < arr[arr.length - 1])
return arr[0];
int mid = (l + r) / 2;
// 這一句就是為了覆蓋數(shù)列數(shù)字全部相等的情況
if(mid == r) return arr[r];
if (arr[mid] < arr[mid - 1])
return arr[mid];
int res = 0;
if(l <= r) {
if (arr[mid] < arr[l])
res = binarySearch(arr, l, mid);
else
res = binarySearch(arr, mid, r);
}
return res;
}
}
第七題
大家都知道斐波那契數(shù)列砍聊，現(xiàn)在要求輸入一個整數(shù)n背稼，請你輸出斐波那契數(shù)列的第n項(xiàng)。
n<=39
????這題沒啥好講的玻蝌，為了避免爆棧蟹肘，應(yīng)該采用迭代的方式。
public class Solution {
public int Fibonacci(int n) {
if(n == 0)
return 0;
if(n == 1)
return 1;
int count = 1;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(0);
queue.add(1);
int res = -1;
while(count != n) {
res = queue.poll() + queue.peek();
queue.add(res);
count++;
}
return res;
}
}
第八題
一只青蛙一次可以跳上1級臺階俯树，也可以跳上2級帘腹。求該青蛙跳上一個n級的臺階總共有多少種跳法。
????這題考察的就是一個遞推的是個思想许饿。假設(shè)i表示青蛙要跳上的臺階阳欲，當(dāng)i==1時，只有一種方法陋率；當(dāng)i==2時球化，可以從上一個臺階，或上上一個臺階跳上去瓦糟，所有有兩種方式筒愚，從而可以知道，當(dāng)i > 1時菩浙，res = step1 + step2(這里的step1和step2分別表示跳到上一個臺階和跳到上上一個臺階的跳法)巢掺。
public class Solution {
public int JumpFloor(int target) {
if(target == 1)
return 1;
if(target == 2)
return 2;
int result = 0;
int step1 = 1, step2 = 1;
target -= 1;
while(target-- != 0) {
result = step1 + step2;
step1 = step2;
step2 = result;
}
return result;
}
}
第九題
一只青蛙一次可以跳上1級臺階扯再，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法址遇。
????這道題熄阻，最簡單最快速的方法，就是直接用排列組合去做倔约。把n個臺階分成1部分秃殉、2部分、3...n部分浸剩，c(N,0)+c(N,1)+...+C(N,N) = 2^N钾军。
public class Solution {
public int JumpFloorII(int target) {
return (int)Math.pow(2, target-1);
}
}
第十題
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形绢要，總共有多少種方法吏恭？
????這道題的思路其實(shí)和第八題非常類似，假設(shè)n=5重罪，我們可以看成n=3和n=4兩種情況樱哼，但是注意：n=3時，剩下2個小矩陣剿配，所以還可以排成2種搅幅，但是有其中一種（豎著排列的）會與n=3時候的重復(fù)，所以其實(shí)也只能排一種呼胚。所以我們可以知道：當(dāng) n==1時 res = 1茄唐；當(dāng)n==2時，res=2蝇更，當(dāng)n>2時沪编，res = cnt[n-1] + cnt[n-2]。
public class Solution {
public int RectCover(int target) {
if(target == 0)
return 0;
if(target == 1)
return 1;
if(target == 2)
return 2;
return RectCover(target-1) + RectCover(target-2);
}
}
