小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2013年5月22日

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 小明 阅读(6108) | 评论 (0)编辑 收藏

2013年5月21日

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 小明 阅读(2092) | 评论 (0)编辑 收藏

2013年5月20日

问题格雷码是一个二进制的编码系统,相邻的两个数只有一位是不同的。
给定一个非负的整数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 小明 阅读(2555) | 评论 (0)编辑 收藏

2013年5月10日

问题给定字符串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 小明 阅读(3197) | 评论 (4)编辑 收藏

2013年5月1日

     摘要: 给定一个由n个整数组成的数组S,是否存在S中的三个数a,b,c使得 a+b+c=0?找出所有的不重复的和为0的三元组。

注意:
1.三元组的整数按照升序排列 a2.给出的结果中不能含有相同的三元组  阅读全文

posted @ 2013-05-01 23:13 小明 阅读(1902) | 评论 (0)编辑 收藏

2013年4月26日

     摘要: 给定两个字符串S和T,计算S的子序列为T的个数。

这里的字符串的子序列指的是删除字符串的几个字符(也可以不删)而得到的新的字符串,但是不能改变字符的相对位置。

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

如果S=“rabbbit” T=“rabit”,有3种不同的子序列为T的构成方法,那么结果应该返回3。  阅读全文

posted @ 2013-04-26 23:33 小明 阅读(1985) | 评论 (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 小明 阅读(2093) | 评论 (0)编辑 收藏

2013年4月25日

问题假设你有一个数组包含了每天的股票价格,它的第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 小明 阅读(2049) | 评论 (0)编辑 收藏

2013年4月19日

问题假设你有一个数组包含了每天的股票价格,它的第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 小明 阅读(1823) | 评论 (0)编辑 收藏

     摘要: 假设你有一个数组包含了每天的股票价格,它的第i个元素就是第i天的股票价格。

你只能进行一次交易(一次买进和一次卖出),设计一个算法求出最大的收益。  阅读全文

posted @ 2013-04-19 15:03 小明 阅读(1556) | 评论 (0)编辑 收藏