LeetCode刷题记录

部分参考网友解答

Posted by 一个算法小白 on January 22, 2020
本页面总访问量

C++题

1. 排列硬币

你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。

给定一个数字 n,找出可形成完整阶梯行的总行数。

n 是一个非负整数,并且在32位有符号整型的范围内。

示例 1:

1
2
3
4
5
6
7
8
n = 5

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤

因为第三行不完整,所以返回2.

示例 2:

1
2
3
4
5
6
7
8
9
n = 8

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

因为第四行不完整,所以返回3.

使用二分法

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
2
3
4
5
6
7
给定 n = 5,并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。 

同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 次。)”

示例:

1
2
3
4
输入: 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 action
      • data为文本中每一行的数据,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