92. Reverse Linked List II
/**
* 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 dummy = new ListNode(-999);
dummy.next = head;
ListNode cur = dummy;
int index = 1;
while(index<m){
index++;
cur = cur.next;
}
ListNode p = cur.next;
if(p.next == null)
return dummy.next;
ListNode q = p.next;
index ++;
while(index <= n){
p.next = q.next;
q.next = cur.next;
cur.next = q;
q = p.next;
index++;
}
return dummy.next;
}
}
93. Restore IP Addresses
回溯法：
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<String>();
if(s==null || s.length()==0 || s.length()>12)
return res;
backtracking(s,res,"",0,0);
return res;
}
public static void backtracking(String s,List<String> res,String ss,int start,int count){
if(count==4 && start == s.length()){
String a = ss.substring(0,ss.length()-1);
res.add(a);
}
for(int i=start;i<start+3 && i<s.length();i++){
if(i>start && s.substring(start,start+1).equals("0"))
break;
if(Integer.parseInt(s.substring(start,i+1)) <= 255){
backtracking(s,res,ss+s.substring(start,i+1)+".",i+1,count+1);
}
}
}
}
94. Binary Tree Inorder Traversal
二叉樹的中序遍歷非遞歸思路
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode t = root;
while(t!=null){
stack.push(t);
t = t.left;
}
while(!stack.empty()){
t = stack.pop();
res.add(t.val);
t = t.right;
while(t!=null){
stack.push(t);
t = t.left;
}
}
return res;
}
}
95. Unique Binary Search Trees II
這題是 96 Unique Binary Search Trees 的延展，它已經(jīng)不是讓求不同構(gòu)二叉樹的種數(shù)，而是直接給出這些不同構(gòu)的二叉樹。
1. 每一次都在一個范圍內(nèi)隨機(jī)選取一個結(jié)點作為根。
2. 每選取一個結(jié)點作為根，就把樹切分成左右兩個子樹，直至該結(jié)點左右子樹為空。
大致思路如上，可以看出這也是一個可以劃分成子問題求解的題目，所以考點是動態(tài)規(guī)劃。
但具體對于本題來說，采取的是自底向上的求解過程。
1. 選出根結(jié)點后應(yīng)該先分別求解該根的左右子樹集合，也就是根的左子樹有若干種，它們組成左子樹集合，根的右子樹有若干種，它們組成右子樹集合。
2. 然后將左右子樹相互配對，每一個左子樹都與所有右子樹匹配，每一個右子樹都與所有的左子樹匹配。然后將兩個子樹插在根結(jié)點上。
3. 最后，把根結(jié)點放入鏈表中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n<=0)
return new ArrayList<TreeNode>();
return generateHelper(1,n);
}
public static List<TreeNode> generateHelper(int start,int end){
List<TreeNode> res = new ArrayList<TreeNode>();
if(start>end){
res.add(null);
return res;
}
for(int i=start;i<=end;i++){
List<TreeNode> leftNode = generateHelper(start,i-1);
List<TreeNode> rightNode = generateHelper(i+1,end);
for(int left=0;left<leftNode.size();left++)
for(int right=0;right<rightNode.size();right++){
TreeNode t = new TreeNode(i);
t.left = leftNode.get(left);
t.right = rightNode.get(right);
res.add(t);
}
}
return res;
}
}
96. Unique Binary Search Trees
這 道題要求可行的二叉查找樹的數(shù)量，其實二叉查找樹可以任意取根，只要滿足中序遍歷有序的要求就可以。從處理子問題的角度來看，選取一個結(jié)點為根，就把結(jié)點 切成左右子樹，以這個結(jié)點為根的可行二叉樹數(shù)量就是左右子樹可行二叉樹數(shù)量的乘積，所以總的數(shù)量是將以所有結(jié)點為根的可行結(jié)果累加起來。寫成表達(dá)式如下：
class Solution {
public int numTrees(int n) {
int [] G = new int[n+1];
G[0] = G[1] = 1;
for(int i=2; i<=n; ++i) {
for(int j=1; j<=i; ++j) {
G[i] += G[j-1] * G[i-j];
}
}
return G[n];
}
}
97. Interleaving String
我自己的思路：回溯法，不過超時了，記錄下：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s3.length() != s2.length() + s1.length())
return false;
return backtracking(s1,s2,s3,0,0);
}
public boolean backtracking(String s1,String s2,String s3,int start1,int start2){
if(start1 == s1.length() && start2 == s2.length())
return true;
if((start1<s1.length() && s1.charAt(start1) != s3.charAt(start1+start2)) && (start2<s2.length() && s2.charAt(start2) != s3.charAt(start1+start2)))
return false;
return (start1 < s1.length() && s1.charAt(start1) == s3.charAt(start1 + start2) && backtracking(s1,s2,s3,start1+1,start2)) || (start2 < s2.length() && s2.charAt(start2) == s3.charAt(start1 + start2) && backtracking(s1,s2,s3,start1,start2+1));
}
}
因此考慮用動態(tài)規(guī)劃做。
s1, s2只有兩個字符串，因此可以展平為一個二維地圖，判斷是否能從左上角走到右下角。
當(dāng)s1到達(dá)第i個元素，s2到達(dá)第j個元素:
地圖上往右一步就是s2[j-1]匹配s3[i+j-1]。
地圖上往下一步就是s1[i-1]匹配s3[i+j-1]。
示例：s1="aa",s2="ab",s3="aaba"。標(biāo)1的為可行。最終返回右下角。
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length())
return false;
boolean[][] arr = new boolean[s1.length()+1][s2.length()+1];
arr[0][0] = true;
for(int i=1;i<s2.length()+1;i++){
if(arr[0][i-1] && s2.charAt(i-1)==s3.charAt(i-1))
arr[0][i] = true;
else
arr[0][i] = false;
}
for(int j=1;j<s1.length()+1;j++){
if(arr[j-1][0] && s1.charAt(j-1) == s3.charAt(j-1))
arr[j][0] = true;
else
arr[j][0] = false;
}
for(int j=1;j<s1.length()+1;j++)
for(int i=1;i<s2.length()+1;i++){
if((arr[j-1][i] && s1.charAt(j-1)==s3.charAt(i+j-1)) || (arr[j][i-1] && s2.charAt(i-1)==s3.charAt(i+j-1)))
arr[j][i] = true;
else
arr[j][i] = false;
}
return arr[s1.length()][s2.length()];
}
}
98. Validate Binary Search Tree
按照中序遍歷的思路，如果發(fā)現(xiàn)遍歷的下一個節(jié)點比前一個節(jié)點大，那么繼續(xù)遍歷，如果比前一個節(jié)點小，則返回false。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return true;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode t = root;
while(t!=null){
stack.push(t);
t = t.left;
}
while(!stack.empty()){
t = stack.pop();
if(res.size()>0 && t.val <= res.get(res.size()-1))
return false;
res.add(t.val);
t = t.right;
while(t!=null){
stack.push(t);
t = t.left;
}
}
return true;
}
}
99. Recover Binary Search Tree
二叉排序樹中有兩個節(jié)點被交換了，要求把樹恢復(fù)成二叉排序樹。
最簡單的辦法，中序遍歷二叉樹生成序列，然后對序列中排序錯誤的進(jìn)行調(diào)整。最后再進(jìn)行一次賦值操作。
但這種方法要求n的空間復(fù)雜度，題目中要求空間復(fù)雜度為常數(shù)，所以需要換一種方法。
遞歸中序遍歷二叉樹，設(shè)置一個pre指針，記錄當(dāng)前節(jié)點中序遍歷時的前節(jié)點，如果當(dāng)前節(jié)點大于pre節(jié)點的值，說明需要調(diào)整次序。
有一個技巧是如果遍歷整個序列過程中只出現(xiàn)了一次次序錯誤，說明就是這兩個相鄰節(jié)點需要被交換。如果出現(xiàn)了兩次次序錯誤，那就需要交換這兩個節(jié)點。
我們交換的是兩個節(jié)點的值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode mistake1,mistake2;
TreeNode pre;
public void recursive_traversal(TreeNode root){
if(root==null)
return;
recursive_traversal(root.left);
if(pre!=null && root.val<pre.val){
if(mistake1==null){
mistake1 = pre;
mistake2 = root;
}
else
mistake2 = root;
}
pre = root;
recursive_traversal(root.right);
}
public void recoverTree(TreeNode root) {
recursive_traversal(root);
int temp = mistake1.val;
mistake1.val = mistake2.val;
mistake2.val = temp;
}
}
100. Same Tree
遞歸
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null)
return true;
else if(p==null || q== null)
return false;
else if(p.val != q.val)
return false;
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
