转置文件

问题描述

给定一个文件 file.txt，转置它的内容。
你可以假设每行列数相同，并且每个字段由 ' ' 分隔.

示例:
假设 file.txt 文件内容如下：
name age
alice 21
ryan 30

应当输出：
name alice ryan
age 21 30

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/transpose-file

题解

一定要使用 awk '' file.txt命名

awk '{ #这个大括号里的代码是 对正文的处理
    # NF表示列数，NR表示已读的行数
    # 注意for中的i从1开始，i前没有类型
    for (i=1; i<=NF; i++){#对每一列
        if(NR==1){       #如果是第一行
            #将第i列的值存入res[i],$i表示第i列的值，i为数组的下标，以列序号为下标，
            #数组不用定义可以直接使用
            res[i]=$i;   
        }
        else{
            #不是第一行时，将该行对应i列的值拼接到res[i]
            res[i]=res[i] " " $i
        }
    }
}
# BEGIN{} 文件进行扫描前要执行的操作；END{} 文件扫描结束后要执行的操作。
END{
    #输出数组
    for (i=1; i<=NF; i++){
        print res[i]
    }
}' file.txt

链接：https://leetcode-cn.com/problems/transpose-file/comments/
来源：livy

部门工资最高的员工

问题描述

Employee 表包含所有员工信息，每个员工有其对应的 Id, salary 和 department Id。

+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
+----+-------+--------+--------------+

Department 表包含公司所有部门的信息。

+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

编写一个 SQL 查询，找出每个部门工资最高的员工。例如，根据上述给定的表格，Max 在 IT 部门有最高工资，Henry 在 Sales 部门有最高工资。

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| Sales      | Henry    | 80000  |
+------------+----------+--------+

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/department-highest-salary

思路

方法：使用 JOIN 和 IN 语句

算法
因为 Employee 表包含 Salary 和 DepartmentId 字段，我们可以以此在部门内查询最高工资。

SELECT
    DepartmentId, MAX(Salary)
FROM
    Employee
GROUP BY DepartmentId;

注意：有可能有多个员工同时拥有最高工资，所以最好在这个查询中不包含雇员名字的信息。

| DepartmentId | MAX(Salary) |
|--------------|-------------|
| 1            | 90000       |
| 2            | 80000       |

然后，我们可以把表 Employee 和 Department 连接，再在这张临时表里用 IN 语句查询部门名字和工资的关系。

代码见题解

| Department | Employee | Salary |
|------------|----------|--------|
| Sales      | Henry    | 80000  |
| IT         | Max      | 90000  |

题解

SELECT
    Department.name AS 'Department',
    Employee.name AS 'Employee',
    Salary
FROM
    Employee
        JOIN
    Department ON Employee.DepartmentId = Department.Id
WHERE
    (Employee.DepartmentId , Salary) IN
    (   SELECT
            DepartmentId, MAX(Salary)
        FROM
            Employee
        GROUP BY DepartmentId
    )
;

作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/bu-men-gong-zi-zui-gao-de-yuan-gong-by-leetcode/

统计词频

问题描述

写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。

为了简单起见，你可以假设：
words.txt只包括小写字母和 ' ' 。
每个单词只由小写字母组成。
单词间由一个或多个空格字符分隔。

示例:
假设 words.txt 内容如下：
the day is sunny the the
the sunny is is
你的脚本应当输出（以词频降序排列）：
the 4
is 3
sunny 2
day 1

说明:
不要担心词频相同的单词的排序问题，每个单词出现的频率都是唯一的。
你可以使用一行 Unix pipes 实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-frequency

思路

本题先用cat命令和管道命令|将文件内容传给awk。

在awk中我们用一个字典(?)count储存每个单词的词频，先遍历每一行(awk自身机制)的每一个字段(i<=NF)，然后用该字段本身作为key,将其value++；最后用一个for循环输出count数组中的每个元素的key(词)及其value(词频)。

最后用|管道命令传给sort命令：

-r是倒序排序，相当于DESC
-n是将字符串当作numeric数值排序
-k则指定用于排序的字段位置，后跟2指将第二位的countk作为排序的key

作者：gao-si-huang-bu
链接：https://leetcode-cn.com/problems/two-sum/solution/awksort-by-gao-si-huang-bu/

题解

cat words.txt | awk '{ for(i=1;i<=NF;i++){count[$i]++} } END { for(k in count){print k" "count[k]} }' | sort -rnk 2

分数排名

问题描述

编写一个 SQL 查询来实现分数排名。如果两个分数相同，则两个分数排名（Rank）相同。请注意，平分后的下一个名次应该是下一个连续的整数值。换句话说，名次之间不应该有“间隔”。

+----+-------+
| Id | Score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+

例如，根据上述给定的 Scores 表，你的查询应该返回（按分数从高到低排列）：

+-------+------+
| Score | Rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rank-scores

思路

对于a表中的每一个分数score，找出b表中有多少个大于或等于该分数的不同的分数，然后按降序排列

题解

select 
    a.Score as score , 
    (select count(distinct b.Score) from Scores b where b.Score >=a.Score) as rank
from Scores a order by Score DESC;

作者：zazalumonster
链接：https://leetcode-cn.com/problems/two-sum/solution/mysqlbi-jiao-hao-li-jie-de-yi-chong-xie-fa-by-zaza/

二叉搜索树迭代器

问题描述

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
 
提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search-tree-iterator

思路

复杂度没满足要求...

• 因为二叉树是搜索二叉树，所以中序遍历的顺序即为从小到大的顺序。
• 设置一个全局变量的指针，指向下一个最小的数。
• 对于bool hasNEXT（）这一函数，当指针指向vec最后一个元素的下一个时，才return false，否则返回true即可。

题解

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class BSTIterator {
private:
    vector<int> vec;
    int location;
public:
    void inorder(TreeNode *node){
        if(node == nullptr){
            return ;
        }
        inorder(node->left);
        vec.push_back(node->val);
        inorder(node->right);
    }
    BSTIterator(TreeNode* root) {
        inorder(root);
        location=0;
    }

    /** @return the next smallest number */
    int next() {
        if(location<vec.size()){
            return vec[location++];
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(location>=vec.size()){
            return false;
        } else return true;
    }
};