|
2013年4月19日
分析: 这个问题是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]; } }
分析: 因为要求结果集是升序排列,所以首先我们要对数组进行排序。 子集的长度可以从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; } }
分析: 格雷码的序列中应包含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; } }
解法一:(递归) 一个简单的想法,是遍历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]; } }
摘要: 给定一个由n个整数组成的数组S,是否存在S中的三个数a,b,c使得 a+b+c=0?找出所有的不重复的和为0的三元组。
注意:
1.三元组的整数按照升序排列 a 2.给出的结果中不能含有相同的三元组 阅读全文
摘要: 给定两个字符串S和T,计算S的子序列为T的个数。
这里的字符串的子序列指的是删除字符串的几个字符(也可以不删)而得到的新的字符串,但是不能改变字符的相对位置。
比如“ACE”是“ABCDE”的子序列,但是“AEC”就不是。
如果S=“rabbbit” T=“rabit”,有3种不同的子序列为T的构成方法,那么结果应该返回3。 阅读全文
分析: 题目不难,但是在面试时,在有限的时间内,没有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; } } }
分析: 这道题相比之前的两道题,难度提高了不少。 因为限制了只能交易两次,所以我们可以把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; }
分析:为了得到最大收益,必须在所有上升的曲线段的开始点买入,在最高点卖出。而在下降阶段不出手。 实现代码如下: 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; } }
摘要: 假设你有一个数组包含了每天的股票价格,它的第i个元素就是第i天的股票价格。
你只能进行一次交易(一次买进和一次卖出),设计一个算法求出最大的收益。 阅读全文
|