❌

阅读视图

发现新文章，点击刷新页面。

贪心（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
endlesscheng

为方便计算差值，先把 $\textit{nums}$ 从小到大排序。

把 $\textit{nums}$ 中的元素画在一维数轴上。如果 $\textit{nums}[i]$ 是 $k$ 个数中的最大值，那么最小值的下标至多为 $i-k+1$（要在最小值和最大值之间再选 $k-2$ 个数）。但最小值越小，差值越大，所以最小值的下标恰好为 $i-k+1$ 是最优的。

枚举最大值的下标 $i = k-1,k,k+1,\ldots, n-1$，计算差值 $\textit{nums}[i] - \textit{nums}[i-k+1]$ 的最大值，即为答案。

class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
return min(nums[i] - nums[i - k + 1] for i in range(k - 1, n))

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(mx - mn for mx, mn in zip(nums[k - 1:], nums))

class Solution {
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
int ans = Integer.MAX_VALUE;
for (int i = k - 1; i < nums.length; i++) {
ans = Math.min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}
}

class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
ranges::sort(nums);
int ans = INT_MAX;
for (int i = k - 1; i < nums.size(); i++) {
ans = min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}
};

#define MIN(a, b) ((b) < (a) ? (b) : (a))

int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}

int minimumDifference(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), cmp);
int ans = INT_MAX;
for (int i = k - 1; i < numsSize; i++) {
ans = MIN(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}

func minimumDifference(nums []int, k int) int {
slices.Sort(nums)
ans := math.MaxInt
for i := k - 1; i < len(nums); i++ {
ans = min(ans, nums[i]-nums[i-k+1])
}
return ans
}

var minimumDifference = function(nums, k) {
nums.sort((a, b) => a - b);
let ans = Infinity;
for (let i = k - 1; i < nums.length; i++) {
ans = Math.min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
};

impl Solution {
pub fn minimum_difference(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort_unstable();
let k = k as usize;
let mut ans = i32::MAX;
for i in k - 1..nums.len() {
ans = ans.min(nums[i] - nums[i - k + 1]);
}
ans
}
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。瓶颈在排序上。
  • 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

Next.js第二十三章(Next配置文件)

✇掘金 前端
小满zs

next.config.js配置

本章会讲解Next.js的配置文件next.config.js的配置项。注：本章不会讲所有的配置项，只会讲使用率50%的配置项，以及项目中真实使用的配置项。

查看完整版配置项观看: next.config.js配置

根据不同环境进行配置

例如我想在开发环境配置 XXX，或者生产环境配置YYY，那么我们可以使用next/constants来判断当前环境。

//Next.js next/constants内置的常量
export declare const PHASE_EXPORT = "phase-export"; // 导出静态站点
export declare const PHASE_PRODUCTION_BUILD = "phase-production-build"; // 生产环境构建
export declare const PHASE_PRODUCTION_SERVER = "phase-production-server"; // 生产环境服务器
export declare const PHASE_DEVELOPMENT_SERVER = "phase-development-server"; // 开发环境服务器
export declare const PHASE_TEST = "phase-test"; // 测试环境
export declare const PHASE_INFO = "phase-info"; // 信息

我们要根据不同环境配置，需要返回一个函数，而不是直接返回一个对象，在函数中会接受一个参数phase，这个参数是Next.js的环境，我们可以根据这个参数来判断当前环境。

//next.config.ts
import { PHASE_DEVELOPMENT_SERVER, PHASE_TYPE } from 'next/constants'
import type { NextConfig } from 'next'

export default (phase: PHASE_TYPE): NextConfig => {
  const nextConfig: NextConfig = {
     reactCompiler: false,
  }

  if (phase === PHASE_DEVELOPMENT_SERVER) {
    nextConfig.reactCompiler = true // 开发环境使用reactCompiler
  }

  //if() 其他环境.....

  return nextConfig
}

Next.js配置端口号

这是Next.js很迷的一个操作，通过一般脚手架或者其他项目都会在配置文件进行配置端口号，但是Next.js却没有，而是在启动命令中进行配置。(默认是3000端口)

  "scripts": {
    "dev": "next dev -p 8888", // 开发环境端口号
    "build": "next build",
    "start": "next start -p 9999 " // 生产环境端口号
  },

Next.js导出静态站点

需要在next.config.js文件中配置output为export，表示导出静态站点。distDir表示导出目录，默认为out。

具体用法请查看: 静态导出SSG

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
  /* config options here */
  output: "export", // 导出静态站点
  distDir: "dist", // 导出目录
  trailingSlash: true, // 添加尾部斜杠，生成 /about/index.html 而不是 /about.html
};

export default nextConfig;

Next.js配置图片优化

Next.jsImage组件默认只允许加载本地图片，如果需要加载远程图片，需要配置next.config.js文件。

详细用法请查看: 图片优化

import type { NextConfig } from "next";

const nextConfig: NextConfig = {
  /* config options here */
  images: {
    remotePatterns: [
      {
        protocol: 'https', // 协议
        hostname: 'eo-img.521799.xyz', // 主机名
        pathname: '/i/pc/**', // 路径
        port: '', // 端口
      },
    ],
    formats: ['image/avif', 'image/webp'], //默认是 ['image/webp']
    deviceSizes: [640, 750, 828, 1080, 1200, 1920, 2048, 3840], // 设备尺寸
    imageSizes: [16, 32, 48, 64, 96, 128, 256, 384], // 图片尺寸
  },
};

自定义响应标头

例如配置CORS跨域，或者是自定义响应标头等，只要是http支持的响应头都可以配置。

HTTP响应头参考: HTTP响应头

  const nextConfig: NextConfig = {
     headers: () => {
      return [
         {
          source: '/:path*', // 匹配路径 所有路径 也支持精准匹配 例如/api/user 包括支持动态路由等 /api/user/:id 
          headers: [
            {
              key: 'Access-Control-Allow-Origin', //允许跨域
              value: '*' // 允许所有域名访问
            },
            {
              key: 'Access-Control-Allow-Methods', //允许的请求方法
              value: 'GET, POST, PUT, DELETE, OPTIONS' // 允许的请求方法
            },
            {
              key: 'Access-Control-Allow-Headers', //允许的请求头
              value: 'Content-Type, Authorization' // 允许的请求头
            }
          ]
         },
         {
          source: '/home', // 精准匹配 /home 路径
          headers: [
            {
              key: 'X-Custom-Header', //自定义响应头
              value: '123456' // 值
            },
          ]
         }
      ]
    }
  }

assetsPrefix配置

assetsPrefix配置用于配置静态资源前缀，例如：部署到CDN后，静态资源路径会发生变化，需要配置这个配置项。

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
  /* config options here */
  assetsPrefix: 'https://cdn.example.com', // 静态资源前缀
};

export default nextConfig;

未配置assetsPrefix时：

/_next/static/chunks/4b9b41aaa062cbbfeff4add70f256968c51ece5d.4d708494b3aed70c04f0.js

配置assetsPrefix后：

https://cdn.example.com/_next/static/chunks/4b9b41aaa062cbbfeff4add70f256968c51ece5d.4d708494b3aed70c04f0.js

basePath配置

应用前缀：也就是跳转路径中增加前缀，例如前缀是/docs，那么跳转/home就需要跳转到/docs/home。访问根目录也需要增加前缀，例如访问/就需要跳转到/docs。这儿可以使用重定向来实现。访问/自动跳转到/docs。

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
  /* config options here */
  basePath: '/docs', // 基础路径
  redirects() {
    return [
      {
        source: '/', // 源路径
        destination: '/docs', // 目标路径
        basePath: false, // 是否使用basePath 默认情况下 source 和 destination 都会自动加上 basePath 前缀 就变成了/docs/docs 所以这儿不需要增加
        permanent: false, // 是否永久重定向
      },
    ]
  },
};

export default nextConfig;

如果使用link跳转的话，无需增加basePath前缀，因为Link组件会自动增加basePath前缀。 当他跳转/home时，会自动跳转到/docs/home。

import Link from 'next/link'
export default function Page() {
  return (<div>
    <h1>小满zs Page</h1>
    <Link href="/home">Home</Link>
  </div>)
}

compress

compress配置用于配置压缩，例如：压缩js/css/html等。默认情况是开启的，如果需要关闭，可以配置为false。

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
  compress: true, // 压缩
};

export default nextConfig;

日志配置

日志配置用于配置日志，例如：显示完整的URL等。

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
  logging:{
    fetches: {
      fullUrl: true, // 显示完整的URL
    },
  }
};

export default nextConfig;

页面扩展

默认情况下，Next.js 接受以下扩展名的文件：.tsx.js、 .js .ts、.jsx.md、.js.js。可以修改此设置以允许其他扩展名，例如 markdown（.md.md、.md .mdx）。

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
  pageExtensions: ['js', 'jsx', 'md', 'mdx', 'ts', 'tsx'],
};

export default nextConfig;

devIndicators

关闭调试指示器，默认情况下是开启的，如果需要关闭，可以配置为false。

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
  devIndicators: false, // 关闭开发指示器
  // devIndicators:{
  //   position:'bottom-right', //也支持放入其他位置 bottom-right bottom-left top-right top-left
  // },
};

export default nextConfig;
image.png

generateEtags

Next.js会为静态文件生成ETag，用于缓存控制。默认情况下是开启的，如果需要关闭，可以配置为false。

浏览器会根据ETag来判断文件是否发生变化，如果发生变化，则重新下载文件。

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
  generateEtags: false, // 关闭生成ETag 默认开启
};

export default nextConfig;

turbopack

Next.js已内置turbopack进行打包编译等操作，所以允许透传配置项给turbopack。

一般情况下是不需要做太多优化的，因为它都内置了例如tree-shaking、压缩 按需编译 语法降级 等优化。

具体用法请查看: turbopack

例如我们需要编译其他文件less配置如下:

npm i less-loader -D

import type { NextConfig } from "next";
const nextConfig: NextConfig = {
    turbopack:{
     rules:{
          '*.less':{
          loaders:['less-loader'],
          as:'*.css',
        }
     }
  }
}
export default nextConfig;

每日一题-学生分数的最小差值🟢

✇LeetCode 每日一题题解

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。

返回可能的 最小差值 。

 

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

 

提示：

  • 1 <= k <= nums.length <= 1000
  • 0 <= nums[i] <= 105

【宫水三叶】排序 + 滑动窗口运用题

✇LeetCode 每日一题题解
AC_OIer

排序 + 滑动窗口

从 $n$ 个元素里找 $k$ 个，使得 $k$ 个元素最大差值最小。

最大值最小化问题容易想到「二分」，利用答案本身具有「二段性」，来将原本的求解问题转化为判断定问题。

回到本题，容易证明，这 $k$ 个元素必然是有序数组中（排序后）的连续段。反证法，若最佳 $k$ 个选择不是连续段，能够调整为连续段，结果不会变差。

因此我们可以先对 $nums$ 进行排序，然后扫描所有大小为 $k$ 的窗口，直接找到答案，而无须使用「二分」。

代码（二分答案代码见 $P2$）：

###Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, ans = nums[k - 1] - nums[0];
        for (int i = k; i < n; i++) {
            ans = Math.min(ans, nums[i] - nums[i - k + 1]);
        }
        return ans;
    }
}

###Java

class Solution {
    int[] nums; int k;
    public int minimumDifference(int[] _nums, int _k) {
        nums = _nums; k = _k;
        Arrays.sort(nums);
        int l = 0, r = 100010;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
    boolean check(int x) {
        int n = nums.length, ans = nums[k - 1] - nums[0];
        for (int i = k; i < n && ans > x; i++) {
            ans = Math.min(ans, nums[i] - nums[i - k + 1]);
        }
        return ans <= x;
    }
}
  • 时间复杂度：排序复杂度为 $O(n\log{n})$；遍历得到答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
  • 空间复杂度：$O(\log{n})$

其他「滑动窗口」内容

题太简单？来看一道 更贴合笔试/面试的滑动窗口综合题 🎉 🎉

或是加练其他「滑动窗口」内容 🍭🍭🍭

题目 题解 难度 推荐指数
3. 无重复字符的最长子串 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
30. 串联所有单词的子串 LeetCode 题解链接 困难 🤩🤩
187. 重复的DNA序列 LeetCode 题解链接 中等 🤩🤩🤩🤩
219. 存在重复元素 II LeetCode 题解链接 简单 🤩🤩🤩🤩
424. 替换后的最长重复字符 LeetCode 题解链接 中等 🤩🤩🤩🤩
438. 找到字符串中所有字母异位词 LeetCode 题解链接 中等 🤩🤩🤩🤩
480. 滑动窗口中位数 LeetCode 题解链接 困难 🤩🤩🤩🤩
567. 字符串的排列 LeetCode 题解链接 中等 🤩🤩🤩
594. 最长和谐子序列 LeetCode 题解链接 简单 🤩🤩🤩🤩
643. 子数组最大平均数 I LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
992. K 个不同整数的子数组 LeetCode 题解链接 困难 🤩🤩🤩🤩
1004. 最大连续1的个数 III LeetCode 题解链接 中等 🤩🤩🤩
1052. 爱生气的书店老板 LeetCode 题解链接 中等 🤩🤩🤩
1208. 尽可能使字符串相等 LeetCode 题解链接 中等 🤩🤩🤩
1423. 可获得的最大点数 LeetCode 题解链接 中等 🤩🤩🤩🤩
1438. 绝对差不超过限制的最长连续子数组 LeetCode 题解链接 中等 🤩🤩🤩
1610. 可见点的最大数目 LeetCode 题解链接 困难 🤩🤩🤩🤩
1838. 最高频元素的频数 LeetCode 题解链接 中等 🤩🤩🤩
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

[Python/Java/JavaScript/Go] 排序+双指针滑窗

✇LeetCode 每日一题题解
himymBen

解题思路

排序后我们要选k个数达到最大最小的差尽可能小，必然是连续的长度为k的子数组的选法，而差值就是最右边的元素减去最左边的元素。
遍历返回其中的最小值即可。

代码

###Python3

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        return min(s[i + k - 1] - s[i] for i in range(len(s) - k + 1)) if k > 1 and (s:=sorted(nums)) else 0

###Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        if(k == 1)
            return 0;
        Arrays.sort(nums);
        int ans = 100005;
        for(int i = 0; i <= nums.length - k; i++)
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        return ans;
    }
}

###JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumDifference = function(nums, k) {
    if(k == 1)
        return 0
    nums.sort((a,b)=>a-b)
    let ans = 100005
    for(let i = 0; i <= nums.length - k; i++)
        ans = Math.min(ans, nums[i + k - 1] - nums[i])
    return ans
};

###Go

func minimumDifference(nums []int, k int) int {
    if k == 1 {
        return 0
    }
    sort.Ints(nums)
    ans := 100005
    for i := 0; i <= len(nums) - k; i++ {
        ans = min(ans, nums[i + k - 1] - nums[i])
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

学生分数的最小差值

✇LeetCode 每日一题题解
LeetCode-Solution

方法一：排序

思路与算法

要想最小化选择的 $k$ 名学生中最高分和最低分的差值，我们一定是在排好序后的数组中连续地进行选择。这是因为在选择时，如果跳过了某个下标 $i$，那么在选择完毕后，将其中的最高分替换成 $\textit{nums}[i]$，最高分一定不会变大，与最低分的差值同样也不会变大。因此，一定存在有一种最优的选择方案，是连续选择了有序数组中的 $k$ 个连续的元素。

这样一来，我们首先对数组 $\textit{nums}$ 进行升序排序，随后使用一个大小固定为 $k$ 的滑动窗口在 $\textit{nums}$ 上进行遍历。记滑动窗口的左边界为 $i$，那么右边界即为 $i+k-1$，窗口中的 $k$ 名学生最高分和最低分的差值即为 $\textit{nums}[i+k-1] - \textit{nums}[i]$。

最终的答案即为所有 $\textit{nums}[i+k-1] - \textit{nums}[i]$ 中的最小值。

代码

###C++

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = INT_MAX;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};

###Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}

###C#

public class Solution {
    public int MinimumDifference(int[] nums, int k) {
        int n = nums.Length;
        Array.Sort(nums);
        int ans = int.MaxValue;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.Min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}

###Python

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

###C

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int cmp(const void * pa, const void *pb) {
    return *(int *)pa - *(int *)pb;
}

int minimumDifference(int* nums, int numsSize, int k){
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans = INT_MAX;
    for (int i = 0; i + k - 1 < numsSize; ++i) {
        ans = MIN(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
}

###JavaScript

var minimumDifference = function(nums, k) {
    const n = nums.length;
    nums.sort((a, b) => a - b);
    let ans = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < n - k + 1; i++) {
        ans = Math.min(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
};

###go

func minimumDifference(nums []int, k int) int {
    sort.Ints(nums)
    ans := math.MaxInt32
    for i, num := range nums[:len(nums)-k+1] {
        ans = min(ans, nums[i+k-1]-num)
    }
    return ans
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。排序需要的时间为 $O(n \log n)$，后续遍历需要的时间为 $O(n)$。

  • 空间复杂度：$O(\log n)$，即为排序需要使用的栈空间。

Elpis 项目 Webpack 配置详解

✇掘金 前端
小居673
Elpis 项目 Webpack 配置详解 本指南详细介绍了 Elpis 项目的 Webpack 5 构建系统设置，涵盖了从基础配置到生产环境优化的核心逻辑。 🏗️ 1. 核心架构 项目采用 分层配置
❌