G家面经，已跪

tuantuan1211

进来学习，也正在面试

readman

炸弹人的题就是今天lc的新题?

sapphirew

July09 发表于 2016-6-14 11:21
第一题
int convertSortedString(String s) {
int length = s.length();

层主方便解释下思路不。。多谢~

dartmoor

分享一下第一题的做法,
time complexity O(N), space complexity O(1)
大家帮忙看看有没有问题

public class CountChange {
public static void main(String[] args){
String s1 = "aaaaaaabbbbb";
System.out.println(countChange(s1)); // expect 0
String s2 = "aabbbaaabbbbb";
System.out.println(countChange(s2)); // expect 3
String s3 = "bbbbbaaaa";
System.out.println(countChange(s3)); // expect 4
String s4 = "aabbaaabbbbbaa";
System.out.println(countChange(s4)); // expect 4
}
private static int countChange(String s){
//Count the number of 'a'
int countA = 0;
for(int i=0; i<s.length(); i++){
if(s.charAt(i)=='a'){ countA++; }
}
// Keep the "change count" in each position
// The idea is: Given a position in the string, the change count is (number of 'b' in my left) + (number of 'a' in my right)
// So when we see a 'a', minus one. Otherwise plus one
int minCount = countA;
int currCount = countA;
for(int i=0; i<s.length(); i++){
currCount = s.charAt(i)=='a'? currCount-1: currCount+1;
minCount = Math.min(minCount, currCount);
}
return minCount;
}
}

复制代码

qiuxuxing007

炸弹人跟看花题思路一模一样, 还是用dfs, 就是leetcode今天的新题

Thunder_up

请问楼主第三题大概是个啥做法

caoyi

blackrose 发表于 2016-6-14 06:46
Dp 解第一题，不知道对不对，测了点cases，没差。

你的解法貌似有点问题，比如: ababbbbaba --> expect应该是4

caoyi

blackrose 发表于 2016-6-14 06:46
Dp 解第一题，不知道对不对，测了点cases，没差。

你的解法貌似有点问题，比如: ababbbbaba --> expect应该是4

caoyi

blackrose 发表于 2016-6-14 06:46
Dp 解第一题，不知道对不对，测了点cases，没差。

你的解法貌似有点问题，比如: ababbbbaba --> expect应该是4

补充内容 (2016-7-5 02:05):
typo : special case是 ababbbaaba ---> expect 是 4

补充内容 (2016-7-5 02:05):
typo : special case是 ababbbaaba ---> expect 是 4

blackrose

caoyi 发表于 2016-7-5 02:00
你的解法貌似有点问题，比如: ababbbbaba --> expect应该是4

补充内容 (2016-7-5 02:05):

好像是哦，那改成存value