206. 反轉(zhuǎn)鏈表
問(wèn)題描述
反轉(zhuǎn)一個(gè)單鏈表囚玫。
解題思路1-迭代法
1）定義指向前一個(gè)節(jié)點(diǎn)的指針prev阱州，初始值為空
2）遍歷鏈表霎迫，將每個(gè)節(jié)點(diǎn)的next指針指向前驅(qū)節(jié)點(diǎn)。每次迭代過(guò)程如下：
-
定義臨時(shí)變量temp悟泵，用于保存當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)
step 1 -
將當(dāng)前節(jié)點(diǎn)的next指針指向前驅(qū)節(jié)點(diǎn)
step 2 -
當(dāng)前節(jié)點(diǎn)成為下一個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
step 3 -
temp中的后繼節(jié)點(diǎn)成為下一個(gè)當(dāng)前節(jié)點(diǎn)
step 4
代碼實(shí)現(xiàn)1-迭代法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head != null){
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}
- 時(shí)間復(fù)雜度O(n)
- 空間復(fù)雜度O(1)
解題思路2-遞歸法
邊界情況：鏈表為空或者鏈表中只有一個(gè)結(jié)點(diǎn)（head == null || head.next == null）
遞歸函數(shù)實(shí)現(xiàn)功能：反轉(zhuǎn)鏈表找到newHead
遞歸參數(shù)：head.next
遞歸執(zhí)行內(nèi)容：
head.next.next = head; //（對(duì)應(yīng)圖中節(jié)點(diǎn)2的next指向1）
head.next=null; //（對(duì)應(yīng)圖中節(jié)點(diǎn)1的next指向空）
代碼實(shí)現(xiàn)2-遞歸法
class Solution {
public ListNode reverseList(ListNode head) {
while(head == null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
- 時(shí)間復(fù)雜度O(n)
- 空間復(fù)雜度O(n)，使用遞歸會(huì)使用隱式椀来ǎ空間蚣录。遞歸深度可能會(huì)達(dá)到 nn 層割择。
10. 正則表達(dá)式匹配
問(wèn)題描述
給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p，請(qǐng)你來(lái)實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配萎河。
- '.' 匹配任意單個(gè)字符
- '*' 匹配零個(gè)或多個(gè)前面的那一個(gè)元素
- 所謂匹配荔泳，是要涵蓋 整個(gè) 字符串 s的，而不是部分字符串虐杯。
解題思路
采用動(dòng)態(tài)規(guī)劃解題玛歌。
- dp數(shù)組：dp[i][j]表示s中前i個(gè)字符和p中前j個(gè)字符能匹配
- base case：分為三種情況。
（1）s和p都為空串：一定能匹配
（2）s不為空擎椰，p為空：一定不能匹配
（3）s為空支子，p不為空：模式串為字母和*間隔排列且長(zhǎng)度為偶數(shù)時(shí)（如，*a*a*a*b*）能夠匹配空串达舒，其他的是都是false值朋。 - 狀態(tài)轉(zhuǎn)移
（1）如果p[j] != '*', 則看s中第i個(gè)字符和p中第j個(gè)字符能否匹配。若不能匹配則dp[i][j] == false休弃；若能匹配則取決dp[i-1[j-1]的值吞歼。
（2）如果p[j] == '*',則看s中第i個(gè)字符和p中第j - 1個(gè)字符能否匹配圈膏。若不能匹配塔猾，則取決于dp[i][j-2]的值（沒(méi)有匹配，模式串中的a*被當(dāng)作空串）稽坤；若能匹配丈甸，則可能有三種情況dp[i][j] = dp[i-1][j] || dp[i][j - 1]|| dp[i][j - 2]：
// = dp[i-1][j]糯俗，多個(gè)字符匹配，模式串中的
a*被當(dāng)作aa...
// = dp[i][j-1]睦擂，單個(gè)字符匹配得湘，模式串中的a*被當(dāng)作a
// = dp[i][j-2]，沒(méi)有匹配, 模式串中的a*被當(dāng)作空串
代碼實(shí)現(xiàn)
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length(), pLen = p.length();
//dp[i][j]表示s中前i個(gè)字符和p中前j個(gè)字符能匹配
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
//base case
// 1.兩個(gè)空串能夠匹配
dp[0][0] = true;
// 2.如果s不為空, p為空顿仇，則一定不能匹配
for(int i = 1; i <= sLen; i++) {
dp[i][0] = false;
}
// 3.如果s為空, p不為空淘正，*a*a*a*a*這種能夠匹配空串，其他的是都是false臼闻。
// 奇數(shù)位不管什么字符都是false鸿吆，偶數(shù)位為* 時(shí)則: dp[0][j] = dp[0][j - 2]
for(int j = 1; j <= pLen ; j++) {
if(j % 2 == 0 && p.charAt(j - 1) == '*'){
dp[0][j] = dp[0][j - 2];
}else{
dp[0][j] = false;
}
}
for(int i = 1; i <= sLen; i++){
//si表示s中的第i個(gè)字符
char si = s.charAt(i - 1);
for(int j = 1; j <= pLen; j++){
if(p.charAt(j - 1) != '*'){
dp[i][j] = dp[i - 1][j - 1] && match(si, p.charAt(j - 1));
}else {
if(match(si, p.charAt(j - 2))){
//dp[i-1][j]，多個(gè)字符匹配述呐，模式串中的a*被當(dāng)作aa...
//dp[i][j-1]惩淳，單個(gè)字符匹配，模式串中的a*被當(dāng)作a
//dp[i][j-2], 沒(méi)有匹配, 模式串中的a*被當(dāng)作空串
dp[i][j] = dp[i-1][j] || dp[i][j - 1]|| dp[i][j - 2];
}else {
//沒(méi)有匹配乓搬，模式串中的a*被當(dāng)作空串
dp[i][j] = dp[i][j-2];
}
}
}
}
return dp[sLen][pLen];
}
//判斷兩個(gè)字符是否能夠匹配
public boolean match(char s, char p){
if(p == '.' || s == p){
return true;
}
return false;
}
}
