C++题
1. 排列硬币
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:
示例 2:
使用二分法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int arrangeCoins(int n) {
// initialize
int st,ed;
st = 0;
ed = n;
while(st<=ed){
int mid = st + (ed-st)/2;
long sum = getSum(mid);
if (sum<n){
st = mid + 1;
} else if (sum>n){
ed = mid - 1;
} else {
return mid;
}
}
return ed;
}
long getSum(int num){
long tmp = num;
return ((1+tmp)*tmp)/2;
}
};
2. 代码审查
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有
n个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用
bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。示例:
同1题用二分法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int st = 0;
int ed = n;
while(st<=ed){
int mid = st + (ed-st)/2;
if(isBadVersion(mid)){
// mid 为坏版本
ed = mid -1;
} else {
st = mid + 1;
}
}
return ed+1;
}
};
3.论文h指数
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）至多有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”
示例:
输入: citations = [3,0,6,1,5] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。 由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。说明: 如果 h 有多种可能的值，h 指数是其中最大的那个。
先排序，按照题意遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(),citations.end());
int ans = 0;
for(int i=citations.size()-1;i>=0;i--){
if(citations[i]>=citations.size()-i){
ans = max(ans,(int)citations.size()-i);
}
}
return ans;
}
};
Shell题
1. 使用Shell进行词频统计
参考答案：
cat hello.txt | xargs -n 1 | sort | uniq -c | sort -nr | awk ‘{print $2" "$1}’
解析1：
-
cat输出hello.txt内容
-
xargs此处的作用是分隔字符串教程
-
-n 1表示每行1个分隔单词 -
-d可以指定分隔符号(实测macOS中没有-d)-
xargs: illegal option – d usage: xargs [-0opt] [-E eofstr] [-I replstr [-R replacements]] [-J replstr] [-L number] [-n number [-x]] [-P maxprocs] [-s size] [utility [argument …]]
-
-
-
uniq可以去重-c显示出现的次数- 注意：
uniq只关心相邻的重复，所以指令uniq之前还要进行一次sort
-
sort排序-nr为-n和-r的缩写-n把数字当做真正的数字作处理，故不会出现11<2的情况-r为反转，实现降序排列
-
awk格式化输出，指令详解- 格式
awk data actiondata为文本中每一行的数据，action为对文本中每一行的操作
- 格式
解析2：
cat words.txt | sed ‘s/[ ][ ]*/\n/g’ | egrep -v “^$“|sort | uniq -c | sort -nr | awk ‘{print $NF,$1}’ sed ‘s/要被取代的字串/新的字串/g’ egrep -v ‘^$’ ：命令的作用是过滤空白符 -v 就是取反 sort ： 给每行字符排序，目的是把相同字符放在一起 uniq -c ：-c或–count 在每列旁边显示该行重复出现的次数。 sort -nr ：按照整个数字排序，目的是让重复出现次数从大到小逆行排序 -n 依照数值的大小排序，升序排列。 以相反的顺# 序来排序。 $NF表示最后一个列（field），即输出最后一个字段的内容 $1 输出第一列的内容
2. 统计指定文件夹下某种类型文件的代码行数和
find . “() -name “*.java” “)” -print xargs wc -l
其中：
"(" -name "*.txt" ")"表示拓展名为.txt的文件，前者指令将.txt筛选出来xargs格式化指令，实现将标准输入作为命令的参数- 与管道不同，管道是实现”将前面的标准输出作为后面的标准输入”.
wc -l加上前面的传参，就可以查找出这些文件的行数
MetaNetworks@jintaodeMacBook-Air /tmp find . “(“ -name “*.txt” “)” -print | xargs wc -l | sort -nr | awk ‘{print $2 “ “$1}’ total 3 ./hello.txt 3 ./crash_repo_pref.txt 0
