劍指offer：45-48記錄

輸入一個正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)，打印能拼接出的所有數(shù)字中最小的一個。

示例 1:

輸入: [10,2]

輸出: "102"

示例?2:

輸入: [3,30,34,5,9]

輸出: "3033459"

提示:

0 < nums.length <= 100

說明:

輸出結(jié)果可能非常大，所以你需要返回一個字符串而不是整數(shù)

拼接起來的數(shù)字可能會有前導(dǎo) 0，最后結(jié)果不需要去掉前導(dǎo) 0

思路：貪心，具體證明略，其他文章寫過。

class Solution {

public String minNumber(int[] nums) {

List strList = new ArrayList<>();

for (int num : nums) {

strList.add(String.valueOf(num));

}

strList.sort((s1, s2) -> (s1 + s2).compareTo(s2 + s1));

StringBuilder sb = new StringBuilder();

for (String str : strList) {

sb.append(str);

}

return sb.toString();

}

}

給定一個數(shù)字，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” ，1 翻譯成 “b”，……，11 翻譯成 “l(fā)”，……，25 翻譯成 “z”。一個數(shù)字可能有多個翻譯。請編程實現(xiàn)一個函數(shù)，用來計算一個數(shù)字有多少種不同的翻譯方法。

示例 1:

輸入: 12258

輸出: 5

解釋: 12258有5種不同的翻譯，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

字符串dp，看代碼很容易看懂。

注意str.charAt(i - 2) != '0'必須加上，不加的例子：

class Solution {

public int translateNum(int num) {

String str = String.valueOf(num);

int len = str.length();

int[] dp = new int[len + 1];

dp[0] = 1;

for (int i = 1; i < len+1; ++i) {

dp[i] += dp[i-1];

if (i>1 && str.charAt(i - 2) != '0' && str.substring(i - 2, i).compareTo("25") < 1)

dp[i] += dp[i - 2];

}

return dp[len];

}

}

在一個 m*n 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0）。你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格、直到到達(dá)棋盤的右下角。給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？

示例 1:

輸入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

輸出: 12

解釋: 路徑 1→3→5→2→1 可以拿到最多價值的禮物

提示：

0 < grid.length <= 200

0 < grid[0].length <= 200

思路：經(jīng)典dp，來一個超級標(biāo)準(zhǔn)的不壓縮空間的一看就懂的寫法吧。

class Solution {

public int maxValue(int[][] grid) {

if (grid.length == 0 )

return 0 ;

int[][] dp = new int[grid.length][grid[0].length] ;

dp[0][0] = grid[0][0] ;

for (int i=1 ; i

dp[i][0] = grid[i][0]+ dp[i-1][0] ;

}

for (int j=1 ; j

dp[0][j] = grid[0][j] + dp[0][j-1] ;

}

for (int i=1 ; i< grid.length ; i++) {

for (int j=1 ; j < grid[0].length ; j++) {

dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j] ;

}

}

return dp[grid.length-1][grid[0].length-1] ;

}

}

請從字符串中找出一個最長的不包含重復(fù)字符的子字符串，計算該最長子字符串的長度。

示例?1:

輸入: "abcabcbb"

輸出: 3

解釋: 因為無重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: "bbbbb"

輸出: 1

解釋: 因為無重復(fù)字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: "pwwkew"

輸出: 3

解釋: 因為無重復(fù)字符的最長子串是?"wke"，所以其長度為 3。

請注意，你的答案必須是 子串 的長度，"pwke"?是一個子序列，不是子串。

提示：

s.length <= 40000

滑動窗口的維護(hù)五花八門：

for循環(huán)往右擴(kuò)，左端點起輔助作用，保證窗口符合要求：

class Solution {

public int lengthOfLongestSubstring(String s) {

int res = 0;

Set set = new HashSet<>();

for(int l = 0, r = 0; r < s.length(); r++) {

char c = s.charAt(r);

while(set.contains(c)) {

set.remove(s.charAt(l++));

}

set.add(c);

res = Math.max(res, r - l + 1);

}

return res;

}

}

機器翻譯

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。