91精品啪在线观看国产手机,成年网站在线,91麻豆精品国产91久久久久久

Scramble String

Problem

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

great

/ \

gr eat

/ \ / \

g r e at

/ \

a t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

rgeat

/ \

rg eat

/ \ / \

r g e at

/ \

a t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

rgtae

/ \

rg tae

/ \ / \

r g ta e

/ \

t a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

分析：

這個問題是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];
    }
}

posted @ 2013-05-22 22:25 小明閱讀(6139) | 評論 (0) | 編輯收藏

Subsets

Problem

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[   [2],   [1],   [1,2,2],   [2,2],   [1,2],   [] ]

分析：
因為要求結果集是升序排列，所以首先我們要對數組進行排序。

子集的長度可以從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;
    }
}

posted @ 2013-05-21 22:50 小明閱讀(2120) | 評論 (0) | 編輯收藏

格雷碼

問題格雷碼是一個二進制的編碼系統，相鄰的兩個數只有一位是不同的。
給定一個非負的整數n，代表了格雷碼的位的總數。輸出格雷碼的序列，這個序列必須以0開始。

比如，給定n=2,輸出［0，1，3，2］，格雷碼是
0 ＝ 00
1 ＝ 01
3 ＝ 11
2 ＝ 10

注：格雷碼的序列并不是唯一，比如n=2時，［0，2，3，1］也滿足條件。

分析：
格雷碼的序列中應包含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;
    }
}

posted @ 2013-05-20 21:09 小明閱讀(2586) | 評論 (0) | 編輯收藏

交叉字符串

問題給定字符串s1,s2,s3,判斷s3是否可以由s1和s2交叉組成得到。

例如：

s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

解法一：（遞歸）

一個簡單的想法，是遍歷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];
   }
}

posted @ 2013-05-10 20:47 小明閱讀(3236) | 評論 (4) | 編輯收藏

三個數之和

摘要: 給定一個由n個整數組成的數組S，是否存在S中的三個數a,b,c使得 a+b+c=0?找出所有的不重復的和為0的三元組。

注意：
1.三元組的整數按照升序排列 a2.給出的結果中不能含有相同的三元組閱讀全文

posted @ 2013-05-01 23:13 小明閱讀(1927) | 評論 (0) | 編輯收藏

子序列計數

摘要: 給定兩個字符串S和T，計算S的子序列為T的個數。

這里的字符串的子序列指的是刪除字符串的幾個字符（也可以不刪）而得到的新的字符串，但是不能改變字符的相對位置。

比如“ACE”是“ABCDE”的子序列，但是“AEC”就不是。

如果S＝“rabbbit” T＝“rabit”，有3種不同的子序列為T的構成方法，那么結果應該返回3。閱讀全文

posted @ 2013-04-26 23:33 小明閱讀(2037) | 評論 (1) | 編輯收藏

設置二叉樹的next節點

問題給定一顆二叉樹：

class TreeLinkNode {

TreeLinkNode left;

TreeLinkNode right;

TreeLinkNode next;

}

要求把所有節點的next節點設置成它右邊的節點，如果沒有右節點，設置成空。初始狀態，所有的next的指針均為null.

要求:你只能使用常數的空間。

比如：

1

/ \

2 3

/ \ \

4 5 7
應該輸出：

1 -> NULL

/ \

2 -> 3 -> NULL

/ \ \

4-> 5 -> 7 -> NULL

分析：
題目不難，但是在面試時，在有限的時間內，沒有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;
            }
        }
    }

posted @ 2013-04-26 11:23 小明閱讀(2129) | 評論 (0) | 編輯收藏

最佳的股票買賣時間III

問題假設你有一個數組包含了每天的股票價格，它的第i個元素就是第i天的股票價格。

設計一個算法尋找最大的收益。你可以最多進行兩次交易。
注意：你不能同時進行多次交易，也就是說你買股票之前，必須賣掉手中股票。

分析：
這道題相比之前的兩道題，難度提高了不少。

因為限制了只能交易兩次，所以我們可以把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;
    }

posted @ 2013-04-25 22:22 小明閱讀(2072) | 評論 (0) | 編輯收藏

最佳的股票買賣時間II

問題假設你有一個數組包含了每天的股票價格，它的第i個元素就是第i天的股票價格。

設計一個算法尋找最大的收益。你可以進行任意多次交易。但是，你不能同時進行多次交易，也就是說你買股票之前，必須賣掉手中股票。

分析：為了得到最大收益，必須在所有上升的曲線段的開始點買入，在最高點賣出。而在下降階段不出手。

實現代碼如下：

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;
    }
}

posted @ 2013-04-19 21:50 小明閱讀(1855) | 評論 (0) | 編輯收藏

最佳的股票買賣時間

摘要: 假設你有一個數組包含了每天的股票價格，它的第i個元素就是第i天的股票價格。

你只能進行一次交易（一次買進和一次賣出），設計一個算法求出最大的收益。閱讀全文

posted @ 2013-04-19 15:03 小明閱讀(1586) | 評論 (0) | 編輯收藏

小明思考

Scramble String

Subsets

格雷碼

交叉字符串

三個數之和

子序列計數

設置二叉樹的next節點

最佳的股票買賣時間III

最佳的股票買賣時間II

最佳的股票買賣時間

日歷

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

相冊

My blogs

搜索

最新評論

閱讀排行榜

評論排行榜