阅读视图

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

How to Install LEMP Stack on Ubuntu 26.04

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

Task Command
Update package index sudo apt update
Install Nginx sudo apt install nginx
Install MySQL sudo apt install mysql-server
Install PHP-FPM sudo apt install php-fpm php-mysql
Secure MySQL sudo mysql_secure_installation
Restart PHP-FPM sudo systemctl restart php8.5-fpm
Reload Nginx sudo systemctl reload nginx
Test Nginx config sudo nginx -t
Allow HTTP/HTTPS sudo ufw allow 'Nginx Full'
PHP-FPM socket /run/php/php8.5-fpm.sock

Prerequisites

Before installing the stack, make sure you have:

Step 1: Install Nginx

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

Terminal
sudo apt update
sudo apt install nginx

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

Terminal
sudo systemctl status nginx

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

Terminal
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:

Terminal
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:

Terminal
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:

Terminal
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:

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

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

Terminal
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:

Terminal
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:

Terminal
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:

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

Create a new server block configuration:

Terminal
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:

nginx
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:

Terminal
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:

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

Test the configuration before reloading:

Terminal
sudo nginx -t

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

Terminal
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:

Terminal
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:

Terminal
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:

Terminal
sudo mysql

In the MySQL prompt, run:

sql
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;
Warning
The password above is a placeholder. Replace changeme with a strong value, and do not commit credentials to version control. Store secrets in environment variables or a .env file outside the repository.

Create a small connection test:

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

Add the following content:

php
<?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:

Terminal
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.

How to Install LAMP Stack on Ubuntu 26.04

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

Task Command
Update package index sudo apt update
Install Apache sudo apt install apache2
Install MySQL sudo apt install mysql-server
Install PHP with Apache sudo apt install php libapache2-mod-php php-mysql
Secure MySQL sudo mysql_secure_installation
Restart Apache sudo systemctl restart apache2
Test Apache config sudo apache2ctl configtest
Allow HTTP/HTTPS sudo ufw allow 'Apache Full'
Enable a site sudo a2ensite example.com
Disable default site sudo a2dissite 000-default

Prerequisites

Before installing the stack, make sure you have:

Step 1: Install Apache

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

Terminal
sudo apt update
sudo apt install apache2

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

Terminal
sudo systemctl status apache2

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

Terminal
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:

Terminal
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:

Terminal
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:

Terminal
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:

Terminal
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:

Terminal
php -v

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

Terminal
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:

Terminal
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:

Terminal
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:

Terminal
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:

apache
<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:

Terminal
sudo a2ensite example.com
sudo a2dissite 000-default

Make sure mod_rewrite is enabled if your application uses it:

Terminal
sudo a2enmod rewrite

Test the configuration before reloading Apache:

Terminal
sudo apache2ctl configtest

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

Terminal
sudo systemctl reload apache2

Step 5: Test the PHP Setup

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

Terminal
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:

Terminal
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:

Terminal
sudo mysql

In the MySQL prompt, run:

sql
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;
Warning
The password above is a placeholder. Replace changeme with a strong value, and do not commit credentials to version control. Store secrets in environment variables or a .env file outside the repository.

Create a small connection test:

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

Add the following content:

php
<?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:

Terminal
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] 是互补的,因为对于所有下标 inums[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 是偶数。

差分数组(Python/Java/C++/Go)

题目说,可以把 $\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] -= 2diff[l] += 1 合并为 diff[l] -= 1
  • diff[r+1] -= 1diff[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站@灵茶山艾府

借这个问题学习一下差分数组,O(n) 算法

假设 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]Anums[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;
    }
};

Nginx Location Blocks: Match Rules and Priority

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:

txt
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:

nginx
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:

nginx
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:

nginx
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

nginx
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

nginx
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

nginx
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

nginx
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

nginx
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:

Terminal
sudo nginx -t

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

Terminal
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

Modifier Meaning Priority
= Exact match 1 (highest)
^~ Preferential prefix match 2 (skips regex)
~ Case-sensitive regex 3 (in source order)
~* Case-insensitive regex 3 (in source order)
(none) Prefix match 4 (longest wins)
@name Named location Only reachable from directives

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

交换论证法(Python/Java/C++/C/Go/JS/Rust)

按照什么规则排序?

本文把 $\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+排序+贪心+数学+模拟

【儿须成名酒须醉】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}$
  1. 由此使用归纳法可知,贪心地将任务$[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;
    }
};

dd Command in Linux: Copy Disks, Partitions, and Files

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:

txt
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.

Warning
dd writes exactly what you tell it to write, to exactly the target you point it at. Pointing of= at the wrong disk will overwrite that disk without warning or confirmation. Always double-check the target device with lsblk or sudo fdisk -l before running a dd command.

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:

Terminal
lsblk
output
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:

Terminal
sudo umount /dev/sdb1

Then write the ISO image:

Terminal
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:

Terminal
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:

Terminal
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:

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

To save space, pipe the output through gzip:

Terminal
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:

Terminal
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:

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

To restore the MBR, swap the input and output:

Terminal
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:

Terminal
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:

Terminal
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 :

Terminal
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:

Terminal
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:

Terminal
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:

Terminal
dd if=/dev/zero of=tempfile bs=1M count=1024 oflag=direct
output
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:

Terminal
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:

Terminal
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:

Terminal
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

Command Description
sudo dd if=image.iso of=/dev/sdX bs=4M status=progress oflag=sync Write an ISO image to a USB drive
sudo dd if=/dev/sda of=/dev/sdb bs=64K conv=noerror,sync status=progress Clone one disk to another
sudo dd if=/dev/sda1 of=/backup/sda1.img bs=4M status=progress Back up a partition to an image file
sudo dd if=/dev/sda bs=4M status=progress | gzip -c > disk.img.gz Compressed disk image backup
sudo dd if=/dev/sda of=/backup/mbr.img bs=512 count=1 Back up the MBR
dd if=/dev/zero of=testfile bs=1M count=100 Create a 100 MB file of zeros
sudo dd if=/dev/zero of=/dev/sdX bs=4M status=progress Wipe a disk with zeros
dd if=/dev/zero of=tempfile bs=1M count=1024 oflag=direct Benchmark disk write speed
sudo kill -USR1 $(pidof dd) Ask a running dd for its progress

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.

每日一题-分割数组中数字的数位🟢

给你一个正整数数组 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

2553. 分割数组中数字的数位

解法

思路和算法

这道题要求将给定的正整数数组 $\textit{nums}$ 中的所有正整数按数位分割,保持数位顺序存入答案数组。需要首先遍历数组 $\textit{nums}$ 得到数位总数,然后将每个正整数按数位分割并存入答案数组。

首先遍历数组 $\textit{nums}$ 得到所有正整数的数位总数 $\textit{totalLength}$,然后创建长度为 $\textit{totalLength}$ 的答案数组 $\textit{answer}$,再次遍历数组 $\textit{nums}$,遍历过程中维护答案数组的当前下标 $\textit{index}$,对于每个正整数,执行如下操作。

  1. 用 $\textit{start}$ 表示当前正整数的数位填入答案数组的起始下标,$\textit{start} = \textit{index}$。

  2. 每次将 $\textit{num}$ 的最低位填入 $\textit{answer}[\textit{index}]$,然后将 $\textit{index}$ 的值增加 $1$,重复该操作直到 $\textit{num}$ 的所有位都填入答案数组。

  3. 当前正整数 $\textit{num}$ 填入答案数组的下标范围是 $[\textit{start}, \textit{index} - 1]$,为按照数位从低到高的顺序填入。为了和数组 $\textit{nums}$ 中的数位顺序保持一致,需要将答案数组的下标范围 $[\textit{start}, \textit{index} - 1]$ 的子数组翻转。

遍历结束之后,即可得到答案数组。

代码

###Java

class Solution {
    public int[] separateDigits(int[] nums) {
        int totalLength = 0;
        for (int num : nums) {
            totalLength += getLength(num);
        }
        int[] answer = new int[totalLength];
        int index = 0;
        for (int num : nums) {
            int start = index;
            int temp = num;
            while (temp != 0) {
                answer[index] = temp % 10;
                index++;
                temp /= 10;
            }
            reverse(answer, start, index - 1);
        }
        return answer;
    }

    public int getLength(int num) {
        int length = 0;
        while (num != 0) {
            length++;
            num /= 10;
        }
        return length;
    }

    public void reverse(int[] answer, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = answer[i];
            answer[i] = answer[j];
            answer[j] = temp;
        }
    }
}

###C#

public class Solution {
    public int[] SeparateDigits(int[] nums) {
        int totalLength = 0;
        foreach (int num in nums) {
            totalLength += GetLength(num);
        }
        int[] answer = new int[totalLength];
        int index = 0;
        foreach (int num in nums) {
            int start = index;
            int temp = num;
            while (temp != 0) {
                answer[index] = temp % 10;
                index++;
                temp /= 10;
            }
            Reverse(answer, start, index - 1);
        }
        return answer;
    }

    public int GetLength(int num) {
        int length = 0;
        while (num != 0) {
            length++;
            num /= 10;
        }
        return length;
    }

    public void Reverse(int[] answer, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = answer[i];
            answer[i] = answer[j];
            answer[j] = temp;
        }
    }
}

###C++

class Solution {
public:
    vector<int> separateDigits(vector<int>& nums) {
        int totalLength = 0;
        for (int num : nums) {
            totalLength += getLength(num);
        }
        vector<int> answer(totalLength);
        int index = 0;
        for (int num : nums) {
            int start = index;
            int temp = num;
            while (temp != 0) {
                answer[index] = temp % 10;
                index++;
                temp /= 10;
            }
            reverse(answer, start, index - 1);
        }
        return answer;
    }

    int getLength(int num) {
        int length = 0;
        while (num != 0) {
            length++;
            num /= 10;
        }
        return length;
    }

    void reverse(vector<int>& answer, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(answer[i], answer[j]);
        }
    }
};

###Python

class Solution:
    def separateDigits(self, nums: List[int]) -> List[int]:
        answer = []
        index = 0
        for num in nums:
            start = index
            temp = num
            while temp != 0:
                answer.append(temp % 10)
                index += 1
                temp //= 10
            self.reverse(answer, start, index - 1)
        return answer

    def getLength(self, num: int) -> int:
        length = 0
        while num != 0:
            length += 1
            num //= 10
        return length

    def reverse(self, answer: List[int], start: int, end: int) -> None:
        i, j = start, end
        while i < j:
            answer[i], answer[j] = answer[j], answer[i]
            i += 1
            j -= 1

###C

int getLength(int num) {
    int length = 0;
    while (num != 0) {
        length++;
        num /= 10;
    }
    return length;
}

void reverse(int* answer, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        int temp = answer[i];
        answer[i] = answer[j];
        answer[j] = temp;
    }
}

int* separateDigits(int* nums, int numsSize, int* returnSize) {
    int totalLength = 0;
    for (int i = 0; i < numsSize; i++) {
        totalLength += getLength(nums[i]);
    }
    int* answer = (int*) malloc(sizeof(int) * totalLength);
    *returnSize = totalLength;
    int index = 0;
    for (int i = 0; i < numsSize; i++) {
        int start = index;
        int temp = nums[i];
        while (temp != 0) {
            answer[index] = temp % 10;
            index++;
            temp /= 10;
        }
        reverse(answer, start, index - 1);
    }
    return answer;
}

###Go

func separateDigits(nums []int) []int {
    totalLength := 0
    for _, num := range nums {
        totalLength += getLength(num)
    }
    answer := make([]int, totalLength)
    index := 0
    for _, num := range nums {
        start := index
        temp := num
        for temp != 0 {
            answer[index] = temp % 10
            index++
            temp /= 10
        }
        reverse(answer, start, index - 1)
    }
    return answer
}

func getLength(num int) int {
    length := 0
    for num != 0 {
        length++
        num /= 10
    }
    return length
}

func reverse(answer []int, start int, end int) {
    for i, j := start, end; i < j; i, j = i + 1, j - 1 {
        answer[i], answer[j] = answer[j], answer[i]
    }
}

###JavaScript

var separateDigits = function(nums) {
    let totalLength = 0;
    for (let num of nums) {
        totalLength += getLength(num);
    }
    let answer = new Array(totalLength);
    let index = 0;
    for (let num of nums) {
        let start = index;
        let temp = num;
        while (temp !== 0) {
            answer[index] = temp % 10;
            index++;
            temp = Math.floor(temp / 10);
        }
        reverse(answer, start, index - 1);
    }
    return answer;
};

var getLength = function(num) {
    let length = 0;
    while (num !== 0) {
        length++;
        num = Math.floor(num / 10);
    }
    return length;
};

var reverse = function(answer, start, end) {
    for (let i = start, j = end; i < j; i++, j--) {
        let temp = answer[i];
        answer[i] = answer[j];
        answer[j] = temp;
    }
};

###TypeScript

function separateDigits(nums: number[]): number[] {
    let totalLength = 0;
    for (let num of nums) {
        totalLength += getLength(num);
    }
    let answer = new Array(totalLength);
    let index = 0;
    for (let num of nums) {
        let start = index;
        let temp = num;
        while (temp !== 0) {
            answer[index] = temp % 10;
            index++;
            temp = Math.floor(temp / 10);
        }
        reverse(answer, start, index - 1);
    }
    return answer;
};

function getLength(num: number): number {
    let length = 0;
    while (num !== 0) {
        length++;
        num = Math.floor(num / 10);
    }
    return length;
};

function reverse(answer: number[], start: number, end: number): void {
    for (let i = start, j = end; i < j; i++, j--) {
        let temp = answer[i];
        answer[i] = answer[j];
        answer[j] = temp;
    }
};

复杂度分析

  • 时间复杂度:$O(n \log_{10} m)$,其中 $n$ 是数组 $\textit{nums}$ 的长度,$m$ 是数组 $\textit{nums}$ 的最大元素。计算答案数组的长度与将数位填入答案数组的时间是 $O(n \log_{10} m)$。

  • 空间复杂度:$O(1)$。注意返回值不计入空间复杂度。

倒序插入

这个刚开始写的时候担心数组的长度和时间复杂度的原因,担心通过不了,结果没想过通过了。
我是用一个result数组来装将返回的分割数位值,考虑他们的长度,每一个元素的大小在10的五次方以内,分割之后100000共有六位,也就是最大是6,加上数组的长度最大是1000,于是我就把数组的大小取为6*10000=60000.
虽然我也知道浪费空间,但是我目前没有更好的方法,希望有大佬能够指点。

确定了返回数组了,然后就是然后把原始的整数拆分插入到结果数组中,后面我想到只要逐个不断求余就可以得到每一位数,后面我就在第一层遍历中添加一个循环得到整数的各个数位,但是提交的结果不符合要求,题目要求将数位按原本出现的顺序排列成数组,于是我就用一个数组作为辅助空间,将它反向添加,于是就得到了和题目意思相同的结果,辅助空间的大小就是一个整数拥有的各个位数的数量,由前面可以知道最大是6。

之后返回即可。

int* separateDigits(int* nums, int numsSize, int* returnSize){
    int *result=(int*)malloc(sizeof(int)*60000);
    int count=0;
    //遍历整个数组
    for(int i=0;i<numsSize;i++){
        int tmp=nums[i];
        int help[6];
        int tmpCount=0;
        //得到整数的各个数位,将他们储存在一个辅助数组中
        while(tmp){
            help[tmpCount++]=tmp%10;
            tmp=tmp/10;
        }
        //把数组中的元素倒序添加到结果数组中
        for(int j=tmpCount-1;j>=0;j--){
            result[count++]=help[j];
        }
    }
    *returnSize=count;
    return result;
}

两种方法:用字符串 / 不用字符串(Python/Java/C++/Go)

写法一:用字符串

把 $\textit{nums}[i]$ 转成字符串,即可从高到低遍历数位。

class Solution:
    def separateDigits(self, nums: List[int]) -> List[int]:
        return [int(ch) for x in nums for ch in str(x)]
class Solution {
    public int[] separateDigits(int[] nums) {
        List<Integer> digits = new ArrayList<>();
        for (int x : nums) {
            for (char ch : String.valueOf(x).toCharArray()) {
                digits.add(ch - '0');
            }
        }

        int m = digits.size();
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            ans[i] = digits.get(i);
        }
        return ans;
    }
}
class Solution {
public:
    vector<int> separateDigits(vector<int>& nums) {
        vector<int> ans;
        for (int x : nums) {
            for (char ch : to_string(x)) {
                ans.push_back(ch - '0');
            }
        }
        return ans;
    }
};
func separateDigits(nums []int) (ans []int) {
for _, x := range nums {
for _, ch := range strconv.Itoa(x) {
ans = append(ans, int(ch-'0'))
}
}
return
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(n\log U)$,其中 $n$ 是 $\textit{nums}$ 的长度,$U=\max(\textit{nums})$。
  • 空间复杂度:$\mathcal{O}(\log U)$。返回值不计入。

方法二:不用字符串

不断地把 $n$ 除以 $10$(下取整)直到 $0$,例如 $123\to 12\to 1\to 0$。在这个过程中的 $n\bmod 10$,即为每个数位。

这样做是从低到高遍历数位,和题目要求的顺序相反。

我们可以从右到左遍历 $\textit{nums}$,从低到高遍历 $\textit{nums}[i]$ 的数位。最后把遍历过的数位反转,即为答案。

class Solution:
    def separateDigits(self, nums: list[int]) -> list[int]:
        ans = []
        for x in reversed(nums):
            while x > 0:
                ans.append(x % 10)
                x //= 10
        ans.reverse()
        return ans
class Solution {
    public int[] separateDigits(int[] nums) {
        List<Integer> digits = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int x = nums[i]; x > 0; x /= 10) {
                digits.add(x % 10);
            }
        }

        int m = digits.size();
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            ans[i] = digits.get(m - 1 - i);
        }
        return ans;
    }
}
class Solution {
public:
    vector<int> separateDigits(vector<int>& nums) {
        vector<int> ans;
        for (int x : nums | views::reverse) {
            for (; x > 0; x /= 10) {
                ans.push_back(x % 10);
            }
        }
        ranges::reverse(ans);
        return ans;
    }
};
func separateDigits(nums []int) (ans []int) {
for _, x := range slices.Backward(nums) {
for ; x > 0; x /= 10 {
ans = append(ans, x%10)
}
}
slices.Reverse(ans)
return
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(n\log U)$,其中 $n$ 是 $\textit{nums}$ 的长度,$U=\max(\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站@灵茶山艾府

每日一题-达到末尾下标所需的最大跳跃次数🟡

给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target

你的初始位置在下标 0 。在一步操作中,你可以从下标 i 跳跃到任意满足下述条件的下标 j

  • 0 <= i < j < n
  • -target <= nums[j] - nums[i] <= target

返回到达下标 n - 1 处所需的 最大跳跃次数

如果无法到达下标 n - 1 ,返回 -1

 

示例 1:

输入:nums = [1,3,6,4,1,2], target = 2
输出:3
解释:要想以最大跳跃次数从下标 0 到下标 n - 1 ,可以按下述跳跃序列执行操作:
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 5 。 
可以证明,从 0 到 n - 1 的所有方案中,不存在比 3 步更长的跳跃序列。因此,答案是 3 。 

示例 2:

输入:nums = [1,3,6,4,1,2], target = 3
输出:5
解释:要想以最大跳跃次数从下标 0 到下标 n - 1 ,可以按下述跳跃序列执行操作:
- 从下标 0 跳跃到下标 1 。 
- 从下标 1 跳跃到下标 2 。 
- 从下标 2 跳跃到下标 3 。 
- 从下标 3 跳跃到下标 4 。 
- 从下标 4 跳跃到下标 5 。 
可以证明,从 0 到 n - 1 的所有方案中,不存在比 5 步更长的跳跃序列。因此,答案是 5 。 

示例 3:

输入:nums = [1,3,6,4,1,2], target = 0
输出:-1
解释:可以证明不存在从 0 到 n - 1 的跳跃序列。因此,答案是 -1 。 

 

提示:

  • 2 <= nums.length == n <= 1000
  • -109 <= nums[i] <= 109
  • 0 <= target <= 2 * 109

C++, 动态规划

思路

  1. f[i]表示从0到下标i的最大跳跃次数;
  2. f[0]=0, f[i]=f[j]+1, 可以从j跳过来;
class Solution {
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> f(n, -1);
        f[0] = 0;
        /* 开始递推 */
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (f[j] != -1 && abs(nums[i] - nums[j]) <= target) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        return f[n - 1];
    }
};
class Solution:
    def maximumJumps(self, nums: List[int], target: int) -> int:
        n = len(nums)
        f = [-1] * n
        f[0] = 0
        for j in range(1, n):
            for i in range(j):
                if f[i] != -1 and abs(nums[i] - nums[j]) <= target:
                    f[j] = max(f[j], f[i] + 1)
        return f[-1]
❌