1.二維數(shù)組中的查找
題目描述
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同）引镊，每一行都按照從左到右遞增的順序排序跳夭，每一列都按照從上到下遞增的順序排序岸浑。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)秫舌，判斷數(shù)組中是否含有該整數(shù)。
public class Solution {
public boolean Find(int target, int [][] array) {
if(array==null||array.length==0||array[0].length==0){
return false;
}
int i=0;
int j=array[0].length-1;
while(i<array.length&&j>=0){
if(target==array[i][j]){
return true;
}else if(target<array[i][j]){
j--;
}else{
i++;
}
}
return false;
}
}
2.替換空格
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)绣檬，將一個(gè)字符串中的每個(gè)空格替換成“%20”足陨。例如，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy娇未。
思路1：從頭到尾掃描字符串墨缘，遇到空格，將后面的字符串后移2位零抬，然后做替換
缺點(diǎn)：后面的字符串將被移動(dòng)多次（多次賦值）镊讼。如果有O(n)個(gè)空格，字符串將移動(dòng)O(n)次平夜，每次需要移動(dòng)O(n)個(gè)字符蝶棋，所以時(shí)間復(fù)雜度是O（n^2）
思路2：從后往前開(kāi)始字符串的替換和移動(dòng)。首先遍歷一次字符串忽妒，找到所有空格的數(shù)目玩裙。替換后字符串長(zhǎng)度為 原來(lái)的字符串長(zhǎng)度+空格個(gè)數(shù)*2。我們新建一個(gè)數(shù)組段直，從尾部開(kāi)始向前遍歷原數(shù)組吃溅，如果是空格，則新數(shù)組的位置替換成“%20”鸯檬，新數(shù)組的下標(biāo)逐個(gè)遞減3格决侈；如果不是空格，直接復(fù)制原數(shù)組的內(nèi)容到新數(shù)組對(duì)應(yīng)位置喧务，下標(biāo)都減1格赖歌。
注意：
1.空字符串
2.null輸入
3.沒(méi)有空格的情況
4.空格在頭枉圃，中，尾的情況
知識(shí)點(diǎn)：
1.StringBuffer線程安全俏站。內(nèi)部char[]數(shù)組讯蒲，方法前加synchronized關(guān)鍵字
2.StringBuffer中的capacity和length是不同的，capacity是容量肄扎，而length是實(shí)際字符串長(zhǎng)度墨林。當(dāng)我們new StringBuffer(16)的時(shí)候，我們得到的是一個(gè)capacity=16犯祠，length=0的StringBuffer旭等。
3.返回值是String，StringBuffer需要toString轉(zhuǎn)化
4.從char[]到String衡载，不能通過(guò)toString方式（沒(méi)有重寫(xiě)這個(gè)方法搔耕，實(shí)際使用的是Object的toString，即返回了地址）痰娱，而通過(guò)new String(char[] array)方式
5.StringBuffer的get和set:str.charAt(i)弃榨、str.setCharAt(int index,char newChar)
6.String的get和set:str.charAt(i)、String不可變梨睁，可以將String轉(zhuǎn)化成StringBuilder/StringBuffer
public class Solution {
public static String replaceSpace(StringBuffer str) {
if(str==null||str.length()<=0){
return str.toString();
}
int count=0;
for(int i=0;i<str.length();i++){
if(str.charAt(i)==' '){
count++;
}
}
char[] newStr = new char[str.length()+count*2];
int i=str.length()-1;
int j=newStr.length-1;
while(i>=0){
if(str.charAt(i)==' '){
newStr[j--]='0';
newStr[j--]='2';
newStr[j--]='%';
}else{
newStr[j--]=str.charAt(i);
}
i--;
}
return new String(newStr);
}
}
3.從尾到頭打印鏈表
題目描述
輸入一個(gè)鏈表鲸睛，按鏈表值從尾到頭的順序返回一個(gè)ArrayList。
思路一：用棧坡贺。先進(jìn)后出官辈。
要點(diǎn)：
1.注意判斷null值
2.stack的pop和peek方法可能會(huì)拋出EmptyStackException()，所以需要先調(diào)用empty()判斷是否為空遍坟，然后再進(jìn)行操作
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result = new ArrayList<Integer>();
if(listNode==null){
return result;
}
Stack<Integer> stack = new Stack<Integer>();
ListNode currentNode = listNode;
while(currentNode!=null){
stack.push(currentNode.val);
currentNode = currentNode.next;
}
while(!stack.empty()){
result.add(stack.pop());
}
return result;
}
}
思路二：用遞歸的方式拳亿。遞歸的終止條件是下一個(gè)節(jié)點(diǎn)為空指針。
需要注意愿伴，如果是遞歸肺魁，需要把返回結(jié)果的list放在遞歸函數(shù)外，以免每次遞歸時(shí)被歸0
public class Solution {
ArrayList<Integer> result = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode==null){
return result;
}
printListFromTailToHead(listNode.next);
result.add(listNode.val);
return result;
}
}
4.重建二叉樹(shù)
題目描述
輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果隔节，請(qǐng)重建出該二叉樹(shù)万搔。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}官帘，則重建二叉樹(shù)并返回瞬雹。
思路：
前序遍歷的首個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)，接下來(lái)是所有左子樹(shù)節(jié)點(diǎn)刽虹，最后是所有右子樹(shù)節(jié)點(diǎn)酗捌。利用中序遍歷得到左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)和右子樹(shù)節(jié)點(diǎn)個(gè)數(shù)；再對(duì)左右子樹(shù)分別重復(fù)上述步驟，進(jìn)行迭代胖缤。
1.前序遍歷和層次遍歷是不同的尚镰。前序遍歷是根左右，深度優(yōu)先哪廓，會(huì)遍歷完左子樹(shù)再遍歷右子樹(shù)狗唉；層次遍歷是廣度優(yōu)先。同層從左到右遍歷涡真。
2.前序遍歷的序列分俯，首個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)。再之后是全部的左子樹(shù)節(jié)點(diǎn)哆料；再然后是全部的右子樹(shù)節(jié)點(diǎn)缸剪。所以給出前序遍歷序列之后，我們需要找到左子樹(shù)截止的位置东亦；
3.這里可以借助中序遍歷的特點(diǎn)杏节，根節(jié)點(diǎn)左邊的是全部的左子樹(shù)序列，根節(jié)點(diǎn)右邊的是全部的右子樹(shù)序列典阵。
4.如果是后序遍歷奋渔，則按照左右根的順序，最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)壮啊，根節(jié)點(diǎn)前面是右子樹(shù)的全部節(jié)點(diǎn)嫉鲸，再往前是左子樹(shù)的全部節(jié)點(diǎn)。也需要找到一個(gè)左右子樹(shù)的分界點(diǎn)他巨。
如果是前序+中序/后序+中序，可以唯一確定一棵二叉樹(shù)减江。
如果是前序+后序染突，無(wú)法唯一確定一棵二叉樹(shù)。
相關(guān)問(wèn)題：
1.二叉樹(shù)遍歷（已知前序和后序遍歷辈灼，求中序遍歷的可能的序列數(shù)）
https://blog.csdn.net/qq_37437983/article/details/79613947
2.已知前序和中序份企，求后序遍歷
遞歸。后序遍歷 右子節(jié)點(diǎn)緊挨根節(jié)點(diǎn)（如果有的話）巡莹；左子節(jié)點(diǎn)位置在根節(jié)點(diǎn)前司志，右子樹(shù)節(jié)點(diǎn)前的位置。
如果降宅，i是后序遍歷數(shù)組每次迭代的根節(jié)點(diǎn)位置骂远，j是右子樹(shù)長(zhǎng)度；則i-j-1是左子樹(shù)根節(jié)點(diǎn)的位置腰根，i-1是右子樹(shù)根節(jié)點(diǎn)的位置激才。
https://blog.csdn.net/qq_29375837/article/details/81160362
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode node=construct(pre,in,0,0,in.length-1);
return node;
}
public TreeNode construct(int [] pre,int [] in,int preStart,int inStart,int inEnd){
TreeNode node=null;
if(pre==null||in==null||preStart<0||preStart>pre.length||inStart<0||
inEnd>in.length-1||inStart>inEnd){
return null;
}
for(int i=inStart;i<=inEnd;i++){
if(in[i]==pre[preStart]){
node = new TreeNode(pre[preStart]);
node.left = construct(pre,in,preStart+1,inStart,i-1);
node.right = construct(pre,in,preStart+(i-inStart)+1,i+1,inEnd);
break;
}
}
return node;
}
}
5.用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
題目描述
用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類(lèi)型瘸恼。
思路：push不變
pop時(shí)先判斷stack2是否為空劣挫，不為空直接pop stack2；為空則把stack1的元素逐一出棧再入棧stack2,最后pop stack2
遵循先進(jìn)先出
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);
}
public int pop() {
if(stack2.empty()){
while(!stack1.empty()){
int node = stack1.pop();
stack2.push(node);
}
}
return stack2.pop();
}
}
附加：如果是用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧呢
思路1：queue1做進(jìn)出隊(duì)列东帅，queue2做中轉(zhuǎn)隊(duì)列压固。push直接push到queue1，pop的時(shí)候靠闭，先把queue1的全部元素pop到queue2,然后queue2.pop帐我，再把queue2中的所有元素pop回queue1（效率不高）
思路2： queue1和queue2都做進(jìn)出隊(duì)列。
push的時(shí)候阎毅，選擇非空的隊(duì)列進(jìn)行push焚刚，如果都空，選擇queue1
push扇调。
pop的時(shí)候矿咕，把非空隊(duì)列的元素全部pop到空隊(duì)列，然后pop狼钮。
6.旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾碳柱，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)熬芜，輸出旋轉(zhuǎn)數(shù)組的最小元素莲镣。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1涎拉。 NOTE：給出的所有元素都大于0瑞侮，若數(shù)組大小為0，請(qǐng)返回0鼓拧。
關(guān)鍵點(diǎn):
1.首先半火，“若干個(gè)元素搬到數(shù)組的末尾”中的若干個(gè)，可以為0個(gè)季俩；即{1,2,3,4,5}也是{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)钮糖。
2.可以有相同元素。
10111是01111的一個(gè)旋轉(zhuǎn)
11101也是01111的一個(gè)旋轉(zhuǎn)
思路：
思路1.遍歷得最凶米 ：O（n）復(fù)雜度
思路2.優(yōu)化一點(diǎn)店归。發(fā)現(xiàn)后面的元素小于前面元素，則break酪我。O(n)復(fù)雜度
思路3：利用二分法消痛。O(logn)復(fù)雜度
利用二分法需要考慮縮小的條件。
考慮對(duì)于一個(gè)非遞減數(shù)組有下面的情況：
（1）旋轉(zhuǎn)0個(gè)元素都哭。即旋轉(zhuǎn)后的數(shù)組也非遞減肄满。返回?cái)?shù)組第一個(gè)元素即可谴古。這時(shí)只要判斷出第一個(gè)元素小于最后一個(gè)元素，必定是這種情況
（2）如果旋轉(zhuǎn)了稠歉，則必定是兩個(gè)非遞減數(shù)組的拼接掰担。我們用low在第一個(gè)非遞減數(shù)組中，high在第二個(gè)非遞減數(shù)組中怒炸，不斷縮小邊界带饱。mid是low和high的中間位置。
最小元素位于兩個(gè)非遞減數(shù)組的分界處阅羹。
如果low指向的值小于等于mid指向的值勺疼，說(shuō)明low和mid都位于第一個(gè)非遞減數(shù)組，low可以后移至mid的位置捏鱼，依舊還是位于第一個(gè)非遞減數(shù)組执庐。
如果high指向的值大于等于mid指向的值，說(shuō)明mid和high都位于第二個(gè)非遞減數(shù)組导梆，high可以前移至mid的位置轨淌，依舊還是位于第二個(gè)非遞減數(shù)組。
最終看尼，low將指向第一個(gè)非遞減數(shù)組的最后一個(gè)元素递鹉，high將指向第二個(gè)非遞減數(shù)組的第一個(gè)元素（即分界處）。這時(shí)藏斩，low和high將相鄰躏结，這就是循環(huán)結(jié)束的條件。high指向的位置就是最小元素的位置狰域。
（3）在（2）中還包含著一個(gè)特殊情況媳拴。比如10111。它的low,high,mid指向的值相同兆览，但是顯然屈溉，low不能縮小到mid的邊界。這說(shuō)明拓颓，當(dāng)low,high,mid指向值相同的時(shí)候语婴，我們無(wú)法判斷該如何移動(dòng)指針描孟。這個(gè)時(shí)候驶睦，應(yīng)該改用遍歷的方式。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array==null||array.length==0)
return 0;
int low = 0;
int high = array.length-1;
int mid = low;
while(array[low]>=array[high]){
if(high-low==1){
mid = high;
break;
}
mid = (low+high)/2;
if(array[low]==array[mid]&&array[mid]==array[high]){
return inOrder(array,low,high);
}else if(array[low]<=array[mid]){
low = mid;
}else if(array[high]>=array[mid]){
high = mid;
}
}
return array[mid];
}
public int inOrder(int[] array,int low,int high){
for(int i=low;i<high;i++){
if(array[i]>array[i+1]){
return array[i+1];
}
}
return array[high];
}
}
7.斐波那契數(shù)列
用循環(huán)匿醒，不要用遞歸
注意取值场航，是否超過(guò)int范圍（一般10位）
39是63245986，沒(méi)超廉羔。
保險(xiǎn)起見(jiàn)溉痢，可以使用long
public class Solution {
public int Fibonacci(int n) {
if(n==0)return 0;
if(n==1)return 1;
int[] fib = {0,1};
int result =0;
for(int i=2;i<=n;i++){
result = fib[0]+fib[1];
fib[0]=fib[1];
fib[1]=result;
}
return result;
}
}
變種1:跳臺(tái)階
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)，求該青蛙跳上一個(gè)n級(jí)臺(tái)階總共有多少種跳法(先后次序不同算不同的結(jié)果)
解法：如果只有一級(jí)臺(tái)階孩饼，有1種跳法髓削；如果有2級(jí)，有2種跳法镀娶。（初始）
如果有n級(jí)臺(tái)階（n>2）立膛，那么如果第一步跳1，有f(n-1)種跳法梯码；如果第一步跳2宝泵，有f(n-2)種跳法。所以轩娶，f(n)=f(n-1)+f(n-2)
如果先后次序不同算相同的結(jié)果的話：n/2 +1種結(jié)果
變種2：變態(tài)跳臺(tái)階
一只青蛙一次可以跳上1級(jí)臺(tái)階儿奶，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法鳄抒。
思路1：
如果只有一級(jí)臺(tái)階闯捎，有1種跳法；如果有2級(jí)嘁酿，有2種跳法隙券。（初始）
如果有n級(jí)臺(tái)階，那么第一步可以跳1闹司，2娱仔，3，……游桩，n牲迫。所以剩下的分別有f(n-1),f(n-2),f(n-3)……，f(1),1種跳法借卧。
用一個(gè)長(zhǎng)度為n的數(shù)組存儲(chǔ)之前計(jì)算出來(lái)的值盹憎。
f(n)=f(n-1)+f(n-2)+……+f(1)+1
public class Solution {
public int JumpFloorII(int target) {
if(target==0)return 0;
if(target==1)return 1;
if(target==2)return 2;
int[] pre = new int[target];
pre[0]=1;
pre[1]=2;
int result=pre[0]+pre[1];
for(int i=2;i<target;i++){
pre[i]=result+1;
result+=pre[i];
}
return pre[target-1];
}
}
然而，這種方式仍然不是最簡(jiǎn)單的
由于
f(n)=f(n-1)+f(n-2)+……+f(1)+1
f(n-1)=f(n-2)+……+f(1)+1
所以f(n) = 2f(n-1)=22f(n-2)=22……f(2) = 2(n-2)*f(2)=2(n-1)
可以根據(jù)這個(gè)遞推式去做铐刘。
pow(2,n-1)或者1<<n-1
變種3：矩形覆蓋
題目描述
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形陪每。請(qǐng)問(wèn)用n個(gè)21的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法镰吵？
可以轉(zhuǎn)化成變種1的思考方式
public class Solution {
public int RectCover(int target) {
if(target==0)return 0;
if(target==1)return 1;
if(target==2)return 2;
int pre1= 1;
int pre2= 2;
int result =0;
for(int i=2;i<target;i++){
result=pre1+pre2;
pre1=pre2;
pre2 = result;
}
return result;
}
}
8.二進(jìn)制中1的個(gè)數(shù)
位運(yùn)算是屬于二進(jìn)制數(shù)的運(yùn)算
基本知識(shí)
- 代碼中在數(shù)字前加前綴
0x十六進(jìn)制
0b二進(jìn)制
0八進(jìn)制 - 操作
&
^
|
m<<n:最左邊的n位將被丟棄檩禾，同時(shí)在右邊補(bǔ)上n個(gè)0
m=m>>n:最右邊的n位將被丟棄。如果是有符號(hào)數(shù)疤祭，用數(shù)字的符號(hào)位填補(bǔ)
左邊的n位
m>>>n:無(wú)符號(hào)右移盼产，補(bǔ)0 - 原碼、反碼和補(bǔ)碼
https://blog.csdn.net/hittata/article/details/9108323
計(jì)算機(jī)中的負(fù)數(shù)表示是補(bǔ)碼
以負(fù)數(shù)-5為例：
1.先將-5的絕對(duì)值轉(zhuǎn)換成二進(jìn)制勺馆，即為0000 0101戏售；
2.然后求該二進(jìn)制的反碼侨核，即為 1111 1010；
3.最后將反碼加1灌灾，即為：1111 1011
所以Java中Integer.toBinaryString(-5)結(jié)果為11111111111111111111111111111011. Integer是32位(bit)的.
題目描述
輸入一個(gè)整數(shù)搓译，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示锋喜。
思路1：整數(shù)右移侥衬，直到為0（負(fù)數(shù)會(huì)陷入死循環(huán)）。但是java提供無(wú)符號(hào)右移方式跑芳，此時(shí)是可行的
public class Solution {
public int NumberOf1(int n) {
int count=0;
while(n!=0){
if((n&1)!=0){
count++;
}
n=n>>>1;
}
return count;
}
}
思路2：設(shè)置一個(gè)無(wú)符號(hào)整型的flag轴总，然后每次flag左移，n&flag博个！=0時(shí)count數(shù)+1,直到flag為0(java語(yǔ)言中沒(méi)有無(wú)符號(hào)整型這樣的變量)
public class Solution {
public int NumberOf1(int n) {
int count=0;
int flag=1;
while(flag!=0){
if((n&flag)!=0){
count++;
}
flag = flag<<1;
}
return count;
}
}
思路3：n&(n-1)會(huì)將n的最右邊一位1變成0怀樟。令n=n&(n-1),直到n為0
public class Solution {
public int NumberOf1(int n) {
int count=0;
while(n!=0){
n=n&(n-1);
count++;
}
return count;
}
}
