題目來自LeetCode

文章目錄

全部章節

1-18題

19-40題

41-60題

61-80題

81-100題

101-120題

121-140題

1.兩數之和

2.兩數相加

3.無重復字符串的最長子串

4.尋找兩個有序數組的中位數

5.最長回文子串

6.Z 字形變換

7.整數反轉

8.字符串轉換整數 (atoi)

9.回文數

10.正則表達式匹配

11.盛最多水的容器

12.整數轉羅馬數字

13.羅馬數字轉整數

14.最長公共前綴

15.三數之和

16.最接近的三數之和

17.電話號碼的字母組合

18. 四數之和

全部章節

1-18題

19-40題

41-60題

61-80題

81-100題

101-120題

121-140題

1.兩數之和

給定一個整數數組nums和一個目標值target，請你在該數組中找出和為目標值的那兩個整數，并返回他們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數組中同樣的元素。

示例:

解答：

private static int[] twoSum(int[] nums, int target) {

int[] indexs = new int[2];

Map map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {

if (map.containsKey(nums[i])) {

indexs[0] = i;

indexs[1] = map.get(nums[i]);

return indexs;

}

map.put(target - nums[i], i);

}

return indexs;

}

分析：

1.需要1個長度為2的數組來保存符合條件的組合下標。

2.因為所有的數值只能使用一次，那么就需要記錄下每一個數與目標數值的差，以及它的下標。可以利用HashMap來實現。差作為key，下標作為value。

過程：

只需要一層循環遍歷HashMap中是否包含原給定數組中的數值，若有，則記錄下該數值的下標，以及此時HashMap中該數值的所對應的value，這個value就是滿足條件的另一個原給定數組中的數值所對應的下標。

若沒有，則將目標值減去該數值的結果作為key，該數值的下標作為value添加到HashMap中。

2.兩數相加

給出兩個非空的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，并且它們的每個節點只能存儲一位數字。

如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。

您可以假設除了數字0之外，這兩個數都不會以0開頭。

示例：

解答：

private ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode root = new ListNode(0);

ListNode cursor = root;

int carry = 0;

while (l1 != null || l2 != null || carry != 0) {

int l1Val = l1 != null ? l1.val : 0;

int l2Val = l2 != null ? l2.val : 0;

int sumVal = l1Val + l2Val + carry;

carry = sumVal / 10;

ListNode sumNode = new ListNode(sumVal % 10);

cursor.next = sumNode;

cursor = sumNode;

if (l1 != null) l1 = l1.next;

if (l2 != null) l2 = l2.next;

}

return root.next;

}

分析：

1.為了保存兩數相加的結果新建一個頭結點root與尾指針cursor，初始指向頭結點。

2.設置一個進位標示位carry，初始位0，用于記錄是否進位。

3.循環條件判斷：初始給定的兩個鏈表若有一條沒遍歷結束，或者進位標示位不為0。

過程：

根據循環條件判斷是否繼續執行，判斷此時鏈表1與鏈表2是否為空，若為空則此時的值為0，若不為空，則記錄該值分別為l1val與l2val，將l1val、l2val、carry相加。判斷是否進位，若進位carry=1，否則=0。新建一個結點，將求和值除以10的余數記錄下來。使用尾插法，將該結點插入到尾指針所指向指針的后面。更新尾指針的位置。最后返回頭結點之后的鏈表即為結果。

3.無重復字符串的最長子串

給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。

示例 1:

示例 2:

示例 3:

解答：

private static int lengthOfLongestSubstring(String s) {

int maxLength = 0;

char[] chars = s.toCharArray();

int leftIndex = 0;

for (int j = 0; j < chars.length; j++) {

for (int innerIndex = leftIndex; innerIndex < j; innerIndex++) {

if (chars[innerIndex] == chars[j]) {

maxLength = Math.max(maxLength, j - leftIndex);

leftIndex = innerIndex + 1;

break;

}

}

}

return Math.max(chars.length - leftIndex, maxLength);

}

分析

1.需要一個最長記錄標示，初始為0

2.將字符串轉成字符數組

3.用于標記已找到最長子串，不用再判斷該標記之前的部分。

過程

外層循環從0到字符串長度，用于從固定長度的字符串中找出最長的不重復的子串。

內層循環從標記位開始到此次外層循環限定的長度，判斷這個范圍內的最長子串。因為外層循環是逐一擴大的，所以只需要判斷內層循環中的字符與外層循環限定的那個位置的字符是否相同，即可判斷出字符串是否有重復。若有重復的字符出現，記錄此時的長度 j(外層循環限定位置)-leftIndex(標志位)。判斷此時的長度與最大記錄的長度，保留最大者。修改標志位leftIndex=出現重復字符串的位置innerIndex+1。結束內層循環。

直到外層循環結束。判斷 (字符串長度-標志位)與記錄的最大長度的大小。返回較大者即為結果。

4.尋找兩個有序數組的中位數

給定兩個大小為m和n的有序數組nums1和nums2。

請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為 O(log(m + n))。

你可以假設nums1和nums2不會同時為空。

示例1

示例2

解答

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int m = nums1.length;

int n = nums2.length;

int left = (m + n + 1) / 2;

int right = (m + n + 2) / 2;

return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;

}

public int findKth(int[] nums1, int i, int[] nums2, int j, int k) {

if (i >= nums1.length) return nums2[j + k - 1];

if (j >= nums2.length) return nums1[i + k - 1];

if (k == 1) {

return Math.min(nums1[i], nums2[j]);

}

int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;

int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;

if (midVal1 < midVal2) {

return findKth(nums1, i + k / 2, nums2, j, k - k / 2);

} else {

return findKth(nums1, i, nums2, j + k / 2, k - k / 2);

}

}

分析

1.數組長度為奇數，則中位數是最中間的值；為偶數，則是最中間兩個值相加/2。

2.考慮到時間復雜度的要求，使用二分查找法。

3.因為不確定奇數還是偶數，所以求兩個第k個值的平均數。初始兩個k分別設為(m+n+1)/2 與 (m+n+2)/2。若m+n為奇數，則兩個k相同，相加求平均等于自身；若m+n為偶數，則兩個k不相同，即為最中間的兩個數求平均。

4.難點在于如何求第k個值，具體看下面過程。

過程

尋找第k個值的方法參數一共5個：

int[] nums1, int i, int[] nums2, int j, int k

分別表示第一個數組，第一個數組起始搜索位置，第二個數組，第二個數組起始搜索位置，要尋找的目標第k個。

首先判斷第一個數組的起始位置是否超過數組長度，若超出則不需要考慮第一個數組，直接返回第二個數組中下標為 j+k-1 的數值，即為要找的第k個。減1是因為數組的下標起始是0不是1。

同理判斷第二個數組的起始位置是否超過數組長度，若超過則不需要考慮第二個數組，直接返回第二個數組中下標為 i+j-1 的數值。

然后分別計算兩個數組中第k/2個值的大小，記錄為midval1與midval2。數組不存在第k/2數值，則設置為無限大。比較midval1midval2的大小，若midval1小，則說明數組1中前k/2個數值中沒有要找的那個數字。

遞歸調用此方法，更新參數 數組1中的起始位置為 i + k/2，k的值更新為 k-k/2。

同理若midval2小，則遞歸調用此方法，更新參數 數組2中的起始位置為 j + k/2，k的值更新為 k-k/2

遞歸出口還缺一個，當k = 1時，則返回兩個數組起始位置的值中較小的那一個。

5.最長回文子串

給定一個字符串s，找到s中最長的回文子串。你可以假設s的最大長度為1000。

示例1:

示例2:

解答

public String longestPalindrome(String s) {

if (s == null || s.length() == 0)

return "";

if (s.length() == 1)

return s;

int size = s.length();

int maxLen = 1;

int start = 0;

int[][] memo = new int[size][size];

char[] chars = s.toCharArray();

for (int i = 0; i < size; i++) {

memo[i][i] = 1;

if (i < size - 1 && chars[i] == chars[i + 1]) {

memo[i][i + 1] = 1;

start = i;

maxLen = 2;

}

}

for (int L = 3; L <= size; L++) {

for (int i = 0; i + L - 1 < size; i++) {

int j = L + i - 1;

if (chars[i] == chars[j] && memo[i + 1][j - 1] == 1) {

memo[i][j] = 1;

start = i;

maxLen = L;

}

}

}

return s.substring(start, start + maxLen);

}

分析

1.理解回文的意思，一個字符串正序讀與反序讀結果是一樣的稱為回文字符串。

2.采用DP的思想將復雜的問題分解成許多子問題。利用一張表來記錄之前問題的結果。

3.一個長的字符串直接很難判斷出最長的回文子串，可以縮小范圍，限定字符串的長度，再小范圍內找最長回文子串是容易的。并且回文子串(長度大于2)去掉收尾也一定是一個回文子串。

過程

首先求得給出字符串的長度size，設置maxLen標示，用于記錄最長回文子串的長度，回文子串的起始位置為0，創建大小為size*size的數組，用于記錄解決的子問題。

第一個for循環就是解決的最小的子問題，尋找長度為2的回文子串。memo[i][i]=1，是因為一個字符屬于長度為1的回文子串。若有相鄰字符一致，說明找到長度為2的回文子串，將其位置記錄在二維數組中，memo[i][i + 1] = 1;記錄該回文子串的起始位置與長度。

第二個兩層循環用于解決長度為3到給定字符串長度范圍內的最長回文子串。外層循環從L=3開始，因為長度為2的問題在前一個循環中已經解決。內層循環從字符串起始位置0開始。設 j = L + i - 1 ，表示長度為L，起始位置為i的字符串最末尾的字符的位置。判斷長度為L的字符串收尾是否一致chars[i] == chars[j]，若一致并且其去掉收尾滿足回文子串(memo[i + 1][j - 1] == 1)，則說明找到更長的回文子串。此時在二維數組中記錄找到回文子串的位置(memo[i][j] = 1)，記錄該子串的起始位置與長度。

循環結束后即可得到最長回文子串的起始位置與最大的長度。

6.Z 字形變換

將一個給定字符串根據給定的行數，以從上往下、從左到右進行Z字形排列。

比如輸入字符串為"LEETCODEISHIRING"行數為3時，排列如下：

之后，你的輸出需要從左往右逐行讀取，產生出一個新的字符串，比如：“LCIRETOESIIGEDHN”。

請你實現這個將字符串進行指定行數變換的函數：

示例1:

示例2:

解答

public static String convert(String s, int numRows) {

char[] chars = s.toCharArray();

if (numRows == 1)

return s;

int step = numRows * 2 - 2;

StringBuffer buffer = new StringBuffer();

for (int i = 0; i < s.length(); i += step)

buffer.append(chars[i]);

for (int i = 1; i < numRows - 1; i++) {

for (int j = i; j < s.length(); ) {

buffer.append(chars[j]);

j += ((numRows - i) * 2 - 2);

if (j < s.length()) {

buffer.append(chars[j]);

j += 2 * i;

}

}

}

for (int i = numRows - 1; i < s.length(); i += step)

buffer.append(chars[i]);

return buffer.toString();

}

分析：

1.這是一道找規律的題目，按照輸出順序畫圖尋找規律，可以發現第一行與最后一行相同的規律，間隔numRows * 2 - 2，中間行是相同的規律。

2.使用StringBuffer效率上更快

過程：

按照尋找出的規律先添加第一行再添加中間行最后是添加最后一行，即可得到結果。此題比較簡單。

7.整數反轉

給出一個32位的有符號整數，你需要將這個整數中每位上的數字進行反轉。

示例1:

示例2:

示例3:

解答

public int reverse(int x) {

long n = 0;

while(x != 0) {

n = n*10 + x%10;

x = x/10;

}

return (int)n==n? (int)n:0;

}

分析

1.限制了整數的位數32位，所以用long來接收整數反轉的結果，java中int是4個字節，long是8個字節。

2.區分好“%”與“/”的差別。

3.長字符轉短字符會有數據丟失

過程

設置一個類型為long的標志n來接收答案，每次將n擴大10倍留出個位數的位置，個位數就等于給定整數x除10取余數，再將x除以10，相當于去掉最后一位的數字。循環直到x等于0。

8.字符串轉換整數 (atoi)

請你來實現一個 atoi 函數，使其能將字符串轉換成整數。

首先，該函數會根據需要丟棄無用的開頭空格字符，直到尋找到第一個非空格的字符為止。

當我們尋找到的第一個非空字符為正或者負號時，則將該符號與之后面盡可能多的連續數字組合起來，作為該整數的正負號；假如第一個非空字符是數字，則直接將其與之后連續的數字字符組合起來，形成整數。

該字符串除了有效的整數部分之后也可能會存在多余的字符，這些字符可以被忽略，它們對于函數不應該造成影響。

注意：假如該字符串中的第一個非空格字符不是一個有效整數字符、字符串為空或字符串僅包含空白字符時，則你的函數不需要進行轉換。

在任何情況下，若函數不能進行有效的轉換時，請返回 0。

說明：

假設我們的環境只能存儲 32 位大小的有符號整數，那么其數值范圍為 [?231, 231 ? 1]。如果數值超過這個范圍，請返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。

示例1：

示例2:

示例3:

示例4:

示例5:

解答

public static int myAtoi(String str) {

long res = 0;

boolean flag = true;

int f = -1;

char[] c = str.toCharArray();

for (int i = 0; i < c.length; i++) {

if (f == -1 && (c[i] == '-' || c[i] == '+')) {

flag = c[i] == '-' ? false : true;

f = 1;

} else if (Character.isDigit(c[i])) {

res = res * 10 + (c[i] - '0');

if (res > Integer.MAX_VALUE) {

if (!flag) return Integer.MIN_VALUE;

return Integer.MAX_VALUE;

}

f = 1;

} else if (c[i] >= 32) {

if (f == -1 && c[i] == ' ') continue;

break;

}

}

return flag == true ? (int) res : (int) -res;

}

分析

1.此題根據給出的例子編寫、修改程序即可

2.設置一個標示位，用來說明正負數

3.需要使用long類型來接收截取到的數據，防止溢出

4.java中char類型與int類型的比較是根據ASCII表進行的。參考表下面給出。

5.java中char類型與int類型的轉換：

int類型轉char類型，將數字加一個’0’

char類型轉int類型，將數字減一個’0’

ASCII表如下：

過程

準備工作，將字符串轉char數組，設置一個正負數標示位，確認是否是數字的標示位，以及用于接收答案的long類型的數據。

開始遍歷轉換后的char數組，判斷是否有正負號存在，如果有則修改正負數標示位，并將數字標示位置1。如果沒有進入下一個if判斷，是否是數字，如果是則接收這一位，(利用char轉int的方式再結合已得到的答案)，接收完后判斷是否越界，之后將數字標示位置1。如果不是數字則進入下一個if判斷，因為空格對應的ASCII碼是32，其他字母也均大于32，所以判斷該位字符是否大于32，如果大于32，繼續判斷，如果該字符是空格，并還未找到數字，則跳過此次循環進入下一輪循環，若不滿足此條件則結束遍歷。

最后根據正負數標示位來返回所要的答案。

9.回文數

判斷一個整數是否是回文數。回文數是指正序(從左向右)和倒序(從右向左)讀都是一樣的整數。

示例1:

示例2:

示例3:

解答

public boolean isPalindrome(int x) {

String s = "" + x;

char[] chars = s.toCharArray();

int len = chars.length;

for (int i = 0; i < len / 2; i++) {

if (chars[i] != chars[len - i - 1])

return false;

}

return true;

}

public boolean isPalindromeTwo(int x) {

int a = x;

if (x < 0) {

return false;

}

if (x < 10) {

return true;

}

if (x % 10 == 0) {

return false;

}

int t = 0;

while (x > 0) {

t = t * 10 + x % 10;

x /= 10;

}

return t == a;

}

分析：

1.相比較之前的尋找最長回文子串簡單很多。

2.想法1比較收尾是否一致。

3.想法2小于0的整數不用管，0-9的整數必定是回文數，個位數為0的必定不是回文數，除此之外的數字倒轉與原數字比較即可。

過程：

略

10.正則表達式匹配

給你一個字符串 s 和一個字符規律 p，請你來實現一個支持 ‘.’ 和 ‘*’ 的正則表達式匹配。

‘.’ 匹配任意單個字符

‘*’ 匹配零個或多個前面的那一個元素

所謂匹配，是要涵蓋 整個 字符串 s的，而不是部分字符串。

說明:

s 可能為空，且只包含從 a-z 的小寫字母。

p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *。

示例1:

示例2:

示例3:

示例4:

示例5:

解答

public boolean isMatch(String s, String p) {

if(s==null || p==null)return false;

char[] sc=s.toCharArray();

char[] pc=p.toCharArray();

return dp(sc,pc,0,0);

}

boolean dp(char[] s,char[] p,int i,int j){

int n=s.length;

int m=p.length;

if(j>=m) return i==n;

boolean j_match=i

if(j+1

return dp(s,p,i,j+2)||(j_match &&dp(s,p,i+1,j));

}

return j_match && dp(s,p,i+1,j+1);

}

分析

1.重點是兩條匹配規則，’.‘代表任意字符，理解為a-z均可匹配；’'匹配之前的任意多個之前的一個字符。相當于復制任意份，可以是0。例如a，則可以表示“”或“aa”或“aaaaaa”任意多個a。

2.重點是如何匹配第二條規則。拆解第二條規則則就兩種情況，要么匹配0個，要么匹配多個，匹配多個則可以先考慮匹配一個，利用遞歸來匹配接下來的。

過程

將字符串轉數組，起始比較位置從每個數組下標“0”開始。首先判斷第一個字符的匹配結果。接著if判斷p規則數組的下一位是否是 “ * ” 號，如果是則根據 “ * ” 規則，第一種情況匹配0個，則i不變，即待匹配數組不變，j+2，則說明從符號 “ * ” 之后開始與待匹配數組匹配，遞歸調用dp方法繼續匹配；第二種情況是匹配任意個，因為不確定匹配多少個，所以i+1，j不變，表示匹配到一位字符，遞歸調用dp方法匹配之后的字符。第二種情況要考慮到第一個字符匹配的結果是否一致，如果一致，則就是要看之后還有多少個相同的字符匹配。

若不滿足if條件則遞歸調用匹配兩個數字各自的下一位，結合上第一個字符匹配的結果。

還要考慮一個問題，若規則數組的起始位置已經超出了規則數組的長度，則直接返回待匹配數組的起始位置是否與其長度一致即可。

11.盛最多水的容器

給定 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

說明：你不能傾斜容器，且 n 的值至少為 2。

圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水(表示為藍色部分)的最大值為 49。

示例：

解答

public int maxArea(int[] height) {

int left = 0;

int right = height.length - 1;

int res = 0;

if (height.length < 2)

return -1;

while (left < right) {

res = Math.max(res, Math.min(height[left], height[right]) * (right - left));

if (height[left] < height[right])

left++;

else right--;

}

return res;

}

分析

1.此題最簡單無腦的解法用暴力解決。

2.也可以使用動態規劃的思想，比較已知解與變更狀態后的解。而這里狀態的變更就是垂線位置的改變。

3.可以先設置兩個變量表示數組的開始與結尾。根據Math.min(height[left], height[right]) * (right - left)

可以求得第一個解，接下來就要考慮垂線如何移動。很顯然一個容器能裝多少的水取決于底部長度與較短一端有關。因為一開始已經將底部設置最大，若要改變垂線，那么底部長度是必然減小的，所以要盡量的使垂線更長，比較height[left]，height[right]，選擇短的一端向另一端移動。

過程

設置變量left指向數組下標0的位置，right指向數組末尾。因為要求的n至少為2，所以要判斷給的數組是否滿足長度大于2。接下來就是計算最大的面積。面積等于Math.max(res, Math.min(height[left], height[right]) * (right - left))，根據上面分析的3更新left/right。直到循環結束。

12.整數轉羅馬數字

羅馬數字包含以下七種字符： I， V， X， L，C，D 和 M。

字符 數值

I 1

V 5

X 10

L 50

C 100

D 500

M 1000

例如， 羅馬數字 2 寫做 II ，即為兩個并列的 1。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 。

通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等于大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。這個特殊的規則只適用于以下六種情況：

I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。

X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90。

C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900。

給定一個整數，將其轉為羅馬數字。輸入確保在 1 到 3999 的范圍內。

示例1:

示例2:

示例3:

示例4:

示例5:

解答

public String intToRoman(int num) {

int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

String[] m = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

StringBuilder builder = new StringBuilder();

for (int i = 0; i < 13; i++) {

while (num >= values[i]){

num -= values[i];

builder.append(m[i]);

}

}

return builder.toString();

}

分析

1.因為判斷的條件很多，情況也很多種，所以可以事先將所有的判斷要用到的條件以及情況都先保存在數組中。

2.StringBuilder效率更高。

過程

準備好情況與條件判斷所需的數據，開始遍歷，一共13種情況，在每一次的迭代中，判斷更新答案即可。此題較為簡單。

13.羅馬數字轉整數

羅馬數字包含以下七種字符: I， V， X， L，C，D 和 M。

字符 數值

I 1

V 5

X 10

L 50

C 100

D 500

M 1000

例如， 羅馬數字 2 寫做 II ，即為兩個并列的 1。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 。

通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等于大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。這個特殊的規則只適用于以下六種情況：

I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。

X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90。

C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900。

給定一個羅馬數字，將其轉換成整數。輸入確保在 1 到 3999 的范圍內。

示例1:

示例2:

示例3:

示例4:

示例5:

解答

public static int romanToInt(String s) {

int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

String[] m = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

HashMap map = new HashMap<>();

for (int i = 0; i < 13; i++) {

map.put(m[i], values[i]);

}

char[] chars = s.toCharArray();

int res = 0;

int i = 0;

while (i < chars.length) {

if (i + 1 < chars.length)

if (map.containsKey("" + chars[i] + chars[i + 1])) {

res += map.get("" + chars[i] + chars[i + 1]);

i += 2;

continue;

}

if (map.containsKey("" + chars[i])) {

res += map.get("" + chars[i]);

i++;

}

}

return res;

}

分析

1.將不同的符號與數值映射，保存在hashmap中

2.遍歷字符串字符，找到hashmap中存在的符號，進行結果疊加。

過程

準備工作，將13種情況的字符與數值映射關系保存在hashmap中，字符串轉為字符數組。從頭開始遍歷字符數組，找到在hashmap中存在的key，將對應的value加到答案中。直到遍歷結束。

14.最長公共前綴

編寫一個函數來查找字符串數組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 “”。

示例1:

示例2:

解答

public String longestCommonPrefix(String[] strs) {

if (strs == null || strs.length == 0 ) return "";

String reg = strs[0];

for (String str : strs){

while (!str.startsWith(reg)) {

if (reg.length() == 1) {

return "";

}

reg = reg.substring(0, reg.length()-1);

}

}

return reg;

}

分析：

1.以第一個詞作為前綴的標準

2.遍歷字符串數組中的字符串，比較字符串前綴是否相同，修改前綴。

過程：

首先判斷字符串數組是否為空，若空則返回”“。將數組中第一個字符串作為當作最長前綴。遍歷數組中的字符串，判斷字符串前綴是否與已知最長前綴相同，若前綴的第一個字符都不相同，則返回””，若前綴不同則逐一縮小最長前綴。直到遍歷結束，返回最長前綴。

15.三數之和

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組。

注意：答案中不可以包含重復的三元組。

示例：

解答

public static List> threeSum(int[] nums) {

Arrays.sort(nums);

List> result = new ArrayList<>();

for (int i = 0; i < nums.length - 2; i++) {

if (i > 0 && nums[i] == nums[i - 1]) {

continue;

}

int left = i + 1, right = nums.length - 1;

if (nums[i] + nums[left] + nums[left + 1] > 0 || nums[i] + nums[right] + nums[right - 1] < 0) {

continue;

}

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {

List triple = new ArrayList<>();

triple.add(nums[i]);

triple.add(nums[left]);

triple.add(nums[right]);

result.add(triple);

while (left < --right && nums[right] == nums[right + 1]) ;

while (++left < right && nums[left] == nums[left - 1]) ;

} else if (sum > 0) {

right--;

} else {

left++;

}

}

}

return result;

}

分析

1.先對數組進行排序，有序的數組更方便操作。

2.考慮是3個數字相加，可以先固定一個數字，變更其他兩個數字。因為數組有序化，可以設置兩個變量分別指向固定數字的后一位以及數組的末尾。

3.因為不能有重復的數字出現，所以第一步的有序就更凸顯出它的用途。排序后的數組，相同的數字必定是相鄰的，可以方便的直接掉過相同的數字。

過程

首先將數組排序，新建一個List用于接收答案。

選擇固定一個數字進行遍歷，因為每次是三個數字相加，所以只需要考慮前n-2個數字作為基準。

每一次的循環，先判斷是否與前一位相同，若相同則跳過這一個數字。設置兩個變量指向當前基準數字的后一位(left)與數組的最后一位(right)。

因為數組是有序排列的。若基準數字加它之后的兩位的和大于0，則不用考慮之后的數字組合，因為之后的數字組合必定大于0;同理基準數字加最后倒數兩個數字的和若小于0，則不用考慮之前的數字組合，必定小于0。

接下來確定好了基準數字后，根據基準數字與其他兩個數字的和變更left與right變量。

若三者之和等于0，則將組合添加到答案中。此時根據left與后一個數字是否相同以及right與其前一位是否相同修改這兩個變量。因為不能有重復數字的組合。

若三者之和大于0，則說明太大了，right指向末尾較大數字一端的變量減一。若三者之和小于0，則left變量加一。

直到left = right。此時該基準數字所有滿足條件的組合已找到，進入下一次循環，基準數字更換繼續尋找組合。

循環結束后，即可求得答案。

16.最接近的三數之和

給定一個包括 n 個整數的數組 nums 和 一個目標值 target。找出 nums 中的三個整數，使得它們的和與 target 最接近。返回這三個數的和。假定每組輸入只存在唯一答案。

例如，給定數組 nums = [-1，2，1，-4], 和 target = 1.

與 target 最接近的三個數的和為 2. (-1 + 2 + 1 = 2).

解答

public int threeSumClosest(int[] nums, int target) {

Arrays.sort(nums);

int res = nums[0] + nums[1] + nums[2];

for (int i = 0; i < nums.length - 2; i++) {

int left = i + 1, right = nums.length - 1;

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];

if (sum == target) return sum;

if (Math.abs(sum - target) < Math.abs(res - target))

res = sum;

if(sum > target)right--;

else left++;

}

}

return res;

}

分析

1.與上一題很相似甚至更簡單了，只需要找到與目標最近的組合。

2.同樣是固定一個數字，更改另外兩個數字。與上題一樣。

3.res接收與答案最接近的和。

過程

首先對數組進行排序，設置一個變量用來保存已經找到的最接近目標的數字組合的和。開始遍歷，固定一個數字，更改另外兩個數字，與上一題的過程類似。若找到的組合結果已經等于目標值則返回目標值。若組合結果距離原先已有答案的結果更接近目標，則更新答案。

如果組合的和大于目標，則高位標示位向低位移動一位，反之則低位向高位移動一位。直到循環結束。

17.電話號碼的字母組合

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。

給出數字到字母的映射如下(與電話按鍵相同)。注意 1 不對應任何字母。

示例：

解答

static Map digitsMap = new HashMap() {{

put("2", "abc");

put("3", "def");

put("4", "ghi");

put("5", "jkl");

put("6", "mno");

put("7", "pqrs");

put("8", "tuv");

put("9", "wxyz");

}};

static List res = new ArrayList();

static StringBuilder tmp = new StringBuilder();

public static List letterCombinations(String digits) {

if (digits == null) return null;

process(digits, 0);

return res;

}

private static void process(String digits, int index) {

if (index == digits.length()) {

res.add(tmp.toString());

return;

}

String letter = digitsMap.get(digits.substring(index, index + 1));

for (int i = 0; i < letter.length(); i++) {

tmp.append(letter, i, i + 1);

process(digits, index + 1);

//去掉添加的字母，開始回溯

tmp.replace(tmp.length() -1, tmp.length(),"");

}

}

分析

1.使用了回朔法，回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇。

2.要求的答案中的字符串長度必定和所給數字的長度是一致的，設置一個index標示位，判斷滿足符合長度的字符串添加的答案中。

3.每次在temp中添加來自不同字符串的一個數字。滿足長度后，去掉添加的字母開始回溯。

過程

首先準備好一個HashMap，保存著數字與字符串的映射關系。需要一個List來接收答案，StringBuilder tmp，用于構造符合條件的字符串。process方法過程，判斷index表示位是否等于數字的長度，若相等則將tmp加入答案中。跳出方法。若不等于，則獲取index下標對應的數字，根據其映射關系得到字符串。遍歷字符串，tmp添加字符，遞歸調用process，是為了從不同的字符串中找組合。最后是去掉添加的字母，開始回溯。

18. 四數之和

給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復的四元組。

注意：

答案中不可以包含重復的四元組。

示例：

解答

public List> fourSum(int[] nums, int target) {

int len = nums.length;

List> res = new ArrayList<>();

if (nums.length < 4) return res;

Arrays.sort(nums);

if (nums[0] > target / 4 || nums[len - 1] < target / 4) return res;

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

if (nums[i] > target / 4) break;

if (i > 0 && nums[i] == nums[i - 1]) continue;

int sum = target - nums[i];

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

if (nums[j] > sum / 3) break;

if (j > i + 1 && nums[j] == nums[j - 1]) continue;

int l = j + 1;

int r = len - 1;

while (l < r) {

if (nums[r] < sum / 3) break;

int temp = nums[j] + nums[l] + nums[r];

if (temp == sum) {

res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));

while (l < r && nums[l] == nums[l + 1]) l++;

while (l < r && nums[r] == nums[r - 1]) r--;

l++;

r--;

} else if (temp > sum) {//結果大了右指針往左

r--;

} else {//結果小了左指針往右

l++;

}

}

}

}

return res;

}

分析

1.此題在三數之和的基礎上多了一個數字，起始只要多一層循環，遍歷數組，將target減去nums[i]作為新的target，之后就和三數之和的過程一致了。

過程

首先將數組排序。判斷最小值是否大于target/4，或最大值是否小于target/4，若滿足則返回空數組。接著遍歷數組，每次選擇一個數字，將target減去這個數字作為新的target，之后就按照3數之和的方式繼續進行即可。

總結

以上是生活随笔為你收集整理的char java 回文_LeetCode刷题笔记（Java）---第1-18题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。