Bash scripts tend to start small and grow over time. A helper you wrote in five minutes to copy a few files can end up running in a cron job, a deployment pipeline, or a server startup script. When that happens, small oversights such as an unquoted variable or an ignored error become real outages.

This guide covers practical Bash best practices that keep scripts predictable, safe to re-run, and easy for other people to read.

Start With a Clear Shebang #

Every Bash script should begin with a proper shebang line. The portable choice for Bash is:

#!/usr/bin/env bash

Using /usr/bin/env bash lets the script find Bash through the PATH, which matters on systems where Bash is installed outside /bin, such as macOS with Homebrew. If you rely on features that exist only in Bash, do not use #!/bin/sh. On many distributions /bin/sh points to dash or another minimal shell, and arrays, [[ ]], and local will not behave the same way.

Enable Strict Mode #

By default, Bash ignores many errors. A command can fail, a variable can be unset, and the script will keep running as if nothing happened. Enabling strict mode at the top of the script changes that behavior.

#!/usr/bin/env bash
set -euo pipefail

Here is what each flag does:

• -e - Exit immediately if any command returns a non-zero status.
• -u - Treat unset variables as an error and exit.
• -o pipefail - Make a pipeline fail if any command in it fails, not only the last one.

A common extra is IFS=$'\n\t', which prevents word splitting on spaces and avoids surprises when iterating over filenames that contain spaces.

#!/usr/bin/env bash
set -euo pipefail
IFS=$'\n\t'

Strict mode is not magic. It will not catch logic errors, and in some scripts you will need to opt out locally with || true for commands that are allowed to fail. The point is to flip the default from “keep going on errors” to “stop on errors”, which is almost always the safer choice.

Always Quote Your Variables #

Unquoted variables in Bash are expanded and then word-split. If a variable contains spaces, wildcards, or is empty, the result may be very different from what you expect.

file="My Report.txt"
printf '<%s>\n' $file

Because $file is not quoted, Bash passes two arguments to printf: My and Report.txt. Quoting fixes it and keeps the filename as one value:

printf '<%s>\n' "$file"

The same rule applies inside tests, loops, and command substitutions. When in doubt, quote. The only common case where you intentionally leave a variable unquoted is when you want word splitting, which should be rare and deliberate.

Prefer [[ ]] Over [ ] #

Bash supports two test constructs: the older [ ] (a synonym for the test command) and the newer [[ ]] keyword. For Bash scripts, prefer [[ ]]:

if [[ -f "$config" && "$env" == "production" ]]; then
 echo "Loading production config"
fi

[[ ]] handles empty variables safely even without quotes, supports pattern matching with == and regex with =~, and allows logical operators such as && and || inside the test. Only fall back to [ ] when writing a portable POSIX script that must run under sh or dash.

Use Functions for Repeated Logic #

Once a script has more than a couple of steps, group related commands into functions. Functions make scripts easier to read, test, and refactor.

log() {
 printf '[%s] %s\n' "$(date +'%F %T')" "$*"
}

backup_dir() {
 local src="$1"
 local dst="$2"

 log "Backing up $src to $dst"
 rsync -a "$src/" "$dst/"
}

backup_dir "/var/www" "/backup/www"

Declare variables inside functions with local so they do not leak into the rest of the script. Pass input as positional parameters, and return output via echo or printf rather than global variables when possible.

See Bash functions for more details on arguments, return values, and scoping.

Handle Errors Explicitly #

Strict mode stops the script on errors, but it does not tell the user what went wrong. Adding a trap on ERR gives you a single place to log failures.

#!/usr/bin/env bash
set -Eeuo pipefail

on_error() {
 local exit_code=$?
 local line=$1
 echo "Error on line $line (exit code $exit_code)" >&2
 exit "$exit_code"
}

trap 'on_error $LINENO' ERR

The -E option makes the ERR trap inherit into functions and subshells. Without it, a failure inside a helper function may exit the script without running your error handler.

For cleanup tasks such as removing temporary files, use trap on EXIT:

tmp_dir=$(mktemp -d)
trap 'rm -rf "$tmp_dir"' EXIT

The EXIT trap runs whether the script exits normally, hits an error under set -e, or is interrupted with Ctrl+C. It is the safest way to guarantee cleanup.

Validate Input Early #

Scripts that take arguments should fail fast when those arguments are missing or invalid. Check them before doing any work:

if [[ $# -lt 2 ]]; then
 echo "Usage: $0 <environment> <version>" >&2
 exit 1
fi

env="$1"
version="$2"

case "$env" in
 staging|production) ;;
 *)
 echo "Unknown environment: $env" >&2
 exit 1
 ;;
esac

For scripts with several flags, use getopts instead of parsing $@ manually. It handles short options, arguments, and error reporting in a consistent way.

Avoid Parsing the Output of ls #

A common beginner mistake is looping over ls output:

for f in $(ls /var/log); do
 echo "$f"
done

This breaks on filenames with spaces, newlines, or special characters. Use a glob or find instead:

for f in /var/log/*; do
 echo "$f"
done

For recursive traversal, use find with -print0 and xargs -0, or a while read loop with IFS= and -d '' to handle unusual filenames correctly.

Keep Scripts Idempotent When Possible #

A script you can safely re-run is much easier to work with than one that breaks on the second attempt. Aim for idempotent behavior: check before creating directories, use mkdir -p instead of mkdir, use ln -sf instead of ln -s, and guard commands with if blocks when they would otherwise fail on re-run.

mkdir -p /opt/app/config

The same pattern applies to package installation, user creation, and configuration edits. Tools like Ansible enforce idempotency by design; in Bash, you have to add those checks yourself.

Use Shellcheck #

Shellcheck is a static analyzer for shell scripts. It catches unquoted variables, unsafe for loops, and many other common mistakes before you hit them in production.

Install it from your package manager:

sudo apt install shellcheck

Then run it against your script:

shellcheck script.sh

Fix the warnings it raises, or document with an inline comment why a specific check is being ignored. Making shellcheck part of your editor or pre-commit hook removes an entire class of Bash bugs.

Prefer Readable Over Clever #

Bash is full of shortcuts and obscure expansions. They can make scripts shorter, but they also make them harder to read six months later. Choose the clearer form, even when it is a few characters longer.

if [[ -z "$name" ]]; then
 name="anonymous"
fi

is almost always easier to maintain than the golfed equivalent:

: "${name:=anonymous}"

Aim for scripts that a teammate can read once and understand, not ones that require a reference manual.

Quick Reference #

For a printable quick reference, see the Bash cheatsheet .

Before committing a Bash script, confirm the following:

• #!/usr/bin/env bash shebang is present.
• set -euo pipefail is enabled.
• All variable expansions are quoted.
• Tests use [[ ]] instead of [ ].
• Functions replace long repeated blocks, with local variables.
• trap handles errors and cleanup.
• Input is validated before work begins.
• No parsing of ls output.
• shellcheck reports no warnings, or they are explicitly ignored.

FAQ #

Is set -e enough on its own?
No. set -e stops on many errors, but it misses failures in pipelines and ignores unset variables. Combine it with -u and -o pipefail to cover those cases.

Does strict mode break existing scripts?
It often surfaces bugs that were already there, such as unset variables and ignored errors. The fix is to quote variables, use default values like ${VAR:-}, and handle expected failures with || true.

Should I write scripts in Bash or switch to Python?
Bash is a good fit for short glue scripts that mostly call other commands. Once a script grows past a few hundred lines, has complex data structures, or needs proper error handling and testing, Python or another language is usually a better choice.

Where can I learn more safe scripting patterns?
Keep the Shellcheck wiki open while you write, and read through the official Bash manual section on shell builtins. Both cover the reasoning behind each rule, not only the rule itself.

Conclusion #

Strict mode, quoting, and a few well-placed traps cover most of the risk in Bash scripting. Make these practices your defaults, run shellcheck on every change, and your scripts will behave the same way on your laptop, in CI, and on a production server.

给你一个整数数组 nums ，如果它是数组 base[n] 的一个排列，我们称它是个 好 数组。

base[n] = [1, 2, ..., n - 1, n, n] （换句话说，它是一个长度为 n + 1 且包含 1 到 n - 1 恰好各一次，包含 n  两次的一个数组）。比方说，base[1] = [1, 1] ，base[3] = [1, 2, 3, 3] 。

如果数组是一个好数组，请你返回 true ，否则返回 false 。

注意：数组的排列是这些数字按任意顺序排布后重新得到的数组。

示例 1：

输入：nums = [2, 1, 3]
输出：false
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 。但是 base[3] 有 4 个元素，但数组 nums 只有 3 个元素，所以无法得到 base[3] = [1, 2, 3, 3] 的排列，所以答案为 false 。

示例 2：

输入：nums = [1, 3, 3, 2]
输出：true
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 ，可以看出数组是 base[3] = [1, 2, 3, 3] 的一个排列（交换 nums 中第二个和第四个元素）。所以答案为 true 。

示例 3：

输入：nums = [1, 1]
输出：true
解释：因为数组的最大元素是 1 ，唯一可以构成这个数组的 base[n] 对应的 n = 1，可以看出数组是 base[1] = [1, 1] 的一个排列。所以答案为 true 。

示例 4：

输入：nums = [3, 4, 4, 1, 2, 1]
输出：false
解释：因为数组的最大元素是 4 ，唯一可以构成这个数组的 base[n] 对应的 n = 4 。但是 base[n] 有 5 个元素而 nums 有 6 个元素。所以答案为 false 。

提示：

• 1 <= nums.length <= 100
• 1 <= num[i] <= 200

解法一

思路和算法

记 $n$ 为数组 $\textit{nums}$ 的长度减 $1$。数组 $\textit{nums}$ 是好数组，等价于将数组 $\textit{nums}$ 按升序排序之后，应满足对于所有 $0 \le i < n$ 都有 $\textit{nums}[i] = i + 1$ 且 $\textit{nums}[n - 1] = \textit{nums}[n] = n$，因此可以将数组 $\textit{nums}$ 按升序排序并判断数组 $\textit{nums}$ 是否为好数组。

排序之后，需要检查 $\textit{nums}[n] = n$、$\textit{nums}[n - 1] = n$ 和对于所有 $0 \le i < n$ 都有 $\textit{nums}[i] = i + 1$ 是否成立，如果上述条件成立，则数组 $\textit{nums}$ 是好数组，返回 $\text{true}$，否则返回 $\text{false}$。

代码

###Java

class Solution {
    public boolean isGood(int[] nums) {
        int n = nums.length - 1;
        Arrays.sort(nums);
        if (nums[n] != n || nums[n - 1] != n) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return false;
            }
        }
        return true;
    }
}

###C#

public class Solution {
    public bool IsGood(int[] nums) {
        int n = nums.Length - 1;
        Array.Sort(nums);
        if (nums[n] != n || nums[n - 1] != n) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：$O(m \log m)$，其中 $m$ 是数组 $\textit{nums}$ 的长度。排序的时间是 $O(m \log m)$，排序后遍历数组的时间是 $O(m)$，因此时间复杂度是 $O(m \log m)$。

• 空间复杂度：$O(\log m)$，其中 $m$ 是数组 $\textit{nums}$ 的长度。排序的递归调用栈空间是 $O(\log m)$。

解法二

思路和算法

记 $n$ 为数组 $\textit{nums}$ 的长度减 $1$。数组 $\textit{nums}$ 是好数组，等价于数组 $\textit{nums}$ 中的元素都不超过 $n$ 且 $1$ 到 $n - 1$ 的每个整数都恰好出现一次。因此可以使用哈希集合存储数组 $\textit{nums}$ 中出现的 $1$ 到 $n - 1$ 的每个整数，遍历数组 $\textit{nums}$ 的过程中维护哈希集合并判断数组 $\textit{nums}$ 是否为好数组。

对于遍历到的每个元素 $\textit{nums}$，执行如下操作。

1. 如果 $\textit{num} > n$，则数组 $\textit{nums}$ 不是好数组，返回 $\text{false}$。

2. 如果 $\textit{num} < n$。执行如下操作。

   • 如果 $\textit{num}$ 已经在哈希集合中，则 $\textit{num}$ 在数组 $\textit{nums}$ 中重复出现，因此数组 $\textit{nums}$ 不是好数组，返回 $\text{false}$。

   • 如果 $\textit{num}$ 尚未在哈希集合中，则将 $\textit{num}$ 加入哈希集合。

遍历结束之后，如果哈希集合中的元素个数等于 $n - 1$，则数组 $\textit{nums}$ 是好数组，返回 $\text{true}$，否则返回 $\text{false}$。

上述做法中没有判断 $n$ 的出现次数，理由如下。

1. 如果数组 $\textit{nums}$ 中存在大于 $n$ 的元素，则数组 $\textit{nums}$ 不是好数组。

2. 如果数组 $\textit{nums}$ 中不存在大于 $n$ 的元素，则由于数组 $\textit{nums}$ 的长度是 $n + 1$，因此只需要确保 $1$ 到 $n - 1$ 的每个整数都出现一次，不存在重复或遗漏，则可以确保 $n$ 出现两次。上述做法中，遍历数组执行哈希集合操作时检查是否存在重复元素，遍历结束之后检查是否存在遗漏元素，因此只有当 $1$ 到 $n - 1$ 的每个整数都出现一次时才会认为数组 $\textit{nums}$ 是好数组。

代码

###Java

class Solution {
    public boolean isGood(int[] nums) {
        int n = nums.length - 1;
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            if (num > n) {
                return false;
            }
            if (num < n && !set.add(num)) {
                return false;
            }
        }
        return set.size() == n - 1;
    }
}

###C#

public class Solution {
    public bool IsGood(int[] nums) {
        int n = nums.Length - 1;
        ISet<int> set = new HashSet<int>();
        foreach (int num in nums) {
            if (num > n) {
                return false;
            }
            if (num < n && !set.Add(num)) {
                return false;
            }
        }
        return set.Count == n - 1;
    }
}

复杂度分析

• 时间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{nums}$ 的长度。需要遍历数组一次，对于每个元素的操作时间都是 $O(1)$。

• 空间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{nums}$ 的长度。哈希集合的空间是 $O(m)$。

Problem: 2784. 检查数组是否是好的

[TOC]

思路

排序 + 一次遍历

解题方法

排序后计算数组长度，如果数组最后一个值大于等于当前数组长度，直接返回False。依次遍历数组起始至倒数第二个值下标与值是否相等，不相等返回False。

复杂度

• 时间复杂度:

添加时间复杂度, 示例： $O(n)$

• 空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

###Python3

class Solution:
    def sort_ergo(self, arr):
        size = len(arr)
        arr.sort()
        if arr[-1] >= size:
            return False
        for indx, val in enumerate(arr[:size-1], 1):
            if indx != val:
                return False
        return True

    def isGood(self, nums: List[int]) -> bool:
        # 方法：排序 + 遍历
        return self.sort_ergo(nums)

方法一：辅助数组

遍历 $\textit{nums}$，同时用一个 $\textit{cnt}$ 数组统计每个元素的出现次数：

设 $n$ 是 $\textit{nums}$ 的长度减一。设 $x = \textit{nums}[i]$。分类讨论：

• 如果 $x > n$，不满足要求，返回 $\texttt{false}$。注意题目保证 $x\ge 1$，无需判断 $x\le 0$ 的情况。
• 如果 $x = n$ 且 $x$ 出现次数大于 $2$，返回 $\texttt{false}$。
• 如果 $x < n$ 且 $x$ 出现次数大于 $1$，返回 $\texttt{false}$。

如果没有出现上述情况，返回 $\texttt{true}$。

class Solution:
    def isGood(self, nums: List[int]) -> bool:
        n = len(nums) - 1
        cnt = [0] * (n + 1)
        for x in nums:
            if (x > n or
                x == n and cnt[x] > 1 or  # cnt[x] 加一之前 > 1，加一之后 > 2
                x < n and cnt[x] > 0):    # cnt[x] 加一之前 > 0，加一之后 > 1
                return False
            cnt[x] += 1
        return True

class Solution {
    public boolean isGood(int[] nums) {
        int n = nums.length - 1;
        int[] cnt = new int[n + 1];
        for (int x : nums) {
            if (x > n ||
                x == n && cnt[x] > 1 || // cnt[x] 加一之前 > 1，加一之后 > 2
                x < n && cnt[x] > 0) {  // cnt[x] 加一之前 > 0，加一之后 > 1
                return false;
            }
            cnt[x]++;
        }
        return true;
    }
}

class Solution {
public:
    bool isGood(vector<int>& nums) {
        int n = nums.size() - 1;
        vector<int> cnt(n + 1);
        for (int x : nums) {
            if (x > n ||
                x == n && cnt[x] > 1 || // cnt[x] 加一之前 > 1，加一之后 > 2
                x < n && cnt[x] > 0) {  // cnt[x] 加一之前 > 0，加一之后 > 1
                return false;
            }
            cnt[x]++;
        }
        return true;
    }
};

func isGood(nums []int) bool {
n := len(nums) - 1
cnt := make([]int, n+1)
for _, x := range nums {
if x > n ||
x == n && cnt[x] > 1 || // cnt[x] 加一之前 > 1，加一之后 > 2
x < n && cnt[x] > 0 {   // cnt[x] 加一之前 > 0，加一之后 > 1
return false
}
cnt[x]++
}
return true
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法二：把 nums 当作辅助数组

由于 $\textit{nums}$ 中的数都是正整数，我们可以在首次遇到元素 $x$ 时，把 $\textit{nums}[x]$ 改成 $-\textit{nums}[x]$，这样再次遇到 $|x|$ 时，就能通过 $\textit{nums}[|x|] < 0$ 得知 $\textit{nums}$ 中至少有两个 $|x|$。

对于 $n$，我们需要判断 $n$ 是否出现超过两次，可以单独用一个变量 $\textit{cntN}$ 统计 $n$ 的出现次数。

class Solution:
    def isGood(self, nums: List[int]) -> bool:
        n = len(nums) - 1
        cnt_n = 0
        for x in nums:
            x = abs(x)
            if (x > n or
                x == n and cnt_n > 1 or
                x < n and nums[x] < 0):  # x 之前遇到过，现在又遇到了，所以 x 的出现次数至少是 2
                return False
            if x == n:
                cnt_n += 1
            else:
                nums[x] = -nums[x]  # 标记 x 遇到过
        return True

class Solution {
    public boolean isGood(int[] nums) {
        int n = nums.length - 1;
        int cntN = 0;
        for (int x : nums) {
            x = Math.abs(x);
            if (x > n ||
                x == n && cntN > 1 ||
                x < n && nums[x] < 0) { // x 之前遇到过，现在又遇到了，所以 x 的出现次数至少是 2
                return false;
            }
            if (x == n) {
                cntN++;
            } else {
                nums[x] = -nums[x]; // 标记 x 遇到过
            }
        }
        return true;
    }
}

class Solution {
public:
    bool isGood(vector<int>& nums) {
        int n = nums.size() - 1;
        int cnt_n = 0;
        for (int x : nums) {
            x = abs(x);
            if (x > n ||
                x == n && cnt_n > 1 ||
                x < n && nums[x] < 0) { // x 之前遇到过，现在又遇到了，所以 x 的出现次数至少是 2
                return false;
            }
            if (x == n) {
                cnt_n++;
            } else {
                nums[x] = -nums[x]; // 标记 x 遇到过
            }
        }
        return true;
    }
};

func isGood(nums []int) bool {
n := len(nums) - 1
cntN := 0
for _, x := range nums {
x = abs(x)
if x > n ||
x == n && cntN > 1 ||
x < n && nums[x] < 0 { // x 之前遇到过，现在又遇到了，所以 x 的出现次数至少是 2
return false
}
if x == n {
cntN++
} else {
nums[x] = -nums[x] // 标记 x 遇到过
}
}
return true
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

相似题目

• 442. 数组中重复的数据
• 448. 找到所有数组中消失的数字

分类题单

如何科学刷题？

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站@灵茶山艾府

When you need to host a PHP application or a CMS such as WordPress, Magento, or Laravel on a fresh Ubuntu server, the LEMP stack is one of the most common ways to get there. LEMP stands for Linux, Nginx (pronounced “engine-x”), MySQL, and PHP, and the four pieces fit together to serve dynamic PHP pages over HTTP.

This guide explains how to install and configure a complete LEMP stack on Ubuntu 26.04. By the end you will have Nginx serving HTTP traffic, MySQL 8.4 running as the database, and PHP 8.5 processing dynamic pages through PHP-FPM.

Quick Reference #

Prerequisites #

Before installing the stack, make sure you have:

• A server running Ubuntu 26.04 with a user with sudo privileges .
• The UFW firewall enabled. If you have not configured it yet, see ufw Command in Linux: Uncomplicated Firewall Reference .

Step 1: Install Nginx #

Nginx is in the default Ubuntu 26.04 repositories. Refresh the package index and install it:

sudo apt update
sudo apt install nginx

Once the install finishes, the service starts automatically. Confirm it is running:

sudo systemctl status nginx

The output shows the service as active (running). If UFW is enabled, allow HTTP and HTTPS traffic:

sudo ufw allow 'Nginx Full'

Open http://your_server_ip in a browser. You should see the default Nginx welcome page, which confirms that Nginx is serving requests.

For a deeper walkthrough of the install and the directory layout, see How to Install Nginx on Ubuntu 26.04 .

Step 2: Install MySQL #

The database tier handles persistence. Install the MySQL server package:

sudo apt install mysql-server

Once the install completes, run the security script. It walks you through removing anonymous users, disabling remote root login, and dropping the test database:

sudo mysql_secure_installation

When prompted, answer Y to each hardening question. The validate password component is optional and you can disable it if you plan to manage credentials yourself.

To verify that the service is running:

sudo systemctl status mysql

For details on creating users and granting privileges, see How to Install MySQL on Ubuntu 26.04 .

Step 3: Install PHP and PHP-FPM #

Nginx does not embed a PHP interpreter. Instead, requests for PHP files are handed off to PHP-FPM (FastCGI Process Manager) over a Unix socket. Install PHP-FPM and the MySQL driver:

sudo apt update
sudo apt install php-fpm php-mysql

On Ubuntu 26.04 this pulls in PHP 8.5. Confirm the version:

php -v

The output starts with PHP 8.5.x. The PHP-FPM service starts automatically and listens on a Unix socket at /run/php/php8.5-fpm.sock:

sudo systemctl status php8.5-fpm

If you need extra extensions such as php-curl, php-gd, php-mbstring, php-xml, or php-zip, install them now:

sudo apt install php-curl php-gd php-mbstring php-xml php-zip

For information on additional modules and switching PHP versions, see How to Install PHP on Ubuntu 26.04 .

Step 4: Configure Nginx to Serve PHP #

Now that Nginx and PHP-FPM are running, you need a server block that passes .php requests to PHP-FPM. Create a directory for the site and a small test file:

sudo mkdir -p /var/www/example.com
sudo chown -R $USER:$USER /var/www/example.com

Create a new server block configuration:

sudo nano /etc/nginx/sites-available/example.com

Paste the following content. Replace example.com with your domain or your server IP if you do not have a domain yet:

server {
 listen 80;
 listen [::]:80;

 server_name example.com www.example.com;
 root /var/www/example.com;

 index index.php index.html;

 location / {
 try_files $uri $uri/ =404;
 }

 location ~ \.php$ {
 include snippets/fastcgi-php.conf;
 fastcgi_pass unix:/run/php/php8.5-fpm.sock;
 }

 location ~ /\.ht {
 deny all;
 }
}

The try_files directive serves static files when they exist and falls back to a 404 otherwise. The location ~ \.php$ block matches any request ending in .php and forwards it to PHP-FPM through the Unix socket. The final location ~ /\.ht block blocks access to legacy .htaccess files, which Nginx does not use.

Enable the site by creating a symlink in sites-enabled:

sudo ln -s /etc/nginx/sites-available/example.com /etc/nginx/sites-enabled/

If the default server block is still enabled, remove its symlink so Nginx serves your new site for matching requests:

sudo unlink /etc/nginx/sites-enabled/default

Test the configuration before reloading:

sudo nginx -t

The output should end with syntax is ok and test is successful. Reload Nginx to apply the change:

sudo systemctl reload nginx

Step 5: Test the PHP Setup #

Create a simple PHP info file to confirm that Nginx hands PHP requests to PHP-FPM:

echo "<?php phpinfo();" | sudo tee /var/www/example.com/info.php

Open http://example.com/info.php (or http://your_server_ip/info.php) in a browser. You should see the PHP information page that lists the PHP version, loaded extensions, and configuration directives. If the page shows the source code as plain text, Nginx is not passing the request to PHP-FPM and the location ~ \.php$ block needs to be reviewed.

Once you confirm PHP is working, remove the info file. It exposes details about your environment that should not be publicly readable:

sudo rm /var/www/example.com/info.php

Step 6: Test the MySQL Connection from PHP #

To confirm that PHP can talk to MySQL, create a test database and user:

sudo mysql

In the MySQL prompt, run:

CREATE DATABASE lemp_test;
CREATE USER 'lemp_user'@'localhost' IDENTIFIED BY 'changeme';
GRANT ALL PRIVILEGES ON lemp_test.* TO 'lemp_user'@'localhost';
FLUSH PRIVILEGES;
EXIT;

Create a small connection test:

sudo nano /var/www/example.com/db-test.php

Add the following content:

<?php
$mysqli = new mysqli("localhost", "lemp_user", "changeme", "lemp_test");
if ($mysqli->connect_error) {
 die("Connection failed: " . $mysqli->connect_error);
}
echo "Connected to MySQL " . $mysqli->server_info;
$mysqli->close();

Open http://example.com/db-test.php. The page prints Connected to MySQL 8.4.x when the credentials and the PHP MySQL driver are working. Remove the file once you confirm the connection:

sudo rm /var/www/example.com/db-test.php

Troubleshooting #

Nginx shows the welcome page after editing the server block
Nginx still serves the default site. Remove the symlink at /etc/nginx/sites-enabled/default or rename your server block so it loads first, then run sudo nginx -t and sudo systemctl reload nginx.

PHP files download instead of executing
Nginx is not forwarding .php requests to PHP-FPM. Verify that the location ~ \.php$ block exists, that fastcgi_pass points to /run/php/php8.5-fpm.sock, and that PHP-FPM is running with sudo systemctl status php8.5-fpm.

502 Bad Gateway
PHP-FPM is not running, or Nginx is pointing at a wrong socket path. Run ls -l /run/php/ and confirm that the socket file matches the version in your config (for example, php8.5-fpm.sock). Restart the service with sudo systemctl restart php8.5-fpm.

Permission denied accessing the socket
The socket is owned by www-data by default. Make sure Nginx runs as www-data (the default on Ubuntu) and that no custom file permissions on /run/php/ block access.

MySQL connection refused from PHP
Confirm that the php-mysql package is installed, that the user has been granted privileges on the target database, and that the password in the PHP code matches the one used in CREATE USER.

FAQ #

What is the difference between LEMP and LAMP?
LEMP uses Nginx as the web server, while LAMP uses Apache. Nginx handles many concurrent connections with low memory and is a strong fit for static content and reverse proxying. Apache supports per-directory .htaccess files and mod_php, which simplifies shared hosting setups. For a step-by-step Apache install, see How to Install LAMP Stack on Ubuntu 26.04 .

Can I use MariaDB instead of MySQL?
Yes. MariaDB is a drop-in replacement for MySQL and uses the same client tools, the same protocol, and the same SQL syntax for the cases covered in this guide.

Which PHP-FPM socket path do I use?
The path follows the PHP version. On Ubuntu 26.04 with the default PHP 8.5, the socket is /run/php/php8.5-fpm.sock. If you install another version, list /run/php/ to find the right socket file.

How do I add HTTPS to the site?
The recommended path is to install Certbot and request a Let’s Encrypt certificate for your domain. The Certbot Nginx plugin updates the server block automatically and sets up redirection from HTTP to HTTPS.

Next Steps #

You now have a working LEMP stack on Ubuntu 26.04. From here you can deploy a PHP application, create additional Nginx server blocks for more sites, or front the stack with HTTPS using Let’s Encrypt.

When you spin up a new server to run a PHP application or a CMS such as WordPress, Joomla, or Drupal, the LAMP stack is one of the most familiar starting points. LAMP stands for Linux, Apache, MySQL, and PHP, and the four pieces work together to serve dynamic web pages over HTTP.

This guide explains how to install and configure a complete LAMP stack on Ubuntu 26.04. By the end you will have Apache serving HTTP traffic, MySQL 8.4 running as the database, and PHP 8.5 processing dynamic pages through mod_php.

Quick Reference #

Prerequisites #

Before installing the stack, make sure you have:

• A server running Ubuntu 26.04 with a user with sudo privileges .
• The UFW firewall enabled. If you have not configured it yet, see ufw Command in Linux: Uncomplicated Firewall Reference .

Step 1: Install Apache #

Apache is in the default Ubuntu 26.04 repositories. Refresh the package index and install it:

sudo apt update
sudo apt install apache2

The service starts automatically after the install. Confirm it is running:

sudo systemctl status apache2

The output shows the service as active (running). If UFW is enabled, allow HTTP and HTTPS through the firewall:

sudo ufw allow 'Apache Full'

Open http://your_server_ip in a browser. You should see the default Apache welcome page, which confirms that Apache is serving requests.

For an in-depth walkthrough of the install and the directory layout, see How to Install Apache on Ubuntu 26.04 .

Step 2: Install MySQL #

The database tier handles persistence. Install the MySQL server package:

sudo apt install mysql-server

Once the install completes, run the security script. It walks you through removing anonymous users, disabling remote root login, and dropping the test database:

sudo mysql_secure_installation

Answer Y to each hardening question. The validate password component is optional; skip it if you plan to manage credentials yourself.

To verify that the service is running:

sudo systemctl status mysql

For details on creating users and granting privileges, see How to Install MySQL on Ubuntu 26.04 .

Step 3: Install PHP #

Apache integrates with PHP through the libapache2-mod-php module, which lets Apache run PHP code in-process. Install PHP, the Apache module, and the MySQL driver:

sudo apt update
sudo apt install php libapache2-mod-php php-mysql

On Ubuntu 26.04 this pulls in PHP 8.5. Confirm the version:

php -v

The output starts with PHP 8.5.x. Restart Apache so the PHP module loads:

sudo systemctl restart apache2

If you need extra extensions such as php-curl, php-gd, php-mbstring, php-xml, or php-zip, install them now:

sudo apt install php-curl php-gd php-mbstring php-xml php-zip

For information on additional modules and switching PHP versions, see How to Install PHP on Ubuntu 26.04 .

Step 4: Configure an Apache Virtual Host #

The default Apache configuration serves files from /var/www/html. For a real site you usually want a dedicated document root and a virtual host. Create the directory and a small placeholder:

sudo mkdir -p /var/www/example.com
sudo chown -R $USER:$USER /var/www/example.com
echo "<h1>example.com is live</h1>" > /var/www/example.com/index.html

Create a new virtual host file:

sudo nano /etc/apache2/sites-available/example.com.conf

Paste the following content. Replace example.com with your domain or your server IP if you do not have a domain yet:

<VirtualHost *:80>
 ServerName example.com
 ServerAlias www.example.com
 ServerAdmin webmaster@example.com
 DocumentRoot /var/www/example.com

 <Directory /var/www/example.com>
 Options -Indexes +FollowSymLinks
 AllowOverride All
 Require all granted
 </Directory>

 ErrorLog ${APACHE_LOG_DIR}/example.com-error.log
 CustomLog ${APACHE_LOG_DIR}/example.com-access.log combined
</VirtualHost>

AllowOverride All lets you use per-directory .htaccess files, which is required by many PHP applications such as WordPress for clean URL rewrites. Enable the site and disable the default one:

sudo a2ensite example.com
sudo a2dissite 000-default

Make sure mod_rewrite is enabled if your application uses it:

sudo a2enmod rewrite

Test the configuration before reloading Apache:

sudo apache2ctl configtest

The output should end with Syntax OK. Reload Apache to apply the change:

sudo systemctl reload apache2

Step 5: Test the PHP Setup #

Create a PHP info file to confirm that Apache executes PHP:

echo "<?php phpinfo();" | sudo tee /var/www/example.com/info.php

Open http://example.com/info.php (or http://your_server_ip/info.php) in a browser. You should see the PHP information page that lists the PHP version, loaded extensions, and configuration directives. If the browser downloads the file or shows the source code, the PHP module is not loaded; reinstall libapache2-mod-php and restart Apache.

Once you confirm PHP is working, remove the info file. It exposes details about your environment that should not be publicly readable:

sudo rm /var/www/example.com/info.php

Step 6: Test the MySQL Connection from PHP #

To confirm that PHP can talk to MySQL, create a test database and user:

sudo mysql

In the MySQL prompt, run:

CREATE DATABASE lamp_test;
CREATE USER 'lamp_user'@'localhost' IDENTIFIED BY 'changeme';
GRANT ALL PRIVILEGES ON lamp_test.* TO 'lamp_user'@'localhost';
FLUSH PRIVILEGES;
EXIT;

Create a small connection test:

sudo nano /var/www/example.com/db-test.php

Add the following content:

<?php
$mysqli = new mysqli("localhost", "lamp_user", "changeme", "lamp_test");
if ($mysqli->connect_error) {
 die("Connection failed: " . $mysqli->connect_error);
}
echo "Connected to MySQL " . $mysqli->server_info;
$mysqli->close();

Open http://example.com/db-test.php. The page prints Connected to MySQL 8.4.x when the credentials and the PHP MySQL driver are working. Remove the file once you confirm the connection:

sudo rm /var/www/example.com/db-test.php

Troubleshooting #

Apache shows the default page after editing the virtual host
The default site is still enabled. Run sudo a2dissite 000-default, then sudo a2ensite example.com, and reload Apache.

PHP files download instead of executing
The Apache PHP module is not loaded. Reinstall it with sudo apt install --reinstall libapache2-mod-php, enable it with sudo a2enmod php8.5, and restart Apache.

AllowOverride All is ignored
The <Directory> block in the virtual host must include AllowOverride All. Confirm that the path matches your DocumentRoot and run sudo apache2ctl configtest after the change.

.htaccess rewrites do not work
The rewrite module is not enabled. Run sudo a2enmod rewrite and restart Apache. Verify that the <Directory> block sets AllowOverride All.

MySQL connection refused from PHP
Confirm that the php-mysql package is installed, that the user has been granted privileges on the target database, and that the password in the PHP code matches the one used in CREATE USER.

FAQ #

What is the difference between LAMP and LEMP?
LAMP uses Apache as the web server, while LEMP uses Nginx. Apache supports .htaccess overrides and mod_php, which makes shared hosting and many PHP CMS workflows simpler. Nginx is event-driven and tends to use less memory under high concurrency. For an Nginx-based stack, see How to Install LEMP Stack on Ubuntu 26.04 .

Can I use MariaDB instead of MySQL?
Yes. MariaDB is a drop-in replacement for MySQL and uses the same client tools, the same protocol, and the same SQL syntax for the cases covered in this guide.

Should I use mod_php or PHP-FPM with Apache?
mod_php is the simplest setup and is fine for many sites. For higher concurrency or when you run multiple PHP versions, switch to PHP-FPM with mpm_event and proxy_fcgi. The php-fpm package and the proxy_fcgi Apache module handle the connection.

How do I add HTTPS to the site?
Install Certbot and request a Let’s Encrypt certificate for your domain. The Certbot Apache plugin updates the virtual host automatically and sets up redirection from HTTP to HTTPS.

Next Steps #

You now have a working LAMP stack on Ubuntu 26.04. From here you can deploy a PHP application, create additional Apache virtual hosts for more sites, or add HTTPS using Let’s Encrypt.

给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组 互补 的 最少 操作次数。

示例 1：

输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。

示例 2：

输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。

示例 3：

输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。

提示：

• n == nums.length
• 2 <= n <= 105
• 1 <= nums[i] <= limit <= 105
• n 是偶数。

题目说，可以把 $\textit{nums}$ 中的任意元素变成 $[1,\textit{limit}]$ 中的整数，所以 $\textit{nums}[i]+\textit{nums}[n-1-i]$ 可以变成 $[2,\textit{limit}\cdot 2]$ 中的整数。

如果写个二重循环，先枚举 $\textit{nums}[i]+\textit{nums}[n-1-i]$ 都变成 $2,3,4,\ldots, \textit{limit}\cdot 2$，再遍历 $\textit{nums}$，计算操作次数，那么时间复杂度为 $\mathcal{O}(n\cdot \textit{limit})$，太慢了。

定义 $a[k]$ 表示 $\textit{nums}[i]+\textit{nums}[n-1-i]$ 都变成 $k$ 所需的操作次数。

横看成岭侧成峰，单看 $(\textit{nums}[i],\textit{nums}[n-1-i])$，这对元素会如何影响数组 $a$？哪些 $a[k]$ 需要增加 $1$，哪些 $a[k]$ 需要增加 $2$？

设 $x = \textit{nums}[i]$，$y = \textit{nums}[n-1-i]$。

• 如果 $x$ 和 $y$ 都不修改，那么 $a[x+y]$ 不变。
• 如果只修改 $y$，那么 $x+y$ 可以是 $[x+1,x+\textit{limit}]$ 中的整数；如果只修改 $x$，那么 $x+y$ 可以是 $[y+1,y+\textit{limit}]$ 中的整数。这两个区间的并集为 $[\min(x,y)+1, \max(x,y)+\textit{limit}]$。这个区间内的整数 $k$，除了 $k=x+y$ 时 $a[x+y]$ 不变，其余 $a[k]$ 都增加 $1$，表示当 $k$ 在这个区间内时，把 $x+y$ 变成 $k$ 只需操作 $1$ 次。
• 其余在 $[2,\min(x,y)]\cup[\max(x,y)+\textit{limit}+1,\textit{limit}\cdot 2]$ 中的 $k$，把 $a[k]$ 都增加 $2$，表示当 $k$ 在这个区间内时，把 $x+y$ 变成 $k$ 需要操作 $2$ 次。

这里用到了区间增加同一个数的操作，这可以用差分数组实现，原理讲解。

计算差分数组的前缀和，就得到了数组 $a$。

答案为 $\min\limits_{k=2}^{\textit{limit}\cdot 2}a[k]$。

注：题目保证 $n$ 是偶数。

优化前

###py

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        diff = [0] * (limit * 2 + 2)

        for i in range(n // 2):
            x = nums[i]
            y = nums[-1 - i]
            l = min(x, y) + 1
            r = max(x, y) + limit

            # [2, l-1] += 2
            diff[2] += 2
            diff[l] -= 2

            # [l, r] += 1
            diff[l] += 1
            diff[r + 1] -= 1

            # x+y 实际操作 0 次，从 [l, r] 中去掉
            # [x+y, x+y] -= 1
            diff[x + y] -= 1
            diff[x + y + 1] += 1

            # [r+1, limit*2] += 2
            diff[r + 1] += 2
            # limit*2+1 不在 [2, limit*2] 中，可以省略

        ans = inf
        sum_d = 0
        for d in diff[2 : limit * 2 + 1]:
            sum_d += d
            ans = min(ans, sum_d)
        return ans

###java

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int[] diff = new int[limit * 2 + 2];

        for (int i = 0; i < n / 2; i++) {
            int x = nums[i];
            int y = nums[n - 1 - i];
            int l = Math.min(x, y) + 1;
            int r = Math.max(x, y) + limit;

            // [2, l-1] += 2
            diff[2] += 2;
            diff[l] -= 2;

            // [l, r] += 1
            diff[l]++;
            diff[r + 1]--;

            // x+y 实际操作 0 次，从 [l, r] 中去掉
            // [x+y, x+y] -= 1
            diff[x + y]--;
            diff[x + y + 1]++;

            // [r+1, limit*2] += 2
            diff[r + 1] += 2;
            // limit*2+1 不在 [2, limit*2] 中，可以省略
        }

        int ans = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 2; i <= limit * 2; i++) {
            sum += diff[i];
            ans = Math.min(ans, sum);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> diff(limit * 2 + 2);

        for (int i = 0; i < n / 2; i++) {
            int x = nums[i];
            int y = nums[n - 1 - i];
            int l = min(x, y) + 1;
            int r = max(x, y) + limit;

            // [2, l-1] += 2
            diff[2] += 2;
            diff[l] -= 2;

            // [l, r] += 1
            diff[l]++;
            diff[r + 1]--;

            // x+y 实际操作 0 次，从 [l, r] 中去掉
            // [x+y, x+y] -= 1
            diff[x + y]--;
            diff[x + y + 1]++;

            // [r+1, limit*2] += 2
            diff[r + 1] += 2;
            // limit*2+1 不在 [2, limit*2] 中，可以省略
        }

        int ans = INT_MAX;
        int sum = 0;
        for (int i = 2; i <= limit * 2; i++) {
            sum += diff[i];
            ans = min(ans, sum);
        }
        return ans;
    }
};

###go

func minMoves(nums []int, limit int) int {
n := len(nums)
diff := make([]int, limit*2+2)
for i, x := range nums[:n/2] {
y := nums[n-1-i]
l := min(x, y) + 1
r := max(x, y) + limit

// [2, l-1] += 2
diff[2] += 2
diff[l] -= 2

// [l, r] += 1
diff[l]++
diff[r+1]--

// x+y 实际操作 0 次，从 [l, r] 中去掉
// [x+y, x+y] -= 1
diff[x+y]--
diff[x+y+1]++

// [r+1, limit*2] += 2
diff[r+1] += 2
// limit*2+1 不在 [2, limit*2] 中，可以省略
}

ans := math.MaxInt
sum := 0
for _, d := range diff[2 : limit*2+1] {
sum += d
ans = min(ans, sum)
}
return ans
}

优化

• diff[2] += 2 执行了 $\dfrac{n}{2}$ 次，相当于 $\textit{diff}[2]$ 整体增加了 $n$。也可以初始化 $\textit{sum}=n$。
• diff[l] -= 2 和 diff[l] += 1 合并为 diff[l] -= 1。
• diff[r+1] -= 1 和 diff[r+1] += 2 合并为 diff[r+1] += 1。

###py

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        diff = [0] * (limit * 2 + 2)

        for i in range(n // 2):
            x = nums[i]
            y = nums[n - 1 - i]
            l = min(x, y) + 1
            r = max(x, y) + limit
            diff[l] -= 1
            diff[x + y] -= 1
            diff[x + y + 1] += 1
            diff[r + 1] += 1

        ans = inf
        sum_d = n
        for d in diff[2 : limit * 2 + 1]:
            sum_d += d
            ans = min(ans, sum_d)
        return ans

###java

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int[] diff = new int[limit * 2 + 2];

        for (int i = 0; i < n / 2; i++) {
            int x = nums[i];
            int y = nums[n - 1 - i];
            int l = Math.min(x, y) + 1;
            int r = Math.max(x, y) + limit;
            diff[l]--;
            diff[x + y]--;
            diff[x + y + 1]++;
            diff[r + 1]++;
        }

        int ans = Integer.MAX_VALUE;
        int sum = n;
        for (int i = 2; i <= limit * 2; i++) {
            sum += diff[i];
            ans = Math.min(ans, sum);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> diff(limit * 2 + 2);

        for (int i = 0; i < n / 2; i++) {
            int x = nums[i];
            int y = nums[n - 1 - i];
            int l = min(x, y) + 1;
            int r = max(x, y) + limit;
            diff[l]--;
            diff[x + y]--;
            diff[x + y + 1]++;
            diff[r + 1]++;
        }

        int ans = INT_MAX;
        int sum = n;
        for (int i = 2; i <= limit * 2; i++) {
            sum += diff[i];
            ans = min(ans, sum);
        }
        return ans;
    }
};

###go

func minMoves(nums []int, limit int) int {
n := len(nums)
diff := make([]int, limit*2+2)
for i, x := range nums[:n/2] {
y := nums[n-1-i]
l := min(x, y) + 1
r := max(x, y) + limit
diff[l]--
diff[x+y]--
diff[x+y+1]++
diff[r+1]++
}

ans := math.MaxInt
sum := n
for _, d := range diff[2 : limit*2+1] {
sum += d
ans = min(ans, sum)
}
return ans
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n+ \textit{limit})$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(\textit{limit})$。

专题训练

见下面差分题单的「§2.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站@灵茶山艾府

假设 res[x] 表示的是，nums[i] + nums[n - 1 - i] 为 x 的时候，需要多少次操作。

我们只需要计算出所有的 x 对应的 res[x], 取最小值就好了。

根据题意，nums[i] + nums[n - 1 - i] 最小是 2，即将两个数都修改为 1；最大是 2 * limit，即将两个数都修改成 limit。

所以，res[x] 中 x 的取值范围是 [2, 2 * limit]。我们用一个 res[2 * limit + 1] 的数组就好。

关键是，如何求出每一个 res[x] 位置的值，即修改后互补的数字和为 x，需要多少操作？

为了叙述方便，假设 nums[i] 为 A；nums[n - 1 - i] 为 B。

显然有：

• 如果修改后两个数字的和是 A + B，我们使用的操作数是 0 (没有修改));

• 否则的话，如果修改后两个数字和在 [1 + min(A, B), limit + max(A, B)] 的范围，我们使用的操作数是 1 (只需要修改 A 或者 B 就好);

• 否则的话，如果修改后两个数字和在 [2, 2 * limit] 的范围，我们使用的操作数是 ``2`(两个数字都要修改));

所以，我们的算法是遍历每一组 nums[i] 和 nums[n - 1 - i]，然后：

• 先将 [2, 2 * limit] 的范围需要的操作数 + 2；

• 之后，将 [1 + min(A, B), limit + max(A, B)] 的范围需要的操作数 - 1（即 2 - 1 = 1，操作 1 次）；

• 之后，将 [A + B] 位置的值再 -1（即 1 - 1 = 0，操作 0 次）。

可以看出，整个过程都是在做区间更新。最后，我们查询每一个位置的值，取最小值就好。

对于这个需求，我们当然可以使用线段树或者树状数组解决，但代码量稍大，且复杂度也是 O(nlogn) 的。

但是仔细观察，我们发现，我们只需要作区间更新，和单点查询。

对于这个需求，有一种非常常规的”数据结构“，叫差分数组，完全满足需求，并且编程极其简单，整体可以在 O(n) 的时间解决。

打上引号，是因为差分数组就是一个数组而已。

简单来说，差分数组 diff[i]，存储的是 res[i] - res[i - 1]；而差分数组 diff[0...i] 的和，就是 res[i] 的值。

大家可以用一个小数据试验一下，很好理解。

如果我们想给 [l, r] 的区间加上一个数字 a, 只需要 diff[l] += a，diff[r + 1] -= a。

这样做，diff[0...i] 的和，就是更新后 res[i] 的值。

依然是，大家可以用一个小数据试验一下，其实很好理解。

有了差分数组这个武器，这个问题就很简单了。

我的参考代码如下（C++）：

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        
        // 差分数组, diff[0...x] 的和表示最终互补的数字和为 x，需要的操作数
        // 因为差分数组的计算需要更新 r + 1，所以数组的总大小在 limit * 2 + 1 的基础上再 + 1
        vector<int> diff(limit * 2 + 2, 0);

        int n = nums.size();
        for(int i = 0; i < n / 2; i ++){
            int A = nums[i], B = nums[n - 1 - i];

            // [2, 2 * limit] 范围 + 2
            int l = 2, r = 2 * limit;
            diff[l] += 2, diff[r + 1] -= 2;

            // [1 + min(A, B), limit + max(A, B)] 范围 -1
            l = 1 + min(A, B), r = limit + max(A, B);
            diff[l] += -1, diff[r + 1] -= -1;

            // [A + B] 再 -1    
            l = A + B, r = A + B;
            diff[l] += -1, diff[r + 1] -= -1;
        }

        // 依次求和，得到 最终互补的数字和 i 的时候，需要的操作数 sum
        // 取最小值
        int res = n, sum = 0;
        for(int i = 2; i <= 2 * limit; i ++){
            sum += diff[i];
            if(sum < res) res = sum;
        }
        return res;
    }
};

整体时间复杂度是 O(n) 的；空间复杂度也是 O(n) 的。

觉得有帮助请点赞哇！

本场周赛题解 | 我的LeetCode比赛题解

我们考虑任意一个数对$(a,b)$，不妨假设$a\leq b$。假设最终选定的和值为$target$，则我们可以发现，对于$(a,b)$这个数对：

• 当$target<1+a$时，需要操作两次；
• 当$1+a\leq target<a+b$时，需要操作一次；
• 当$target=a+b$时，不需要操作；
• 当$a+b<target\leq b+limit$时，需要操作一次；
• 当$target>b+limit$时，需要操作两次。

我们设初始操作次数为两次。令$target$从数轴最左端开始向右移动，我们会发现：

• 在$1+a$处，操作次数减少一次；
• 在$a+b$处，操作次数减少一次；
• 在$a+b+1$处，操作次数增加一次；
• 在$b+limit+1$处，操作次数增加一次。

因此，我们可以遍历数组中的所有数对，求出每个数对的这四个关键位置，然后更新差分数组。最后，我们遍历（扫描）差分数组，就可以找到令总操作次数最小的$target$，同时可以得到最少的操作次数。

• 时间复杂度$O(N+L)$。
• 空间复杂度$O(L)$。

###cpp

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> delta(limit * 2 + 2);
        for (int i = 0; i < n / 2; ++i) {
            int lo = 1 + min(nums[i], nums[n - i - 1]);
            int hi = limit + max(nums[i], nums[n - i - 1]);
            int sum = nums[i] + nums[n - i - 1];
            delta[lo]--;
            delta[sum]--;
            delta[sum + 1]++;
            delta[hi + 1]++;
        }
        int now = n;
        int ans = n;
        for (int i = 2; i <= limit * 2; ++i) {
            now += delta[i];
            ans = min(ans, now);
        }
        return ans;
    }
};

Sooner or later, every Nginx configuration grows beyond a single catch-all rule. You want PHP files to reach PHP-FPM, static assets to be served directly with long cache headers, one endpoint to be proxied to an application server, and an admin path to be protected with basic auth. Each of these rules lives in its own location block.

The part that trips people up is not writing a location block, it is predicting which one Nginx will pick when a request could match more than one. Nginx does not scan top to bottom. It uses a specific priority order that mixes prefix length, match type, and regex ordering. This guide walks through the match types, the exact order Nginx follows, and the patterns you will use most often.

Location Block Syntax #

A location block lives inside a server block and defines how Nginx handles requests whose URI matches a given pattern:

location [modifier] pattern {
 # directives
}

The modifier is optional. When it is omitted, Nginx treats the pattern as a prefix. The pattern is a string (for prefix and exact matches) or a regular expression (when the modifier is ~ or ~*).

A minimal server block that uses two location blocks looks like this:

server {
 listen 80;
 server_name example.com;
 root /var/www/example.com;

 location / {
 try_files $uri $uri/ =404;
 }

 location /api/ {
 proxy_pass http://127.0.0.1:3000;
 }
}

Requests for /about.html fall into the first block and are served as static files. Requests for /api/users fall into the second block and are proxied to the application.

The Five Match Types #

Nginx supports five kinds of location matches. Each one uses a different modifier, and each one has its own role in the priority order covered in the next section.

• location /path/ - Prefix match. Matches any URI that begins with the given string. This is the default when no modifier is used.
• location = /path - Exact match. Matches only when the request URI is exactly equal to the given string.
• location ^~ /path/ - Preferential prefix match. Same matching rules as a plain prefix match, but tells Nginx to stop searching for regex matches once this block is selected as the longest prefix.
• location ~ pattern - Case-sensitive regex match. Matches if the URI matches the regular expression.
• location ~* pattern - Case-insensitive regex match. Same as ~, but ignores letter case.

There is also a sixth form, location @name, for named locations. Named locations are not used during the normal match process; they are jumped to from directives such as try_files and error_page. We cover them later in this guide.

How Nginx Picks a Location #

When a request comes in, Nginx does not walk through location blocks top to bottom. It picks the block that wins according to a fixed priority order.

The order Nginx follows is:

1. Look for an exact match (=). If one matches, stop and use it.
2. Look at all prefix matches (plain and ^~) and remember the longest one that matches.
3. If the longest prefix match was defined with ^~, stop and use it.
4. Otherwise, go through regex matches (~ and ~*) in the order they appear in the configuration. The first one that matches wins.
5. If no regex matches, fall back to the longest prefix match remembered in step 2.

The consequences of this order are worth pausing on. Regex blocks are checked in source order, but prefix blocks are not; the longest match wins regardless of position in the file. The ^~ modifier changes the outcome by skipping the regex pass entirely when it is the longest prefix match, even if a regex block would also have matched.

A Worked Example #

The easiest way to understand the priority order is to trace a few requests through a real configuration:

server {
 listen 80;
 server_name example.com;
 root /var/www/example.com;

 location = / {
 return 200 "home\n";
 }

 location / {
 try_files $uri $uri/ =404;
 }

 location /images/ {
 expires 30d;
 }

 location ^~ /downloads/ {
 autoindex on;
 }

 location ~* \.(png|jpg|jpeg|gif)$ {
 expires 7d;
 access_log off;
 }

 location ~ \.php$ {
 fastcgi_pass unix:/run/php/php-fpm.sock;
 include fastcgi_params;
 }
}

Now trace what happens for a few requests:

• GET /: The = block matches exactly and wins immediately. Nginx returns the text home.
• GET /about.html: No exact match, no ^~ match, and no regex match. The longest prefix match is /, so the try_files block serves the static file.
• GET /images/logo.png: The longest prefix match is /images/, which is a plain prefix (no ^~), so regex checking still happens. The first regex to match is the image extension block (~*), so that block wins and the file is served with a 7-day expiry.
• GET /downloads/setup.exe: The longest prefix match is /downloads/, defined with ^~. Because of the ^~, regex checking is skipped and the directory listing block wins.
• GET /info.php: The longest prefix match is /. Regex checking runs, and the \.php$ block matches, so the request is passed to PHP-FPM.

Notice that the block order in the file did not change the outcome for prefix matches. It only changed the outcome for regex matches, where the first match wins.

Named Locations #

A named location starts with @ and does not take part in the matching logic. You can only enter a named location by being redirected there from another directive:

server {
 listen 80;
 server_name example.com;
 root /var/www/example.com;

 location / {
 try_files $uri $uri/ @fallback;
 }

 location @fallback {
 proxy_pass http://127.0.0.1:3000;
 }
}

In this configuration, Nginx first tries to serve the request as a static file. If the file is not found, try_files jumps to @fallback, which proxies the request to an application server on port 3000. This is a common pattern for single-page apps and for frameworks that handle their own routing.

Named locations are also useful with the error_page directive, where you can route errors into a named block that returns a custom response.

Common Patterns #

Most Nginx configurations end up using a handful of recurring location patterns. The snippets below show the shapes you will reach for most often.

Serve Static Files with a Fallback #

location / {
 try_files $uri $uri/ /index.html;
}

Nginx tries the requested URI as a file, then as a directory, and falls back to /index.html. This works well for single-page apps where the router lives in the browser.

Cache Long-Lived Assets #

location ~* \.(?:css|js|woff2?|png|jpg|jpeg|gif|svg|ico)$ {
 expires 30d;
 add_header Cache-Control "public, immutable";
 access_log off;
}

Assets whose content is fingerprinted by the build pipeline can be cached aggressively. The access_log off directive keeps the access log focused on real page requests; see the Nginx log files guide for where those logs live and how to tune them.

Pass PHP Requests to PHP-FPM #

location ~ \.php$ {
 include snippets/fastcgi-php.conf;
 fastcgi_pass unix:/run/php/php-fpm.sock;
}

The regex matches any URI that ends with .php. The fastcgi-php.conf snippet shipped with most distributions sets the correct SCRIPT_FILENAME and related parameters.

Proxy a Path to an Application #

location /api/ {
 proxy_pass http://127.0.0.1:3000;
 proxy_set_header Host $host;
 proxy_set_header X-Real-IP $remote_addr;
 proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
 proxy_set_header X-Forwarded-Proto $scheme;
}

For a deeper walkthrough of the proxy headers and common pitfalls, see the Nginx reverse proxy guide .

Protect an Admin Path #

location ^~ /admin/ {
 auth_basic "Restricted";
 auth_basic_user_file /etc/nginx/.htpasswd;
}

The ^~ modifier makes sure this block wins over any regex block (for example, a generic static-asset rule), so the auth challenge is not accidentally bypassed by a more specific pattern. Basic auth sends credentials in clear text, so serve the site over HTTPS; see how to redirect HTTP to HTTPS in Nginx .

Test the Configuration #

After changing location blocks, always test the Nginx configuration before reloading the service:

sudo nginx -t

If the syntax check passes, reload Nginx so the change takes effect without dropping active connections:

sudo systemctl reload nginx

If the test fails, Nginx prints the file name and line number that caused the error. Fix that issue first, then run sudo nginx -t again.

Quick Reference #

Common Mistakes #

A few patterns cause most of the confusion around location blocks.

Assuming top-to-bottom evaluation. Moving a prefix block higher in the file does not make it more likely to match. Prefix matches are chosen by length, not by position.

Forgetting that ^~ skips regex. If a request matches both a ^~ prefix and a regex block, the regex block is not evaluated. This is a feature, not a bug, but it is easy to forget when debugging why a regex rule is being ignored.

Trailing slashes. location /images/ and location /images behave differently. The first only matches URIs that start with /images/, while the second also matches /imagesfoo. Stick to trailing slashes for directory-like prefixes.

Using proxy_pass with a trailing slash on the upstream. Writing proxy_pass http://backend/; rewrites the path in a different way than proxy_pass http://backend;. The Nginx proxy_pass documentation explains the URI replacement rules in detail.

Regex order. When two regex blocks can match the same URI, the one that appears first in the config wins. If requests are landing in the wrong regex block, check the order.

Conclusion #

Most Nginx misconfigurations come from assumptions about the order of evaluation, not from the directives themselves. Once you know that exact matches win first, that ^~ can short-circuit the regex pass, and that regex blocks are tried in source order, the behavior of a complex server block becomes predictable.

给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：

• actuali 是完成第 i 个任务 需要耗费 的实际能量。
• minimumi 是开始第 i 个任务前需要达到的最低能量。

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的 最少 初始能量。

示例 1：

输入：tasks = [[1,2],[2,4],[4,8]]
输出：8
解释：
一开始有 8 能量，我们按照如下顺序完成任务：
    - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
    - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
    - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。

示例 2：

输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出：32
解释：
一开始有 32 能量，我们按照如下顺序完成任务：
    - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
    - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
    - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
    - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
    - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。

示例 3：

输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出：27
解释：
一开始有 27 能量，我们按照如下顺序完成任务：
    - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
    - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
    - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
    - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
    - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
    - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。

提示：

• 1 <= tasks.length <= 105
• 1 <= actuali <= minimumi <= 104

按照什么规则排序？

本文把 $\textit{actual}$ 简称为 $a$，把 $\textit{minimum}$ 简称为 $m$。

如果 $\textit{tasks}$ 的某个排列 $T$ 是最优的（完成所有任务所需的初始能量最少），那么 $T$ 中的相邻任务满足什么性质？

设 $T$ 中的一对相邻任务为 $t_1 = (a_1,m_1)$ 和 $t_2 = (a_2,m_2)$。设初始能量为 $E_0$，完成这两个任务之前的能量为 $E$。由于从一开始到完成这两个任务之前，所消耗的能量之和是固定的 $S$，所以有 $E = E_0-S$。根据该式，$E$ 越小，初始能量 $E_0$ 也越小。

先完成哪个任务更好？

• 如果先完成 $t_1$ 再完成 $t_2$，那么完成 $t_1$ 之前，必须满足 $E\ge m_1$；完成 $t_2$ 之前，必须满足 $E-a_1\ge m_2$。联立得 $E\ge \max(m_1,m_2+a_1)$。
• 如果先完成 $t_2$ 再完成 $t_1$，那么完成 $t_2$ 之前，必须满足 $E\ge m_2$；完成 $t_1$ 之前，必须满足 $E-a_2\ge m_1$。联立得 $E\ge \max(m_2,m_1+a_2)$。

如果先完成 $t_1$ 再完成 $t_2$ 更优（或者相同），则有

$$
\max(m_1,m_2+a_1)\le \max(m_2,m_1+a_2)
$$

两边同时减去 $a_1+a_2$，得

$$
\max(m_1-a_1-a_2,m_2-a_2)\le \max(m_2-a_1-a_2,m_1-a_1)
$$

为方便阅读，令 $X=m_1-a_1$，$Y = m_2-a_2$，上式化简为

$$
\max(X-a_2,Y)\le \max(Y-a_1,X)
$$

• 如果 $X<Y$，那么上式左侧等于 $Y$，右侧严格小于 $Y$（题目保证 $a_1 > 0$），此时 $\max(X-a_2,Y) > \max(Y-a_1,X)$。
• 如果 $X\ge Y$，那么上式左侧两个值都 $\le X$，右侧等于 $X$，此时 $\max(X-a_2,Y) \le \max(Y-a_1,X)$。

所以当且仅当 $X\ge Y$ 成立时，$\max(X-a_2,Y)\le \max(Y-a_1,X)$ 成立。

所以当且仅当 $m_1-a_1 \ge m_2-a_2$ 成立时，先完成 $t_1$ 再完成 $t_2$ 更优（或者相同）。

这意味着，对于 $\textit{tasks}$ 中的相邻任务，设左边的任务为 $(a_1,m_1)$，右边的任务为 $(a_2,m_2)$，如果 $m_1-a_1 < m_2-a_2$，那么交换这两个任务可以让初始能量变得更小（或者不变）。于是通过交换 $\textit{tasks}$ 的相邻任务（类似冒泡排序的过程），把 $\textit{tasks}$ 按照 $m_i-a_i$ 从大到小排序，可以得到 $\textit{tasks}$ 的最优排列。

计算初始能量（正序）

设初始能量为 $E_0$，设执行 $\textit{tasks}[i] = (a_i,m_i)$ 之前，累计耗费的能量为 $S$，那么当前能量为 $E_0 - S$，必须满足

$$
E_0 - S \ge m_i
$$

即

$$
E_0 \ge S + m_i
$$

由此可以得到 $n$ 个关于 $E_0$ 的下界，所有下界取最大值，即为答案。

###py

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda t: t[0] - t[1])  # 按照 minimum - actual 从大到小排序

        ans = 0
        s = 0  # 累计耗费的能量
        for actual, minimum in tasks:
            # 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
            # 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
            ans = max(ans, s + minimum)
            s += actual
        return ans

###java

class Solution {
    public int minimumEffort(int[][] tasks) {
        // 按照 minimum - actual 从大到小排序
        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));

        int ans = 0;
        int s = 0; // 累计耗费的能量
        for (int[] t : tasks) {
            int actual = t[0];
            int minimum = t[1];
            // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
            // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
            ans = Math.max(ans, s + minimum);
            s += actual;
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        ranges::sort(tasks, {}, [](auto& t) { return t[0] - t[1]; }); // 按照 minimum - actual 从大到小排序

        int ans = 0;
        int s = 0; // 累计耗费的能量
        for (auto& t : tasks) {
            int actual = t[0], minimum = t[1];
            // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
            // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
            ans = max(ans, s + minimum);
            s += actual;
        }
        return ans;
    }
};

###c

int cmp(const void* p, const void* q) {
    int* a = *(int**)p;
    int* b = *(int**)q;
    return (b[1] - b[0]) - (a[1] - a[0]); // 按照 minimum - actual 从大到小排序
}

int minimumEffort(int** tasks, int tasksSize, int* tasksColSize) {
    qsort(tasks, tasksSize, sizeof(int*), cmp);

    int ans = 0;
    int s = 0; // 累计耗费的能量
    for (int i = 0; i < tasksSize; i++) {
        int actual = tasks[i][0];
        int minimum = tasks[i][1];
        // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
        // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
        ans = MAX(ans, s + minimum);
        s += actual;
    }
    return ans;
}

###go

func minimumEffort(tasks [][]int) (ans int) {
slices.SortFunc(tasks, func(a, b []int) int {
return (b[1] - b[0]) - (a[1] - a[0]) // 按照 minimum - actual 从大到小排序
})

s := 0 // 累计耗费的能量
for _, t := range tasks {
actual, minimum := t[0], t[1]
// 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
// 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
ans = max(ans, s+minimum)
s += actual
}
return
}

###js

var minimumEffort = function(tasks) {
    tasks.sort((a, b) => (b[1] - b[0]) - (a[1] - a[0])); // 按照 minimum - actual 从大到小排序

    let ans = 0;
    let s = 0; // 累计耗费的能量
    for (const [actual, minimum] of tasks) {
        // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
        // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
        ans = Math.max(ans, s + minimum);
        s += actual;
    }
    return ans;
};

###rust

impl Solution {
    pub fn minimum_effort(mut tasks: Vec<Vec<i32>>) -> i32 {
        tasks.sort_unstable_by_key(|t| t[0] - t[1]); // 按照 minimum - actual 从大到小排序

        let mut ans = 0;
        let mut s = 0; // 累计耗费的能量
        for t in tasks {
            let actual = t[0];
            let minimum = t[1];
            // 题目要求 E0 - s >= minimum，即 E0 >= s + minimum
            // 由此可以得到 n 个关于 E0 的下界，所有下界的最大值即为答案
            ans = ans.max(s + minimum);
            s += actual;
        }
        ans
    }
}

计算初始能量（倒序）

也可以从右到左计算。

设完成任务 $t_i = (a_i,m_i)$ 之后的能量为 $E$，那么完成 $t_i$ 之前的能量为 $E+a_i$，但这个能量又必须 $\ge m_i$，所以完成 $t_i$ 之前的能量至少为

$$
\max(E+a_i, m_i)
$$

为了最小化初始能量，完成最后一个任务后的能量应当为 $0$，作为 $E$ 的初始值。

代码实现时，可以改成按照 $m_i-a_i$ 从小到大排序，这样可以正序遍历数组，更方便。

###py

class Solution:
    def minimumEffort(self, tasks: list[list[int]]) -> int:
        tasks.sort(key=lambda t: t[1] - t[0])  # 按照 minimum - actual 从小到大排序

        e = 0
        for actual, minimum in tasks:
            # 完成该任务之后的能量为 e，那么完成该任务之前的能量为 e+actual，同时该能量必须至少为 minimum
            e = max(e + actual, minimum)
        return e

###java

class Solution {
    public int minimumEffort(int[][] tasks) {
        // 按照 minimum - actual 从小到大排序
        Arrays.sort(tasks, (a, b) -> (a[1] - a[0]) - (b[1] - b[0]));

        int e = 0;
        for (int[] t : tasks) {
            int actual = t[0];
            int minimum = t[1];
            // 完成 t 之后的能量为 e，那么完成 t 之前的能量为 e+actual，同时该能量必须至少为 minimum
            e = Math.max(e + actual, minimum);
        }
        return e;
    }
}

###cpp

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        ranges::sort(tasks, {}, [](auto& t) { return t[1] - t[0]; }); // 按照 minimum - actual 从小到大排序

        int e = 0;
        for (auto& t : tasks) {
            int actual = t[0], minimum = t[1];
            // 完成 t 之后的能量为 e，那么完成 t 之前的能量为 e+actual，同时该能量必须至少为 minimum
            e = max(e + actual, minimum);
        }
        return e;
    }
};

###c

int cmp(const void* p, const void* q) {
    int* a = *(int**)p;
    int* b = *(int**)q;
    return (a[1] - a[0]) - (b[1] - b[0]); // 按照 minimum - actual 从小到大排序
}

int minimumEffort(int** tasks, int tasksSize, int* tasksColSize) {
    qsort(tasks, tasksSize, sizeof(int*), cmp);

    int e = 0;
    for (int i = 0; i < tasksSize; i++) {
        int actual = tasks[i][0];
        int minimum = tasks[i][1];
        // 完成 tasks[i] 之后的能量为 e，那么完成 tasks[i] 之前的能量为 e+actual，同时该能量必须至少为 minimum
        e = MAX(e + actual, minimum);
    }
    return e;
}

###go

func minimumEffort(tasks [][]int) (e int) {
slices.SortFunc(tasks, func(a, b []int) int {
return (a[1] - a[0]) - (b[1] - b[0]) // 按照 minimum - actual 从小到大排序
})

for _, t := range tasks {
actual, minimum := t[0], t[1]
// 完成 t 之后的能量为 e，那么完成 t 之前的能量为 e+actual，同时该能量必须至少为 minimum
e = max(e+actual, minimum)
}
return
}

###js

var minimumEffort = function(tasks) {
    tasks.sort((a, b) => (a[1] - a[0]) - (b[1] - b[0])); // 按照 minimum - actual 从小到大排序

    let e = 0;
    for (const [actual, minimum] of tasks) {
        // 完成该任务之后的能量为 e，那么完成该任务之前的能量为 e+actual，同时该能量必须至少为 minimum
        e = Math.max(e + actual, minimum);
    }
    return e;
};

###rust

impl Solution {
    pub fn minimum_effort(mut tasks: Vec<Vec<i32>>) -> i32 {
        tasks.sort_unstable_by_key(|t| t[1] - t[0]); // 按照 minimum - actual 从小到大排序

        let mut e = 0;
        for t in tasks {
            let actual = t[0];
            let minimum = t[1];
            // 完成 t 之后的能量为 e，那么完成 t 之前的能量为 e+actual，同时该能量必须至少为 minimum
            e = minimum.max(e + actual);
        }
        e
    }
}

复杂度分析

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

专题训练

见下面贪心题单的「§1.7 交换论证法」。

分类题单

如何科学刷题？

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站@灵茶山艾府

【儿须成名酒须醉】Python3+排序+贪心+数学证明+模拟

提交结果

• 执行用时： 164 ms , 在所有 Python3 提交中击败了 94.62% 的用户
• 内存消耗： 42.6 MB , 在所有 Python3 提交中击败了 58.06% 的用户
• 通过测试用例： 42 / 42

解题思路

1. 考虑两个任务的能量组合任务1为$[a_1,m_1]$与任务2为$[a_2,m_2]$
2. 则先做任务1再做任务2的最小初始能量为$s_{12}=max(m_1,m_2+a_1)$，反之则是$s_{21}=max(m_2,m_1+a_2)$
3. 不失一般地设$m_1-a_1>=m_2-a_2$，则有$m_1+a_2>=m_2+a_1$

• 当$m_1<=m_2$时，显然有$s_{12}=m_2+a_1$，而$s_{21}=max(m_2,m_1+a_2)$，由上可得$m_2+a_1<=m_1+a_2$，因此有$s_{12}<=s_{21}$
• 当$m_1>m_2$时，显然有$s_{12}=max(m_1,m_2+a_1)$，而$s_{21}=m_1+a_2$，由上可得$m_2+a_1<=m_1+a_2$，因此有$s_{12}<=s_{21}$

4. 由此使用归纳法可知，贪心地将任务$[a,m]$当中$m-a$较大即$a-m$较小的排在前面进行即可

性能优化

• 无

复杂度分析

• 设任务个数为$n$，则有
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(1)$

代码

###python3

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[0] - x[1])
        ans = 0
        cur = 0
        for a, m in tasks:
            if cur < m:
                ans += m - cur
                cur = m
            cur -= a
        return ans

逆向思维

从结果状态反推：$初始能量=总消耗能量+剩余能量$ 在剩余能量为$0$时的初始能量最优

• 执行用时： 180 ms , 在所有 Python3 提交中击败了 80.65% 的用户
• 内存消耗： 42.5 MB , 在所有 Python3 提交中击败了 81.72% 的用户
• 通过测试用例： 42 / 42

代码

###python3

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1] - x[0])
        ans = 0
        for a, m in tasks:
            ans = ans + a if ans + a > m else m
        return ans

纯例子讲解帮助不太明白的人感受到其中的道理；

例1：【5，5】【5，7】

定义：minimum-actual越小的人称为越老实的人；反之，称为装逼人。
讲解： 显然【5，5】是个老实人，【5，7】是个装逼人。老实人很实在，最后剩下5给他，他就会欣然接受，不需要额外的需求，但是装逼人不一样，他明明只要5，确装逼说自己要7，这个时候怎么办呢，拿什么东西来装逼呢，只能借一下老实人的来装一下逼！

我们明白，这个答案显然是10，装逼人【5，7】可以拿老实人的5给自己来装逼，所以在不改变结果的情况下他可以乱叫6，7，8，9，10，这些情况下答案都不会改变，一旦装逼人叫了【5，11】，就会发现老实人借给他的也不够他装逼了，无可奈何，我们只能给他分配额外资源让他装逼。

一旦相通这个之后，我们解题思路变成了：倒着安排，先把大量“老实人”放在前面把需求数字垫起来，这样后面的装逼人能装更大的逼，例2有两个老实人【5，5】【5，5】，装逼人就能叫道【5，15】，只要老实人还能借，他就还能装

下面的例子是举例让大家理解装逼程度一致，起始先后顺序是一样的
例3：【1，3】【3，5】 他们的老实程度一致 结果： 3（给第一个装逼） + 3（因为3+3>5） = 6 = 5(给第二个先装逼) + 1（5+ 1 > 3,够装逼了）

例4： 【1，4】【3，5】
大家自己思考一下这个就明白结果了，结果放在评论区，希望大家都能理解，喜欢的或者觉得有趣的不妨点个赞！！！！谢谢你们！

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {//把握额外报的这部分如何让其无损
        sort(tasks.begin(), tasks.end(), [&](vector<int> &a, vector<int> &b){
            return a[1] - a[0] < b[1] - b[0];
        });

        int result = 0;

        for (const auto &task: tasks){
            result = max(result + task[0], task[1]);
        }

        return result;
    }
};

Most of the time when you copy a file on Linux, you reach for cp. It walks the filesystem, respects permissions, and works on individual files. But when you need to copy an entire disk, write an ISO image to a USB stick, or create a byte-for-byte backup of a partition, the filesystem view is not enough. For that, Linux ships with dd, a tool that copies raw data block by block between any two files or devices.

This guide explains how to use dd safely to write ISO images, clone disks, back up partitions, create test files, and benchmark storage performance.

dd Syntax #

The general form of the dd command is:

dd if=INPUT of=OUTPUT [OPTIONS]

The two key operands are if (input file) and of (output file). Either one can be a regular file, a block device such as /dev/sda, or even /dev/zero and /dev/urandom. Options control the block size, how many blocks to copy, and what conversions to apply.

Writing an ISO Image to a USB Drive #

The most common use for dd is flashing a Linux ISO to a USB drive so you can boot and install from it. First, identify the USB device with lsblk or sudo fdisk -l:

lsblk

NAME MAJ:MIN RM SIZE RO TYPE MOUNTPOINTS
sda 8:0 0 465.8G 0 disk
├─sda1 8:1 0 512M 0 part /boot/efi
└─sda2 8:2 0 465.3G 0 part /
sdb 8:16 1 14.5G 0 disk
└─sdb1 8:17 1 14.5G 0 part

Here sda is the system disk and sdb is the USB drive. Make sure the USB is unmounted before writing to it:

sudo umount /dev/sdb1

Then write the ISO image:

sudo dd if=ubuntu-24.04-desktop-amd64.iso of=/dev/sdb bs=4M status=progress oflag=sync

Notice that the output target is the whole disk (/dev/sdb), not a partition (/dev/sdb1). Writing an ISO to a partition would leave the USB unbootable. The options do the following:

• bs=4M - Read and write 4 MB at a time, which is much faster than the 512-byte default.
• status=progress - Print a live progress indicator so you can see how much has been written.
• oflag=sync - Flush every write to the device, so the final byte count reflects data actually on disk.

When dd finishes, run sync once more to make sure all buffered writes hit the USB stick before you remove it:

sync

For alternative methods and distro-specific tips, see the guide on how to create a bootable Linux USB drive .

Cloning a Whole Disk #

To make an exact block-level copy of one disk onto another, point if= and of= at two different block devices:

sudo dd if=/dev/sda of=/dev/sdb bs=64K conv=noerror,sync status=progress

The destination disk must be at least as large as the source. Anything already on it is overwritten. The conversion flags handle read errors gracefully:

• conv=noerror - Keep going when a read error occurs instead of aborting.
• conv=sync - Pad short reads with zeros so the output stays aligned with the source.

Clone offline whenever possible. Cloning a disk that is actively being written to produces an inconsistent copy, especially for databases and journaling filesystems.

Backing Up a Partition to an Image File #

dd can also write a partition or whole disk to a regular file. That file becomes a bit-for-bit image you can restore later:

sudo dd if=/dev/sda1 of=/backup/sda1.img bs=4M status=progress

To save space, pipe the output through gzip:

sudo dd if=/dev/sda1 bs=4M status=progress | gzip -c > /backup/sda1.img.gz

The compressed image is much smaller for filesystems that contain text or empty space, though the compression step adds CPU time.

To restore the image to a partition:

gunzip -c /backup/sda1.img.gz | sudo dd of=/dev/sda1 bs=4M status=progress

The target partition must be unmounted during restore, and it must be at least as large as the original.

Backing Up and Restoring the MBR #

The Master Boot Record sits in the first 512 bytes of a disk that uses a traditional BIOS partition table. You can back it up with dd:

sudo dd if=/dev/sda of=/backup/mbr.img bs=512 count=1

To restore the MBR, swap the input and output:

sudo dd if=/backup/mbr.img of=/dev/sda bs=512 count=1

On modern UEFI systems the partition table uses GPT instead of MBR, so this trick only applies to older BIOS installations. For GPT disks, use sgdisk --backup and sgdisk --load-backup from the gdisk package.

Creating an Empty File of a Specific Size #

dd is often used to create test files of a known size. The count option sets how many blocks to write, and bs sets the block size:

dd if=/dev/zero of=testfile bs=1M count=100

This creates a 100 MB file filled with zeros, useful for testing backups, simulating quota limits, or preparing a swap file. To create a file filled with random data instead, read from /dev/urandom:

dd if=/dev/urandom of=random.bin bs=1M count=10

Random data is slower to generate because the kernel has to produce the bytes, while /dev/zero is effectively free.

Creating a Swap File #

One practical use of the empty-file pattern is creating a swap file :

sudo dd if=/dev/zero of=/swapfile bs=1M count=2048 status=progress
sudo chmod 600 /swapfile
sudo mkswap /swapfile
sudo swapon /swapfile

The chmod 600 step keeps the swap file readable only by root, which is required by mkswap on most distros. After swapon, the 2 GB swap file is active immediately. Add an entry to /etc/fstab to make it permanent.

Wiping a Disk #

To destroy data on a disk before disposing of it or repurposing it, overwrite the entire device with zeros:

sudo dd if=/dev/zero of=/dev/sdb bs=4M status=progress

For a stronger wipe that makes recovery harder on traditional spinning disks, use random data:

sudo dd if=/dev/urandom of=/dev/sdb bs=4M status=progress

On SSDs, a dd wipe is not the right tool. SSDs remap blocks internally, so a full write does not guarantee every cell was overwritten. Use blkdiscard or the drive vendor’s secure-erase utility instead.

Benchmarking Disk Write Speed #

dd is a quick way to measure sustained write throughput. Write a 1 GB file of zeros and let dd report the rate:

dd if=/dev/zero of=tempfile bs=1M count=1024 oflag=direct

1024+0 records in
1024+0 records out
1073741824 bytes (1.1 GB, 1.0 GiB) copied, 3.1 s, 346 MB/s

The oflag=direct flag bypasses the page cache, so the number reflects actual disk speed rather than memory throughput. For a read benchmark, drop the caches first and then read the file back:

sudo sh -c "sync && echo 3 > /proc/sys/vm/drop_caches"
dd if=tempfile of=/dev/null bs=1M

Remove the test file when you are done:

rm tempfile

For more detailed I/O profiling, tools like fio and ioping produce more accurate, repeatable results.

Showing Progress on a Running dd #

If you started dd without status=progress, you can still ask it to print a status line by sending the USR1 signal to its process. From another terminal, run:

sudo kill -USR1 $(pidof dd)

dd will respond by printing the number of bytes copied so far and its current rate, then keep running.

Common Options #

A quick rundown of the options covered in this guide, plus a few more worth knowing:

• if=FILE - Input file or device.
• of=FILE - Output file or device.
• bs=N - Block size for both reads and writes (e.g., 4M for 4 MB).
• ibs=N / obs=N - Separate input and output block sizes.
• count=N - Number of input blocks to copy.
• skip=N - Skip N blocks at the start of the input.
• seek=N - Skip N blocks at the start of the output.
• status=progress - Print progress while copying.
• conv=noerror - Continue past read errors.
• conv=sync - Pad short reads with zeros to keep block alignment.
• oflag=direct - Bypass the kernel page cache on write.
• oflag=sync - Flush each write to the device before continuing.

Quick Reference #

Troubleshooting #

dd: failed to open ‘/dev/sdX’: Permission denied
Writing to a block device requires root privileges. Prefix the command with sudo. If you are already using sudo, double-check that the device path is correct and that the device is not exclusively held by another process.

dd: error writing ‘/dev/sdX’: No space left on device
The destination is smaller than the source. When cloning, the target disk or partition must be at least as large as the source. When writing an ISO, the USB drive must be larger than the ISO file.

The write is much slower than expected
The default block size of 512 bytes forces millions of tiny syscalls. Set bs=4M or bs=64K to speed things up. Also check whether other processes are doing heavy I/O on the same device.

The USB does not boot after writing the ISO
Verify that you wrote the image to the disk (/dev/sdb), not a partition (/dev/sdb1). Also confirm the ISO download with its SHA256 checksum; a truncated or corrupted download produces an unbootable stick.

dd: invalid number: ‘4M’
Older or minimal systems may ship a dd that does not accept the M, G, or K suffixes. On those systems, spell out the block size in bytes (bs=4194304 for 4 MB), or install GNU coreutils.

FAQ #

What does dd stand for?
The name comes from the IBM Job Control Language statement “Data Definition.” Because of how often the command is used to overwrite disks by mistake, many Linux users jokingly call it “disk destroyer.” Either way, the behavior is the same: it copies bytes from input to output without touching the filesystem layer.

Is dd faster than cp for copying large files?
For regular files on a normal filesystem, cp is usually just as fast and safer to use. dd only wins when you are copying raw devices, working with exact byte offsets, or deliberately limiting how much data is copied with count.

Can I use dd on an SSD without damaging it?
Reading and writing with dd is fine. The concern with SSDs is full-disk wipes: a single pass of zeros is enough to erase visible data, but repeated full-drive writes wear out the flash cells. For secure erase, use blkdiscard or the drive’s built-in secure-erase command.

How do I see how much data dd has copied?
Add status=progress to the command, or send the running process the USR1 signal with sudo kill -USR1 $(pidof dd). Both methods print the byte count and current throughput without interrupting the copy.

Why use bs=4M instead of the default?
The default block size of 512 bytes means dd issues a separate read and write for every 512 bytes of data. Larger block sizes such as 4 MB dramatically reduce syscall overhead and let the kernel fill the disk pipeline efficiently, often cutting copy times by a factor of ten.

Conclusion #

dd is one of the most direct tools in the Linux toolbox. It copies bytes, no more and no less, between any two files or devices. That power makes it indispensable for flashing installers, cloning disks, and building image backups, and the same power makes it unforgiving if you point it at the wrong target.

For related disk tools, see the guides on fdisk for partitioning and df for checking free space.

1.将int数组转换成一个字符串

2.定义一个新数组长度是字符串的长度

3.用chartAt方法取出每一个下标下的char转为数字塞进新数组里

给你一个正整数数组 nums ，请你返回一个数组 answer ，你需要将 nums 中每个整数进行数位分割后，按照 nums 中出现的 相同顺序 放入答案数组中。

对一个整数进行数位分割，指的是将整数各个数位按原本出现的顺序排列成数组。

• 比方说，整数 10921 ，分割它的各个数位得到 [1,0,9,2,1] 。

示例 1：

输入：nums = [13,25,83,77]
输出：[1,3,2,5,8,3,7,7]
解释：
- 分割 13 得到 [1,3] 。
- 分割 25 得到 [2,5] 。
- 分割 83 得到 [8,3] 。
- 分割 77 得到 [7,7] 。
answer = [1,3,2,5,8,3,7,7] 。answer 中的数字分割结果按照原数字在数组中的相同顺序排列。

示例 2：

输入：nums = [7,1,3,9]
输出：[7,1,3,9]
解释：nums 中每个整数的分割是它自己。
answer = [7,1,3,9] 。

提示：

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