|
|
2013年5月10日
分析： 這個(gè)問(wèn)題是google的面試題。由于一個(gè)字符串有很多種二叉表示法，貌似很難判斷兩個(gè)字符串是否可以做這樣的變換。 對(duì)付復(fù)雜問(wèn)題的方法是從簡(jiǎn)單的特例來(lái)思考，從而找出規(guī)律。 先考察簡(jiǎn)單情況： 字符串長(zhǎng)度為1：很明顯，兩個(gè)字符串必須完全相同才可以。 字符串長(zhǎng)度為2：當(dāng)s1="ab", s2只有"ab"或者"ba"才可以。 對(duì)于任意長(zhǎng)度的字符串，我們可以把字符串s1分為a1,b1兩個(gè)部分，s2分為a2,b2兩個(gè)部分，滿足（(a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2)） 如此，我們找到了解決問(wèn)題的思路。首先我們嘗試用遞歸來(lái)寫。 解法一（遞歸） 兩個(gè)字符串的相似的必備條件是含有相同的字符集。簡(jiǎn)單的做法是把兩個(gè)字符串的字符排序后，然后比較是否相同。 加上這個(gè)檢查就可以大大的減少遞歸次數(shù)。 代碼如下： 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;
} 解法二（動(dòng)態(tài)規(guī)劃） 減少重復(fù)計(jì)算的方法就是動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃是一種神奇的算法技術(shù)，不親自去寫，是很難完全掌握動(dòng)態(tài)規(guī)劃的。 這里我使用了一個(gè)三維數(shù)組boolean result[len][len][len],其中第一維為子串的長(zhǎng)度，第二維為s1的起始索引，第三維為s2的起始索引。 result[k][i][j]表示s1[i...i+k]是否可以由s2[j...j+k]變化得來(lái)。 代碼如下，非常簡(jiǎn)潔優(yōu)美： 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];
}
}
分析： 因?yàn)橐蠼Y(jié)果集是升序排列，所以首先我們要對(duì)數(shù)組進(jìn)行排序。 子集的長(zhǎng)度可以從0到整個(gè)數(shù)組的長(zhǎng)度。長(zhǎng)度為n+1的子集可以由長(zhǎng)度為n的子集再加上在之后的一個(gè)元素組成。 這里我使用了三個(gè)技巧 1。使用了一個(gè)index數(shù)組來(lái)記錄每個(gè)子集的最大索引，這樣添加新元素就很簡(jiǎn)單。 2。使用了兩個(gè)變量start和end來(lái)記錄上一個(gè)長(zhǎng)度的子集在結(jié)果中的起始和終止位置。 3。去重處理使用了一個(gè)last變量記錄前一次的值，它的初始值設(shè)為S[0]-1,這樣就保證了和數(shù)組的任何一個(gè)元素不同。 代碼如下： 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; } }
分析： 格雷碼的序列中應(yīng)包含2^n個(gè)數(shù)。這個(gè)問(wèn)題初看起來(lái)不容易，我們要想出一個(gè)生成方法。 對(duì)于n=2,序列是： 00，01，11，10 那對(duì)于n=3,如何利用n=2的序列呢？一個(gè)方法是，先在n=2的四個(gè)序列前加0（這其實(shí)是保持不變），然后再考慮把最高位變成1，只需要把方向反過(guò)來(lái)就可以了 000，001，011，010 100，101，111，110－> 110,111,101,100 把這兩行合起來(lái)就可以得到新的序列。 想通了，寫代碼就很容易了。 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;
}
}
解法一：（遞歸） 一個(gè)簡(jiǎn)單的想法，是遍歷s3的每個(gè)字符，這個(gè)字符必須等于s1和s2的某個(gè)字符。如果都不相等，則返回false 我們使用3個(gè)變量i,j,k分別記錄當(dāng)前s1,s2,s3的字符位置。 如果s3[k] = s1[i], i向后移動(dòng)一位。如果s3[k]=s2[j],j向后移動(dòng)一位。 這個(gè)題目主要難在如果s1和s2的字符出現(xiàn)重復(fù)的時(shí)候，就有兩種情況，i,j都可以向后一位。 下面的算法在這種情況使用了遞歸，很簡(jiǎn)單的做法。但是效率非常差，是指數(shù)復(fù)雜度的。 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;
}
} 解法二：（動(dòng)態(tài)規(guī)劃） 為了減少重復(fù)計(jì)算，就要使用動(dòng)態(tài)規(guī)劃來(lái)記錄中間結(jié)果。 這里我使用了一個(gè)二維數(shù)組result[i][j]來(lái)表示s1的前i個(gè)字符和s2的前j個(gè)字符是否能和s3的前i+j個(gè)字符匹配。 狀態(tài)轉(zhuǎn)移方程如下： 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)
這樣算法復(fù)雜度就會(huì)下降到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];
}
}
|