##節選劍指offer比較經典和巧妙的一些題目，以便複習使用。一部分題目給出了完整代碼，一部分題目比較簡單直接給出思路。但是不保證我說的思路都是正确的，個人對算法也不是特别在行，隻不過這本書的算法多看了幾遍多做了幾遍多了點心得體會。于是想總結一下。如果有錯誤也希望能指出，謝謝。
#具體代碼可以參考我的GitHub倉庫：
#https://github.com/h2pl/SwordToOffer
數論和數字規律
從1到n整數中1出現的次數
題目描述
求出113的整數中1出現的次數,并算出1001300的整數中1出現的次數？為此他特别數了一下1~13中包含1的數字有1、10、11、12、13是以共出現6次,但是對于後面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數。
1暴力辦法，把整數轉為字元串，依次枚舉相加。複雜度是O（N * k）k為數字長度。
2第二種辦法看不懂，需要數學推導，太長不看
排數組排成最小的數
輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則列印出這三個數字能排成的最小數字為321323。
解析：本題的關鍵是，兩個數如何排成最小的，答案是，如果把數字看成字元串a,b那麼如果a+b>b+a，則a應該放在b後面。
例如 3和32 3 + 32 = 332,32 + 3 = 323,332>323,是以32要放在前面。
根據這個規律，構造一個比較器，使用排序方法即可。
醜數
把隻包含因子2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但14不是，因為它包含因子7。 習慣上我們把1當做是第一個醜數。求按從小到大的順序的第N個醜數。
解析
1 暴力枚舉每個醜數，找出第N個即可。
2 這個思路比較巧妙，由于醜數一定是由2,3,5三個因子構成的，是以我們每次構造出一個比前面醜數大但是比後面小的醜數，構造N次即可。
public class Solution {
public static int GetUglyNumber_Solution(int index) {
if (index == 0) return 0;
int []res = new int[index];
res[0] = 1;
int i2,i3,i5;
i2 = i3 = i5 = 0;
for (int i = 1;i < index;i ++) {
res[i] = Math.min(res[i2] * 2, Math.min(res[i3] * 3, res[i5] * 5));
if (res[i] == res[i2] * 2) i2 ++;
if (res[i] == res[i3] * 3) i3 ++;
if (res[i] == res[i5] * 5) i5 ++;
}
return res[index - 1];
}
}
}
i2,i3,i5分别代表目前有幾個2,3,5的因子，每次選一個最小的醜數，然後開始找下一個。當然i2，i3，i5也要跟着變。
數組和矩陣
二維數組的查找
/**
* Created by 周傑倫 on 2018/2/25.
* 題目描述
在一個二維數組中，每一行都按照從左到右遞增的順序排序，
每一列都按照從上到下遞增的順序排序。請完成一個函數，
輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
1 2 3
2 3 4
3 4 5
*/
解析：比較經典的一題，解法也比較巧妙，由于數組從左向右和從上到下的都是遞增的，是以找一個數可以先從最右開始找。
假設最右值為a，待查數為x，那麼如果x < a說明x在a的左邊，往左找即可，如果x > a，說明x 在 a的下面一行，到下面一行繼續按照該規則查找，就可以周遊所有數。
算法的時間複雜度是O(M * N)
public class 二維數組中的查找 {
public static boolean Find(int target, int[][] array) {
if(array[0][0] > target) {
return false;
}
int row = 0;
int col = 0;
while (row < array.length && col >0) {
if (target == array[row][col]) {
return true;
}
else if (target <array[row][col]) {
col --;
}
else if (target > array[row][col]) {
col ++;
}
else row++;
}
return false;
}
}
順時針列印矩陣。
輸入一個矩陣，按照從外向裡以順時針的順序依次列印出每一個數字，例如，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次列印出數字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
這題還是有點麻煩的，因為要順時針列印，是以實際上是由外向内列印，邊界的處理和遞歸調用需要謹慎。
這題我自己沒寫出标準答案。參考一個答案吧。關鍵在于四個循環中的分界點設定。
//主體循環部分才5行。其實是有規律可循的。将每一層的四個邊角搞清楚就可以列印出來了
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] array) {
ArrayList<Integer> result = new ArrayList<Integer> ();
if(array.length==0) return result;
int n = array.length,m = array[0].length;
if(m==0) return result;
int layers = (Math.min(n,m)-1)/2+1;//這個是層數
for(int i=0;i<layers;i++){
for(int k = i;k<m-i;k++) result.add(array[i][k]);//左至右
for(int j=i+1;j<n-i;j++) result.add(array[j][m-i-1]);//右上至右下
for(int k=m-i-2;(k>=i)&&(n-i-1!=i);k--) result.add(array[n-i-1][k]);//右至左
for(int j=n-i-2;(j>i)&&(m-i-1!=i);j--) result.add(array[j][i]);//左下至左上
}
return result;
}
}
調整數組中數字的順序，使正數在負數的前面
雙指針即可以解決，變式有正負，奇偶等等。
數組中出現次數超過一半的數字
本題有很多種解法。
1 最笨的解法，統計每個數的出現次數，O（n2)
2 使用hashmap，空間換時間O（n)
3 由于出現超過一半的數字一定也是中位數，是以可以先排序，再找到第n/2位置上的節點。
4 使用快速排序的複雜度是O（nlogn)，基于快排的特性，每一輪的過程都會把一個數放到最終位置，是以我們可以判斷一下這個數的位置是不是n/2，如果是的話，那麼就直接傳回即可。這樣就優化了快排的步驟。
4.5事實上，上述辦法的複雜度仍然是O（nlogn）
快速排序的partition函數将一個數組分為左右兩邊，并且我們可以知道，如果flag值在k位置左邊，那麼往左找，如果在k位置右邊，那麼往左找。
這裡科普一下經典快排中的一個方法partition，劍指offer書中直接跳過了這部分，讓我摸不着頭腦。
雖然快排用到了經典的分而治之的思想，但是快排實作的前提還是在于 partition 函數。正是有了 partition 的存在，才使得可以将整個大問題進行劃分，進而分别進行處理。
除了用來進行快速排序，partition 還可以用 O(N) 的平均時間複雜度從無序數組中尋找第K大的值。和快排一樣，這裡也用到了分而治之的思想。首先用 partition 将數組分為兩部分，得到分界點下标 pos，然後分三種情況：
pos == k-1，則找到第 K 大的值，arr[pos]；
pos > k-1，則第 K 大的值在左邊部分的數組。
pos < k-1，則第 K 大的值在右邊部分的數組。
下面給出基于疊代的實作（用來尋找第 K 小的數）：
int find_kth_number(vector<int> &arr, int k){
int begin = 0, end = arr.size();
assert(k>0 && k<=end);
int target_num = 0;
while (begin < end){
int pos = partition(arr, begin, end);
if(pos == k-1){
target_num = arr[pos];
break;
}
else if(pos > k-1){
end = pos;
}
else{
begin = pos + 1;
}
}
return target_num;
}
該算法的時間複雜度是多少呢？考慮最壞情況下，每次 partition 将數組分為長度為 N-1 和 1 的兩部分，然後在長的一邊繼續尋找第 K 大，此時時間複雜度為 O(N^2 )。不過如果在開始之前将數組進行随機打亂，那麼可以盡量避免最壞情況的出現。而在最好情況下，每次将數組均分為長度相同的兩半，運作時間 T(N) = N + T(N/2)，時間複雜度是 O(N)。
是以也就是說，本題用這個方法解的話，複雜度隻需要O（n),因為第一次交換需要N/2,j接下來的交換的次數越來越少，最後加起來就是O（N）了。
5 由于數字出現次數超過長度的一半，也就是平均每兩個數字就有一個該數字，但他們不一定連續，是以變量time儲存一個數的出現次數，然後變量x代表目前選擇的數字，周遊中，如果x與後一位不相等則time–，time=0時x改為後一位，time重新變為1。最終x指向的數字就是出現次數最多的。
舉兩個例子，比如1,2,3,4,5,6,6,6,6,6,6。明顯符合。1,6,2,6,3,6,4,6,5,6,6 周遊到最後得到x=6，以此類推，可以滿足要求。
找出前k小的數
-
輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。
*/
解析：
1如果允許改變數組，那麼則可以繼承上一題的思想。，使用快速排序中的partition方法，隻需要O（N）的複雜度
2使用堆排序
解析：用前k個數構造一個大小為k的大頂堆，然後周遊餘下數字，如果比堆頂大，則跳過，如果比堆頂小，則替換掉堆頂元素，然後執行一次堆排序（即根節點向下調整)。此時的堆頂元素已被替換，
然後周遊完所有元素，堆中的元素就是最小的k個元素了。
如果要求最大的k個元素，則構造小頂堆就可以了。
構造堆的方法是，數組的第N/2号元素到0号元素依次向下調整，此時數組就構成了堆。
實際上我們可以使用現成的集合類，紅黑樹是一棵搜尋樹，他是排序的，是以可以得到最大和最小值，那麼我們每次和最小值比較，符合條件就進行替換即可。複雜度是O（nlogn)
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer>arrayList=new ArrayList<>();
if(input==null || input.length==0 ||k==0 ||k>input.length)return arrayList;
TreeSet<Integer> treeSet=new TreeSet<>();
for(int i=0;i<input.length;i++){
if(treeSet.size()<k){
treeSet.add(input[i]);
}
else {
if(input[i]<treeSet.last()){
treeSet.pollLast();
treeSet.add(input[i]);
}
}
}
for(Integer x:treeSet){
arrayList.add(x);
}
return arrayList;
}
連續子數組的最大和
**
- Created by 周傑倫 on 2017/3/23.
-
HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。
今天測試組開完會後,他又發話了:在古老的一維模式識别中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。
但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？
例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。
你會不會被他忽悠住？(子向量的長度至少是1)
解析：笨辦法需要O（n2）的複雜度。
1 但是實際上隻需要
一次周遊即可解決。通過sum儲存目前和，然後如果目前和為正，那麼繼續往後加，如果目前和為負，則直接丢棄，令目前和等于一個新值。并且每一步都要比較目前和與最大值。
*/
public class 連續數字序列的最大和 {
public int FindGreatestSumOfSubArray(int[] array) {
if(array==null || array.length==0)return 0;
int sum=0;int max=array[0];
for(int i=0;i<array.length;i++){
//如果目前和<0，那就不加，直接賦新值
if(sum<=0){
sum=array[i];
}//如果目前和大于零，則繼續加。
else {
sum+=array[i];
}
if(max<sum){
max=sum;
}
}
return max;
}
2 本題也可以使用DP解法
DP數組代表以i為結尾元素的連續最大和
DP[i] = arr[i] (DP[i-1] < 0)
= DP[i] + arr[i] (DP[i -1] > 0)
逆序對
/**
-
在數組中的兩個數字，如果前面一個數字大于後面的數字，則這兩個數字組成一個逆序對。
輸入一個數組,求出這個數組中的逆序對的總數P。并将P對1000000007取模的結果輸出。
即輸出P%1000000007
解析：本題采用歸并排序的架構，隻是在歸并的時候做出逆序對查找，具體參見下面代碼。
核心點是，在歸并兩個有序數組時，如果a數組的元素a1比b數組的元素b1大時，說明有mid - i + 1個數都比b1大。i為a1元素的位置。
這樣子我們就可以統計逆序對的個數了。經典巧妙。！
public class 逆序對 {
public double Pairs = 0;
public int InversePairs(int [] array) {
if (array.length0 ||arraynull)
return 0;
mergesort(array,0,array.length-1);
Pairs = Pairs + 1000000007;
return (int) (Pairs % 1000000007);
}
public void merge(int []array,int left,int mid,int right){
//有一點很重要的是，歸并分成兩部分，其中一段是left到mid，第二段是mid+1到right。
//不能從0到mid-1，然後mid到right。因為這樣左右不均分，會出錯。千萬注意。
//mid=(left+right)/2
if (array.length0 ||arraynull ||left>=right)
return ;
int p=left,q=mid+1,k=0;
int []temp=new int[right-left+1]; while (p<=mid && q<=right){ if(array[p]>array[q]){ temp[k++]=array[q++]; //目前半數組中有一個數p比後半個數組中的一個數q大時，由于兩個數組 //已經分别有序，是以說明p到中間數之間的所有數都比q大。 Pairs+=mid-p+1; } else temp[k++]=array[p++]; } while (p<=mid){ temp[k++]=array[p++];} while (q<=right){ temp[k++]=array[q++];} for (int m = 0; m < temp.length; m++) array[left + m] = temp[m]; } public void mergesort(int []arr,int left,int right){ if (arr.length==0 ||arr==null) return ; int mid=(right+left)/2; if(left<right) { mergesort(arr, left, mid); mergesort(arr, mid + 1, right); merge(arr, left,mid, right); } }
數字在排序數組中出現的次數
1 順序掃描
魯迅說過：看到排序數組要想到二分法！
2 通過二分查找找到數字k第一次出現的位置，即先比較k和中間值，再依次二分，如果中間值等于k并且中間值左邊！=k，則是第一個k。
反之可以找到最後一次出現k的位置。然後相減即可。複雜度是logn
和為s的兩個整數，和為s的連續正數序列
1 和為s的兩個整數，雙指針周遊即可
2 和為s的連續正數序列。維護一個範圍，start到end表示目前的數字序列。大于S則start++,小于S則start–
n個色子的點數
求n個色子點數之和等于s的機率
1 遞歸實作
2 循環實作，所有可能值存成一個數組，大小為6n，然後把每個出現數字次數存入數組，周遊一遍即可得到機率。
撲克牌的順子
LL今天心情特别好,因為他去買了一副撲克牌,發現裡面居然有2個大王,2個小王(一副牌原本是54張_)…他随機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子…LL不高興了,他想了想,決定大\小 王可以看成任何數字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL決定去買體育彩票啦。 現在,要求你使用這幅牌模拟上面的過程,然後告訴我們LL的運氣如何。為了友善起見,你可以認為大小王是0。
把撲克牌存到數組中，并且A看作1,J為11,Q為12,K為13，然後進行排序，如果有不連續的數字，不存在順子，如果都連續，則是順子
Arrays.sort(arr);
for (int i = 1 ;i < arr.length;i ++) {
if (arr[i] == arr[i - 1]) {
return false;
}
if (arr[i] - arr[i - 1] == 1) {
continue;
}else if (arr[i] - arr[i - 1] - 1 <= cnt) {
cnt -= arr[i] - arr[i - 1] - 1;
}else {
return false;
}
}
return true;
}
數組中重複的數字
在一個長度為n的數組裡的所有數字都在0到n-1的範圍内。 數組中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出數組中任意一個重複的數字。 例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那麼對應的輸出是第一個重複的數字2。
解析：一般使用hashmap即可達到O（n)
但劍指offer的解法可以隻用O(1)的空間做到。
實際上當每個數字a和他們所在的位置n相同時，每個數字隻出現一次，但如果n + 1的位置上的數也是a，那麼a就是第一個重複出現的數字。
根據這個思路。我們在循環中當第i個數a與arr[a]相等時，不變，如果不相等，則兩者互換，然後開始下一輪周遊。接下來繼續交換，如果出現相等的情況，則就是第一個重複出現的數。
舉例 2 3 1 0 2 5 3
1 arr[0] = 2 != 0,是以arr[0]與arr[2]做交換，得1 3 2 0 2 5 3
2 arr[0] = 1 != 0，是以arr[0]和arr[1]交換，的3 1 2 0 2 5 3
3 arr[0] = 3 != 0,是以arr[0]和arr[3]交換，得0 1 2 3 2 5 3
4 arr[0]到arr[3]都符合要求,arr[4] = 2 != 4，是以arr[4]和arr[2]交換，發現兩者相等，是以他就是第一個重複的數。
public boolean duplicate(int array[],int length,int [] duplication) {
if ( array==null ) return false;
// key step
for( int i=0; i<length; i++ ){
while( i!=array[i] ){
if ( array[i] == array[array[i]] ) {
duplication[0] = array[i];
return true;
}
int temp = array[i];
array[i] = array[array[i]];
array[array[i]] = temp;
}
}
return false;
}
從上述例子可以看到，一個數最多被交換兩次。是以複雜度為O（N)
建構乘積數組
給定一個數組A[0,1,…,n-1],請建構一個數組B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。
不能用除法，那麼就兩個循環，一個從0乘到i - 1，一個從i + 1乘到n-1
資料流的中位數
如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值。如果從資料流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。
解析，與字元流第一個不重複的字元類似，每次添加數字都要輸出一次結果。
public class Solution {
static ArrayList<Integer> list = new ArrayList<>();
public static void Insert(Integer num) {
list.add(num);
Collections.sort(list);
}
public static Double GetMedian() {
if (list.size() % 2 == 0) {
int l = list.get(list.size()/2);
int r = list.get(list.size()/2 - 1);
return (l + r)/2.0;
}
else {
return list.get(list.size()/2)/1.0;
}
}
}
滑動視窗中的最大值
給定一個數組和滑動視窗的大小，找出所有滑動視窗裡數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動視窗的大小3，那麼一共存在6個滑動視窗，他們的最大值分别為{4,4,6,6,6,5}； 針對數組{2,3,4,2,6,2,5,1}的滑動視窗有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
1 保持視窗為3進行右移，每次計算出一個最大值即可。
2 使用兩個棧實作一個隊列，複雜度O（N）,使用兩個棧實作最大值棧，複雜度O（1）。兩者結合可以完成本題。但是太麻煩了。
3 使用雙端隊列解決該問題。
import java.util.*;
/**
用一個雙端隊列，隊列第一個位置（隊頭）儲存目前視窗的最大值，當視窗滑動一次
1.判斷目前最大值是否過期（如果最大值所在的下标已經不在視窗範圍内，則過期）
2.對于一個新加入的值，首先一定要先放入隊列，即使他比隊頭元素小，因為隊頭元素可能過期。
3.新增加的值從隊尾開始比較，把所有比他小的值丢掉(因為隊列隻存最大值，是以之前比他小的可以丢掉)
*/
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> res = new ArrayList<>();
if(size == 0) return res;
int begin;
ArrayDeque<Integer> q = new ArrayDeque<>();
for(int i = 0; i < num.length; i++){
begin = i - size + 1;
if(q.isEmpty())
q.add(i);
else if(begin > q.peekFirst())
q.pollFirst();
while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
q.pollLast();
q.add(i);
if(begin >= 0)
res.add(num[q.peekFirst()]);
}
return res;
}
}
字元串
字元串的排列
輸入一個字元串,按字典序列印出該字元串中字元的所有排列。例如輸入字元串abc,則列印出由字元a,b,c所能排列出來的所有字元串abc,acb,bac,bca,cab和cba。
解析：這是一個全排列問題，也就是N個不同的數排成所有不同的序列，隻不過把數換成了字元串。
全排列的過程就是，第一個元素與後續的某個元素交換，然後第二個元素也這麼做，直到最後一個元素為之，過程是一個遞歸的過程，也是一個dfs的過程。
注意元素也要和自己做一次交換，要不然會漏掉自己作為頭部的情況。
然後再進行一次字典序的排序即可。
public static ArrayList<String> Permutation(String str) {
char []arr = str.toCharArray();
List<char []> list = new ArrayList<>();
all(arr, 0, arr.length - 1, list);
Collections.sort(list, (o1, o2) -> String.valueOf(o1).compareTo(String.valueOf(o2)));
ArrayList<String> res = new ArrayList<>();
for (char[] c : list) {
if (!res.contains(String.valueOf(c)))
res.add(String.valueOf(c));
}
return res;
}
//注意要換完為之，因為每換一次可以去掉頭部一個數字，這樣可以避免重複
public static void all(char []arr, int cur, int end, List<char[]> list) {
if (cur == end) {
// System.out.println(Arrays.toString(arr));
list.add(Arrays.copyOf(arr, arr.length));
}
for (int i = cur;i <= end;i ++) {
//這裡的交換包括跟自己換，是以隻有一輪換完才能确定一個結果
swap(arr, cur, i);
all(arr, cur + 1, end, list);
swap(arr, cur, i);
}
}
public static void swap(char []arr, int i, int j) {
if (i > arr.length || j > arr.length || i >= j)return;
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
替換空格
/**
* Created by 周傑倫 on 2018/2/25.
* 請實作一個函數，将一個字元串中的空格替換成“%20”。例如，當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy。
*/
解析：如果單純地按順序替換空格，每次替換完還要将數組擴容，再右移，這部操作的時間複雜度就是O（2*N）=O（N)，是以總的複雜度是O（n^2)，是以應該采取先擴容的辦法，統計出空格數，然後擴容，接下來按順序添加字元，遇到空格直接改成添加%20即可，這樣避免了右移操作和多次擴容，複雜度是O（N)
public class 替換空格 {
public static String replaceSpace(StringBuffer str) {
int newlen = 0;
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i) == ' ') {
newlen = newlen + 3;
}
else {
newlen ++;
}
}
char []newstr = new char[newlen];
int j = 0;
for(int i = 0 ; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
newstr[j++] = '%';
newstr[j++] = '2';
newstr[j++] = '0';
}else {
newstr[j++] = str.charAt(i);
}
}
return String.valueOf(newstr);
}
第一次隻出現一次的字元
哈希表可解
翻轉單詞順序和左旋轉字元串
1
牛客最近來了一個新員工Fish，每天早晨總是會拿着一本英文雜志，寫些句子在本子上。同僚Cat對Fish寫的内容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。例如，“student. a am I”。後來才意識到，這家夥原來把句子單詞的順序翻轉了，正确的句子應該是“I am a student.”。Cat對一一的翻轉這些單詞順序可不在行，你能幫助他麼？
這個解法很經典，先把每個單詞逆序，再把整個字元串逆序，結果就是把每個單詞都進行了翻轉。
2
彙編語言中有一種移位指令叫做循環左移（ROL），現在有個簡單的任務，就是用字元串模拟這個指令的運算結果。對于一個給定的字元序列S，請你把其循環左移K位後的序列輸出。例如，字元序列S=”abcXYZdef”,要求輸出循環左移3位後的結果，即“XYZdefabc”。是不是很簡單？OK，搞定它！
字元串循環左移N位的處理方法也很經典，先把前N位逆序，再把剩餘字元串逆序，最後整體逆序。
abcXYZdef -> cbafedZYX -> XYZdefabc
把字元串轉換為整數
将一個字元串轉換成一個整數，要求不能使用字元串轉換整數的庫函數。 數值為0或者字元串不是一個合法的數值則傳回0
解析：首先需要判斷正負号，然後判斷每一位是否是數字，然後判斷是否溢出，判斷溢出可以通過加完第n位的和與未加第n位的和進行比較。最後可以得出結果。是以需要3-4步判斷。
表示數值的字元串
請實作一個函數用來判斷字元串是否表示數值（包括整數和小數）。例如，字元串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示數值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。
不得不說這種題型太惡心了，就是需要一直判斷邊界條件
參考一個答案。比較完整
bool isNumeric(char* str) {
// 标記符号、小數點、e是否出現過
bool sign = false, decimal = false, hasE = false;
for (int i = 0; i < strlen(str); i++) {
if (str[i] == 'e' || str[i] == 'E') {
if (i == strlen(str)-1) return false; // e後面一定要接數字
if (hasE) return false; // 不能同時存在兩個e
hasE = true;
} else if (str[i] == '+' || str[i] == '-') {
// 第二次出現+-符号，則必須緊接在e之後
if (sign && str[i-1] != 'e' && str[i-1] != 'E') return false;
// 第一次出現+-符号，且不是在字元串開頭，則也必須緊接在e之後
if (!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E') return false;
sign = true;
} else if (str[i] == '.') {
// e後面不能接小數點，小數點不能出現兩次
if (hasE || decimal) return false;
decimal = true;
} else if (str[i] < '0' || str[i] > '9') // 不合法字元
return false;
}
return true;
}
字元流中第一個不重複的字元
請實作一個函數用來找出字元流中第一個隻出現一次的字元。例如，當從字元流中隻讀出前兩個字元"go"時，第一個隻出現一次的字元是"g"。當從該字元流中讀出前六個字元“google"時，第一個隻出現一次的字元是"l"。
本題主要要注意的是流。也就是說每次輸入一個字元就要做一次判斷。比如輸入aaaabbbcd，輸出就是a###b##cd
StringBuilder sb = new StringBuilder();
int []map = new int[256];
public void Insert(char ch)
{
sb.append(ch);
if (map[ch] == 0) {
map[ch] = 1;
}else {
map[ch] ++;
}
System.out.println(FirstAppearingOnce());
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
for (int i = 0;i < sb.length();i ++) {
if (map[sb.charAt(i)] == 1) {
return sb.charAt(i);
}
}
return '#';
}
連結清單
從尾到頭列印連結清單
考查遞歸，遞歸可以使輸出的順序倒置
public static void printReverse(Node node) {
if (node.next != null) {
printReverse(node.next);
}
System.out.print(node.val + " ");
}
連結清單倒數第k個節點
使用兩個指針，一個先走k步。然後一起走即可。
反轉連結清單
老生常談，但是容易寫錯。
public ListNode ReverseList(ListNode head) {
if(head==null || head.next==null)return head;
ListNode pre,next;
pre=null;
next=null;
while(head!=null){
//儲存下一個結點
next=head.next;
//連接配接下一個結點
head.next=pre;
pre=head;
head=next;
}
return pre;
}
}
合并兩個排序連結清單
與歸并排序的合并類似
複雜連結清單的複制
輸入一個複雜連結清單（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），傳回結果為複制後複雜連結清單的head。（注意，輸出結果中請不要傳回參數中的節點引用，否則判題程式會直接傳回空）
這題比較惡心。
1 直接複制連結清單，然後再去複制特殊指針，複雜度是O(n2)
2 使用hash表儲存特殊指針的映射關系，第二步簡化操作，複雜度是O（n）
3 複制每個節點并且連成一個大連結清單A-A’-B-B’，然後從頭到尾判斷特殊指針，如果有特殊指針，則讓後續節點的特殊指針指向原節點特殊指針指向的節點的後置節點，暈了吧，其實就是原來是A指向B，現在是A’指向B‘。
最後我們根據奇偶序号把連結清單拆開，複雜度是O（N)且不用額外空間。
兩個連結清單的第一個公共節點
1 逆置連結清單，反向找第一個不同節點，前一個就是公共節點
2 求長度并相減得n，短的連結清單先走n步，然後一起走即可。
孩子們的遊戲(圓圈中最後剩下的數)
這是一個約瑟夫環問題。
1 使用循環連結清單求解，每次走n步摘取一個節點，然後繼續，直到最後一個節點就是剩下的數，空間複雜度為O（n)
2 使用數組來做
public static int LastRemaining_Solution(int n, int m) {
int []arr = new int[n];
for (int i = 0;i < n;i ++) {
arr[i] = i;
int cnt = 0;
int sum = 0;
for (int i = 0;i < n;i = (i + 1) % n) {
if (arr[i] == -1) {
continue;
}
cnt ++;
if (cnt == m) {
arr[i] = -1;
cnt = 0;
sum ++;
}
if (sum == n) {
return i;
}
}
return n - 1;
}
3 使用餘數法求解
int LastRemaining_Solution(int n, int m) {
if (m == 0 || n == 0) {
return -1;
}
ArrayList<Integer> data = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
data.add(i);
}
int index = -1;
while (data.size() > 1) {
// System.out.println(data);
index = (index + m) % data.size();
// System.out.println(data.get(index));
data.remove(index);
index--;
}
return data.get(0);
}
連結清單的環的入口結點
一個連結清單中包含環，請找出該連結清單的環的入口結點。
1 指定兩個指針，一個一次走兩步，一個一次走一步，然後當兩個節點相遇時，這個節點必定在環中。既然這個節點在環中，那麼讓這個節點走一圈直到與自己相等為之，可以得到環的長度n。
2 得到了環的長度以後，根據數學推導的結果，我們可以指定兩個指針，一個先走n步，然後兩者同時走，這樣的話，當慢節點到達入口節點時，快節點也轉了一圈剛好又到達入口節點，是以也就是他們相等的時候就是入口節點了。
删除連結清單中重複的節點
在一個排序的連結清單中，存在重複的結點，請删除該連結清單中重複的結點，重複的結點不保留，傳回連結清單頭指針。 例如，連結清單1->2->3->3->4->4->5 處理後為 1->2->5
保留頭結點，然後找到下一個不重複的節點，與他相連，重複的節點直接跳過即可。
#二叉樹
二叉搜尋樹轉換為雙向連結清單
輸入一棵二叉搜尋樹，将該二叉搜尋樹轉換成一個排序的雙向連結清單。要求不能建立任何新的結點，隻能調整樹中結點指針的指向。
二叉搜尋樹要轉換成有序的雙向連結清單，實際上就是使用中序周遊把節點連傳入連結表中，并且題目要求在原來節點上進行操作，也就是使用左指針和右指針表示連結清單的前置節點和後置節點。
使用棧實作中序周遊的非遞歸算法，便可以找出節點的先後關系，依次連接配接即可。
public TreeNode Convert(TreeNode root) {
if(root==null)
return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
TreeNode pre = null;// 用于儲存中序周遊序列的上一節點
boolean isFirst = true;
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p = p.left;
}
p = stack.pop();
if(isFirst){
root = p;// 将中序周遊序列中的第一個節點記為root
pre = root;
isFirst = false;
}else{
pre.right = p;
p.left = pre;
pre = p;
}
p = p.right;
}
return root;
}
}
重建二叉樹
* 題目描述
輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。
*/
解析：首先，頭結點一定是先序周遊的首位，并且該節點把中序分為左右子樹，根據這個規則，左子樹由左邊數組來完成，右子樹由右邊數組來完成，根節點由中間節點來建構，于是便有了如下的遞歸代碼。該題的難點就在于邊界的判斷。
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
if(pre.length == 0||in.length == 0){
return null;
}
TreeNode node = new TreeNode(pre[0]);
for(int i = 0; i < in.length; i++){
if(pre[0] == in[i]){
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));//為什麼不是i和i-1呢，因為要避免出錯，中序找的元素需要再用一次。
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
}
}
return node;
}
樹的子結構
/**
* Created by 周傑倫 on 2018/3/27.
* 輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
*/
解析：本題還是有點難度的，子結構要求節點完全相同，是以先判斷節點是否相同，然後使用先序周遊進行遞判斷，判斷的依據是如果子樹為空，則說明節點都找到了，如果原樹節點為空，說明找不到對應節點,接着遞歸地判斷該節點的左右子樹是否符合要求.
public class 樹的子結構 {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
boolean res = false;
if (root1 != null && root2 != null) {
if (root1.val == root2.val) {
res = aHasb(root1, root2);
}
if (res == false) {
res = HasSubtree(root1.left,root2);
}
if (res == false) {
res = HasSubtree(root1.right,root2);
}
return res;
}
else return false;
}
public boolean aHasb(TreeNode t1, TreeNode t2){
if (t2 == null) return true;
if (t1 == null) return false;
if (t1.val != t2.val) return false;
return aHasb(t1.left,t2.left) && aHasb(t1.right,t2.right);
}
}
鏡像二叉樹
/**
* Created by 周傑倫 on 2017/3/19.操作給定的二叉樹，将其變換為源二叉樹的鏡像。
輸入描述:
二叉樹的鏡像定義：源二叉樹
8
/ \
6 10
/ \ / \
5 7 9 11
鏡像二叉樹
8
/ \
10 6
/ \ / \
11 9 7 5
*/
解析：其實鏡像二叉樹就是交換所有節點的左右子樹，是以使用周遊并且進行交換即可。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class 鏡像二叉樹 {
public void Mirror(TreeNode root) {
if(root == null)return;
if(root.left!=null || root.right!=null)
{
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
Mirror(root.left);
Mirror(root.right);
}
樹的層次周遊
也就是從上到下列印節點，使用隊列即可完成。
二叉樹的深度
經典周遊。
判斷是否平衡二叉樹
判斷左右子樹的高度差是否 <= 1即可。
二叉搜尋樹的後序周遊
輸入一個整數數組，判斷該數組是不是某二叉搜尋樹的後序周遊的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。
解析：這題其實也非常巧妙。二叉搜尋樹的特點就是他的左子樹都比根節點小，右子樹都比跟節點大。而後序周遊的根節點在最後，是以後續周遊的第1到N-1個節點應該是左右子樹的節點（不一定左右子樹都存在）。
後續周遊的序列是先左子樹，再右子樹，最後根節點，那麼就要求，左半部分比根節點小，右半部分比根節點大，當然，左右部分不一定都存在。
是以，找出根節點後，首先找出左半部分，要求小于根節點，然後找出右半部分，要求大于根節點，如果符合，則遞歸地判斷左右子樹到的根節點（本步驟已經将左右部分劃分，割據中間節點進行遞歸），如果不符合，直接傳回false。
同理也可以判斷前序周遊和中序周遊。
public class 二叉搜尋樹的後序周遊序列 {
public static void main(String[] args) {
int []a = {7,4,6,5};
System.out.println(VerifySquenceOfBST(a));
}
public static boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0) {
return false;
}
return isBST(sequence, 0, sequence.length - 1);
}
public static boolean isBST(int []arr, int start, int end) {
if (start >= end) return true;
int root = arr[end];
int mid = start;
for (mid = start;mid < end && arr[mid] < root;mid ++) {
}
for (int i = mid;i < end; i ++) {
if (arr[i] < root)return false;
}
return isBST(arr, start, mid - 1) && isBST(arr, mid, end - 1);
}
}
二叉樹中和為某一值的路徑
- Created by 周傑倫 on 2018/3/29.
-
輸入一顆二叉樹和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。
解析：由于要求從根節點到達葉子節點，并且要列印出所有路徑，是以實際上用到了回溯的思想。
通過target跟蹤目前和，進行先序周遊，當和滿足要求時，加入集合，由于有多種結果，是以需要回溯，将通路過的節點彈出通路序列，才能繼續通路下一個節點。
終止條件是和滿足要求，并且節點是葉節點，或者已經通路到空節點也會傳回。
public class 二叉樹中和為某一值的路徑 {
private ArrayList<ArrayList> listAll = new ArrayList<ArrayList>();
private ArrayList list = new ArrayList();
public ArrayList<ArrayList> FindPath(TreeNode root,int target) {
if(root == null) return listAll;
list.add(root.val);
target -= root.val;
if(target == 0 && root.left == null && root.right == null)
listAll.add(new ArrayList(list));
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size()-1);
return listAll;
static int count = 0; static Stack<Integer> path = new Stack<>(); static Stack<Integer> stack = new Stack<>(); static ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
二叉樹的下一個節點
給定一個二叉樹和其中的一個結點，請找出中序周遊順序的下一個結點并且傳回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。
解析：給出一個比較好懂的解法，中序周遊的結果存在集合中，找到根節點，進行中序周遊，然後找到該節點，下一個節點就是集合後一位
public TreeLinkNode GetNext(TreeLinkNode TreeLinkNode)
{
return findNextNode(TreeLinkNode);
}
public TreeLinkNode findNextNode(TreeLinkNode anynode) {
if (anynode == null) return null;
TreeLinkNode p = anynode;
while (p.next != null) {
p = p.next;
}
ArrayList<TreeLinkNode> list = inOrderSeq(p);
for (int i = 0;i < list.size();i ++) {
if (list.get(i) == anynode) {
if (i + 1 < list.size()) {
return list.get(i + 1);
}
else return null;
}
}
return null;
}
static ArrayList<TreeLinkNode> list = new ArrayList<>();
public static ArrayList<TreeLinkNode> inOrderSeq(TreeLinkNode TreeLinkNode) {
if (TreeLinkNode == null) return null;
inOrderSeq(TreeLinkNode.left);
list.add(TreeLinkNode);
inOrderSeq(TreeLinkNode.right);
return list;
}
對稱的二叉樹
請實作一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。
解析，之前有一題是二叉樹的鏡像，遞歸交換左右子樹即可求出鏡像，然後遞歸比較兩個樹的每一個節點，則可以判斷是否對稱。
boolean isSymmetrical(TreeNode pRoot)
{
TreeNode temp = copyTree(pRoot);
Mirror(pRoot);
return isSameTree(temp, pRoot);
}
void Mirror(TreeNode root) {
if(root == null)return;
Mirror(root.left);
Mirror(root.right);
if(root.left!=null || root.right!=null)
{
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
}
boolean isSameTree(TreeNode t1,TreeNode t2){
if(t1==null && t2==null)return true;
else if(t1!=null && t2!=null && t1.val==t2.val) {
boolean left = isSameTree(t1.left, t2.left);
boolean right = isSameTree(t1.right, t2.right);
return left && right;
}
else return false;
}
TreeNode copyTree (TreeNode root) {
if (root == null) return null;
TreeNode t = new TreeNode(root.val);
t.left = copyTree(root.left);
t.right = copyTree(root.right);
return t;
}
把二叉樹列印成多行
從上到下按層列印二叉樹，同一層結點從左至右輸出。每一層輸出一行。
解析：1 首先要知道到本題的基礎思想，層次周遊。
2 然後是進階的思想，按行列印二叉樹并輸出行号，方法是，一個節點last指向目前行的最後一個節點，一個節點nlast指向下一行最後一個節點。使用t表示現在周遊的節點，當t = last時，表示本行結束。此時last = nlast，開始下一行周遊。
同時，當t的左右子樹不為空時，令nlast = t的左子樹和右子樹。每當last 指派為nlast時，行号加一即可。
按之字形順序列印二叉樹
請實作一個函數按照之字形列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右至左的順序列印，第三行按照從左到右的順序列印，其他行以此類推。
3 基于第2步的思想，現在要z字型列印，隻需把偶數行逆序即可。是以把每一行的數存起來，然後偶數行逆置即可。
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
LinkedList<TreeNode> queue = new LinkedList<>();
TreeNode root = pRoot;
if(root == null) {
return new ArrayList<>();
}
TreeNode last = root;
TreeNode nlast = root;
queue.offer(root);
ArrayList<Integer> list = new ArrayList<>();
list.add(root.val);
ArrayList<Integer> one = new ArrayList<>();
one.addAll(list);
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
lists.add(one);
list.clear();
int row = 1;
while (!queue.isEmpty()){
TreeNode t = queue.poll();
if(t.left != null) {
queue.offer(t.left);
list.add(t.left.val);
nlast = t.left;
}
if(t.right != null) {
queue.offer(t.right);
list.add(t.right.val);
nlast = t.right;
}
if(t == last) {
if(!queue.isEmpty()) {
last = nlast;
row ++;
ArrayList<Integer> temp = new ArrayList<>();
temp.addAll(list);
list.clear();
if (row % 2 == 0) {
Collections.reverse(temp);
}
lists.add(temp);
}
}
}
return lists;
}
序列化和反序列化二叉樹
解析：序列化和反序列化關鍵是要确定序列化方式。我麼使用字元串來序列化。
用#代表空，用!分隔左右子樹。
比如 1
2 3
4 5
使用先序周遊
序列化結果是1!2!4!###3!#5!##
反序列化先讓根節點指向第一位字元，然後左子樹遞歸進行連接配接，右子樹
public class Solution {
public int index = -1;
StringBuffer sb = new StringBuffer();
String Serialize(TreeNode root) {
if(root == null) {
sb.append("#!") ;
}
else {
sb.append(root.val + "!");
Serialize(root.left);
Serialize(root.right);
}
return sb.toString();
}
TreeNode Deserialize(String str) {
index ++;
int len = str.length();
if(index >= len) {
return null;
}
String[] strr = str.split("!");
TreeNode node = null;
if(!strr[index].equals("#")) {
node = new TreeNode(Integer.valueOf(strr[index]));
node.left = Deserialize(str);
node.right = Deserialize(str);
}
return node;
}
}
二叉搜尋樹的第k個結點
解析：二叉搜尋樹的中序周遊是有序的，隻需要在中序中判斷數字是否在第k個位置即可。
如果在左子樹中發現了，那麼遞歸傳回該節點，如果在右子樹出現，也遞歸傳回該節點。注意必須要傳回，否則結果會被遞歸抛棄掉。
TreeNode KthNode(TreeNode pRoot, int k)
{
count = 0;
return inOrderSeq(pRoot, k);
}
static int count = 0;
public TreeNode inOrderSeq(TreeNode treeNode, int k) {
if (treeNode == null) return null;
TreeNode left = inOrderSeq(treeNode.left, k);
if (left != null) return left;
if (++ count == k) return treeNode;
TreeNode right = inOrderSeq(treeNode.right, k);
if (right != null) return right;
return null;
}
棧和隊列
用兩個隊列實作棧，用兩個棧實作隊列。
簡單說下思路
1 兩個棧實作隊列，要求先進先出，入隊時節點先進入棧A，如果棧A滿并且棧B空則把全部節點壓入棧B。
出隊時，如果棧B為空，那麼直接把棧A節點全部壓入棧B，再從棧B出棧，如果棧B不為空，則從棧B出棧。
2 兩個隊列實作棧，要求後進先出。入棧時，節點先加入隊列A，出棧時，如果隊列B不為空，則把頭結點以後的節點出隊并加入到隊列B，然後自己出隊。
如果出棧時隊列B不為空，則把B頭結點以後的節點移到隊列A，然後出隊頭結點，以此類推。
包含min函數的棧
- 設計一個傳回最小值的棧
- 定義棧的資料結構，請在該類型中實作一個能夠得到棧最小元素的min函數。
-
Created by 周傑倫 on 2017/3/22.
解析：這道題的解法也是非常巧妙的。因為每次進棧和出棧都有可能導緻最小值發生改變。而我們要維護的是整個棧的最小值。
如果單純使用一個數來儲存最小值，會出現一種情況，最小值出棧時，你此時的最小值隻能改成棧頂元素，但這個元素不一定時最小值。
是以需要一個數組來存放最小值，或者是一個棧。
使用另一個棧B存放最小值，每次壓棧時比較節點值和棧B頂端節點值，如果比它小則壓棧，否則不壓棧，這樣就可以從b的棧頂到棧頂依次通路最小值，次小值。以此類推。
當最小值節點出棧時，判斷棧B頂部的節點和出棧節點是否相同，相同則棧B也出棧。
這樣就可以維護一個最小值的函數了。
同理，最大值也是這樣。
public class 包含min函數的棧 {
Stack stack=new Stack<>();
Stack minstack=new Stack<>();
public void push(int node) { if(stack.isEmpty()) { stack.push(node); minstack.push(node); } else if(node<stack.peek()){ stack.push(node); minstack.push(node); } else { stack.push(node); } } public void pop() { if(stack.isEmpty())return; if(stack.peek()==minstack.peek()){ stack.pop(); minstack.pop(); } else { stack.pop(); } } public int top() { return stack.peek(); } public int min() { if(minstack.isEmpty())return 0; return minstack.peek(); }
棧的壓入和彈出序列
題目描述
輸入兩個整數序列，第一個序清單示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）
解析：本題是比較抽象的，首先，根據入棧出棧的規則，我們可以建立一個棧A，用于儲存壓棧序列，然後壓入第一個元素，比較出棧序列的第一個元素，如果不相等，繼續壓棧，直到二者相等，此時棧A元素出棧，然後重複上一步的操作。
如果在每次壓棧過程中，入棧序列已經全部入棧A但是還是找不到出棧序列的第一個元素時，則說明不是出棧序列。
當棧A的元素全部壓入并出棧後，如果出棧序列也出棧完畢，則滿足題意。
public static boolean IsPopOrder(int[] pushA, int[] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;
int i = 0;
while (i < pushA.length) {
stack.push(pushA[i]);
i++;
while (!stack.empty() && stack.peek() == popA[j]) {
stack.pop();
j++;
}
if (i == pushA.length) {
if (!stack.empty()) {
return false;
} else return true;
}
}
return false;
}
排序和查找
旋轉數組的最小數字
把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請傳回0。
解析：這題的思路很巧妙，如果直接周遊複雜度為O（N），但是使用二分查找可以加快速度，因為兩邊的數組都是遞增的最小值一定在兩邊數組的邊緣，于是通過二分查找，逐漸縮短左右指針的距離，知道左指針和右指針隻差一步，那麼右指針所在的數就是最小值了。
複雜度是O（logN)
//這段代碼忽略了三者相等的情況
public int minNumberInRotateArray(int [] array) {
if (array.length == 0) return 0;
if (array.length == 1) return array[0];
int min = 0;
int left = 0, right = array.length - 1;
//隻有左邊值大于右邊值時，最小值才可能出現在中間
while (array[left] > array[right]) {
int mid = (left + right)/2;
if (right - left == 1) {
min = array[right];
break;
}
//如果左半部分遞增，則最小值在右側
if (array[left] < array[mid]) {
left = mid;
}
//如果右半部分遞增，則最小值在左側。
//由于左邊值比右邊值大，是以兩種情況不會同時發生
else if (array[right] > array[mid]) {
right = mid ;
}
}
return array[min];
}
注意：但是當arr[left] = arr[right] = arr[min]時。三個數都相等無法确定最小值，此時隻能周遊。
遞歸
斐波那契數列
1遞歸做法
2記憶搜尋，用數組存放使用過的元素。
3DP，本題中dp就是記憶化搜尋
青蛙跳台階
一次跳兩步或者跳一步，問一共多少種跳法到達n級，是以和斐波那契數列是一樣的。
變态跳台階
一次跳1到n步，問一共幾種跳法，這題是找數字規律的，一共有2^(n-1)種方法
矩形覆寫
和上題一樣，也是找規律，答案也是2^(n-1)
位運算
二進制中1的個數
- Created by 周傑倫 on 2018/6/29.
-
輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。
解析:
1 循環右移數字n，每次判斷最低位是否為1，但是可能會導緻死循環。
2 使用數字a = 1和n相與，a每次左移一位，再與n相與得到次低位，最多循環32次，當數字1左移32次也會等于0，是以結束循環。
3 非常奇葩的做法，把一個整數減去1，再與原整數相與，會把最右邊的一個1變成0，于是統計可以完成該操作的次數即可知道有多少1了。
public class 二進制中1的個數 { public static int NumberOf1(int n) { int count = 0; while (n != 0) { ++count; n = (n - 1) & n; } return count; } }
數組中隻出現一次的數字
一個整型數組裡除了一個數字之外，其他的數字都出現了兩次。請寫程式找出這一個隻出現一次的數字。
解析：左神稱之為神仙題。
利用位運算的異或操作^。
由于a^a = 0,0^b=b，是以。所有數執行異或操作，結果就是隻出現一次的數。
不用加減乘除做加法
解析：不用加減乘，那麼隻能用二進制了。
兩個數a和b，如果不考慮進位，則0 + 1 = 1,1 + 1 = 0，0 + 0 = 0，這就相當于異或操作。
如果考慮進位，則隻有1 + 1有進位，是以使用相與左移的方法得到每一位的進位值，再通過異或操作和原來的數相加。當沒有進位值的時候，運算結束。
public static int Add(int num1,int num2) {
if( num2 == 0 )return num1;
if( num1 == 0 )return num2;
int temp = num2;
while(num2!=0) {
temp = num1 ^num2;
num2 = (num1 & num2)<<1;
num1 = temp;
}
return num1;
}
回溯和DFS
矩陣中的路徑
請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字元串所有字元的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則之後不能再次進入這個格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字元串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字元串的第一個字元b占據了矩陣中的第一行第二個格子之後，路徑不能再次進入該格子。
解析：回溯法也就是特殊的dfs，需要找到所有的路徑，是以每當到達邊界條件或抵達目标時，遞歸傳回，由于需要儲存路徑中的字母，是以遞歸傳回時需要删除路徑最後的節點，來保證路徑合法。不過本題隻有一個解，是以找到即可傳回。
public class 矩陣中的路徑 {
public static void main(String[] args) {
char[][]arr = {{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};
char []str = {'b','c','c','e','d'};
System.out.println(hasPath(arr, arr.length, arr[0].length, str));
}
static int flag = 0;
public static boolean hasPath(char[][] matrix, int rows, int cols, char[] str)
{
int [][]visit = new int[rows][cols];
StringBuilder sb = new StringBuilder();
for (int i = 0;i < rows;i ++) {
for (int j = 0;j < cols;j ++) {
if (matrix[i][j] == str[0]) {
visit[i][j] = 1;
sb.append(str[0]);
dfs(matrix, i, j, visit, str, 1, sb);
visit[i][j] = 0;
sb.deleteCharAt(sb.length() - 1);
}
}
}
return flag == 1;
}
public static void dfs(char [][]matrix, int row, int col, int [][]visit, char []str, int cur, StringBuilder sb) {
if (sb.length() == str.length) {
// System.out.println(sb.toString());
flag = 1;
return;
}
int [][]pos = {{1,0},{-1,0},{0,1},{0,-1}};
for (int i = 0;i < pos.length;i ++) {
int x = row + pos[i][0];
int y = col + pos[i][1];
if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0) {
continue;
}
if (visit[x][y] == 0 && matrix[x][y] == str[cur]) {
sb.append(matrix[x][y]);
visit[x][y] = 1;
dfs(matrix, x, y, visit, str, cur + 1, sb);
sb.deleteCharAt(sb.length() - 1);
visit[x][y] = 0;
}
}
}
機器人的運動範圍
地上有一個m行和n列的方格。一個機器人從坐标0,0的格子開始移動，每一次隻能向左，右，上，下四個方向移動一格，但是不能進入行坐标和列坐标的數位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？
解析：這是一個可達性問題，使用dfs方法，走到的每一格标記為走過，走到無路可走時就是最終的結果。每次都有四個方向可以選擇，是以寫四個遞歸即可。
public class Solution {
static int count = 0;
public static int movingCount(int threshold, int rows, int cols)
{
count = 0;
int [][]visit = new int[rows][cols];
dfs(0, 0, visit, threshold);
return count;
}
public static void dfs(int row, int col, int[][]visit, int k) {
if (row >= visit.length || row < 0 || col >= visit[0].length || col < 0) {
return;
}
if (sum(row) + sum(col) > k) {
return;
}
if (visit[row][col] == 1){
return;
}
visit[row][col] = 1;
count ++;
dfs(row + 1,col,visit, k);
dfs(row - 1,col,visit, k);
dfs(row,col + 1,visit, k);
dfs(row,col - 1,visit, k);
}
public static int sum(int num) {
String s = String.valueOf(num);
int sum = 0;
for (int i = 0;i < s.length();i ++) {
sum += Integer.valueOf(s.substring(i, i + 1));
}
return sum;
}
}
## 微信公衆号
個人公衆号：程式員黃小斜
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)