<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    小明思考

    Just a software engineer
    posts - 124, comments - 36, trackbacks - 0, articles - 0
      BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

    2012年11月7日

    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.

     


    分析:

    這個(gè)問題是google的面試題。由于一個(gè)字符串有很多種二叉表示法,貌似很難判斷兩個(gè)字符串是否可以做這樣的變換。
    對(duì)付復(fù)雜問題的方法是從簡(jiǎn)單的特例來思考,從而找出規(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))

    如此,我們找到了解決問題的思路。首先我們嘗試用遞歸來寫。


    解法一(遞歸)

    兩個(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]變化得來。

    代碼如下,非常簡(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];
        }
    }

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

    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],   [] ] 

    分析:
    因?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ù)組來記錄每個(gè)子集的最大索引,這樣添加新元素就很簡(jiǎn)單。
    2。使用了兩個(gè)變量start和end來記錄上一個(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;
        }
    }

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

    問題格雷碼是一個(gè)二進(jìn)制的編碼系統(tǒng),相鄰的兩個(gè)數(shù)只有一位是不同的。
    給定一個(gè)非負(fù)的整數(shù)n,代表了格雷碼的位的總數(shù)。輸出格雷碼的序列,這個(gè)序列必須以0開始。

    比如,給定n=2,輸出[0,1,3,2],格雷碼是
    0 = 00
    1 = 01
    3 = 11
    2 = 10

    注:格雷碼的序列并不是唯一,比如n=2時(shí),[0,2,3,1]也滿足條件。


    分析:
    格雷碼的序列中應(yīng)包含2^n個(gè)數(shù)。這個(gè)問題初看起來不容易,我們要想出一個(gè)生成方法。

    對(duì)于n=2,序列是:
    00,01,11,10
    那對(duì)于n=3,如何利用n=2的序列呢?一個(gè)方法是,先在n=2的四個(gè)序列前加0(這其實(shí)是保持不變),然后再考慮把最高位變成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 小明 閱讀(2582) | 評(píng)論 (0)編輯 收藏

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

    例如:

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

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


    解法一:(遞歸)

    一個(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ī)劃來記錄中間結(jié)果。

    這里我使用了一個(gè)二維數(shù)組result[i][j]來表示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];
       }
    }

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

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

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

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

         摘要: 給定兩個(gè)字符串S和T,計(jì)算S的子序列為T的個(gè)數(shù)。

    這里的字符串的子序列指的是刪除字符串的幾個(gè)字符(也可以不刪)而得到的新的字符串,但是不能改變字符的相對(duì)位置。

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

    如果S=“rabbbit” T=“rabit”,有3種不同的子序列為T的構(gòu)成方法,那么結(jié)果應(yīng)該返回3。  閱讀全文

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

    問題給定一顆二叉樹:
    class TreeLinkNode {
      TreeLinkNode left;
      TreeLinkNode right;
      TreeLinkNode next;
    }
    要求把所有節(jié)點(diǎn)的next節(jié)點(diǎn)設(shè)置成它右邊的節(jié)點(diǎn),如果沒有右節(jié)點(diǎn),設(shè)置成空。初始狀態(tài),所有的next的指針均為null.

    要求:你只能使用常數(shù)的空間。

    比如:
             1
           /  \
          2    3
         / \    \
        4   5    7
    應(yīng)該輸出:

    1 -> NULL
           /  \
          2 -> 3 -> NULL
         / \    \
        4-> 5 -> 7 -> NULL

    分析:
    題目不難,但是在面試時(shí),在有限的時(shí)間內(nèi),沒有bug寫出,還是很考驗(yàn)功力的。

    解決這個(gè)問題的思路是逐層掃描,上一層設(shè)置好下一層的next關(guān)系,在處理空指針的時(shí)候要格外小心。
    代碼如下,有注釋,應(yīng)該很容易看懂:
    使用了三個(gè)指針:
    node:當(dāng)前節(jié)點(diǎn)
    firstChild:下一層的第一個(gè)非空子節(jié)點(diǎn)
    lastChild:下一層的最后一個(gè)待處理(未設(shè)置next)的子節(jié)點(diǎn)

        public void connect(TreeLinkNode root) {
            TreeLinkNode node = root;
            TreeLinkNode firstChild = null;
            TreeLinkNode lastChild = null;
            
            while(node!=null){
                if(firstChild == null){ //記錄第一個(gè)非空子節(jié)點(diǎn)
                    firstChild = node.left!=null?node.left:node.right;
                }
                //設(shè)置子節(jié)點(diǎn)的next關(guān)系,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;
                }
                //設(shè)置下一個(gè)節(jié)點(diǎn),如果本層已經(jīng)遍歷完畢,移到下一層的第一個(gè)子節(jié)點(diǎn)
                if(node.next!=null){
                    node = node.next;
                }
                else{
                    node = firstChild;
                    firstChild = null;
                    lastChild = null;
                }
            }
        }

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

    問題假設(shè)你有一個(gè)數(shù)組包含了每天的股票價(jià)格,它的第i個(gè)元素就是第i天的股票價(jià)格。 

    設(shè)計(jì)一個(gè)算法尋找最大的收益。你可以最多進(jìn)行兩次交易。
    注意:你不能同時(shí)進(jìn)行多次交易,也就是說你買股票之前,必須賣掉手中股票。


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

    因?yàn)橄拗屏酥荒芙灰變纱危晕覀兛梢园裯天分為兩段,分別計(jì)算這兩段的最大收益,就可以得到一個(gè)最大收益。窮舉所有這樣的分法,就可以得到全局的最大收益。

    為了提高效率,這里使用動(dòng)態(tài)規(guī)劃,即把中間狀態(tài)記錄下來。使用了兩個(gè)數(shù)組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 小明 閱讀(2066) | 評(píng)論 (0)編輯 收藏

    問題假設(shè)你有一個(gè)數(shù)組包含了每天的股票價(jià)格,它的第i個(gè)元素就是第i天的股票價(jià)格。

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

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



    實(shí)現(xiàn)代碼如下:
    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 小明 閱讀(1850) | 評(píng)論 (0)編輯 收藏

         摘要: 假設(shè)你有一個(gè)數(shù)組包含了每天的股票價(jià)格,它的第i個(gè)元素就是第i天的股票價(jià)格。

    你只能進(jìn)行一次交易(一次買進(jìn)和一次賣出),設(shè)計(jì)一個(gè)算法求出最大的收益。  閱讀全文

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

         摘要: 給定一個(gè)二叉樹,尋找最大的路徑和.
    路徑可以從任意節(jié)點(diǎn)開始到任意節(jié)點(diǎn)結(jié)束。(也可以是單個(gè)節(jié)點(diǎn))

    比如:對(duì)于二叉樹
    1
    / \
    2 3
    和最大的路徑是2->1->3,結(jié)果為6
    /**
    * Definition for binary tree
    * public class TreeNode {
    * int val;
    * TreeNode left;
    * TreeNode right;
    * TreeNode(int x) { val = x; }
    * }
    */  閱讀全文

    posted @ 2013-04-18 21:31 小明 閱讀(4009) | 評(píng)論 (0)編輯 收藏

         摘要: 給定兩個(gè)單詞(一個(gè)開始,一個(gè)結(jié)束)和一個(gè)字典,找出所有的最短的從開始單詞到結(jié)束單詞的變換序列的序列(可能不止一個(gè)),并滿足:

    1.每次只能變換一個(gè)字母
    2.所有的中間單詞必須存在于字典中

    比如:
    輸入:
    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]

    那么最短的變化序列有兩個(gè)
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]。
    注意:
    1. 所有單詞的長(zhǎng)度都是相同的
    2. 所有單詞都只含有小寫的字母。  閱讀全文

    posted @ 2013-04-18 17:32 小明 閱讀(1364) | 評(píng)論 (0)編輯 收藏

         摘要: 給定兩個(gè)排序好的數(shù)組A和B,把B合并到A并保持排序。

    public class Solution {
    public void merge(int A[], int m, int B[], int n) {
    //write your code here }
    }

    注意:
    假定A有足夠的額外的容量?jī)?chǔ)存B的內(nèi)容,m和n分別為A和B的初始化元素的個(gè)數(shù)。要求算法復(fù)雜度在O(m+n)。  閱讀全文

    posted @ 2013-04-18 13:44 小明 閱讀(1282) | 評(píng)論 (0)編輯 收藏

         摘要: 給定兩個(gè)單詞(一個(gè)開始,一個(gè)結(jié)束)和一個(gè)字典,找出最短的從開始單詞到結(jié)束單詞的變換序列的長(zhǎng)度,并滿足:

    1.每次只能變換一個(gè)字母
    2.所有的中間單詞必須存在于字典中

    比如:
    輸入:
    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]

    那么最短的變化序列是"hit" -> "hot" -> "dot" -> "dog" -> "cog",所以返回長(zhǎng)度是5。
    注意:
    1. 如果找不到這樣的序列,返回0
    2. 所有單詞的長(zhǎng)度都是相同的
    3. 所有單詞都只含有小寫的字母。  閱讀全文

    posted @ 2013-04-18 12:46 小明 閱讀(1516) | 評(píng)論 (0)編輯 收藏

         摘要: 給定一個(gè)二叉樹,每個(gè)節(jié)點(diǎn)的值是一個(gè)數(shù)字(0-9),每個(gè)從根節(jié)點(diǎn)到葉節(jié)點(diǎn)均能組成一個(gè)數(shù)字。
    比如如果從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑是1-2-3,那么這代表了123這個(gè)數(shù)字。
    求出所有這樣從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的數(shù)字之和。

    比如,對(duì)于二叉樹
    1
    / \
    2 3

    一共有兩條路徑1->2和1->3,那么求和的結(jié)果就是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  閱讀全文

    posted @ 2013-04-16 11:37 小明 閱讀(2541) | 評(píng)論 (1)編輯 收藏

         摘要: 給定一個(gè)2D的棋盤,含有‘X'和’O',找到所有被‘X'包圍的’O',然后把該區(qū)域的‘O’都變成'X'。

    例子-輸入:
    X X X X
    X O O X
    X X O X
    X O X X

    應(yīng)該輸出:

    X X X X
    X X X X
    X X X X
    X O X X

    public void solve(char[][] board) {
    }  閱讀全文

    posted @ 2013-04-15 18:17 小明 閱讀(1560) | 評(píng)論 (2)編輯 收藏

         摘要: 給定一個(gè)字符串s,切割字符串使得每個(gè)子串都是回文的。(比如aba,對(duì)稱)
    要求返回所有可能的分割。

    比如,對(duì)于字符串s="aab",
    返回:

    [
    ["aa","b"],
    ["a","a","b"]
    ]
      閱讀全文

    posted @ 2013-04-15 13:52 小明 閱讀(1502) | 評(píng)論 (0)編輯 收藏

    +1

         摘要: 給定一個(gè)有由數(shù)字構(gòu)成的數(shù)組表示的數(shù),求該數(shù)加1的結(jié)果。
    public class Solution {
    public int[] plusOne(int[] digits) {
    }
    }  閱讀全文

    posted @ 2013-04-15 11:22 小明 閱讀(1374) | 評(píng)論 (3)編輯 收藏

         摘要: 實(shí)現(xiàn) int sqrt(int x);
    計(jì)算和返回x的平方根。  閱讀全文

    posted @ 2013-04-15 10:19 小明 閱讀(1466) | 評(píng)論 (0)編輯 收藏

         摘要: 給定一個(gè)未排序的整數(shù)數(shù)組,求最長(zhǎng)的連續(xù)序列的長(zhǎng)度。要求算法的時(shí)間復(fù)雜度在O(n)
    比如對(duì)于數(shù)組[100, 4, 200, 1, 3, 2],其中最長(zhǎng)序列為[1,2,3,4],所以應(yīng)該返回4

    public class Solution {
    public int longestConsecutive(int[] num) {
    //write your code here
    }
    }  閱讀全文

    posted @ 2013-04-12 15:58 小明 閱讀(2414) | 評(píng)論 (7)編輯 收藏

         摘要: 給定一個(gè)字符串s,分割s使得每個(gè)子串都是回文的(即倒過來和原字符串是一樣的,如aba)
    求最少的分割次數(shù)。  閱讀全文

    posted @ 2013-04-11 11:24 小明 閱讀(4142) | 評(píng)論 (3)編輯 收藏

    問題描述:
    Problem Statement
    THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
    TOURNAMENT
    DEFINITION
    Class Name: MatchMaker
    Method Name: getBestMatches
    Paramaters: String[], String, int
    Returns: String[]
    Method signature (be sure your method is public):  String[]
    getBestMatches(String[] members, String currentUser, int sf);
    PROBLEM STATEMENT
    A new online match making company needs some software to help find the "perfect
    couples".  People who sign up answer a series of multiple-choice questions.
    Then, when a member makes a "Get Best Mates" request, the software returns a
    list of users whose gender matches the requested gender and whose answers to
    the questions were equal to or greater than a similarity factor when compared
    to the user's answers.
    Implement a class MatchMaker, which contains a method getBestMatches.  The
    method takes as parameters a String[] members, String currentUser, and an int
    sf:
    - members contains information about all the members.  Elements of members are
    of the form "NAME G D X X X X X X X X X X" 
       * NAME represents the member's name
       * G represents the gender of the current user. 
       * D represents the requested gender of the potential mate. 
    * Each X indicates the member's answer to one of the multiple-choice
    questions.  The first X is the answer to the first question, the second is the
    answer to the second question, et cetera. 
    - currentUser is the name of the user who made the "Get Best Mates" request.  
    - sf is an integer representing the similarity factor.
    The method returns a String[] consisting of members' names who have at least sf
    identical answers to currentUser and are of the requested gender.  The names
    should be returned in order from most identical answers to least.  If two
    members have the same number of identical answers as the currentUser, the names
    should be returned in the same relative order they were inputted.
    TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
    the following criteria are met:
    - members will have between 1 and 50 elements, inclusive.
    - Each element of members will have a length between 7 and 44, inclusive.
    - NAME will have a length between 1 and 20, inclusive, and only contain
    uppercase letters A-Z.
    - G can be either an uppercase M or an uppercase F.
    - D can be either an uppercase M or an uppercase F.
    - Each X is a capital letter (A-D).
    - The number of Xs in each element of the members is equal.  The number of Xs
    will be between 1 and 10, inclusive. 
    - No two elements will have the same NAME.
    - Names are case sensitive.
    - currentUser consists of between 1 and 20, inclusive, uppercase letters, A-Z,
    and must be a member.
    - sf is an int between 1 and 10, inclusive.
    - sf must be less than or equal to the number of answers (Xs) of the members.
    NOTES
    The currentUser should not be included in the returned list of potential mates.
    EXAMPLES
    For the following examples, assume members =
    {"BETTY F M A A C C",
     "TOM M F A D C A",
     "SUE F M D D D D",
     "ELLEN F M A A C A",
     "JOE M F A A C A",
     "ED M F A D D A",
     "SALLY F M C D A B",
     "MARGE F M A A C C"}
    If currentUser="BETTY" and sf=2, BETTY and TOM have two identical answers and
    BETTY and JOE have three identical answers, so the method should return
    {"JOE","TOM"}.
    If currentUser="JOE" and sf=1, the method should return
    {"ELLEN","BETTY","MARGE"}.
    If currentUser="MARGE" and sf=4, the method should return [].
    Definition
    Class:
    MatchMaker
    Method:
    getBestMatches
    Parameters:
    String[], String, int
    Returns:
    String[]
    Method signature:
    String[] getBestMatches(String[] param0, String param1, int param2)
    (be sure your method is public)


    ================================================================我的代碼=============

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;

    public class MatchMaker {
        enum GENDER{MALE,FEMALE};
        
        //"NAME G D X X X X X X X X X X" 
        private static class Member{
            String name;
            GENDER gender;
            GENDER mate;
            String[] answers;
            int index;
            int matched = 0;
        }
        
        String[] getBestMatches(String[] members, String currentUser, int sf){
            List<Member> allMembers = new ArrayList<Member>();
            Member cu = null;
            for(int i=0;i<members.length;++i){
                String m = members[i];
                String[] c = m.split(" ");
                Member mem = new Member();
                mem.name= c[0];
                mem.gender = c[1].equals("M")?GENDER.MALE:GENDER.FEMALE;
                mem.mate = c[2].equals("M")?GENDER.MALE:GENDER.FEMALE;
                mem.index = i;
                mem.matched = 0;
                String[] answers = mem.answers = new String[c.length-3];
                for(int j=3;j<c.length;++j){
                    answers[j-3] = c[j];
                }
                allMembers.add(mem);
                if(c[0].equals(currentUser)){
                    cu = mem;
                }
            }
            List<Member> matched = new ArrayList<Member>();
            if(cu!=null){
                for(Member mem:allMembers){
                    if(mem!=cu && mem.gender==cu.mate){
                        for(int i=0;i<mem.answers.length;++i){
                            if(mem.answers[i].equals(cu.answers[i])){
                                ++mem.matched;
                            }
                        }
                        if(mem.matched>=sf){
                            matched.add(mem);
                        }
                    }
                }
                
                Collections.sort(matched, new Comparator<Member>(){
                    public int compare(Member ma, Member mb) {
                        if(ma.matched!=mb.matched){
                            return mb.matched - ma.matched;
                        }
                        return ma.index-mb.index;
                    }
                });
                
                String[] result = new String[matched.size()];
                for(int i=0;i<result.length;++i){
                    result[i] = matched.get(i).name;
                }
                return result;
            }
            return new String[0];
        }
    }


    posted @ 2013-04-02 14:04 小明 閱讀(401) | 評(píng)論 (0)編輯 收藏

    以下是我在上一家公司出的java筆試題,有些難度,感興趣的同學(xué)可以做做看。

    ---Question---

    1.What is the output of the following program? 

    public class Foo {

           public static void main(String[] args){

                  Map<byte[], String> m = new HashMap<byte[], String>();

                  byte[] key = "abcd".getBytes();

                  m.put(key, "abcd");

                  System.out.println(m.containsKey(key));

                  System.out.println(m.containsKey("abcd"));

                  System.out.println(m.containsKey("abcd".getBytes()));

           }

    }

    a) true,true,false b)true,false,false c)true,true,true d) false,false,false e)Program throws an exception

     

    2. What is the proper string filled in the following program?

    Public class Foo {

           public static void main(String[] args) {

                  String s=”1\\2\\3\\4”;

                  //split the string with “\”

                  String []result = s.split(“____”);

                  for(String r:result){

                         System.out.println(r);

                  }

           }

    }

    a) \ b) \\ c) \\\ d)\\\\ e)\\\\\

     

    3. What is the output of the following program? 

    public class Foo {

           public static void main(String[] args) {

                  char[] c = new char[] { '1' };

                  String s = new String(c);

                  System.out.println("abcd" + c);

                  System.out.println("abcd" + s);

           }

    }

    a) Compile error b)abcd1,abcd1 c) abcd49,abcd1 d) Program throws an exception e)none of above

     

    4. Which class is threading safe which one object can be used between multi-threads without extra synchronized? 

    a) Vector b) HashMap c) ArrayList d)StringBuilder e)HashSet

     

    5. What is the output of the following program? 

    public class Foo {

           public static void main(String[] args) throws IOException {

                  ByteArrayOutputStream baos = new ByteArrayOutputStream();

                  byte[] b = new byte[]{(byte)0x0,(byte)0x1,(byte)0x2};

                  baos.write(b);

                  baos.write(0x0102);

                  byte[] result = baos.toByteArray();

                  ByteArrayInputStream bais = new ByteArrayInputStream(result);

                  System.out.println(bais.available());

           }

    }

    a) 0 b) 1 c)4 d) 5 e) Program throws an exception

     

    6. What is return value of function “calc”?

    public class Foo {

           public static int calc() throws IOException{

                  int ret = 0;

                  try{

                         ++ret;

                         throw new IOException("try");

                  }

                  catch(IOException ioe){

                         --ret;

                         return ret;

                  }

                  finally{

                         ++ret;

                         return ret;

                  }

           }

    }

    a) 0 b) 1 c)2 d)3 e) throws an exception

     

    7. What is the output of the following program?

    public class Foo {

           public static class Value {

                  private int value;

                  public int get(){

                         return value;

                  }

                  public void set(int v){

                         value = v;

                  }

           }

           public static class Values implements Iterable<Value>{

                  public Values(int capacity){

                         this.capacity = capacity;

                  }

                 

                  int count =1 ;

                  int capacity;

                  Value v = new Value();

                  public Iterator<Value> iterator() {

                         return new Iterator<Value>(){

                                public boolean hasNext() {

                                       return count<=capacity;

                                }

     

                                public Value next() {

                                       v.set(count++);

                                       return v;

                                }

     

                                public void remove() {

                                       throw new UnsupportedOperationException();

                                }

                         };

                  }

           }

           public static void main(String[] args) {

                  Values vs = new Values(10);

                  Value result = null;

                  for(Value v:vs){

                         if(result ==  null){

                                result = v;

                         }

                         else{

                                result.set(result.get()+v.get());

                         }

                  }

                  System.out.println(result.get());

           }

    }

    a)       20 b)40 c)45 d)55 e)throws NullpointerException

     

    8. If add keyword “final” before a class member function, it means:

    a) The method can’t access the non-final member variable.

    b) The method can’t modify the member variable.

    c) The method can’t be override by subclass.

    d) The method is a thread-safe function.

    e) The method can’t be accessed by other non-final function.

     

    9. About java memory and garbage collector, which statement is correct?

    a) Moving variable from locale to class will make GC more effectively.

    b) When Full GC is executing, all the user threads will be paused.

    c) If object A contains a reference of object B and object B contains a reference of object A, the two objects can’t be reclaimed by GC.

    d) When a thread exits, all objects which created by that thread will be reclaimed

    e) It is recommended that calling “System.gc()” to control the memory usage.

     

    10. About java classpath and classloader, which statement is NOT correct?

    a) User can specify the classpath by using the option “-cp” in Java command line.

    b) If user doesn’t specify classpath, the JVM search the class from the current folder by default.

    c) A JVM can load two different versions of a library.

    d) To define customized class loader, it is possible to load class from internet at runtime.

     

     

    11. Which data structure has best performance when remove an element from it?

    a) Vector b)ArrayList c)LinkedList d)HashMap e)HashSet

     

    12. Which is the correct way to convert bytes from charset “gb2312” to “utf-8”?

    byte[] src , dst;

    a) dst = new String(src,”utf-8”).getBytes(“gb2312”);

    b) dst = new String(src,”gb2312”).getBytes(“utf-8”);

    c) dst = new String(src,”utf-16”).getBytes();

    d) dst = new String(src).getBytes();

    e) None of above.

     

    posted @ 2012-11-07 09:46 小明 閱讀(2539) | 評(píng)論 (3)編輯 收藏

    主站蜘蛛池模板: 国产亚洲成av片在线观看| 亚洲国产成人影院播放| 永久久久免费浮力影院| 午夜亚洲国产成人不卡在线| 亚洲乱码国产一区网址| 亚洲av永久无码精品漫画| 亚洲黄色三级视频| 亚洲精华国产精华精华液| 免费一区二区无码视频在线播放 | 久久精品国产精品亚洲精品 | 中文字幕亚洲日本岛国片| 亚洲精品免费观看| 亚洲乱码av中文一区二区| 一区二区三区免费高清视频| 久久精品成人免费网站| 岛国av无码免费无禁网站| 国产亚洲精品AA片在线观看不加载 | 亚洲国产日韩女人aaaaaa毛片在线| 一本色道久久88—综合亚洲精品| 成年免费大片黄在线观看com| 无码日韩精品一区二区免费暖暖 | 成人影片一区免费观看| 99视频全部免费精品全部四虎| 国产a级特黄的片子视频免费| 亚洲成亚洲乱码一二三四区软件| 亚洲AV成人噜噜无码网站| caoporn成人免费公开| 四虎在线免费视频| 亚洲精品第一国产综合境外资源| 精品亚洲麻豆1区2区3区| 国产亚洲女在线线精品| **毛片免费观看久久精品| 免费一区二区视频| 亚洲黄色网址在线观看| 黄人成a动漫片免费网站| 久久A级毛片免费观看| 亚洲av日韩片在线观看| 亚洲av专区无码观看精品天堂| a级毛片免费观看在线| 成人免费看吃奶视频网站| 久久九九亚洲精品|