|
|
2013年4月11日
分析： 這個問題是google的面試題。由于一個字符串有很多種二叉表示法，貌似很難判斷兩個字符串是否可以做這樣的變換。 對付復雜問題的方法是從簡單的特例來思考，從而找出規律。 先考察簡單情況： 字符串長度為1：很明顯，兩個字符串必須完全相同才可以。 字符串長度為2：當s1="ab", s2只有"ab"或者"ba"才可以。 對于任意長度的字符串，我們可以把字符串s1分為a1,b1兩個部分，s2分為a2,b2兩個部分，滿足（(a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2)） 如此，我們找到了解決問題的思路。首先我們嘗試用遞歸來寫。 解法一（遞歸） 兩個字符串的相似的必備條件是含有相同的字符集。簡單的做法是把兩個字符串的字符排序后，然后比較是否相同。 加上這個檢查就可以大大的減少遞歸次數。 代碼如下： public boolean isScramble(String s1, String s2) {
int l1 = s1.length();
int l2 = s2.length();
if(l1!=l2){
return false;
}
if(l1==0){
return true;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
if(l1==1){
return c1[0]==c2[0];
}
Arrays.sort(c1);
Arrays.sort(c2);
for(int i=0;i<l1;++i){
if(c1[i]!=c2[i]){
return false;
}
}
boolean result = false;
for(int i=1;i<l1 && !result;++i){
String s11 = s1.substring(0,i);
String s12 = s1.substring(i);
String s21 = s2.substring(0,i);
String s22 = s2.substring(i);
result = isScramble(s11,s21) && isScramble(s12,s22);
if(!result){
String s31 = s2.substring(0,l1-i);
String s32 = s2.substring(l1-i);
result = isScramble(s11,s32) && isScramble(s12,s31);
}
}
return result;
} 解法二（動態規劃） 減少重復計算的方法就是動態規劃。動態規劃是一種神奇的算法技術，不親自去寫，是很難完全掌握動態規劃的。 這里我使用了一個三維數組boolean result[len][len][len],其中第一維為子串的長度，第二維為s1的起始索引，第三維為s2的起始索引。 result[k][i][j]表示s1[i...i+k]是否可以由s2[j...j+k]變化得來。 代碼如下，非常簡潔優美： public class Solution {
public boolean isScramble(String s1, String s2) {
int len = s1.length();
if(len!=s2.length()){
return false;
}
if(len==0){
return true;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
boolean[][][] result = new boolean[len][len][len];
for(int i=0;i<len;++i){
for(int j=0;j<len;++j){
result[0][i][j] = (c1[i]==c2[j]);
}
}
for(int k=2;k<=len;++k){
for(int i=len-k;i>=0;--i){
for(int j=len-k;j>=0;--j){
boolean r = false;
for(int m=1;m<k && !r;++m){
r = (result[m-1][i][j] && result[k-m-1][i+m][j+m]) || (result[m-1][i][j+k-m] && result[k-m-1][i+m][j]);
}
result[k-1][i][j] = r;
}
}
}
return result[len-1][0][0];
}
}
分析： 因為要求結果集是升序排列，所以首先我們要對數組進行排序。 子集的長度可以從0到整個數組的長度。長度為n+1的子集可以由長度為n的子集再加上在之后的一個元素組成。 這里我使用了三個技巧 1。使用了一個index數組來記錄每個子集的最大索引，這樣添加新元素就很簡單。 2。使用了兩個變量start和end來記錄上一個長度的子集在結果中的起始和終止位置。 3。去重處理使用了一個last變量記錄前一次的值，它的初始值設為S[0]-1,這樣就保證了和數組的任何一個元素不同。 代碼如下： public class Solution { public ArrayList<ArrayList<Integer>> subsetsWithDup( int[] S) { Arrays.sort(S); ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> indexs = new ArrayList<Integer>(); result.add( new ArrayList<Integer>()); indexs.add(-1); int slen = S.length; int start=0,end=0; for( int len=1;len<=slen;++len){ int e = end; for( int i=start;i<=end;++i){ ArrayList<Integer> ss = result.get(i); int index = indexs.get(i).intValue(); int last = S[0]-1; for( int j = index+1;j<slen;++j){ int v = S[j]; if(v!=last){ ArrayList<Integer> newss = new ArrayList<Integer>(ss); newss.add(v); result.add(newss); indexs.add(j); ++e; last = v; } } } start = end+1; end = e; } return result; } }
分析： 格雷碼的序列中應包含2^n個數。這個問題初看起來不容易，我們要想出一個生成方法。 對于n=2,序列是： 00，01，11，10 那對于n=3,如何利用n=2的序列呢？一個方法是，先在n=2的四個序列前加0（這其實是保持不變），然后再考慮把最高位變成1，只需要把方向反過來就可以了 000，001，011，010 100，101，111，110－> 110,111,101,100 把這兩行合起來就可以得到新的序列。 想通了，寫代碼就很容易了。 public class Solution {
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(0);
if(n>0){
result.add(1);
}
int mask = 1;
for(int i=2;i<=n;++i){
mask *= 2;
for(int j=result.size()-1;j>=0;--j){
int v = result.get(j).intValue();
v |= mask;
result.add(v);
}
}
return result;
}
}
解法一：（遞歸） 一個簡單的想法，是遍歷s3的每個字符，這個字符必須等于s1和s2的某個字符。如果都不相等，則返回false 我們使用3個變量i,j,k分別記錄當前s1,s2,s3的字符位置。 如果s3[k] = s1[i], i向后移動一位。如果s3[k]=s2[j],j向后移動一位。 這個題目主要難在如果s1和s2的字符出現重復的時候，就有兩種情況，i,j都可以向后一位。 下面的算法在這種情況使用了遞歸，很簡單的做法。但是效率非常差，是指數復雜度的。 public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
if(l1+l2!=l3){
return false;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
char[] c3 = s3.toCharArray();
int i=0,j=0;
for(int k=0;k<l3;++k){
char c = c3[k];
boolean m1 = i<l1 && c==c1[i];
boolean m2 = j<l2 && c==c2[j];
if(!m1 && !m2){
return false;
}
else if(m1 && m2){
String news3 = s3.substring(k+1);
return isInterleave(s1.substring(i+1),s2.substring(j),news3)
|| isInterleave(s1.substring(i),s2.substring(j+1),news3);
}
else if(m1){
++i;
}
else{
++j;
}
}
return true;
}
} 解法二：（動態規劃） 為了減少重復計算，就要使用動態規劃來記錄中間結果。 這里我使用了一個二維數組result[i][j]來表示s1的前i個字符和s2的前j個字符是否能和s3的前i+j個字符匹配。 狀態轉移方程如下： result[i,j] = (result[i-1,j] && s1[i] = s3[i+j]) || (result[i,j-1] && s2[j] = s3[i+j]); 其中0≤i≤len(s1) ,0≤j≤len(s2)
這樣算法復雜度就會下降到O(l1*l2)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
if(l1+l2!=l3){
return false;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
char[] c3 = s3.toCharArray();
boolean[][] result = new boolean[l1+1][l2+1];
result[0][0] = true;
for(int i=0;i<l1;++i){
if(c1[i]==c3[i]){
result[i+1][0] = true;
}
else{
break;
}
}
for(int j=0;j<l2;++j){
if(c2[j]==c3[j]){
result[0][j+1] = true;
}
else{
break;
}
}
for(int i=1;i<=l1;++i){
char ci = c1[i-1];
for(int j=1;j<=l2;++j){
char cj = c2[j-1];
char ck = c3[i+j-1];
result[i][j] = (result[i][j-1] && cj==ck) || (result[i-1][j] && ci==ck);
}
}
return result[l1][l2];
}
}
摘要: 給定一個由n個整數組成的數組S，是否存在S中的三個數a,b,c使得 a+b+c=0?找出所有的不重復的和為0的三元組。
注意：
1.三元組的整數按照升序排列 a 2.給出的結果中不能含有相同的三元組 閱讀全文
摘要: 給定兩個字符串S和T，計算S的子序列為T的個數。
這里的字符串的子序列指的是刪除字符串的幾個字符（也可以不刪）而得到的新的字符串，但是不能改變字符的相對位置。
比如“ACE”是“ABCDE”的子序列，但是“AEC”就不是。
如果S＝“rabbbit” T＝“rabit”，有3種不同的子序列為T的構成方法，那么結果應該返回3。 閱讀全文
分析： 題目不難，但是在面試時，在有限的時間內，沒有bug寫出，還是很考驗功力的。 解決這個問題的思路是逐層掃描，上一層設置好下一層的next關系，在處理空指針的時候要格外小心。 代碼如下，有注釋，應該很容易看懂： 使用了三個指針： node:當前節點 firstChild:下一層的第一個非空子節點 lastChild:下一層的最后一個待處理（未設置next)的子節點 public void connect(TreeLinkNode root) {
TreeLinkNode node = root;
TreeLinkNode firstChild = null;
TreeLinkNode lastChild = null;
while(node!=null){
if(firstChild == null){ //記錄第一個非空子節點
firstChild = node.left!=null?node.left:node.right;
}
//設置子節點的next關系，3種情況
if(node.left!=null && node.right!=null){
if(lastChild!=null){
lastChild.next = node.left;
}
node.left.next = node.right;
lastChild = node.right;
}
else if(node.left!=null){
if(lastChild!=null){
lastChild.next = node.left;
}
lastChild = node.left;
}
else if(node.right!=null){
if(lastChild!=null){
lastChild.next = node.right;
}
lastChild = node.right;
}
//設置下一個節點，如果本層已經遍歷完畢，移到下一層的第一個子節點
if(node.next!=null){
node = node.next;
}
else{
node = firstChild;
firstChild = null;
lastChild = null;
}
}
}
分析： 這道題相比之前的兩道題，難度提高了不少。 因為限制了只能交易兩次，所以我們可以把n天分為兩段，分別計算這兩段的最大收益，就可以得到一個最大收益。窮舉所有這樣的分法，就可以得到全局的最大收益。 為了提高效率，這里使用動態規劃，即把中間狀態記錄下來。使用了兩個數組profits，nprofits分別記錄從0..i和i..n的最大收益。 代碼如下： public int maxProfit( int[] prices) { int days = prices.length; if(days<2){ return 0; } int[] profits = new int[days]; int min = prices[0]; int max = min; for( int i=1;i<days;++i){ int p = prices[i]; if(min>p){ max = min = p; } else if(max<p){ max = p; } int profit = max - min; profits[i] = (profits[i-1]>profit)?profits[i-1]:profit; } int[] nprofits = new int[days]; nprofits[days-1] = 0; max = min = prices[days-1]; for( int i=days-2;i>=0;--i){ int p = prices[i]; if(min>p){ min =p; } else if(max<p){ max = min = p; } int profit = max - min; nprofits[i] = (nprofits[i+1]>profit)?nprofits[i+1]:profit; } int maxprofit = 0; for( int i=0;i<days;++i){ int profit = profits[i]+nprofits[i]; if(maxprofit<profit){ maxprofit = profit; } } return maxprofit; }
分析：為了得到最大收益，必須在所有上升的曲線段的開始點買入，在最高點賣出。而在下降階段不出手。  實現代碼如下： public class Solution { public int maxProfit( int[] prices) { int len = prices.length; if(len<2){ return 0; } int min=0; int result = 0; boolean inBuy = false; for( int i=0;i<len-1;++i){ int p = prices[i]; int q = prices[i+1]; if(!inBuy){ if(q>p){ inBuy = true; min=p ; } } else{ if(q<p){ result += (p-min); inBuy = false; } } } if(inBuy){ result += ((prices[len-1])-min); } return result; } }
摘要: 假設你有一個數組包含了每天的股票價格，它的第i個元素就是第i天的股票價格。
你只能進行一次交易（一次買進和一次賣出），設計一個算法求出最大的收益。 閱讀全文
摘要: 給定一個二叉樹，尋找最大的路徑和.
路徑可以從任意節點開始到任意節點結束。（也可以是單個節點）
比如：對于二叉樹
1
/ \
2 3
和最大的路徑是2->1->3，結果為6
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/ 閱讀全文
摘要: 給定兩個單詞(一個開始，一個結束）和一個字典，找出所有的最短的從開始單詞到結束單詞的變換序列的序列（可能不止一個），并滿足：
1.每次只能變換一個字母
2.所有的中間單詞必須存在于字典中
比如：
輸入：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
那么最短的變化序列有兩個
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]。
注意：
1. 所有單詞的長度都是相同的
2. 所有單詞都只含有小寫的字母。 閱讀全文
摘要: 給定兩個排序好的數組A和B,把B合并到A并保持排序。
public class Solution {
public void merge(int A[], int m, int B[], int n) {
//write your code here }
}
注意：
假定A有足夠的額外的容量儲存B的內容，m和n分別為A和B的初始化元素的個數。要求算法復雜度在O(m+n)。 閱讀全文
摘要: 給定兩個單詞(一個開始，一個結束）和一個字典，找出最短的從開始單詞到結束單詞的變換序列的長度，并滿足：
1.每次只能變換一個字母
2.所有的中間單詞必須存在于字典中
比如：
輸入：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
那么最短的變化序列是"hit" -> "hot" -> "dot" -> "dog" -> "cog"，所以返回長度是5。
注意：
1. 如果找不到這樣的序列，返回0
2. 所有單詞的長度都是相同的
3. 所有單詞都只含有小寫的字母。 閱讀全文
摘要: 給定一個二叉樹，每個節點的值是一個數字（0-9），每個從根節點到葉節點均能組成一個數字。
比如如果從根節點到葉節點的路徑是1-2-3，那么這代表了123這個數字。
求出所有這樣從根節點到葉節點的數字之和。
比如，對于二叉樹
1
/ \
2 3
一共有兩條路徑1->2和1->3，那么求和的結果就是12+13=25
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
//write c 閱讀全文
摘要: 給定一個2D的棋盤，含有‘X'和’O'，找到所有被‘X'包圍的’O'，然后把該區域的‘O’都變成'X'。
例子-輸入：
X X X X
X O O X
X X O X
X O X X
應該輸出：
X X X X
X X X X
X X X X
X O X X
public void solve(char[][] board) {
} 閱讀全文
摘要: 給定一個字符串s，切割字符串使得每個子串都是回文的。（比如aba，對稱）
要求返回所有可能的分割。
比如，對于字符串s="aab",
返回:
[
["aa","b"],
["a","a","b"]
]
閱讀全文
摘要: 給定一個有由數字構成的數組表示的數，求該數加1的結果。
public class Solution {
public int[] plusOne(int[] digits) {
}
} 閱讀全文
摘要: 實現 int sqrt(int x);
計算和返回x的平方根。 閱讀全文
摘要: 給定一個未排序的整數數組，求最長的連續序列的長度。要求算法的時間復雜度在O(n)
比如對于數組[100, 4, 200, 1, 3, 2]，其中最長序列為[1,2,3,4]，所以應該返回4
public class Solution {
public int longestConsecutive(int[] num) {
//write your code here
}
} 閱讀全文
摘要: 給定一個字符串s，分割s使得每個子串都是回文的（即倒過來和原字符串是一樣的，如aba）
求最少的分割次數。 閱讀全文
|