LeetCode 92反转链表Ⅱ93复制ip地址94二叉树的中序遍历
微信搜一搜：bigsai 專注于Java、數(shù)據(jù)結(jié)構(gòu)與算法，一起進(jìn)大廠不迷路！
算法文章題解全部收錄在github倉庫bigsai-algorithm,求star！
關(guān)注回復(fù)進(jìn)群即可加入力扣打卡群，歡迎劃水。近期打卡：
LeetCode 90子集Ⅱ&91解碼方法
LeetCode 86分割鏈表&87擾亂字符串
LeetCode 88合并兩個(gè)有序數(shù)組&89格雷編碼
反轉(zhuǎn)鏈表Ⅱ
反轉(zhuǎn)從位置 m 到 n 的鏈表。請(qǐng)使用一趟掃描完成反轉(zhuǎn)。
說明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度。
示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
分析：
這種題實(shí)現(xiàn)的方法可能比較多，但是我這里使用頭插法去實(shí)現(xiàn)。m-n范圍內(nèi)進(jìn)行反轉(zhuǎn)，那么只需要將這部分的鏈表順序頭插在m-1位的后面即可。后面再拼接起來。
防止m包含頭部，可以引入一個(gè)頭節(jié)點(diǎn)進(jìn)行處理。在具體的處理上可能有點(diǎn)繁瑣，因?yàn)轭^插的時(shí)候遍歷這個(gè)節(jié)點(diǎn)插入要改變結(jié)構(gòu)，要在插入前將后側(cè)nextNode存儲(chǔ)下來下次使用。
具體實(shí)現(xiàn)代碼為：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode reverseBetween(ListNode head, int m, int n) {ListNode value=new ListNode(0);//頭節(jié)點(diǎn)value.next=head;ListNode team=value;//臨時(shí)節(jié)點(diǎn)int index=1;//記錄標(biāo)記while (index<m) {team=team.next;index++;}//team 后面需要頭插ListNode tail=team.next;//m節(jié)點(diǎn)，最后會(huì)在最后ListNode node=team.next;while (index<=n) {ListNode nextNode=node.next;//先儲(chǔ)存右側(cè)節(jié)點(diǎn)node.next=team.next;//插入第一步。將自己右側(cè)指向team.next=node;//插入第二步，前面team指過來node=nextNode;index++;}tail.next=node; //逆置的鏈表和后面節(jié)點(diǎn)連接return value.next;} }復(fù)原ip地址
給定一個(gè)只包含數(shù)字的字符串，復(fù)原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于 0 到 255 之間組成，且不能含有前導(dǎo) 0），整數(shù)之間用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 無效的 IP 地址。
示例 1：
輸入：s = "25525511135" 輸出：["255.255.11.135","255.255.111.35"]示例 2：
輸入：s = "0000" 輸出：["0.0.0.0"]示例 3：
輸入：s = "1111" 輸出：["1.1.1.1"]示例 4：
輸入：s = "010010" 輸出：["0.10.0.10","0.100.1.0"]示例 5：
輸入：s = "101023" 輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]提示：
0 <= s.length <= 3000 s 僅由數(shù)字組成分析
本題的話是一種典型的回溯算法，不過這題剪枝的方法非常重要，否則會(huì)產(chǎn)生很多不必要的計(jì)算。
不考慮其他條件，其實(shí)就是要枚舉所有的劃分方式，然后分成4份、每個(gè)數(shù)字滿足條件，且剛好用完所有數(shù)字。而本題設(shè)計(jì)遞歸函數(shù)的時(shí)候，可以帶上當(dāng)前index和當(dāng)前數(shù)字?jǐn)?shù)量進(jìn)行向下遞歸，且向下的時(shí)候要注意數(shù)字大小在0-255且0不能做其他數(shù)字前綴。另外還可以進(jìn)行其他剪枝(從字符剩余數(shù)量判斷能否組成答案每位1-3位)。
具體代碼為：
class Solution {public List<String> restoreIpAddresses(String s) {List<String>list=new ArrayList<String>();List<String>value=new ArrayList<String>();char ch[]=s.toCharArray();dfs(value,list,ch,0,0);return value;}private void dfs(List<String> value, List<String> list, char[] ch, int index, int num) {// TODO Auto-generated method stubif(num==4&&index==ch.length){StringBuilder sBuilder=new StringBuilder();sBuilder.append(list.get(0));for(int i=1;i<4;i++){sBuilder.append('.');sBuilder.append(list.get(i));}value.add(sBuilder.toString());}else if(num==4||index>=ch.length) return;else {if((4-num)*3<ch.length-index-1||ch.length-index<4-num)//剩下的已經(jīng)不可能{return;}else if (ch[index]=='0') {list.add("0");dfs(value, list, ch, index+1, num+1);list.remove(list.size()-1);}else {StringBuilder sBuilder=new StringBuilder();for(int i=0;i<3&&index+i<ch.length;i++){sBuilder.append(ch[index+i]);if(i==2&&Integer.parseInt(sBuilder.toString())>255)return;list.add(sBuilder.toString());dfs(value, list, ch, index+i+1, num+1);list.remove(list.size()-1);}}}} }二叉樹的中序遍歷
示例 1：
輸入：root = [1,null,2,3] 輸出：[1,3,2]示例 2：
輸入：root = [] 輸出：[]示例 3：
輸入：root = [1] 輸出：[1]示例 4：
輸入：root = [1,2] 輸出：[2,1]示例 5：
輸入：root = [1,null,2] 輸出：[1,2]提示：
樹中節(jié)點(diǎn)數(shù)目在范圍 [0, 100] 內(nèi) -100 <= Node.val <= 100分析
中序遍歷可以看這篇：數(shù)據(jù)結(jié)構(gòu)與算法—二叉樹的層序、前序中序后序(遞歸、非遞歸)遍歷
上代碼：
原創(chuàng)不易，bigsai請(qǐng)你幫兩件事幫忙一下:
star支持一下， 您的肯定是我在平臺(tái)創(chuàng)作的源源動(dòng)力。
微信搜索「bigsai」，關(guān)注我的公眾號(hào)，不僅免費(fèi)送你電子書，我還會(huì)第一時(shí)間在公眾號(hào)分享知識(shí)技術(shù)。加我還可拉你進(jìn)力扣打卡群一起打卡LeetCode。
記得關(guān)注、咱們下次再見！
總結(jié)
以上是生活随笔為你收集整理的LeetCode 92反转链表Ⅱ93复制ip地址94二叉树的中序遍历的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： LeetCode 90子集Ⅱ91解码方法
- 下一篇： LeetCode 96不同的二叉搜索树9