46：把數(shù)字翻譯成字符串
題目要求：
給定一個(gè)數(shù)字历筝，按照如下規(guī)則翻譯成字符串：0翻譯成“a”期犬，1翻譯成“b”...25翻譯成“z”。
一個(gè)數(shù)字有多種翻譯可能弊仪，例如12258一共有5種揭厚，分別是bccfi币砂，bwfi鞭呕，bczi苟耻，mcfi篇恒，mzi。
實(shí)現(xiàn)一個(gè)函數(shù)凶杖，用來計(jì)算一個(gè)數(shù)字有多少種不同的翻譯方法胁艰。
解題思路：
下面我們從自上而下和自下而上兩種角度分析這道題目，以12258為例：
自上而下智蝠，從最大的問題開始腾么，遞歸 ：
12258
/ \
b+2258 m+258
/ \ / \
bc+258 bw+58 mc+58 mz+8
/ \ \ \ \
bcc+58 bcz+8 bwf+8 mcf+8 mzi
/ \ \ \
bccf+8 bczi bwfi mcfi
/
bccfi
有很多子問題被多次計(jì)算，比如258被翻譯成幾種這個(gè)子問題就被計(jì)算了兩次杈湾。
自下而上解虱，動(dòng)態(tài)規(guī)劃，從最小的問題開始 ：
f(r)表示以r為開始（r最小取0）到最右端所組成的數(shù)字能夠翻譯成字符串的種數(shù)漆撞。
對(duì)于長度為n的數(shù)字殴泰，f(n)=0,f(n-1)=1,求f(0)。
遞推公式為 f(r-2) = f(r-1)+g(r-2,r-1)*f(r)浮驳；
其中悍汛，如果r-2，r-1能夠翻譯成字符至会，則g(r-2,r-1)=1离咐，否則為0。
因此奉件，對(duì)于12258：
f(5) = 0
f(4) = 1
f(3) = f(4)+0 = 1
f(2) = f(3)+f(4) = 2
f(1) = f(2)+f(3) = 3
f(0) = f(1)+f(2) = 5
package chapter5;
public class P231_TranslateNumbersToStrings {
public static int getTranslationCount(int number){
if(number<0)
return 0;
if(number==1)
return 1;
return getTranslationCount(Integer.toString(number));
}
//動(dòng)態(tài)規(guī)劃宵蛀，從右到左計(jì)算。
//f(r-2) = f(r-1)+g(r-2,r-1)*f(r);
//如果r-2县貌，r-1能夠翻譯成字符术陶，則g(r-2,r-1)=1，否則為0
public static int getTranslationCount(String number) {
int f1 = 0,f2 = 1,g = 0;
int temp;
for(int i=number.length()-2;i>=0;i--){
if(Integer.parseInt(number.charAt(i)+""+number.charAt(i+1))<26)
g = 1;
else
g = 0;
temp = f2;
f2 = f2+g*f1;
f1 = temp;
}
return f2;
}
public static void main(String[] args){
System.out.println(getTranslationCount(-10)); //0
System.out.println(getTranslationCount(1234)); //3
System.out.println(getTranslationCount(12258)); //5
}
}
47：禮物的最大值
題目要求：
在一個(gè)m*n的棋盤的每一個(gè)格都放有一個(gè)禮物煤痕，每個(gè)禮物都有一定價(jià)值（大于0）瞳别。
從左上角開始拿禮物征候，每次向右或向下移動(dòng)一格，直到右下角結(jié)束祟敛。給定一個(gè)棋盤疤坝，
求拿到禮物的最大價(jià)值。例如馆铁，對(duì)于如下棋盤
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
禮物的最大價(jià)值為1+12+5+7+7+16+5=53跑揉。
解題思路：
思路1：動(dòng)態(tài)規(guī)劃
申請(qǐng)一個(gè)與原矩陣行列數(shù)一樣的二維數(shù)組dp[][]，初始化dp[0][i] = data[0][i]
埠巨；然后依次更新dp的每一行即可历谍。由于第m行的值與第m-1行和第m行有關(guān)，因此可以
對(duì)dp進(jìn)行簡化辣垒，僅用兩行的dp望侈，即dp[2][]即可完成狀態(tài)的記錄與更新。
思路2：廣度優(yōu)先遍歷
這個(gè)棋盤其實(shí)可以看成一個(gè)有向圖勋桶，起點(diǎn)為左上角脱衙，終點(diǎn)為右下角，每一點(diǎn)僅僅指向
右側(cè)和下側(cè)例驹。因此我們可以從左上角開始進(jìn)行廣度優(yōu)先遍歷捐韩。此外，遍歷過程中可以
進(jìn)行剪枝鹃锈，最終移動(dòng)到右下角時(shí)會(huì)僅剩下一個(gè)枝荤胁，該路徑所經(jīng)的點(diǎn)的數(shù)值之和即為所求。
package chapter5;
import java.util.LinkedList;
import java.util.Queue;
public class P233_MaxValueOfGifts {
//方法一：動(dòng)態(tài)規(guī)劃
public static int getMaxVaule(int[][] data){
if(data.length==0||data[0].length==0)
return 0;
int[][] dp = new int[2][data[0].length];
int dpCurRowIndex = 0,dpPreRowIndex = 0;
for(int row=0;row<data.length;row++){
dpCurRowIndex = row&1;
dpPreRowIndex = 1 - dpCurRowIndex;
for(int col=0;col<data[0].length;col++){
if(col==0)
dp[dpCurRowIndex][col] = dp[dpPreRowIndex][col]+data[row][col];
else{
if(dp[dpPreRowIndex][col]>=dp[dpCurRowIndex][col-1])
dp[dpCurRowIndex][col] = dp[dpPreRowIndex][col]+data[row][col];
else
dp[dpCurRowIndex][col] = dp[dpCurRowIndex][col-1]+data[row][col];
}
}
}
return dp[(data.length-1)&1][data[0].length-1];
}
//方法二：有向圖的遍歷（廣度優(yōu)先屎债，可再剪枝進(jìn)行優(yōu)化）
public static int getMaxVaule2(int[][] data){
if(data.length==0||data[0].length==0)
return 0;
int maxRowIndex = data.length-1;
int maxColIndex = data[0].length-1;
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(0,0,data[0][0]));
Node nodeCur = null;
while (!(queue.peek().row==maxRowIndex && queue.peek().col==maxColIndex)){
nodeCur = queue.poll();
if(nodeCur.row!=maxRowIndex)
queue.offer(new Node(nodeCur.row+1,nodeCur.col,nodeCur.sum+data[nodeCur.row+1][nodeCur.col]));
if(nodeCur.col!=maxColIndex)
queue.offer(new Node(nodeCur.row,nodeCur.col+1,nodeCur.sum+data[nodeCur.row][nodeCur.col+1]));
}
int maxSum = 0,temp = 0;
while (!queue.isEmpty()){
temp = queue.poll().sum;
if(temp>maxSum)
maxSum = temp;
}
return maxSum;
}
public static class Node{
int row;
int col;
int sum;
public Node(int r,int c,int s){
row = r;col = c;sum = s;
}
}
public static void main(String[] args){
int[][] data = {
{1,10,3,8},
{12,2,9,6},
{5,7,4,11},
{3,7,16,5}};
System.out.println(getMaxVaule(data));
System.out.println(getMaxVaule2(data));
}
}
- 最長不含重復(fù)字符的子字符串
題目要求：
輸入一個(gè)字符串（只包含a~z的字符）仅政，求其最長不含重復(fù)字符的子字符串的長度。
例如對(duì)于arabcacfr盆驹，最長不含重復(fù)字符的子字符串為acfr圆丹，長度為4。
解題思路：
動(dòng)態(tài)規(guī)劃召娜。用dp[]記錄狀態(tài)运褪，dp[i]表示以下標(biāo)為i的字符結(jié)尾不包含重復(fù)字符的
最長子字符串長度惊楼。初始化dp[0] = 1玖瘸，求maxdp。每次可以根據(jù)dp的前一個(gè)狀態(tài)
推導(dǎo)出后一個(gè)狀態(tài)檀咙，因此可以省略dp數(shù)組雅倒，使用一個(gè)變量記錄dp值，使用maxdp
記錄最大的dp值弧可。
package chapter5;
public class P236_LongestSubstringWithoutDup {
//動(dòng)態(tài)規(guī)劃
//dp[i]表示以下標(biāo)為i的字符結(jié)尾不包含重復(fù)字符的最長子字符串長度
public static int longestSubstringWithoutDup(String str){
if(str==null || str.length()==0)
return 0;
//dp數(shù)組可以省略蔑匣，因?yàn)橹恍栌涗浨耙晃恢玫膁p值即可
int[] dp = new int[str.length()];
dp[0] = 1;
int maxdp = 1;
for(int dpIndex = 1;dpIndex<dp.length;dpIndex++){
//i最終會(huì)停在重復(fù)字符或者-1的位置,要注意i的結(jié)束條件
int i = dpIndex-1;
for(;i>=dpIndex-dp[dpIndex-1];i--){
if(str.charAt(dpIndex)==str.charAt(i))
break;
}
dp[dpIndex] = dpIndex - i;
if(dp[dpIndex]>maxdp)
maxdp = dp[dpIndex];
}
return maxdp;
}
public static void main(String[] args){
System.out.println(longestSubstringWithoutDup("arabcacfr"));
System.out.println(longestSubstringWithoutDup("abcdefaaa"));
}
}
public class P236_LongestSubstringWithoutDup {
public static void main(String[] args) {
System.out.println(findLongestSubstringLength("arabcacfr")); //4
System.out.println(findLongestSubstringLength("bbb")); //1
System.out.println(findLongestSubstringLength("")); //0
}
private static int findLongestSubstringLength(String string) {
if (string == null || string.equals("")) return 0;
int maxLength = 0;
int curLength = 0;
int[] positions = new int[26];
for (int i = 0; i < positions.length; i++) {
positions[i] = -1; //初始化為-1，負(fù)數(shù)表示沒出現(xiàn)過
}
for (int i = 0; i < string.length(); i++) {
int curChar = string.charAt(i) - 'a';
int prePosition = positions[curChar];
//當(dāng)前字符與它上次出現(xiàn)位置之間的距離
int distance = i - prePosition;
//當(dāng)前字符第一次出現(xiàn)，或者前一個(gè)非重復(fù)子字符串中沒有包含當(dāng)前字符
if (prePosition < 0 || distance > curLength) {
curLength++;
} else {
curLength = distance;
}
positions[curChar] = i; //更新字符出現(xiàn)的位置
//更新最長非重復(fù)子字符串的長度
if (curLength > maxLength) {
maxLength = curLength;
}
}
return maxLength;
}
}
- 丑數(shù)
題目要求：
我們把只包含因子2,3,5的數(shù)成為丑數(shù)裁良。求按照從小到大的順序第1500個(gè)丑數(shù)凿将。1作為第一個(gè)丑數(shù)。
解題思路：
思路1：從1開始遞增价脾，依次判斷每個(gè)數(shù)是否是丑數(shù)牧抵，不夠高效；
思路2：思路1之所以效率低侨把，比較關(guān)鍵的一點(diǎn)是遍歷的每一個(gè)數(shù)字都進(jìn)行丑數(shù)判斷犀变。思路2
不是去判斷丑數(shù)，而是計(jì)算出丑數(shù)：因?yàn)槊總€(gè)丑數(shù)都可以看成是由1去乘以2秋柄、3获枝、5，再乘以
2骇笔、3省店、5而衍生出來的≈├可以用三個(gè)指針指向第一個(gè)丑數(shù)1萨西，三個(gè)指針分別表示乘2，乘3旭旭，乘5谎脯，
將三個(gè)指針計(jì)算出來的最小的丑數(shù)放在數(shù)組中，并將該指針向后移動(dòng)一個(gè)位置持寄。為了得到第
1500個(gè)丑數(shù)源梭，需要一個(gè)長度1500的數(shù)組來記錄已經(jīng)計(jì)算出來的丑數(shù)。因此這個(gè)思路也可以說
是用空間換時(shí)間稍味。
package chapter5;
public class P240_GetUglyNumber {
public static int getUglyNumber(int num){
if(num<=0)
return 0;
int number = 0,uglyFound = 0;
while (uglyFound<num){
number++;
if(isUgly(number))
uglyFound++;
}
return number;
}
public static boolean isUgly(int number){
while (number%2==0)
number/=2;
while (number%3==0)
number/=3;
while (number%5==0)
number/=5;
return number==1;
}
//獲取從1開始的第num個(gè)丑數(shù)
public static int getUglyNumber2(int num){
int[] uglyNumber = new int[num];
uglyNumber[0] = 1;
int uglyIndex=0, multiply2=0, multiply3=0, multiply5=0;
while (uglyIndex+1<num){
uglyNumber[++uglyIndex] = min(uglyNumber[multiply2]*2,uglyNumber[multiply3]*3,uglyNumber[multiply5]*5);
//2*3=6废麻，3*2=6，會(huì)有重復(fù)值模庐，因此下面需要使用if烛愧，而不能用if-else
if(uglyNumber[multiply2]*2==uglyNumber[uglyIndex])
multiply2++;
if(uglyNumber[multiply3]*3==uglyNumber[uglyIndex])
multiply3++;
if(uglyNumber[multiply5]*5==uglyNumber[uglyIndex])
multiply5++;
}
return uglyNumber[num-1];
}
public static int min(int x,int y,int z){
int temp = x<y?x:y;
return temp<z?temp:z;
}
public static void main(String[] args){
System.out.println(getUglyNumber(10));
System.out.println(getUglyNumber2(10));
}
}
- 第一個(gè)只出現(xiàn)一次的字符
題目要求：
字符串中第一個(gè)只出現(xiàn)一次的字符。在字符串中找出第一個(gè)只出現(xiàn)一次的字符掂碱。
如輸入abaccdeff怜姿，則輸出b。
解題思路：
思路1：暴力求解疼燥，從前到后依次判斷每個(gè)字符是否只出現(xiàn)一次沧卢，時(shí)間復(fù)雜度
o(n^2)，空間復(fù)雜度o(1)醉者；
思路2：用空間換時(shí)間但狭。這個(gè)思路可行的前提是題目中所說的“字符”指的是ascii編碼的字符披诗。
0-127是7位ASCII碼的范圍，是國際標(biāo)準(zhǔn)立磁。128-255稱為擴(kuò)展ASCII碼呈队，不是國際標(biāo)準(zhǔn)。在C++
中唱歧，char是1字節(jié)（8bit）掂咒，能表示256個(gè)不同的字符。而java中迈喉，char是unicode編碼绍刮，2字
節(jié)（16bit）。但本題中挨摸，假設(shè)所有字符都可用ascii表示（0-255）孩革。
在上述假設(shè)下，可以申請(qǐng)一個(gè)長度為256的int數(shù)組作為哈希表得运，占用空間1kB膝蜈，用它來記錄字
符出現(xiàn)的次數(shù)。第一掃描字符串熔掺，修改對(duì)應(yīng)字符的次數(shù)饱搏；第二遍掃描，當(dāng)遇到在數(shù)組中對(duì)應(yīng)值
為1的字符置逻，即得到所求推沸，時(shí)間復(fù)雜度o(n)。
package chapter5;
public class P243_FirstNotRepeatingChar {
//暴力求解券坞，時(shí)間復(fù)雜度o(n^2),空間復(fù)雜度o(1)
public static char firstNotRepeatingChar(String str){
//此處鬓催，\77表示ascii為77的字符(即?),用于表征沒有只出現(xiàn)一次的字符
if(str==null||str.length()==0)
return '\77';
for(int i=0;i<str.length()-1;i++){
char temp = str.charAt(i);
for(int j=0;j<=str.length();j++){
if(j==i)
continue;
if(j==str.length())
return temp;
if(temp==str.charAt(j))
break;
}
}
return '\77';
}
//引入哈希表，用空間換時(shí)間恨锚。時(shí)間復(fù)雜度o(n),空間占用1kB
public static char firstNotRepeatingChar2(String str){
//使用這個(gè)數(shù)組記錄字符出現(xiàn)次數(shù)
int[] times = new int[256];
for(int i=0;i<str.length();i++)
times[str.charAt(i)]++;
for(int i=0;i<str.length();i++){
if(times[str.charAt(i)]==1)
return str.charAt(i);
}
return '\77';
}
public static void main(String[] args){
System.out.println(firstNotRepeatingChar("abaccdeff"));
System.out.println(firstNotRepeatingChar2("abaccdeff"));
}
}
50.2：字符流中第一個(gè)只出現(xiàn)一次的字符
題目要求：
找出字符流中第一個(gè)只出現(xiàn)一次的字符宇驾。例如，當(dāng)從字符流google中只讀出前兩個(gè)字符go時(shí)猴伶，
第一個(gè)只出現(xiàn)一次的字符是g课舍；當(dāng)讀完google時(shí)，第一個(gè)只出現(xiàn)一次的字符是l他挎。
解題思路：
此題的關(guān)鍵在于“字符流”筝尾。因此最好能夠記住在哪個(gè)位置出現(xiàn)了哪個(gè)字符，從而可以完成每讀
到一個(gè)字符雇盖，就能動(dòng)態(tài)更新到目前為止第一個(gè)出現(xiàn)一次的字符忿等。此題同樣使用了長度為256的
int數(shù)組作為哈希表栖忠，用字符的ascii碼值作為表的鍵值崔挖，當(dāng)字符僅出現(xiàn)了一次贸街，就把字符的
位置作為哈希表的值，如果沒有出現(xiàn)則值為-1狸相，如果出現(xiàn)的次數(shù)大于1則哈希表對(duì)應(yīng)的值為-2薛匪。
當(dāng)想要知道到某一位置時(shí)第一個(gè)出現(xiàn)一次的字符，可以通過掃描該哈希表脓鹃，找到大于等于0的
值中的最小值逸尖，該值所對(duì)應(yīng)的字符就是當(dāng)前狀態(tài)第一個(gè)出現(xiàn)一次的字符。
public class P247_FirstNotRepeatingCharInStream {
public static class CharStatistics{
private int[] times;
private int index;
public CharStatistics(){
index = 0;
times = new int[256];
//-1表示未出現(xiàn)瘸右，>=0表示出現(xiàn)的位置且僅出現(xiàn)一次娇跟，-2表示出現(xiàn)兩次及以上
for(int i=0;i<256;i++)
times[i] = -1;
}
public void insert(char ch){
if(times[ch]==-1)
times[ch] = index;
else
times[ch] = -2;
index++;
}
public char find(){
int minIndex = 256;
char ret = '\77'; //若沒有只出現(xiàn)一次的字符，顯示\77太颤，即苞俘？
for(int i=0;i<256;i++){
if(times[i]>=0 && times[i]<minIndex) {
minIndex = times[i];
ret = (char)i;
}
}
return ret;
}
}
public static void main(String[] args){
String str = "google";
CharStatistics charStatistics = new CharStatistics();
for(int i=0;i<str.length();i++){
charStatistics.insert(str.charAt(i));
System.out.print(charStatistics.find());
}
}
}
