作者:泱泱大国吴 | 来源:互联网 | 2023-05-17 18:24
给一个string,一个整数k,每2k个char中前k个reverse,后k个不变。如果剩下的字符不满k个则把剩下的全部reverse,如果剩下大于k小于2k,那么前k个reverse,剩
给一个string,一个整数 k, 每2k个char 中前k个reverse, 后k个不变。 如果剩下的字符不满k个则把剩下的全部reverse,如果剩下大于k小于2k,那么前k个reverse,剩下的不变。
eg. "abcdefg" k = 2, output "bacdfeg"
秒了之后口头run了一下
class Solution {
public void reverse(String s, int k) {
if (s == null || s.length() <2) {
return;
}
int len = s.length();
int count = len / k;
int i = 0;
StringBuilder sb = new StringBuilder();
while (i if (i % 2 == 0) {
StringBuilder temp = new StringBuilder();
temp.append(s.substring(i * k, i * k + k));
sb.append(temp.reverse());
} else {
sb.append(s.substring(i * k, i * k + k));
}
i++;
}
if (len % k == 0) {
System.out.println(sb.toString());
return ;
}
if (count % 2 == 1) {
sb.append(s.substring(count * k, s.length()));
System.out.println(sb.toString());
return ;
} else {
StringBuilder temp = new StringBuilder();
temp.append(s.substring(count * k, s.length()));
sb.append(temp.reverse());
System.out.println(sb.toString());
return ;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
String s = "abcdefg";
sol.reverse(s, 2);
}
}
当我看到只有一个白大叔的时候心里一凉。。。这不会是礼节性第二轮面试吧。。。直接导致刚开始有点不兴奋。。。。
聊了下简历然后做了design的题目
1. web browser 的前进后退功能。要求实现一个class,有add url(访问新网址,有size上限k), goback, gofront分别能显示前后各访问过的所有网址。然后如果在后退了之后所在的页面访问了新网址,则丢弃所有原来的向前的页面。(基本上要求就是面试官一遍用电脑上的chrome给我秀,一边讲的)
eg. 访问顺序是 a-> b -> c -> d -> e -> f
然后后退回到d, 那么getback返回的就是c, b, a(按时间顺序), getfront返回的是e, f。如果在d这个页面又访问了新的页面 g, 那么就丢弃e, f。 把g放在d后面。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
用list, 一个capacity的整数加上一个current page 的list::iterator就可以搞定。 搞完之后大哥说哎哟还有点时间,我们再design一个东西吧。。。。
2.twitter有个功能叫做hashtag 比如"#trump",要求设计一个class,能够记录所有的hashtag,以及被提及的次数,然后实现一个trending 功能,返回当前被提及次数最高的20个hashtag。说完大哥掏出手机又给我demo了一遍。。。这个没有要求细节的coding,详细的说了下实际的数据结构还有函数 怎么写就完了. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
用了unordered_map记录每个hashtag的提及次数,又有用了个大小为20的map>保存最大的20个频率的值和有这么多频率的hashtag的名字,这里lz本来想把所有hashtag都放到map里,然后被质疑hashtag太多这样太慢,然后经过提醒,维护一个size为20的map,插入时间从lgn优化成o1。 获取前20 只要从最大的频率开始遍历map,凑满20个就行。 但是维护大小为20的map,每次frequency改变需要检查并且更新这个map。