# 小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
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.

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

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 小明 阅读(5883) | 评论 (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],   [] ] `

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>();

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);
++e;
last = v;
}
}
}

start = end+1;
end = e;
}
return result;
}
}

posted @ 2013-05-21 22:50 小明 阅读(1936) | 评论 (0)编辑 收藏

0 ＝ 00
1 ＝ 01
3 ＝ 11
2 ＝ 10

00，01，11，10

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>();
if(n>0){
}

int mask = 1;
for(int i=2;i<=n;++i){
for(int j=result.size()-1;j>=0;--j){
int v = result.get(j).intValue();
}
}
return result;
}
}

posted @ 2013-05-20 21:09 小明 阅读(2356) | 评论 (0)编辑 收藏

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

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

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] = (result[i-1,j] && s1[i] = s3[i+j])  || (result[i,j-1] && s2[j] = s3[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();

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

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

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

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

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

posted @ 2013-04-26 23:33 小明 阅读(1724) | 评论 (1)编辑 收藏

}

1
/  \
2    3
/ \    \
4   5    7

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

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

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

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(q>p){
min=p ;
}
}
else{
if(q<p){
result += (p-min);
}
}
}