共67道捡硅，未完成47道
第1題：在二維數(shù)組中查找
這道題就屬于巧妙的利用了數(shù)組的特點，從一個特定點開始找起盗棵。
public class Solution {
public boolean Find(int target, int [][] array) {
int row = array.length;
int column = array[0].length;
int m = row - 1, n = 0;
while (m >= 0 && n < column) {
if (array[m][n] == target) {
return true;
} else if (array[m][n] > target) {
m--;
} else {
n++;
}
}
return false;
}
}
第2題：替換空格
請實現(xiàn)一個函數(shù)壮韭，將一個字符串中的每個空格替換成“%20”。例如纹因，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy喷屋。
- 最簡單的調(diào)用string的api
public String replaceSpace(StringBuffer str) {
return str.toString().replace(" ", "%20");
}
- 全部遍歷，遇到" "就追加"%20"
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
stringBuilder.append("%20");
} else {
stringBuilder.append(str.charAt(i));
}
}
return stringBuilder.toString();
}
}
第3題：從尾到頭打印鏈表
輸入一個鏈表瞭恰，按鏈表從尾到頭的順序返回一個ArrayList屯曹。
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack();
ArrayList arraylist = new ArrayList();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while (!stack.empty()) {
arraylist.add(stack.pop());
}
return arraylist;
}
}
這道題就非常的簡單了，需要注意的就是從尾到頭打印內(nèi)容惊畏，所以需要考慮到其對應(yīng)的數(shù)據(jù)結(jié)構(gòu)恶耽，就是棧。
棧常用的api有4 + 1個 因為search我?guī)缀跏遣挥玫?/p>
- 入棧：push()
- 出棧：pop()
- 返回棧頂元素：peek()
- 判斷棧是否為空：empty()
- 查找棧的元素：search()颜启，在就返回1偷俭，不在返回-1
第4題 重建二叉樹
第5題 用兩個棧來實現(xiàn)一個隊列
用兩個棧來實現(xiàn)一個隊列，完成隊列的Push和Pop操作缰盏。 隊列中的元素為int類型涌萤。
思考：毫無思路的就就是模擬進行考慮
總結(jié)：
- push的話就直接放到stack1中
- pop的話，先看stack2有沒有元素乳规，有的話就彈出形葬。沒有的話合呐，把所有的stack1中的元素放到stack2中暮的，然后stack2再出棧。
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
//這個寫的就不是很好淌实，return上都重復(fù)了冻辩，就進行一波重構(gòu)。
public int pop() {
if (!stack2.empty()) {
return stack2.pop();
} else {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
//上邊的方法寫的就不是很好拆祈，有重復(fù)的語句
public int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
第6題 旋轉(zhuǎn)數(shù)組中最小數(shù)字
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾恨闪，我們稱之為數(shù)組的旋轉(zhuǎn)。
輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)放坏，輸出旋轉(zhuǎn)數(shù)組的最小元素咙咽。
思考：
有三種情況
- 情況1，arr[mid] > target：4 5 6 1 2 3
- arr[mid] 為 6淤年， target為右端點 3钧敞， arr[mid] > target, 說明[first ... mid] 都是 >= target 的蜡豹，因為原始數(shù)組是非遞減，所以可以確定答案為 [mid+1...last]區(qū)間,所以 first = mid + 1
- 情況2秉犹，arr[mid] < target:5 6 1 2 3 4
- arr[mid] 為 1撵割， target為右端點 4斗幼， arr[mid] < target, 說明答案肯定不在[mid+1...last]，但是arr[mid] 有可能是答案,所以答案在[first, mid]區(qū)間娇唯，所以last = mid;
- 情況3，arr[mid] == target:
如果是 1 0 1 1 1寂玲， arr[mid] = target = 1, 顯然答案在左邊
如果是 1 1 1 0 1, arr[mid] = target = 1, 顯然答案在右邊
所以這種情況塔插，不能確定答案在左邊還是右邊，那么就讓last = last - 1;慢慢縮少區(qū)間拓哟，同時也不會錯過答案佑淀。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int i = 0, j = array.length - 1;
while (i < j) {
if (array[i] < array[j]) {
return array[i];
}
int mid = (i + j) >> 1;
if (array[mid] > array[i]) {
i = mid + 1;
} else if (array[mid] < array[i]) {
j = mid;
} else i++;
}
return array[i];
}
}
第7題 斐波那契數(shù)列
遞歸
public class Solution {
public int Fibonacci(int n) {
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
動態(tài)規(guī)劃
public class Solution {
public int Fibonacci(int n) {
int[] dp = new int[n + 2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
第8題 跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級彰檬。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結(jié)果）伸刃。
**思考：*這個題和上邊的那個題是一樣的，都是需要來寫一個公式逢倍，然后進行反推的捧颅。
public class Solution {
public int JumpFloor(int target) {
if (target == 1 || target == 2 || target == 0) return target;
int[] dp = new int[target + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= target; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[target];
}
}
第9題 變態(tài)跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級较雕。求該青蛙跳上一個n級的臺階總共有多少種跳法碉哑。
思考：這道題屬于有一些公式上的推導(dǎo)了，本身上也不是特別的有意思的呢亮蒋，不過這里邊有一個強轉(zhuǎn)扣典，我有段時間沒有寫，確實是忘記了的
public class Solution {
public int JumpFloorII(int target) {
if (target == 0 || target == 1) return 1;
return (int) Math.pow(2, target - 1);
}
}
第10題 矩陣覆蓋
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形慎玖。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形贮尖，總共有多少種方法？
思考：這個和上邊的情況基本上還是一樣的趁怔，不過這次使用一種特別的方法來寫一下
public class Solution {
public int RectCover(int target) {
if (target == 0 || target == 1 || target == 2) return target;
int a = 1, b = 2, c = 0;
for (int i = 3; i <= target; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
第11題 二進制中1的個數(shù)
輸入一個整數(shù)湿硝，輸出該數(shù)32位二進制表示中1的個數(shù)。其中負數(shù)用補碼表示润努。
思考：以后扯到了二進制关斜，就考慮使用位運算
- 與（AND，&）：全1為1铺浇，有0則0痢畜。
特殊情況&0，得到的就是0 - 或（OR，|）：有1則1丁稀，全0為0繁涂。
- 異或（XOR，^）：不同為1二驰，相同為0扔罪。
- 非（NOT，~）：取反桶雀。
在這道題里就是使用的有一個技巧
如果一個整數(shù)不為0矿酵，那么這個整數(shù)至少有一位是1。如果我們把這個整數(shù)減1矗积，那么原來處在整數(shù)最右邊的1就會變?yōu)?全肮，原來在1后面的所有的0都會變成1(如果最右邊的1后面還有0的話)。其余所有位將不會受到影響棘捣。
舉個例子：一個二進制數(shù)1100辜腺，從右邊數(shù)起第三位是處于最右邊的一個1。減去1后乍恐，第三位變成0评疗，它后面的兩位0變成了1，而前面的1保持不變茵烈，因此得到的結(jié)果是1011.我們發(fā)現(xiàn)減1的結(jié)果是把最右邊的一個1開始的所有位都取反了百匆。這個時候如果我們再把原來的整數(shù)和減去1之后的結(jié)果做與運算，從原來整數(shù)最右邊一個1那一位開始所有位都會變成0呜投。如1100&1011=1000.也就是說加匈，把一個整數(shù)減去1，再和原整數(shù)做與運算仑荐，會把該整數(shù)最右邊一個1變成0.那么一個整數(shù)的二進制有多少個1雕拼，就可以進行多少次這樣的操作。
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
第13題 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
輸入一個整數(shù)數(shù)組粘招，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序啥寇，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分男图，并保證奇數(shù)和奇數(shù)示姿，偶數(shù)和偶數(shù)之間的相對位置不變甜橱。
思考：這里邊用的是插入思想的方法
- 如果遇到偶數(shù)逊笆，j++
- 如果遇到奇數(shù),假設(shè)位置為j，就將此奇數(shù)插入到i所指的位置岂傲，然后i往后移動一個位置难裆，在插入之前，顯然會涉及到數(shù)據(jù)的移動，也就是將[i,j-1]整體往后移動乃戈。
- 直到整個數(shù)組遍歷完畢褂痰，結(jié)束
public class Solution {
public void reOrderArray(int [] array) {
int i = 0;
for (int j = 0; j < array.length; j++) {
if (array[j] % 2 == 1) {
int tmp = array[j];
for (int k = j - 1; k >= i; k--) {
array[k + 1] = array[k];
}
array[i] = tmp;
i++;
}
}
}
}
第14題 鏈表中倒數(shù)第k個節(jié)點
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點症虑。
思考：鏈表是不知道長度的缩歪，所以要么是先一次遍歷以后再二次遍歷，或者是使用快慢指針的方法谍憔，我就讓快指針比慢指針快k-1個身位匪蝙，就可以解決這個問題了。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode fast = head;
ListNode slow = head;
for (int i = 0; i < k; i++) {
if (fast == null) return null;
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
第15題 反轉(zhuǎn)列表
輸入一個鏈表习贫，反轉(zhuǎn)鏈表后逛球，輸出新鏈表的表頭。
思考：這里也是需要用兩個指針苫昌，一個是新的鏈表颤绕，一個要遍歷的鏈表。然后挨個節(jié)點祟身，指向輸出鏈表奥务，即可得到需要的內(nèi)容了。
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
第20題 包含min函數(shù)的棧
定義棧的數(shù)據(jù)結(jié)構(gòu)袜硫，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復(fù)雜度應(yīng)為O（1））汗洒。
思考：因為是要用O(1)來實現(xiàn)，所以使用一個輔助棧父款，來解決溢谤。但一定要讓兩個棧的數(shù)量是相等的，才能實現(xiàn)這個同進同出的效果憨攒。
import java.util.Stack;
public class Solution {
Stack<Integer> stackTotal = new Stack<Integer>();
Stack<Integer> stackMin = new Stack<Integer>();
public void push(int node) {
stackTotal.push(node);
if (stackMin.empty()) stackMin.push(node);
else {
if (node < stackMin.peek()) stackMin.push(node);
else stackMin.push(stackMin.peek());
}
}
public void pop() {
stackTotal.pop();
stackMin.pop();
}
public int top() {
return stackTotal.peek();
}
public int min() {
return stackMin.peek();
}
}
第21題 棧的壓入和退出
輸入兩個整數(shù)序列世杀，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序肝集。假設(shè)壓入棧的所有數(shù)字均不相等瞻坝。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列杏瞻，但4,3,5,1,2就不可能是該壓棧序列的彈出序列所刀。（注意：這兩個序列的長度是相等的）
思考：模擬法，新建一個棧捞挥，將數(shù)組A壓入棧中浮创，當(dāng)棧頂元素等于數(shù)組B時，就將其出棧砌函，當(dāng)循環(huán)結(jié)束時斩披，判斷棧是否為空溜族，若為空則返回true.
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int j = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while (!stack.empty() && stack.peek() == popA[j]) {
stack.pop();
j++;
}
}
return stack.empty();
}
}
第32題 把數(shù)組排成最小的數(shù)
輸入一個正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)垦沉，打印能拼接出的所有數(shù)字中最小的一個煌抒。例如輸入數(shù)組{3，32厕倍，321}寡壮，則打印出這三個數(shù)字能排成的最小數(shù)字為321323。
思考：這里邊用的是貪心算法讹弯，貪心算法就是在求局部最優(yōu)解诬像，從而逼近全局最優(yōu)解。這里的做法闸婴，就是先得到第一個和別人拼接后最小的值坏挠，以此類推，進行循環(huán)遍歷邪乍。在這里自定義一個比較大小的函數(shù)降狠，比較兩個字符串s1, s2大小的時候，先將它們拼接起來庇楞，比較s1+s2,和s2+s1那個大榜配，如果s1+s2大，那說明s2應(yīng)該放前面吕晌，所以按這個規(guī)則蛋褥，s2就應(yīng)該排在s1前面。
public class Solution {
public String PrintMinNumber(int [] numbers) {
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
int sum1 = Integer.valueOf(numbers[i] + "" + numbers[j]);
int sum2 = Integer.valueOf(numbers[j] + "" + numbers[i]);
if (sum1 > sum2) {
int temp = numbers[j];
numbers[j] = numbers[i];
numbers[i] = temp;
}
}
}
String answer = "";
for (int i = 0; i < numbers.length; i++) {
answer += numbers[i];
}
return answer;
}
}
第34題 第一個只出現(xiàn)一次的字符
在一個字符串(0<=字符串長度<=10000睛驳，全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置, 如果沒有則返回 -1（需要區(qū)分大小寫）.（從0開始計數(shù)）
思考：這個其實也沒啥的烙心，就是先用數(shù)組存一次，然后再遍歷一次乏沸，看看誰等于1
public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) return -1;
int[] tmp = new int[256];
for (int i = 0; i < str.length(); i++) {
tmp[str.charAt(i)]++;
}
for (int i = 0 ; i < str.length(); i++) {
if (tmp[str.charAt(i)] == 1) {
return i;
}
}
return -1;
}
}
第36題 兩個鏈表的第一個公共節(jié)點
輸入兩個鏈表淫茵，找出它們的第一個公共結(jié)點。（注意因為傳入數(shù)據(jù)是鏈表蹬跃，所以錯誤測試數(shù)據(jù)的提示是用其他方式顯示的匙瘪，保證傳入數(shù)據(jù)是正確的）
思考：設(shè)置a和b兩個指針，a走head1蝶缀，b走head2丹喻，走到盡頭了以后就再走另一個鏈表，這樣第一次重合的地方就是兩者第一個公共節(jié)點翁都。
//這個方法很簡單碍论，但是問題是如果兩個鏈表沒有交點就會死循環(huán)。
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while (p1 != p2) {
p1 = p1 != null ? p1.next : pHead2;
p2 = p2 != null ? p2.next : pHead1;
}
return p1;
}
}
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
//這個方法的問題是不加if判斷這一句就會死循環(huán)荐吵，我沒有搞懂
if (p1 != p2) {
if (p1 == null) p1 = pHead2;
if (p2 == null) p2 = pHead1;
}
}
return p1;
}
}
第37題 數(shù)字在升序數(shù)組中重現(xiàn)的次數(shù)
統(tǒng)計一個數(shù)字在升序數(shù)組中出現(xiàn)的次數(shù)骑冗。
思考：看到有序數(shù)組就考慮使用二分查找
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int lbound = 0, rbound = 0;
int left = 0, right = array.length;
int mid = 0;
while (left < right) {
mid = (left + right) >> 1;
if (array[mid] < k) left = mid + 1;
else right = mid;
}
lbound = left;
left = 0;
right = array.length;
while (left < right) {
mid = (left + right) >> 1;
if (array[mid] <= k) left = mid + 1;
else right = mid;
}
rbound = left;
return rbound - lbound;
}
}
總結(jié)：二分查找
- 尋找左側(cè)邊界的二分搜索
public int left_bound(int[] nums, int target) {
int left = 0; int right = nums.length; //因為就算是左邊界赊瞬，可能所有的數(shù)都比他小
int mid = 0;
while (left < right) { //這里是<
mid = left + (right - left) / 2;
if (nums[mid] < target) mid = left + 1;
//上邊沒有判斷等號情況先煎，而是在這里進行判斷的贼涩，因為這個“=”不一定就是最左側(cè)的，還需要繼續(xù)逼近
else mid = right;
}
return nums[left] == target ? left : -1;
}
- 尋找右側(cè)邊界的二分搜索
public int right_bound(int[] nums, int target) {
int left = 0; int right = nums.length; //因為就算是左邊界薯蝎，可能所有的數(shù)都比他小
int mid = 0;
while (left < right) { //這里是<
mid = left + (right - left) / 2;
//left的指向的位置本身就是要最右側(cè)的右一個遥倦，所以相等了，可以繼續(xù)逼近的
if (nums[mid] <= target) mid = left + 1;
else mid = right;
}
//這里返回的是最右側(cè)的值
return nums[left] == target ? left - 1 : -1;
}
第42題 和為s的兩個數(shù)字
輸入一個遞增排序的數(shù)組和一個數(shù)字S占锯，在數(shù)組中查找兩個數(shù)袒哥，使得他們的和正好是S，如果有多對數(shù)字的和等于S消略，輸出兩個數(shù)的乘積最小的堡称。
思考：最外圍的情況時才是兩個數(shù)的乘積是最小的。所以設(shè)置兩個指針左右逼夾就好了艺演。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
int left = 0;
int right = array.length - 1;
int tmp = 0;
while (left < right) {
tmp = array[left] + array[right];
if (tmp == sum) {
list.add(array[left]);
list.add(array[right]);
return list;
} else if (tmp > sum) right--;
else left++;
}
return list;
}
}
第43題 左旋字符串
匯編語言中有一種移位指令叫做循環(huán)左移（ROL）却紧，現(xiàn)在有個簡單的任務(wù)，就是用字符串模擬這個指令的運算結(jié)果胎撤。對于一個給定的字符序列S晓殊，請你把其循環(huán)左移K位后的序列輸出。例如伤提，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果巫俺，即“XYZdefabc”。是不是很簡單肿男？OK介汹，搞定它
思考：這個題就很簡單的了，拼接字符串就可以了
public class Solution {
public String LeftRotateString(String str,int n) {
// 這里圖省事了舶沛，n要是大于字符串的長度痴昧，應(yīng)該是做一個除模處理的
if (str == null || n > str.length()) {
return str;
}
//substring(pos):表示開始位置，一直截取完
//substring(begin, end):從begin截取到end冠王，左閉右開的格式
return str.substring(n) + str.substring(0, n);
}
}
別人的方法
public:
string LeftRotateString(string str, int n) {
int len = str.length();
if(len == 0) return "";
n = n % len;
str += str;
return str.substr(n, len + n);
}
};
第44題 翻轉(zhuǎn)單詞順序
鸥献客最近來了一個新員工Fish，每天早晨總是會拿著一本英文雜志柱彻，寫些句子在本子上豪娜。同事Cat對Fish寫的內(nèi)容頗感興趣，有一天他向Fish借來翻看哟楷，但卻讀不懂它的意思瘤载。例如，“student. a am I”卖擅。后來才意識到鸣奔，這家伙原來把句子單詞的順序翻轉(zhuǎn)了墨技，正確的句子應(yīng)該是“I am a student.”。Cat對一一的翻轉(zhuǎn)這些單詞順序可不在行挎狸，你能幫助他么扣汪？
思考：就也沒啥的，分割以后裝進去唄锨匆。
public String ReverseSentence(String str) {
if (str.trim().equals("")) return str;
String[] tmp = str.split(" ");
StringBuffer answer = new StringBuffer();
for (int i = tmp.length - 1; i >= 0; i--) {
answer.append(tmp[i]);
if (i != 0) answer.append(" ");
}
return answer.toString();
}
第46題 孩子們的游戲（圓圈中最后剩下的孩子）
每年六一兒童節(jié),耪副穑客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為趴致啵客的資深元老,自然也準備了一些小游戲茅主。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)土榴。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續(xù)0...m-1報數(shù)....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到啪饕Γ客名貴的“名偵探柯南”典藏版(名額有限哦!!_)。請你試著想下,哪個小朋友會得到這份禮品呢玷禽？(注：小朋友的編號是從0到n-1)
第50題
第55題 鏈表中環(huán)的入口位置
給一個鏈表赫段，若其中包含環(huán)，請找出該鏈表的環(huán)的入口結(jié)點论衍，否則瑞佩，輸出null。
思考：快慢指針解決
