分类 LeetCode 下的文章

水壶问题

问题描述

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的z升水。

你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4
输出: True

示例 2:
输入: x = 2, y = 6, z = 5
输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/water-and-jug-problem

思路

满足题意需要有z=x+y;
如果z=ax+by（a，b均整），x与y最大公约数为g，那么z一定是g的整数倍，即z%g=0;
需要注意的是，g不能为0，所以，x==0&&y==0这一种情况需要特判。

题解

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(x==0&&y==0) return z==x;
        return z%gcd(x,y)==0&&(x+y>=z);
    }
    int gcd(int x,int y){
        return y?gcd(y,x%y):x;
    }
};

数字范围按位与

问题描述

给定范围 [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/

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. ...
  9. 28