-
從尾到頭打印鏈表
輸入一個鏈表的頭節(jié)點，從尾到頭反過來返回每個節(jié)點的值（用數(shù)組返回）吉挣。
示例 1：
輸入：head = [1,3,2] 輸出：[2,3,1]分析：可以首先遍歷一次鏈表崖蜜，獲得鏈表的長度，創(chuàng)建一個相同長度的數(shù)組，然后再從頭到尾遍歷一次苟鸯，從數(shù)組的尾部開始添加元素。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int[] reversePrint(ListNode head) { //先獲取鏈表長度棚点，創(chuàng)建對應(yīng)長度數(shù)組 ListNode currNode = head; int len = 0; while(currNode != null){ len ++; currNode = currNode.next; } int[] result = new int[len]; //再次遍歷鏈表早处，將值倒序填充至結(jié)果數(shù)組 currNode = head; while(currNode != null){ result[len - 1] = currNode.val; len --; currNode = currNode.next; } return result; } } -
二維數(shù)組的查找
在一個 n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序瘫析，每一列都按照從上到下遞增的順序排序砌梆。請完成一個函數(shù)默责，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)咸包。
示例:
現(xiàn)有矩陣 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
給定 target = 5桃序，返回 true。
給定 target = 20烂瘫，返回 false媒熊。
分析：這個二維數(shù)組有一個特點，右上角的元素是這行中最大的忱反，是這列中最小的泛释，這種類似二叉樹。
class Solution {
public static boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int rows = matrix.length;
int columns = matrix[0].length;
int row = 0;
int column = columns - 1;
if(target<matrix[0][0] || target > matrix[rows-1][column]){
return false;
}
while (row<=rows-1 && column >=0){
//如果相等温算，直接返回true
if(target == matrix[row][column]){
return true;
}
//如果小于當(dāng)前元素怜校，列數(shù)減一
else if(target<matrix[row][column]){
column--;
}
//如果大于當(dāng)前元素，行數(shù)加一
else {
row++;
}
}
return false;
}
}
-
重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果注竿，請重建該二叉樹茄茁。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。
例如巩割，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：3 / \ 9 20 / \ 15 7分析：只要知道一個二叉樹的中序遍歷結(jié)果以及先序遍歷和后序遍歷中的一個裙顽，就能完整地構(gòu)建出這棵二叉樹。
比如一棵二叉樹的先序遍歷結(jié)果為a b c d e f g h j i 宣谈，中序遍歷的結(jié)果為c b e d a h g i j f
我們知道先序遍歷的第一個元素必定是根節(jié)點愈犹，所以根節(jié)點是a，從中序遍歷的結(jié)果中找到a闻丑，那么a之前的所有元素都是a的左子樹漩怎，有4個元素：c b e d，先序遍歷中選擇4個元素：b c d e嗦嗡。那么b是a的左子樹的根節(jié)點......在a之后的所有元素都是a的右子樹
使用一個 Map 存儲中序遍歷的每個元素及其對應(yīng)的下標(biāo)勋锤，目的是為了快速獲得一個元素在中序遍歷中的位置。調(diào)用遞歸方法侥祭，對于前序遍歷和中序遍歷叁执，下標(biāo)范圍都是從 0 到 n-1，其中 n 是二叉樹節(jié)點個數(shù)矮冬。
遞歸方法的基準(zhǔn)情形有兩個：判斷前序遍歷的下標(biāo)范圍的開始和結(jié)束谈宛，若開始大于結(jié)束，則當(dāng)前的二叉樹中沒有節(jié)點胎署，返回空值 null入挣。若開始等于結(jié)束，則當(dāng)前的二叉樹中恰好有一個節(jié)點硝拧，根據(jù)節(jié)點值創(chuàng)建該節(jié)點作為根節(jié)點并返回径筏。
若開始小于結(jié)束葛假，則當(dāng)前的二叉樹中有多個節(jié)點。在中序遍歷中得到根節(jié)點的位置滋恬，從而得到左子樹和右子樹各自的下標(biāo)范圍和節(jié)點數(shù)量聊训，知道節(jié)點數(shù)量后，在前序遍歷中即可得到左子樹和右子樹各自的下標(biāo)范圍恢氯，然后遞歸重建左子樹和右子樹带斑，并將左右子樹的根節(jié)點分別作為當(dāng)前根節(jié)點的左右子節(jié)點。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //保存中序遍歷的結(jié)果集 HashMap<Integer, Integer> dic = new HashMap<>(); //保存先序遍歷數(shù)組 int[] po; public TreeNode buildTree(int[] preorder, int[] inorder) { po = preorder; //遍歷中序結(jié)果集放進(jìn)HashMap中方便查詢獲得根節(jié)點 for(int i = 0; i < inorder.length; i++) dic.put(inorder[i], i); return recur(0, 0, inorder.length - 1); } /** * pre_root是先序遍歷結(jié)果集中的根節(jié)點 * in_left是中序遍歷的左邊界 * in_right是中序遍歷的右邊界 */ TreeNode recur(int pre_root, int in_left, int in_right) { //如果左邊界大于右邊界勋拟，停止遞歸 if(in_left > in_right) return null; //生成一個根節(jié)點 TreeNode root = new TreeNode(po[pre_root]); //找到這個根節(jié)點在中序遍歷集中的位置 int i = dic.get(po[pre_root]); //左子樹 root.left = recur(pre_root + 1, in_left, i - 1); //右子樹勋磕，根節(jié)點索引+左子樹長度+1 root.right = recur(pre_root + i - in_left + 1, i + 1, in_right); return root; } } -
最長不含重復(fù)字符的子字符串
請從字符串中找出一個最長的不包含重復(fù)字符的子字符串，計算該最長子字符串的長度敢靡。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"挂滓，所以其長度為 3。
示例 2:輸入: "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"啸胧，所以其長度為 1赶站。
示例 3:輸入: "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"，所以其長度為 3纺念。
請注意贝椿，你的答案必須是 子串 的長度，"pwke" 是一個子序列陷谱，不是子串烙博。
public static int lengthOfLongestSubstring(String s){
//這里 是不包含start的
//ans是最大子串的長度，初始為0烟逊，start是最大子串的開始的下標(biāo)的前一位渣窜，初始為-1
int ans = 0, start = -1;
//使用Map存儲字符及對應(yīng)的下標(biāo)
Map<Character, Integer> map = new HashMap<>();
//遍歷這個字符串
for(int i = 0; i < s.length() ; i++){
char k = s.charAt(i);
if(map.containsKey(k)){
// 如果遇到重復(fù)字符，就要更新了焙格！
int index = map.get(k);
//index是當(dāng)前重復(fù)字符對應(yīng)的下標(biāo)，如果大于start
if(index > start) {
start = index;
}
}
map.put(k, i);
//比較
ans = Math.max(ans, i - start);
}
return ans;
}
-
兩數(shù)之和
給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target夷都，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù)眷唉，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案囤官。但是冬阳，數(shù)組中同一個元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]解法一：暴力破解法
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return new int[] { i, j }; } } } throw new IllegalArgumentException("No two sum solution"); } }暴力破解法的時間復(fù)雜度是O(n^2)党饮，空間復(fù)雜度是O(1).
解法二：哈希表的一次遍歷
class Solution{ public int[] twoSum(int[] nums, int target){ Map<Integer,Integer> map = new HashMap<>(); for(int i = 0;i<nums.length;i++){ if(map.containsKey(target-nums[i])){ return new int[]{map.get(target-nums[i]),i}; } map.put(nums[i],i); } throw new IllegalArgumentException("No two sum solution"); } }這種方法的時間復(fù)雜度是O(n)肝陪，空間復(fù)雜度也是O(n)。
-
兩數(shù)相加
給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)刑顺。其中氯窍，它們各自的位數(shù)是按照 逆序 的方式存儲的饲常，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。
如果狼讨，我們將這兩個數(shù)相加起來贝淤，則會返回一個新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外政供，這兩個數(shù)都不會以 0 開頭播聪。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807分析：最開始想的是分別將這兩個鏈表轉(zhuǎn)換為int型的整數(shù)，然后兩數(shù)相加得到一個int整數(shù)布隔，最后將這個整數(shù)轉(zhuǎn)成鏈表离陶。可惜這個想法太天真了衅檀，不僅時間復(fù)雜度很高招刨，而且還會出現(xiàn)int溢出的問題。最后看了答案：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1,q = l2,curr = dummyHead; int carry = 0; while (p != null || q!= null){ int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; int sum = x + y + carry; carry = sum / 10; curr.next = new ListNode(sum%10); curr = curr.next; if(p != null){ p = p.next; } if( q != null){ q = q.next; } } if (carry > 0) { curr.next = new ListNode(carry); } return dummyHead.next; }使用了一個dummyHead作為頭節(jié)點之前的節(jié)點术吝。0-9之內(nèi)的數(shù)字相加有可能出現(xiàn)溢出的問題使用carry保存溢出的十位上的數(shù)字计济。最后還有可能出現(xiàn)進(jìn)位的問題，所以要對carry進(jìn)行判斷排苍。
-
尋找兩個正序數(shù)組的中位數(shù)(https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/)
給定兩個大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2沦寂。
請你找出這兩個正序數(shù)組的中位數(shù)，并且要求算法的時間復(fù)雜度為 O(log(m + n))淘衙。
你可以假設(shè) nums1 和 nums2 不會同時為空传藏。
示例 1:
nums1 = [1, 3]
nums2 = [2]則中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]則中位數(shù)是 (2 + 3)/2 = 2.5
分析：剛開始的時候我的思路是將這兩個數(shù)組合并為一個大數(shù)組，然后根據(jù)合并后數(shù)組的長度計算中位數(shù)彤守。但是這種算法的時間復(fù)雜度為O(m+n)毯侦，不能滿足題目的要求。無奈只能看參考答案：
public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int leftLength = nums1.length; int rightLength = nums2.length; // 為了保證第一個數(shù)組比第二個數(shù)組小(或者相等) if (leftLength > rightLength) { return findMedianSortedArrays(nums2, nums1); } // 分割線左邊的所有元素需要滿足的個數(shù) m + (n - m + 1) / 2; // 兩個數(shù)組長度之和為偶數(shù)時具垫，當(dāng)在長度之和上+1時侈离，由于整除是向下取整，所以不會改變結(jié)果 // 兩個數(shù)組長度之和為奇數(shù)時筝蚕，按照分割線的左邊比右邊多一個元素的要求卦碾，此時在長度之和上+1，就會被2整除起宽，會在原來的數(shù) //的基礎(chǔ)上+1洲胖，于是多出來的那個1就是左邊比右邊多出來的一個元素 int totalLeft = (leftLength + rightLength + 1) / 2; // 在 nums1 的區(qū)間 [0, leftLength] 里查找恰當(dāng)?shù)姆指罹€， // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i] int left = 0; int right = leftLength; // nums1[i - 1] <= nums2[j] // 此處要求第一個數(shù)組中分割線的左邊的值 不大于(小于等于) 第二個數(shù)組中分割線的右邊的值 // nums2[j - 1] <= nums1[i] // 此處要求第二個數(shù)組中分割線的左邊的值 不大于(小于等于) 第一個數(shù)組中分割線的右邊的值 // 循環(huán)條件結(jié)束的條件為指針重合坯沪，即分割線已找到 while (left < right) { // 二分查找绿映，此處為取第一個數(shù)組中左右指針下標(biāo)的中位數(shù)，決定起始位置 // 此處+1首先是為了不出現(xiàn)死循環(huán)，即left永遠(yuǎn)小于right的情況 // left和right最小差距是1叉弦，此時下面的計算結(jié)果如果不加1會出現(xiàn)i一直=left的情況丐一，而+1之后i才會=right // 于是在left=i的時候可以破壞循環(huán)條件，其次下標(biāo)+1還會保證下標(biāo)不會越界卸奉，因為+1之后向上取整钝诚，保證了 // i不會取到0值，即i-1不會小于0 // 此時i也代表著在一個數(shù)組中左邊的元素的個數(shù) int i = left + (right - left + 1) / 2; // 第一個數(shù)組中左邊的元素個數(shù)確定后榄棵，用左邊元素的總和-第一個數(shù)組中元素的總和=第二個元素中左邊的元素的總和 // 此時j就是第二個元素中左邊的元素的個數(shù) int j = totalLeft - i; // 此處用了nums1[i - 1] <= nums2[j]的取反凝颇，當(dāng)?shù)谝粋€數(shù)組中分割線的左邊的值大于第二個數(shù)組中分割線的右邊的值 // 說明又指針應(yīng)該左移，即-1 if (nums1[i - 1] > nums2[j]) { // 下一輪搜索的區(qū)間 [left, i - 1] right = i - 1; // 此時說明條件滿足疹鳄，應(yīng)當(dāng)將左指針右移到i的位置拧略，至于為什么是右移，請看i的定義 } else { // 下一輪搜索的區(qū)間 [i, right] left = i; } } // 退出循環(huán)時left一定等于right瘪弓，所以此時等于left和right都可以 // 為什么left一定不會大于right?因為left=i垫蛆。 // 此時i代表分割線在第一個數(shù)組中所在的位置 // nums1[i]為第一個數(shù)組中分割線右邊的第一個值 // nums[i-1]即第一個數(shù)組中分割線左邊的第一個值 int i = left; // 此時j代表分割線在第二個數(shù)組中的位置 // nums2[j]為第一個數(shù)組中分割線右邊的第一個值 // nums2[j-1]即第一個數(shù)組中分割線左邊的第一個值 int j = totalLeft - i; // 當(dāng)i=0時，說明第一個數(shù)組分割線左邊沒有值腺怯，為了不影響 // nums1[i - 1] <= nums2[j] 和 Math.max(nums1LeftMax, nums2LeftMax) // 的判斷袱饭，所以將它設(shè)置為int的最小值 int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1]; // 等i=第一個數(shù)組的長度時，說明第一個數(shù)組分割線右邊沒有值呛占，為了不影響 // nums2[j - 1] <= nums1[i] 和 Math.min(nums1RightMin, nums2RightMin) // 的判斷虑乖，所以將它設(shè)置為int的最大值 int nums1RightMin = i == leftLength ? Integer.MAX_VALUE : nums1[i]; // 當(dāng)j=0時，說明第二個數(shù)組分割線左邊沒有值晾虑，為了不影響 // nums2[j - 1] <= nums1[i] 和 Math.max(nums1LeftMax, nums2LeftMax) // 的判斷疹味，所以將它設(shè)置為int的最小值 int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1]; // 等j=第二個數(shù)組的長度時，說明第二個數(shù)組分割線右邊沒有值帜篇，為了不影響 // nums1[i - 1] <= nums2[j] 和 Math.min(nums1RightMin, nums2RightMin) // 的判斷糙捺，所以將它設(shè)置為int的最大值 int nums2RightMin = j == rightLength ? Integer.MAX_VALUE : nums2[j]; // 如果兩個數(shù)組的長度之和為奇數(shù)，直接返回兩個數(shù)組在分割線左邊的最大值即可 if (((leftLength + rightLength) % 2) == 1) { return Math.max(nums1LeftMax, nums2LeftMax); } else { // 如果兩個數(shù)組的長度之和為偶數(shù)笙隙，返回的是兩個數(shù)組在左邊的最大值和兩個數(shù)組在右邊的最小值的和的二分之一 // 此處不能被向下取整洪灯，所以要強制轉(zhuǎn)換為double類型 return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2; } }這種方式基于一種分割線的思路來尋找中位數(shù)。第一個數(shù)組有一個分割線竟痰，第二個數(shù)組也有一個分割線签钩，分割線左側(cè)的所有元素要小于分割線右側(cè)的所有元素，也就意味著第一個數(shù)組的分割線左側(cè)的最后一個元素要小于第二個數(shù)組分割線右側(cè)的第一個元素凯亮，同理边臼，第二個數(shù)組的分割線左側(cè)的最后一個元素要小于第一個數(shù)組分割線右側(cè)的第一個元素哄尔。同時假消，上下兩個數(shù)組分割線左側(cè)的元素的數(shù)量是(上面數(shù)組的元素個數(shù)+下面數(shù)組的元素的個數(shù)+1)/2。當(dāng)總元素的個數(shù)是偶數(shù)的時候岭接，左側(cè)的元素的數(shù)量是總元素數(shù)量的一半富拗，當(dāng)是奇數(shù)的時候臼予，左側(cè)元素的數(shù)量是總元素的數(shù)量的一半再加一。這種思路相當(dāng)于只要找到上下兩個數(shù)組的分割線兩側(cè)的四個元素就可以計算出中位數(shù)了啃沪。
需要注意的是有四種特殊情況：上面的數(shù)組分割線左邊沒有元素粘拾、右邊沒有元素，下面的數(shù)組分割線左邊沒有元素创千，右邊沒有元素缰雇。
-
最長回文子串
給定一個字符串
s，找到s中最長的回文子串追驴。你可以假設(shè)s的最大長度為 1000械哟。示例 1：
輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案。示例 2：
輸入: "cbbd" 輸出: "bb"
? 解法一：中心擴展算法
? 對每一個字符殿雪，向兩邊擴展暇咆，可以分為兩種情況：奇數(shù)與偶數(shù)，分別計算這兩種情況下最長回文子串的值并進(jìn)行比較丙曙。
/**
* 中心擴散法尋找最長子串
* @param s
* @return
*/
public String longestPalindrome(String s) {
if (s == null || s.length() < 1){
return "";
}
// 初始化最大回文子串的起點和終點
int start = 0;
int end = 0;
// 遍歷每個位置爸业，當(dāng)做中心位
for (int i = 0; i < s.length(); i++) {
// 分別拿到奇數(shù)偶數(shù)的回文子串長度
int lenOdd = expandCenter(s,i,i);
int lenEven = expandCenter(s,i,i + 1);
// 對比最大的長度
int len = Math.max(lenOdd,lenEven);
// 計算對應(yīng)最大回文子串的起點和終點
//與len>=end-start+1同樣的效果
if (len > end - start){
//len-1兼顧了偶數(shù)的情況
start = i - (len - 1)/2;
end = i + len/2;
}
}
// 注意：這里的end+1是因為 java自帶的左閉右開的原因
return s.substring(start,end + 1);
}
/**
*
* @param s 輸入的字符串
* @param left 起始的左邊界
* @param right 起始的右邊界
* @return 回文串的長度
*/
private int expandCenter(String s,int left,int right){
// left = right 的時候，此時回文中心是一個字符亏镰，回文串的長度是奇數(shù)
// right = left + 1 的時候扯旷，此時回文中心是一個空隙，回文串的長度是偶數(shù)
// 跳出循環(huán)的時候恰好滿足 s.charAt(left) 拆挥！= s.charAt(right)
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
// 回文串的長度是right-left+1-2 = right - left - 1
return right - left - 1;
}
? 解法二：動態(tài)規(guī)劃
使用一個二維數(shù)組表示各個階段的狀態(tài)薄霜，這個二維數(shù)組的行是子串的起始位置，列是子串的結(jié)束位置纸兔。由于j>=i惰瓜，所以只需要考慮二維數(shù)組的主對角線的上半部分，對角線上的值永遠(yuǎn)是true汉矿。用true表示這個子串是回文串崎坊，false不是回文串。那么對于某個固定位置的數(shù)組元素來說洲拇，它的值依賴于左下角的元素的值奈揍。進(jìn)行填充的時候只能一列一列地進(jìn)行填充，同一列的元素從上到下依次填充赋续。
給定一個字符串s="abcba"
0 1 2 3 4 0 true false false false true 1 true false true false 2 true false false 3 true false 4 true
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
// 特判
if (len < 2){
return s;
}
//最大長度初始是1
int maxLen = 1;
int begin = 0;
// 1. 狀態(tài)定義
// dp[i][j] 表示s[i...j] 是否是回文串
// 2. 初始化
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] chars = s.toCharArray();
// 3. 狀態(tài)轉(zhuǎn)移
// 注意：先填左下角
// 填表規(guī)則：先一列一列的填寫男翰，再一行一行的填，保證左下方的單元格先進(jìn)行計算
for (int j = 1;j < len;j++){
for (int i = 0; i < j; i++) {
// 頭尾字符不相等纽乱，不是回文串
if (chars[i] != chars[j]){
dp[i][j] = false;
}else {
// 相等的情況下
// 考慮頭尾去掉以后沒有字符剩余蛾绎，或者剩下一個字符的時候，肯定是回文串
if (j - i < 3){
dp[i][j] = true;
}
//否則，判斷其左下角的元素的狀態(tài)
else {
// 狀態(tài)轉(zhuǎn)移
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要dp[i][j] == true 成立租冠，表示s[i...j] 是否是回文串
// 此時更新記錄回文長度和起始位置
if (dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
// 4. 返回值
return s.substring(begin,begin + maxLen);
}
}
-
Z字形變換
將一個給定字符串根據(jù)給定的行數(shù)鹏倘，以從上往下、從左到右進(jìn)行 Z 字形排列顽爹。
比如輸入字符串為 "LEETCODEISHIRING" 行數(shù)為 3 時纤泵，排列如下：
L C I R E T O E S I I G E D H N之后，你的輸出需要從左往右逐行讀取镜粤，產(chǎn)生出一個新的字符串捏题，比如："LCIRETOESIIGEDHN"。
請你實現(xiàn)這個將字符串進(jìn)行指定行數(shù)變換的函數(shù)：
string convert(string s, int numRows);
分析：最后需要按行讀取肉渴，所以可以考慮每一行使用一個字符串進(jìn)行保存涉馅。最后將字符串進(jìn)行拼接。最開始的想法是用一個變量記錄當(dāng)前所在的行黄虱，但是有一個問題稚矿，行數(shù)加一還是減一怎么判斷，苦思冥想不了了之捻浦，看了官方題解才恍然大悟晤揣，使用一個標(biāo)志位進(jìn)行標(biāo)記。根據(jù)這個標(biāo)志位的狀態(tài)進(jìn)行加一或是減一的操作朱灿。
public static String convert(String s, int numRows){ //如果行數(shù)為1或者字符串的長度小于等于行數(shù)昧识，就返回字符串本身，不需要轉(zhuǎn)換 if(numRows == 1 || s.length()<=numRows){ return s; } //同一行的字符保存在一個StringBuilder中盗扒，需要一個list來存放這些StringBuilder List<StringBuilder> list = new ArrayList<>(); char[] chars = s.toCharArray(); for (int i = 0; i < numRows; i++) { list.add(new StringBuilder()); } //狀態(tài)位跪楞，根據(jù)這個變量判斷行數(shù)加一還是減一 boolean goingDown = false; //初始當(dāng)前行為1 int curRow = 1; //遍歷每個字符，追加到對應(yīng)的StringBuilder后面 for (char aChar : chars) { //因為list的下標(biāo)從0開始侣灶，所以curRow需要減一 list.get(curRow-1).append(aChar); //如果是第一行或者最后一行就需要對goingDown進(jìn)行取反操作 if (curRow == 1 || curRow == numRows) { goingDown = !goingDown; } //根據(jù)goingDown的值進(jìn)行加一或者減一的操作 curRow += goingDown ? 1 : -1; } StringBuilder sb = new StringBuilder(); //合并list中的stringBuilder for (StringBuilder builder : list) { sb.append(builder); } return sb.toString(); }- 正則表達(dá)式匹配(難度：困難)
給你一個字符串 s 和一個字符規(guī)律 p甸祭，請你來實現(xiàn)一個支持 '.' 和 '*' 的正則表達(dá)式匹配。
'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素
所謂匹配褥影，是要涵蓋 整個 字符串 s的池户，而不是部分字符串。說明:
s 可能為空凡怎，且只包含從 a-z 的小寫字母校焦。
p 可能為空寨典，且只包含從 a-z 的小寫字母，以及字符 . 和 *耸成。
示例 1:輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串注暗。示例 2:
輸入:
s = "aa"
p = "a"
輸出: true
解釋: 因為 '' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'。因此墓猎，字符串 "aa" 可被視為 'a' 重復(fù)了一次。示例 3:
輸入:
s = "ab"
p = "."
輸出: true
解釋: "." 表示可匹配零個或多個（'*'）任意字符（'.'）赚楚。
示例 4:輸入:
s = "aab"
p = "cab"
輸出: true
解釋: 因為 '*' 表示零個或多個毙沾，這里 'c' 為 0 個, 'a' 被重復(fù)一次。因此可以匹配字符串 "aab"宠页。
示例 5:輸入:
s = "mississippi"
p = "misisp*."
輸出: false
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
}
else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
//.可以匹配任意字符左胞，所以返回true
if (p.charAt(j - 1) == '.') {
return true;
}
//i-1與j-1是否匹配
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
-
盛最多水的容器
給你 n 個非負(fù)整數(shù) a1，a2举户，...烤宙，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 俭嘁。在坐標(biāo)內(nèi)畫 n 條垂直線躺枕，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線供填，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水拐云。
說明：你不能傾斜容器，且 n 的值至少為 2近她。
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]叉瘩。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49粘捎。
示例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
> 分析：
>
> 這道一乍一看不就是一個雙重for循環(huán)嗎薇缅，很簡單的一道題，為什么還是中等難度攒磨。結(jié)果一提交運行速度只擊敗了14.7%的用戶泳桦。尋思這還有其他更快速的算法，苦思冥想有一個雙指針的方法娩缰，一個指針指向頭蓬痒，一個指針指向尾，循環(huán)的終止條件是指針重合漆羔。但是在判斷應(yīng)該移動哪個指針的問題上不知道怎么辦梧奢。果斷看了答案，原來只需要移動元素值較小的那個指針就行了演痒。原因就是如果說你移動元素值較大的那個指針亲轨，無論下一個元素的值大還是小鸟顺。面積一定小于之前的面積器虾。所以只能移動較小元素的那個指針兆沙，時間復(fù)雜度是O(n)葛圃。
```java
public static int maxArea(int[] height){
int max = 0;
int length = height.length;
// 雙重循環(huán)的方法
// for (int i = 0; i < length-1; i++) {
// for (int j = i+1; j < length; j++) {
// int min = Math.min(height[i], height[j]);
// int temp = min*(j-i);
// if(temp>max){
// max = temp;
// }
// }
// }
// return max;
int left = 0;
int right = length-1;
while (left<right){
int min = Math.min(height[left],height[right]);
int temp = min*(right-left);
max = Math.max(temp, max);
if(height[left]<=height[right]){
left++;
}
else {
right--;
}
}
return max;
}
```
