ireneliu 发布的文章

数字范围按位与

问题描述

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1: 
输入: [5,7]
输出: 4

示例 2:
输入: [0,1]
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range

思路

当一个数+1时，总会有这么一个规律“某一位后的数字，全部被置为相反数”。举个例子：

  • 010111 + 1 = 011000，则010111 & 011000 = 010000。那么，x & (x+1) 后几位相反数的“与操作”，结果总为0。
  • 所以，当(m,m+1,...n-1,n)进行连续“与操作”时，会按照上述规律被抵消很大一部分，而只剩下n的前缀部分，最后只需将n归位。举个例子：
    m = 5(0101), n = 7 (0111)。不停右移，得到n前缀部分为01，最后归位前缀得res=0100=4

来源：李一一
链接：https://blog.csdn.net/smile_watermelon/article/details/47320381

题解

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int count=0;
        for(;m!=n;count++){
            m>>=1;
            n>>=1;
        }
        int ret;
        ret=n<<count;
        return ret;
    }
};

二叉树的右视图

问题描述

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

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

思路

和层次遍历的思路是一样的

  • 按层将二叉树存到vector<vector<int>> vec中，此处和二叉树的层次遍历不同的是，本题从每层的右侧开始存。
    当然也可以从每层的左边开始遍历，用reverse反转一下就可以了。
  • 将veci存到vector<int> ret中。
  • 最后return ret即可。

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> vec;
    vector<int> ret;

    vector<int> rightSideView(TreeNode *root) {
        dfs(root, 0);
        int n = vec.size();
        if (n == 0) return ret;
        for(int i=0;i<n;i++){
            ret.push_back(vec[i][0]);
        }
        return  ret;
    }

    void dfs(TreeNode *node, int level) {
        if (node == nullptr) return;
        if (level + 1 > vec.size()) vec.push_back(vector<int>());
        vec[level].push_back(node->val);
        dfs(node->right, level + 1);
        dfs(node->left, level + 1);
    }
};

转置文件

问题描述

给定一个文件 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
  1. 1
  2. ...
  3. 11
  4. 12
  5. 13
  6. 14
  7. 15
  8. 16
  9. 17
  10. ...
  11. 38