手撕题整理¶

一、算法题¶

1. 数组与字符串¶

数组判重（O(1) 空间）¶

题目：有一个容量为 N 的数组，里面存放了 N 个数，每个数的取值范围是 1~N。快速判断是否有重复元素，以及哪个元素重复了。空间复杂度要求 O(1)。

思路：利用数组下标作为哈希。遍历数组，将每个数 num 交换到下标 num - 1 处。如果发现目标位置已经是 num，则 num 为重复元素。

数组 append¶

题目：实现数组的 append 方法，排除空情况。

最大子数组和¶

题目：最大子数组和

大数字相加¶

题目：JS 中数字最大值不能超过 2^53，若必须进行更大数字的加法，且不允许使用 BigInt，如何处理？

前提：参数必须为字符串类型。

思路：先将较短的数字补前导零，使两数长度相同，再从最低位逐位相加，记录进位。

function addLargeNumbers(num1, num2) {
    let carry = 0;
    let result = "";
    const maxLength = Math.max(num1.length, num2.length);

    num1 = num1.padStart(maxLength, "0");
    num2 = num2.padStart(maxLength, "0");

    for (let i = maxLength - 1; i >= 0; i--) {
        let sum = parseInt(num1[i], 10) + parseInt(num2[i], 10) + carry;
        carry = Math.floor(sum / 10);
        result = (sum % 10) + result;
    }

    if (carry > 0) {
        result = carry + result;
    }

    return result;
}

版本号排序¶

题目：给定版本号字符串数组，按从小到大排序。注意版本号分段比较，如 "1.8" < "1.45"。

思路：按 . 分割成数字数组，逐位比较。

function versionSort(arr) {
    function compareVersions(a, b) {
        const partsA = a.split(".").map(Number);
        const partsB = b.split(".").map(Number);

        const len = Math.max(partsA.length, partsB.length);
        for (let i = 0; i < len; i++) {
            const pa = partsA[i] || 0;
            const pb = partsB[i] || 0;
            if (pa !== pb) {
                return pa - pb;
            }
        }
        return 0;
    }
    return arr.sort(compareVersions);
}

合并区间¶

题目：合并区间

20250312：这道题只有前半部分的思路，但是不理解代码的具体使用，需改善。

字符串转整数（atoi）¶

题目：字符串转整数

找出整数数组中第二大的数¶

题目：输入为字符串形式的数组（表示大整数），输出第二大的数。

思路：先按字符串长度降序，长度相同则按字典序降序。

public String kthLargestNumber(String[] nums, int k) {
    Arrays.sort(nums, (a, b) -> {
        if (a.length() == b.length()) {
            return b.compareTo(a);
        } else {
            return b.length() - a.length();
        }
    });
    return nums[k - 1];
}

找出最小无法取得数¶

题目：给定数组 arr，求数组内元素最小的无法取到的正整数和。

条件： 1. 每个元素可选或不选； 2. 同一个元素不能重复使用； 3. arr[i] 全为正整数。

思路：贪心。排序后维护一个 result，表示当前 [1, result) 区间都可以被覆盖。若 arr[i] > result，则 result 即为答案；否则 result += arr[i]。

public int findMinImpossible(int[] arr) {
    Arrays.sort(arr);
    int result = 1;
    for (int j : arr) {
        if (result < j) {
            break;
        }
        result += j;
    }
    return result;
}

2. 链表¶

两个链表找第一个公共节点¶

题目：两个链表找第一个公共节点（口头描述）。

思路：双指针法。两个指针分别从头出发，走到末尾后切换到另一个链表的头，最终会在第一个公共节点相遇。

链表就地反转¶

基础技巧，常与双指针配合实现。

合并两个升序链表¶

题目：合并两个升序链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    current.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

环形链表¶

题目：141. 环形链表

3. 树与图¶

多叉树路径和¶

题目：多叉树数据结构自己定义，判断是否存在一条路径上的和等于 sum。

目录树查找¶

题目：给定一个树状数组表示的目录结构，每个对象包含 name 和 children，根据目录名找到对应节点。

黑白块¶

题目：167. 黑白块

待做。

迭代后序遍历二叉树¶

题目：迭代实现二叉树的后序遍历。

4. 栈、队列与单调栈¶

设计一个队列（数组动态扩容）¶

题目：设计一个队列，要求底层用数组支持动态扩容。

单调栈¶

常用于解决「下一个更大元素」等问题。

LRU 缓存¶

题目：146. LRU 缓存

5. 二分与前缀和¶

二分查找¶

题目：在有序的（升序）整型数组 nums 中查找目标值 target。

思路：左右指针取中，每次排除一半不符合条件的数据。

public int search(int[] nums, int target) {
    if (target < nums[0] || target > nums[nums.length - 1]) {
        return -1;
    }
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

区间和（前缀和）¶

题目：58. 区间和

描述：给定整数数组，计算每个指定区间内元素的总和。

思路：构造前缀和数组 p，区间 [a, b] 的和为 p[b] - p[a - 1]（若 a == 0 则为 p[b]）。

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] vec = new int[n];
    int[] p = new int[n];

    int presum = 0;
    for (int i = 0; i < n; i++) {
        vec[i] = scanner.nextInt();
        presum += vec[i];
        p[i] = presum;
    }

    while (scanner.hasNextInt()) {
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        int sum;
        if (a == 0) {
            sum = p[b];
        } else {
            sum = p[b] - p[a - 1];
        }
        System.out.println(sum);
    }

    scanner.close();
}

开发商购买土地（二维前缀和）¶

题目：44. 开发商购买土地

描述：在 n * m 的区域内，只能横向或纵向切成两个子区域，求两个子区域总价值之差的最小值。

import java.util.Scanner;
import static java.lang.Math.abs;
import static java.lang.Math.min;

public class p44 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int sum = 0;
        int[][] nums = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nums[i][j] = scanner.nextInt();
                sum += nums[i][j];
            }
        }

        // 横向每行总和
        int[] hori = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                hori[i] += nums[i][j];
            }
        }

        // 纵向每列总和
        int[] ver = new int[m];
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                ver[j] += nums[i][j];
            }
        }

        int result = Integer.MAX_VALUE;
        int horizontalCut = 0;
        for (int i = 0; i < n; i++) {
            horizontalCut += hori[i];
            result = min(result, abs(sum - horizontalCut - horizontalCut));
        }

        int verticalCut = 0;
        for (int j = 0; j < m; j++) {
            verticalCut += ver[j];
            result = min(result, abs(sum - verticalCut - verticalCut));
        }

        System.out.println(result);
    }
}

注：原代码在 hori 与 ver 的维度及循环变量上存在笔误，上述代码已按题意修正。

照明灯安装（二分答案）¶

题目：166. 照明灯安装

待做。

6. 其他经典算法¶

扑克牌顺子问题¶

题目：输入一个长度为 5 的列表，判断是否为顺子（连续）。

64 匹马，8 个赛道¶

题目：64 匹马，8 个赛道，每次可同时跑 8 匹，如何找出最快的四匹？最少需要多少轮？

手写 WordCount¶

题目：写一个 wordcount。

二、SQL 题¶

1. 连续登录¶

查出连续登录 3 天以上的人¶

思路： 1. t1：用 date_sub(date, dense_rank() over (partition by uid order by date)) 计算连续登录分组标识 dt。 2. t2：按 uid, dt 分组，统计每个连续区间的登录天数 count(distinct date)。 3. t3：筛选天数 >= 3 的用户。

WITH t1 AS (
    SELECT
        uid,
        date,
        DATE_SUB(date, INTERVAL DENSE_RANK() OVER (PARTITION BY uid ORDER BY date) DAY) AS dt
    FROM user_login
),
t2 AS (
    SELECT
        uid,
        dt,
        COUNT(DISTINCT date) AS days_cnt
    FROM t1
    GROUP BY uid, dt
)
SELECT uid
FROM t2
WHERE days_cnt >= 3;

最大连续登录天数¶

SELECT
    B.uid,
    MAX(B.num) AS cnt_days
FROM (
    SELECT
        A.uid,
        A.dt1,
        COUNT(A.dt1) AS num
    FROM (
        SELECT
            uid,
            DATE_SUB(dt, ROW_NUMBER() OVER (PARTITION BY uid ORDER BY dt)) AS dt1
        FROM user_login
    ) A
    GROUP BY A.uid, A.dt1
) B
GROUP BY B.uid;

2. 留存率与同时在线¶

次日留存率（通用模板）¶

SELECT
    k1.dt,
    COUNT(DISTINCT k1.tuid) AS dau,
    COUNT(DISTINCT CASE
        WHEN DATE_DIFF('day', CAST(k1.dt AS DATE), CAST(k2.dt AS DATE)) = 1
        THEN k2.tuid
    END) * 1.0 / COUNT(DISTINCT k1.tuid) AS day_rate_2
FROM (
    SELECT DISTINCT dt, tuid
    FROM dwd_dau_custom_di
    WHERE dt >= '2020-06-01'
) k1
LEFT JOIN (
    SELECT DISTINCT dt, tuid
    FROM dwd_dau_custom_di
    WHERE dt >= '2020-06-01'
) k2
ON k1.dt <= k2.dt AND k1.tuid = k2.tuid
GROUP BY k1.dt
ORDER BY k1.dt DESC;

=1 为次日留存，=3 为第三日留存，<=3 为三日留存。

同时在线人数峰值¶

题目：根据主播开播及关播时间，计算平台最高峰同时在线的主播人数。

SELECT MAX(cnt)
FROM (
    SELECT
        id,
        dt,
        SUM(flag) OVER (ORDER BY dt) AS cnt
    FROM (
        SELECT id, stt AS dt, 1 AS flag FROM test5
        UNION ALL
        SELECT id, edt AS dt, -1 AS flag FROM test5
    ) t
) t;

留存问题（左连接写法）¶

SELECT
    t1.dt,
    COUNT(t1.uid) AS active_users,
    COUNT(CASE WHEN DATEDIFF(t2.dt, t1.dt) = 1 THEN t2.uid END) AS day2_active_users,
    COUNT(CASE WHEN DATEDIFF(t2.dt, t1.dt) = 6 THEN t2.uid END) AS day7_active_users
FROM (
    SELECT uid, dt
    FROM ods_app_open
    WHERE dt = '20211118'
    GROUP BY uid, dt
) t1
LEFT JOIN (
    SELECT uid, dt
    FROM ods_app_open
    WHERE dt > '20211118' AND dt <= '20211124'
    GROUP BY uid, dt
) t2
ON t1.uid = t2.uid
GROUP BY t1.dt;

3. 窗口函数与排名¶

计算部门收入占比¶

题目：有一张每年每个部门的收入表，和一张部门分类表。计算 2023 年收入第二高的事业线，给出其下每个部门的收入占事业线的占比，以及事业线在整个公司的占比。

注意： - 未分类的部门归为「其它」。 - 多条事业线收入相同时，按 1、2、2、3 的形式排序（DENSE_RANK）。

WITH department_data AS (
    SELECT
        d.department,
        COALESCE(c.business_line, '其它') AS business_line,
        d.revenue
    FROM department_revenue d
    LEFT JOIN department_category c ON d.department = c.department
    WHERE d.year = 2023
),
business_line_summary AS (
    SELECT
        business_line,
        SUM(revenue) AS business_line_total,
        DENSE_RANK() OVER (ORDER BY SUM(revenue) DESC) AS business_rank
    FROM department_data
    GROUP BY business_line
),
company_total AS (
    SELECT SUM(business_line_total) AS company_total
    FROM business_line_summary
),
second_ranked_business AS (
    SELECT business_line, business_line_total
    FROM business_line_summary
    WHERE business_rank = 2
)
SELECT
    d.department,
    d.revenue AS department_revenue,
    s.business_line_total,
    ROUND(d.revenue * 100.0 / s.business_line_total, 2) AS department_percent_in_business,
    ROUND(s.business_line_total * 100.0 / c.company_total, 2) AS business_percent_in_company
FROM department_data d
JOIN second_ranked_business s ON d.business_line = s.business_line
CROSS JOIN company_total c;

每个用户浏览次数最多的前 3 个商品¶

题目：用户行为表 user_behavior(user_id, item_id, behavior_type, timestamp)，找出每个用户浏览次数最多的前 3 个商品（behavior_type='pv'）。

SELECT
    user_id,
    item_id
FROM (
    SELECT
        user_id,
        item_id,
        RANK() OVER (PARTITION BY user_id ORDER BY num DESC) AS rk
    FROM (
        SELECT
            user_id,
            item_id,
            COUNT(item_id) AS num
        FROM behavior
        WHERE behavior_type = 'pv'
        GROUP BY user_id, item_id
    ) t1
) t2
WHERE rk <= 3;

去掉最高和最低工资后的平均工资¶

思路：使用窗口函数（如 MAX() OVER / MIN() OVER 或 RANK）标记最高和最低工资，排除后再求平均；或通过 UNION 去重后计算。

查找首次消费首月大于 1000 的集团¶

思路：先找到每个集团首次消费的日期，再关联原表筛选首月记录并求和。

4. 集合与关联查询¶

求跟一号学生上课课程完全一样的其他学生¶

思路： 1. 查出 01 号学生选修的所有课程； 2. 与成绩表自连接，找出选修了相同课程的其他学生； 3. 排除 01 号本人； 4. 按学号分组，确保课程数量与 01 号相同。

SELECT a.sid, a.cid
FROM grade a
JOIN (
    SELECT cid
    FROM grade
    WHERE sid = '01'
) b ON a.cid = b.cid
WHERE a.sid <> '01'
GROUP BY a.sid, a.cid
HAVING COUNT(*) = (
    SELECT COUNT(*)
    FROM grade
    WHERE sid = '01'
);

三、手写实现题¶

递归访问文件夹¶

需求 1：递归遍历并打印所有 .java 文件。

package Demo02;

import java.io.File;
import java.io.IOException;

public class test {
    public static void main(String[] args) throws IOException {
        print(new File("D:\\桌面\\java实验文件夹"));
    }

    public static void print(File dir) {
        File[] arr = dir.listFiles();
        for (File f : arr) {
            if (f.isDirectory()) {
                print(f);
            } else if (f.getAbsolutePath().toLowerCase().endsWith(".java")) {
                System.out.println(f);
            }
        }
    }
}

需求 2：递归打印所有子目录和文件。

package Demo02;

import java.io.File;
import java.io.IOException;

public class test {
    public static void main(String[] args) throws IOException {
        print(new File("D:\\桌面\\java实验文件夹"));
    }

    public static void print(File dir) {
        File[] arr = dir.listFiles();
        for (File f : arr) {
            if (f.isDirectory()) {
                System.out.println(f);
                print(f);
            } else {
                System.out.println(f);
            }
        }
    }
}

四、面经索引¶

公司	时间	岗位/轮次	结果	考点
字节数开（国际化商业产品与技术）	2024-09-19	一面	凉（SQL 没写出来）	计算部门收入占比（SQL）
影石	2024-09-23	笔试	—	次日留存率（SQL）、二分查找、学生选课关联（SQL）；原题「两个维表一个明细表算目标表」未做出，换题。
网易云音乐	—	—	—	窗口函数：每个用户浏览次数 Top 3 商品（SQL）
网易有道	—	一面	—	SQL：连续 3 天登录、首次消费首月大于 1000 的集团、去极值平均工资；算法：第二大数、两数之和、数组小和、环形链表、LRU、迭代后序遍历、字符串压缩、全排列、买卖股票、最长无重复子串、字符串相加