小明思考

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

          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.

           


          分析:

          這個問題是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 小明 閱讀(6141) | 評論 (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],   [] ] 

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

          子集的長度可以從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 小明 閱讀(2122) | 評論 (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 小明 閱讀(2587) | 評論 (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 小明 閱讀(3238) | 評論 (4)編輯 收藏

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

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

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

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

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

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

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

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

          問題給定一顆二叉樹:
          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 小明 閱讀(2133) | 評論 (0)編輯 收藏

          問題假設你有一個數組包含了每天的股票價格,它的第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 小明 閱讀(2074) | 評論 (0)編輯 收藏

          問題假設你有一個數組包含了每天的股票價格,它的第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 小明 閱讀(1857) | 評論 (0)編輯 收藏

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

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

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

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

          比如:對于二叉樹
          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; }
          * }
          */  閱讀全文

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

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

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

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

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

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

               摘要: 給定兩個排序好的數組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)。  閱讀全文

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

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

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

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

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

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

               摘要: 給定一個二叉樹,每個節點的值是一個數字(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  閱讀全文

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

               摘要: 給定一個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) {
          }  閱讀全文

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

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

          比如,對于字符串s="aab",
          返回:

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

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

          +1

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

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

               摘要: 實現 int sqrt(int x);
          計算和返回x的平方根。  閱讀全文

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

               摘要: 給定一個未排序的整數數組,求最長的連續序列的長度。要求算法的時間復雜度在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
          }
          }  閱讀全文

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

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

          posted @ 2013-04-11 11:24 小明 閱讀(4150) | 評論 (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 小明 閱讀(406) | 評論 (0)編輯 收藏

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

          ---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 小明 閱讀(2546) | 評論 (3)編輯 收藏

          主站蜘蛛池模板: 肃南| 独山县| 阜新市| 菏泽市| 清河县| 锡林郭勒盟| 浮梁县| 桐庐县| 荣昌县| 什邡市| 临猗县| 漯河市| 漳平市| 庆安县| 晋州市| 澎湖县| 辽源市| 建平县| 罗城| 二手房| 嵩明县| 仁化县| 梅州市| 民权县| 高清| 荆州市| 永清县| 正安县| 宁晋县| 安徽省| 台州市| 桂阳县| 通道| 五寨县| 湖南省| 宝清县| 利津县| 宜良县| 玉林市| 济源市| 湖南省|