DEV Community: Young Kraken

FOP4:Search & Sort

Young Kraken — Sun, 29 Jan 2023 18:40:28 +0000

Find prime numbers

A simple way to find prime numbers

#include <iostream>
using namespace std;

bool isPrime(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

int main()
{
    for (int n = 2; n <= 100; n++)
    {
        if (isPrime(n))
            cout << n << endl;
    }
    return 0;
}

sieve of Eratosthenes

A more efficienty way to find prime numbers:

#include <iostream>
using namespace std;

const int N = 100;
bool seive[N + 1];

int main() {
    for (int i = 2; i <= N; i++)
        seive[i] = true;
    for (int d = 2; d * d <= N; d++)
        if (seive[d])
            for (int n = d * d; n <= N; n += d)
                seive[n] = false;
    for (int n = 2; n <= N; n++)
        if (seive[n])
            cout << n << endl;
    return 0;
}

#include <iostream>
using namespace std;

int main()
{
    int r3 = 0, r5 = 0, r7 = 0, seive[200];
    cin >> r3 >> r5 >> r7;
    for (int i = 0; i < 200; i++)
        seive[i] = 0;
    for (int i = r3; i < 200; i = i + 3)
        seive[i]++;
    for (int i = r5; i < 200; i = i + 5)
        seive[i]++;
    for (int i = r7; i < 200; i = i + 7)
        seive[i]++;
    for (int i = 0; i < 200; i++)
        if (seive[i] == 3)
        {
            cout << i << endl;
            break;
        }
    return 0;
}

Search

Binary search

#include <iostream>
using namespace std;

int main()
{
    int cards[13] = {101, 112, 113, 206, 207, 208,
                     303, 304, 309, 311, 402, 405, 410};
    int id = -1, low = 0, high = 12;
    while (low <= high)
    {
        int middle = (low + high) / 2;
        if (cards[middle] == 112)
        {
            id = middle;
            break;
        }
        else if (cards[middle] > 112)
            high = middle - 1;
        else
            low = middle + 1;
    }
    cout << "黑桃Q在第" << id + 1 << "张" << endl; 
    return 0;
}

Insertion sort

#include <iostream>
using namespace std;

void InsertionSort(int cards[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int target = cards[i], pos = 0;
        while (target > cards[pos])
            pos++;
        for (int j = i; j > pos; j--)
            cards[j] = cards[j - 1];
        cards[pos] = target;
    }
}

Selection Sort

void SelectionSort(int cards[], int n)
{
    for (int i = 0; i < n; i++)
    {
        int min = cards[i], min_id = i;
        for (int j = i + 1; j < n; j++)
            if (cards[j] < min)
            {
                min = cards[j];
                min_id = j;
            }
        cards[min_id] = cards[i];
        cards[i] = min;
    }
}

Application

int main()
{
    int cards[13] = {101, 113, 303, 206, 405, 208,
                     311, 304, 410, 309, 112, 207, 402};
    for (int i = 0; i < 13; i++)
        cout << cards[i] << " ";
    cout << endl;
    SelectionSort(cards, 13);
    for (int i = 0; i < 13; i++)
        cout << cards[i] << " ";
    cout << endl;
    return 0;
}

184. 部门工资最高的员工

Young Kraken — Mon, 07 Feb 2022 21:43:15 +0000

184. 部门工资最高的员工

SQL架构
表： Employee

+--------------+---------+
| 列名          | 类型    |
+--------------+---------+
| id           | int     |
| name         | varchar |
| salary       | int     |
| departmentId | int     |
+--------------+---------+

id是此表的主键列。
departmentId是Department表中ID的外键。
此表的每一行都表示员工的ID、姓名和工资。它还包含他们所在部门的ID。

表： Department

+-------------+---------+
| 列名         | 类型    |
+-------------+---------+
| id          | int     |
| name        | varchar |
+-------------+---------+

id是此表的主键列。
此表的每一行都表示一个部门的ID及其名称。

编写SQL查询以查找每个部门中薪资最高的员工。
按任意顺序返回结果表。
查询结果格式如下例所示。

示例 1:

输入：
Employee 表:
+----+-------+--------+--------------+
| id | name  | salary | departmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Jim   | 90000  | 1            |
| 3  | Henry | 80000  | 2            |
| 4  | Sam   | 60000  | 2            |
| 5  | Max   | 90000  | 1            |
+----+-------+--------+--------------+
Department 表:
+----+-------+
| id | name  |
+----+-------+
| 1  | IT    |
| 2  | Sales |
+----+-------+
输出：
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Jim      | 90000  |
| Sales      | Henry    | 80000  |
| IT         | Max      | 90000  |
+------------+----------+--------+
解释：Max 和 Jim 在 IT 部门的工资都是最高的，Henry 在销售部的工资最高。

197. 上升的温度

Young Kraken — Mon, 07 Feb 2022 17:50:59 +0000

197. 上升的温度

SQL架构
表 Weather

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| recordDate    | date    |
| temperature   | int     |
+---------------+---------+

id 是这个表的主键
该表包含特定日期的温度信息

编写一个 SQL 查询，来查找与之前（昨天的）日期相比温度更高的所有日期的 id 。

返回结果不要求顺序。

查询结果格式如下例：

Weather
+----+------------+-------------+
| id | recordDate | Temperature |
+----+------------+-------------+
| 1  | 2015-01-01 | 10          |
| 2  | 2015-01-02 | 25          |
| 3  | 2015-01-03 | 20          |
| 4  | 2015-01-04 | 30          |
+----+------------+-------------+

Result table:
+----+
| id |
+----+
| 2  |
| 4  |
+----+

2015-01-02 的温度比前一天高（10 -> 25）
2015-01-04 的温度比前一天高（20 -> 30）