大数据numbers优先级输出

来自MAKA后端笔试的一道题

问题

给一组长度巨大的整数 numbers 和 数值 M, 输出优先级最高的 M 个整数.

约定:

  • 偶数的优先级大于奇数
  • 同样是奇数(或偶数)，数值越小优先级越高
  • 算法时间复杂度最优

分析

  • 长度巨大, 因而需要考虑高精度数字
  • 偶数的优先级大于奇数, 这说明是需要进行奇偶的判断的, 可以想到需要分成两组数据
  • 数值越小优先级越高, 那么则是在同组内, 进行顺序排序
  • 算法时间复杂度最优, 那应该选快速排序, 在数据平均的情况下, 时间复杂度最低

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
class Item
{
    public $length;
    public $data;

    /**
     * Item constructor.
     * @param string $number
     */
    public function __construct($number)
    {
        $this->length = strlen($number);
        $this->data   = $number;
    }

    public function isEven(): bool
    {
        return $this->data[$this->length - 1] % 2 === 0;
    }

    /**
     * @param Item $b
     * @return int
     */
    public function compareWith(Item $b): int
    {
        if ($this->length > $b->length) {
            return 1;
        }
        if ($this->length < $b->length) {
            return -1;
        }

        $result = 0;
        for ($i = 0; $i < $this->length; $i++) {
            if ($this->data[$i] > $b->data[$i]) {
                $result++;
            }
            if ($this->data[$i] < $b->data[$i]) {
                $result--;
            }
        }
        if ($result > 0) {
            return 1;
        }
        if ($result < 0) {
            return -1;
        }
        return 0;
    }
}

/**
 * @param Item[] $arr
 * @return Item[]
 */
function quickSort(array $arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    $left = $right = [];
    // 基准值
    $middle = $arr[0];

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值，存入左边；大于基准值，存入右边
        if ($arr[$i]->compareWith($middle) < 0) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    $left  = quickSort($left);
    $right = quickSort($right);

    // 顺序
    return array_merge($left, [$middle], $right);
    // 降序
//     return array_merge($right, [$middle], $left);
}

function run($numbers, $M)
{
    $odd  = [];
    $even = [];

    foreach ($numbers as $number) {
        $number = new Item($number);
        if ($number->isEven()) {
            $even[] = $number;
        } else {
            $odd[] = $number;
        }
    }

    // TODO: 这里其实还可以再根据 M 来做一些小优化的

    foreach (quickSort($even) as $item) {
        echo $item->data . ' ';
        $M--;
        if ($M === 0) {
            echo PHP_EOL;
            return;
        }
    }

    foreach (quickSort($odd) as $item) {
        echo $item->data . ' ';
        $M--;
        if ($M === 0) {
            echo PHP_EOL;
            return;
        }
    }

    echo PHP_EOL;
}

run(['6', '7', '3', '5', '4', '2', '3', '3', '1'], 3);

柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

  • 输入：[5,5,5,10,20]
  • 输出：true
  • 解释：
  • 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
  • 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
  • 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
  • 由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

  • 输入：[5,5,10]
  • 输出：true

示例 3：

  • 输入：[10,10]
  • 输出：false

示例 4：

  • 输入：[5,5,10,10,20]
  • 输出：false
  • 解释：
  • 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
  • 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
  • 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
  • 由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示： 0 <= bills.length <= 10000

bills[i] 不是 5 就是 10 或是 20

解法:

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
27
28
29
30
31
32
class Solution {
    /**
     * @param Integer[] $bills
     * @return Boolean
     */
    function lemonadeChange($bills) {
        $a = $b = 0;
        foreach ($bills as $bill) {
            if ($bill === 5) {
                $a++;
            }
            if ($bill === 10) {
		if ($a === 0) {
                    return false;
                }
                $b++;
                $a--;
            }
            if ($bill === 20) {
		if ($b > 0 && $a > 0) {
                    $b--;
                    $a--;
                } else if ($a >= 3) {
                    $a -= 3;
                } else {
                    return false;
		}
            }
        }
        return true;
    }
}

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

  • 输入: s = “abcabcbb”
  • 输出: 3
  • 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

  • 输入: s = “bbbbb”
  • 输出: 1
  • 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

  • 输入: s = “pwwkew”
  • 输出: 3
  • 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
  • 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

示例 4:

  • 输入: s = “”
  • 输出: 0

解法一: 暴力解法

我采用的是暴力的解法, 复杂度最差 O(n^2), 话不多说, 贴代码:

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
{
    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s)
    {
        $len = strlen($s);
        $i = $max = 0;

        for ($j = 0; $j < $len; $j++) {
            for ($k = $i; $k < $j; $k++) {
                if ($s[$k] === $s[$j]) {
                    $i = $k + 1;
                    break;
                }
            }
            if ($j - $i + 1 > $max) {
                $max = $j - $i + 1;
            }
        }

        return $max;
    }
}

运行时间 16ms, 内存 15.2MB

解法二: 哈希表解法

还是那句话, 空间换时间!

未完待续… 下次补..下次补..

高效算法设计

  • 算法分析初步
  • 排序与检索
    • 归并
    • 快速
    • 二分查找
  • 递归和分治
  • 贪心
    • 背包
    • 区间
    • 哈夫曼编码
  • 算法设计与优化策略

暴力求解法

  • 简单枚举
  • 排列
  • 子集生成
    • 增量构造
    • 位向量法
    • 二进制法
  • 回溯法
    • 八皇后
  • 路径寻找问题
  • 迭代加深搜索

数论概念和方法

  • 数论初步
  • 计数与概率基础
  • 其他数学专题

数据结构基础

  • 栈与队列
  • 链表
  • 树和二叉树
    • 二叉树的层次遍历
    • 二叉树的递归遍历
  • 图
    • BFS
    • DFS
    • 拓补排序
    • 欧拉回路

平衡二叉树

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。

在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

特点

AVL树本质上还是一棵二叉搜索树，它的特点是：

  1. 本身首先是一棵二叉搜索树。
  2. 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
    也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

图论模型与算法

  • 再谈树
  • 最小生成树
  • 最短路问题
  • 网络流初步

动态规划初步

  • 数字三角形
  • DAG的动态规划
  • 多阶段决策问题
  • 更多经典模型
    • 线性结构
    • 树
    • 复杂状态