Skip to content

笔/面试准备

手撕代码两方面：核心代码模式，ACM（全部代码模式）

面试时间：2025/6/6 开始准备时间：5/29

看过的题目总结

5/29

  1. 求1~n这n个数的最小公倍数。

  2. 思路：lcm[i] = LCM(lcm[i-1], i)，算是动态规划。

  3. 核心实现：

    int lcm = 1;
for(int i = 2; i <= n; i++){
    lcm = i*lcm/gcd(lcm, i);
}

  4. 给定一个点O和n个点的坐标，求n个点中距离O最近的m的个点。

  5. 思路：依次求出各个点与O的距离，加入大小为m的最大堆。前m个点一定在堆中，之后每个比当前堆顶元素（堆中最大元素）小的距离，用它替换堆顶元素并perculate down。

  6. 分隔回文串： 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。

    1. 返回 s 所有可能的分割方案。
      • 思路：回溯
    2. 返回符合要求的 最少分割次数 。
      • 思路：DP方程： [ f(n)=\begin{cases} f(n-1) + 1 &\text{如果s[n]不与前面字符回文}\ min(f(n-1), f(i-1))+1 &\text{如果s[i]~s[n]形成回文} \end{cases} ] 其中s[i]表示s中第i个字符，f(n)表示从第一个字符开始长度为n的字符串中，分割出的最少回文串数。f(0)=0,f(1)=1

Comments