刷一下算法題吧碟婆。
https://foreti.me/2017/09/08/jianzhi-offer/
替換空格
題目描述
請實(shí)現(xiàn)一個(gè)函數(shù)累奈，將一個(gè)字符串中的空格替換成“%20”。例如瞬捕，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy员咽。
思路
看到問題第一反應(yīng)是用replaceAll()方法惹骂，但這樣挺沒意思的。所以自己寫解決方法毛仪，這樣的話搁嗓，就有了兩種思路。
- 從前往后替換箱靴，當(dāng)遇到第一個(gè)空格時(shí)腺逛，要移動第一個(gè)空格后所有的字符一次；當(dāng)遇到第二個(gè)空格時(shí)衡怀，要移動第二個(gè)空格后所有的字符一次棍矛；以此類推。
- 從后往前狈癞，先計(jì)算需要多少空間茄靠，然后從后往前移動，則每個(gè)字符只為移動一次蝶桶，這樣效率更高一點(diǎn)慨绳。
這里提供第二種方法的代碼
public class Solution {
public String replaceSpace(StringBuffer str) {
int spacenum = 0;//spacenum為計(jì)算空格數(shù)
for(int i=0;i<str.length();i++){
if(str.charAt(i)==' ')
spacenum++;
}
int indexold = str.length()-1; //indexold為為替換前的str下標(biāo)
int newlength = str.length() + spacenum*2;//計(jì)算空格轉(zhuǎn)換成%20之后的str長度
int indexnew = newlength-1;//indexnew為把空格替換為%20后的str下標(biāo)
str.setLength(newlength);//使str的長度擴(kuò)大到轉(zhuǎn)換成%20之后的長度,防止下標(biāo)越界
for(;indexold>=0 && indexold<newlength;--indexold){
if(str.charAt(indexold) == ' '){ //
str.setCharAt(indexnew--, '0');
str.setCharAt(indexnew--, '2');
str.setCharAt(indexnew--, '%');
}else{
str.setCharAt(indexnew--, str.charAt(indexold));
}
}
return str.toString();
}
}
從尾到頭打印鏈表
題目描述
輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。
思路2：
遞歸
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> arrayList = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode != null){
this.printListFromTailToHead(listNode.next);
arrayList.add(listNode.val);
}
return arrayList;
}
}
思路2：
利用棧
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> list = new ArrayList<>();
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}
二維數(shù)組中的查找
題目描述
在一個(gè)二維數(shù)組中脐雪，每一行都按照從左到右遞增的順序排序厌小，每一列都按照從上到下遞增的順序排序。請完成一個(gè)函數(shù)战秋，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)璧亚，判斷數(shù)組中是否含有該整數(shù)。
解題思路
利用二維數(shù)組由上到下脂信，由左到右遞增的規(guī)律癣蟋，
那么選取右上角或者左下角的元素a[row][col]與target進(jìn)行比較，
當(dāng)target小于元素a[row][col]時(shí)狰闪，那么target必定在元素a所在行的左邊,
即col--疯搅；
當(dāng)target大于元素a[row][col]時(shí)，那么target必定在元素a所在列的下邊,
即row++埋泵；
時(shí)間復(fù)雜度是O(2n)
public class Solution {
public boolean Find(int target, int [][] array) {
int row=0;
int col=array[0].length-1;
while(row<=array.length-1&&col>=0){
if(target==array[row][col])
return true;
else if(target>array[row][col])
row++;
else
col--;
}
return false;
}
}
另一種思路是
把每一行看成有序遞增的數(shù)組幔欧，
利用二分查找，
通過遍歷每一行得到答案丽声，
時(shí)間復(fù)雜度是O(nlogn)
public class Solution {
public boolean Find(int [][] array,int target) {
for(int i=0;i<array.length;i++){
int low=0;
int high=array[i].length-1;
while(low<=high){
int mid=(low+high)/2;
if(target>array[i][mid])
low=mid+1;
else if(target<array[i][mid])
high=mid-1;
else
return true;
}
}
return false;
}
}
<p id="div-border-left-red"><i>DigitalOcean 優(yōu)惠碼礁蔗，注冊充值 100，鏈接一 鏈接二</i></p>
<p id="div-border-left-red"><i>Lastly, welcome to follow me on github</i></p>
