阅读视图

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

每日一题-两个字符串的最小ASCII删除和🟡

给定两个字符串s1 和 s2,返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 

 

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时,两个字符串相等,115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let",
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时,两个字符串都等于 "let",结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet",我们会得到 433 或 417 的结果,比答案更大。

 

提示:

  • 0 <= s1.length, s2.length <= 1000
  • s1 和 s2 由小写英文字母组成

uni-app实现本地MQTT连接

最近接到安卓端的需求,要求使用MQTT连接实现设备信息的收发。

可能有兄弟不太清楚 MQTT协议 是什么,简单地说它是一种轻量级的、基于发布/订阅模式的消息传输协议,广泛用于物联网(IoT)领域。

常见的操作就是连接后有N个设备订阅了主题A,这时候任意一台设备对主题A发布了一条信息,则当前N个设备都能收到这条消息。

至于其他的也不用知道的太清楚,反正知道一般是这么玩的就行。

假如你想知道的更为详细,可以询问 Trae

image.png

需求

  1. 实现MQTT连接
  2. 实现主题(Topic)订阅
  3. 能够发送消息
  4. 能够接收消息

实现方案

首先是安装 mqtt.js 插件和 uuid.js 插件。

npm i mqtt@3.0.0 uuid

注意: 这里一定要安装 mqtt v3.0 版本,我之前装了一个 v5.x 版本,有比较大的 API 改动。项目上时间紧张,遂没有再尝试。(有兴趣的朋友可以考虑用最新版实现)

uuid 只是起到生成 连接ID 和 消息ID 的作用,这里也可以直接使用时间戳的方式,但是为了保证不重复,这里便不再更换了。

// mqttClient.js 对 MQTT 的简单封装
let client = null;
/**
 * 初始化 MQTT 连接
 * @param {Object} options
 * @param {string} options.host - 服务器地址(不带协议)
 * @param {number} options.port - 端口(通常 WebSocket 是 8083、8084 或 443)
 * @param {string} options.clientId - 客户端 ID(建议唯一)
 * @param {string} [options.username] - 用户名
 * @param {string} [options.password] - 密码
 * @param {boolean} [options.useWss=false] - 是否使用 wss(HTTPS)
 */
export function initMqtt(options) {
const {
host,
port,
clientId,
username = '',
password = '',
useWss = false
} = options;

// 根据平台选择协议(App 和 H5 用 ws/wss,小程序用 wxs/wss)
let protocol = 'ws';
if (useWss) protocol = 'wss';

// #ifdef MP-WEIXIN
protocol = useWss ? 'wxs' : 'wxs';
// #endif

const url = `${protocol}://${host}:${port}/mqtt`; // 注意:路径可能是 / 或 /mqtt,根据你的 broker 配置

const connectOptions = {
clientId: clientId,
username: username,
password: password,
keepalive: 60, // 心跳间隔(秒)
reconnectPeriod: 5000, // 自动重连间隔(毫秒)
connectTimeout: 10000, // 连接超时
clean: true // 是否清除会话
};

// 引入 mqtt(必须用 min 版本,否则小程序报错)
const mqtt = require('mqtt/dist/mqtt.min.js');

client = mqtt.connect(url, connectOptions);

// 监听连接事件
client.on('connect', () => {
console.log('MQTT 连接成功');
});

client.on('reconnect', () => {
console.log('MQTT 正在重连...');
});

client.on('error', (err) => {
console.error('MQTT 连接错误:', err);
});

client.on('close', () => {
console.log('MQTT 连接已关闭');
});

return client;
}

/**
 * 订阅主题
 * @param {string} topic
 * @param {Function} callback - (topic, message) => {}
 */
export function subscribe(topic, callback) {
if (!client) {
console.warn('MQTT 客户端未初始化');
return;
}

client.subscribe(topic, (err) => {
if (!err) {
console.log(`订阅主题成功: ${topic}`);
} else {
console.error('订阅失败:', err);
}
});

// 监听消息(全局监听,需配合 topic 过滤)
client.on('message', (receivedTopic, message) => {
// if (receivedTopic === topic) {
try {
// 尝试解析 JSON
const payload = JSON.parse(message.toString());
callback(receivedTopic, payload);
} catch (e) {
// 非 JSON 消息
callback(receivedTopic, message.toString());
}
// }
});
}

/**
 * 发布消息
 * @param {string} topic
 * @param {string|object} message
 */
export function publish(topic, message) {
if (!client) {
console.warn('MQTT 客户端未初始化');
return;
}

const payload = typeof message === 'object' ? JSON.stringify(message) : message;
client.publish(topic, payload, {
qos: 1
}, (err) => {
if (err) {
console.error('发布失败:', err);
} else {
console.log(`发布成功: ${topic}`, payload);
}
});
}

/**
 * 断开连接
 */
export function disconnect() {
if (client) {
client.end(true); // true 表示强制断开
client = null;
console.log('MQTT 已断开');
}
}

我让 Trae 基于网上的封装简单进行了修改,生成了上述封装Js文件。

注意:在监听消息的部分,如果你的 Topic 是固定的,则请将 if (receivedTopic === topic)注释打开,如果不是,则注释掉,后续有详解。

现在进入到 page/index/index.vue 文件中

import {initMqtt, subscribe, publish, disconnect} from './mqttClient.js';
export default {
    data() {
        return {
            host: 'broker.emqx.io',
            messages: []
        }
    },
    mounted() {
        this.connect()
    },
    beforeDestroy() {
        this.disconnect()
    },
    methods: {
        // 连接
        connect() {
            const uuid = uuidv4();
            const client = initMqtt({
                host: this.host,
                port: 8083,
                clientId: uuid,
                username: '',
                password: '',
                useWss: false // 如果是 HTTPS/WSS,设为 true
            });
            if (client) {
                this.subscribeTopic();
            }
        },
        // 订阅 test/topic 主题
        subscribeTopic() {
            subscribe('test/topic', (topic, message) => {
                // 接收到的消息
                const msg = JSON.stringify(message);
                this.messages.unshift(msg);
            });
        },
        // 订阅 带通配符 的主题
        subscribeTopics() {
            subscribe('+/topic', (topic, message) => {
                // 接收到的消息
                const msg = JSON.stringify(message);
                this.messages.unshift(msg);
            });
        },
        // 发送消息到 test/topic 主题
        publishMessage() {
            publish('test/topic', {
                name: 'uni-app',
                time: new Date().toISOString(),
                msg: '测试信息'
            });
        },
        disconnect() {
            disconnect();
        }
    }
}

注意:在卸载页面的时候建议将 MQTT连接 断开,或者在 uni-app 中使用也可以使用 unload 方法断开连接。

另外订阅主题可以采用常规的,确定性的 Topic 主题名称,也可以采用 通配符(+) 的主题名称。

Trae还提醒我一定要注意,假如你的 Topic 为:

123/456/report 则你的通配符主题名称为 +/+/report

假如你的 Topic 为:

/123/456/report 则你的通配符主题名称为 +/+/+/report,因为他的第一位是 空字符串

结论

在开发 IoT 设备时这个协议用的比较广泛,如果不接触这个方面一般不会用上这个。

另外 MQTT 本身自带心跳自动重连机制,大致上相当于 WebSocket,这个部分一般不需要做特殊开发。

GDAL 实现空间分析

^ 关注我,带你一起学GIS ^

前言

空间分析基于空间关系,常见的如叠加、求差、取反等。在GIS开发中,空间分析作为其灵魂支柱,具有重要意义,是每一个GISer都必须要掌握的技能。

在之前的文章中讲了如何使用GDAL或者ogr2ogr工具将txt以及csv文本数据转换为Shp格式,本篇教程在之前一系列文章的基础上讲解如何使用GDAL 实现空间分析

如果你还没有看过,建议从以上内容开始。

1. 开发环境

本文使用如下开发环境,以供参考。

时间:2025年

系统:Windows 11

Python:3.11.7

GDAL:3.11.1

2. 空间分析

定义一个方法SpatialAnalysis用于判断要素间空间关系,该方法接收两个参数,其中sourcePath指向源数据路径,resultPath指向结果文件路径。

"""说明:GDAL 空间分析操作参数:    -sourcePath:Shp 数据路径    -resultPath:生成结果数据路径"""def SpatialAnalysis(sourcePath,resultPath):

接着是基础的常规操作,添加数据驱动,获取数据源,获取目标图层。

# 检查文件是否存在checkFilePath(sourcePath)# 添加数据驱动shpDriver = ogr.GetDriverByName("ESRI Shapefile")# 获取数据源shpDs = shpDriver.Open(sourcePath)# 获取图层shpLayer = shpDs.GetLayer(0)srs = shpLayer.GetSpatialRef()geomType = shpLayer.GetGeomType()

方法checkFilePath用于检查文件路径是否正常,接受一个路径参数。

"""说明:检查文件路径是否正常参数:    -filePath:文件数据路径"""def checkFilePath(filePath):    if os.path.exists(filePath):        print("文件数据路径存在")    else:        print("文件数据路径不存在,请检查!")

本文基于以下数据进行空间分析操作。对涉及面的操作分别获取面0和面1两个要素。GDAL中的几何处理操作,如叠加、缓冲、求差等均返回一个新的几何对象。

"""获取第一个图层要素"""# feature = shpLayer.GetNextFeature()# 根据FId获取指定要素feature1 = shpLayer.GetFeature(0)print(f"n面状要素~~~~~Id:{feature1.GetField('Id')}n")# 获取要素IdfeatId1 = feature1.GetField("Id")# 获取几何要素geom1 = feature1.GetGeometryRef()# print(f"面状几何:{geom1}")"""    获取第二个要素"""feature2 = shpLayer.GetFeature(1)geom2 = feature2.GetGeometryRef()featId2 = feature2.GetField("Id")

3. 空间叠加

Geometry对象上具有一个方法Intersection用于空间叠加操作,该方法接收另一个几何对象,并返回一个新的Geometry对象。

"""    空间操作之【叠加】"""resultGeom = geom1.Intersection(geom2)# print(f"面要素【{featId1}】与 面要素【{featId2}】相交结果:{resultGeom}")

如下面0和面1相交结果为图中高亮部分。

4. 空间缓冲

Geometry对象上具有一个方法Buffer用于空间缓冲区生成,该方法接收另一个几何对象,并返回一个新的Geometry对象。

"""    空间操作之【缓冲】"""resultGeom = geom1.Buffer(1)# print(f"面要素【{featId1}】缓冲结果:{resultGeom}")

如下面0缓冲结果为图中高亮部分。

如下线段缓冲结果为图中高亮部分。

如下点缓冲结果为图中高亮部分。

5. 空间联合

Geometry对象上具有一个方法Union用于合并几何对象,该方法接收另一个几何对象,并返回一个新的Geometry对象。

"""    空间操作之【联合】"""resultGeom = geom1.Union(geom2)# print(f"面要素【{featId1}】联合结果:{resultGeom}")

如下面0和面1联合结果为图中高亮部分。

6. 空间求差

Geometry对象上具有一个方法Difference用于求取目标几何对象差集,该方法接收另一个几何对象,并返回一个新的Geometry对象。

"""    空间操作之【求差】"""resultGeom = geom1.Difference(geom2)# print(f"面要素【{featId1}】联合结果:{resultGeom}")

如下面0和面1求差结果为图中高亮部分。

7. 对称差集

Geometry对象上具有一个方法SymmetricDifference用于几何对象交集取反操作,该方法接收另一个几何对象,并返回一个新的Geometry对象。

"""    空间操作之【求对称差集】"""resultGeom = geom1.SymmetricDifference(geom2)print(f"面要素【{featId1}】联合结果:{resultGeom}")

如下面0和面1求对称差集结果为图中高亮部分。

还有一些几何操作,如求等、求距离等内容本教程并未涉及,留给感兴趣的读者自行实践。

8. 创建新图层

几何运算完成之后,需要将分析结果保存到新的Shp图层。通过数据驱动方法CreateDataSource创建Shp数据源,再使用数据源方法CreateLayer创建图层即可。

"""    创建新图层"""targetDs = shpDriver.CreateDataSource(resultPath)targetLayer = targetDs.CreateLayer("result_layer",srs,ogr.wkbPolygon)featureDefn = shpLayer.GetLayerDefn()tarFeat = ogr.Feature(featureDefn)fieldCount = featureDefn.GetFieldCount()tarFeat.SetGeometry(resultGeom)for i in range(fieldCount):    fieldDefn = featureDefn.GetFieldDefn(i)    name = fieldDefn.GetName()    value = feature1.GetField(i)    print(f"字段名称:{name},字段值:{value}")    # tarFeat.SetField(i,value)    tarFeat.SetField(name,value)targetLayer.CreateFeature(tarFeat)

9. 注意事项

windows开发环境中同时安装GDALPostGIS,其中投影库PROJ的环境变量指向PostGIS的安装路径,在运行GDAL程序时,涉及到要素、几何与投影操作时会导致异常。具体意思为GDAL不支持PostGIS插件中的投影库版本,需要更换投影库或者升级版本。

RuntimeError: PROJ: proj_identify: D:Program FilesPostgreSQL13sharecontribpostgis-3.5projproj.db contains DATABASE.LAYOUT.VERSION.MINOR = 2 whereas a number >= 5 is expected. It comes from another PROJ installation.

解决办法为修改PROJ的环境变量到GDAL支持的版本或者在GDAL程序开头添加以下代码:

os.environ['PROJ_LIB'] = r'D:\Programs\Python\Python311\Libsite-packages\osgeo\data\proj'

视频效果

GDAL 实现空间分析操作

OpenLayers示例数据下载,请在公众号后台回复:ol数据

全国信息化工程师-GIS 应用水平考试资料,请在公众号后台回复:GIS考试

GIS之路 公众号已经接入了智能 助手,可以在对话框进行提问,也可以直接搜索历史文章进行查看。

都看到这了,不要忘记点赞、收藏 + 关注

本号不定时更新有关 GIS开发 相关内容,欢迎关注 


    

GeoTools 开发合集(全)

OpenLayers 开发合集

GDAL 实现空间分析操作

GDAL 空间关系解析

GDAL 实现数据空间查询

GDAL 实现数据属性查询

GDAL 实现创建几何对象

GDAL 实现自定义数据坐标系

GDAL 实现矢量数据读写

GDAL 数据类型大全

GDAL 实现 GIS 数据读取转换(全)

正难则反:计算最多保留的 ASCII 之和(Python/Java/C++/Go)

用 $s_1$ 和 $s_2$ 的 ASCII 值之和,减去保留的 ASCII 之和的最大值,就是删除字符的 ASCII 值之和的最小值。

计算最多保留的 ASCII 之和,方法和 1143. 最长公共子序列 一样:

  • 1143 题,$s_1[i] = s_2[j]$ 时,都保留,最长公共子序列长度增加 $1$。
  • 本题,$s_1[i] = s_2[j]$ 时,都保留,保留的 ASCII 之和增加 $\text{ASCII}(s_1[i])\cdot 2$。

所以只需把 1143 题的 $+1$ 改成 $+\text{ASCII}(s_1[i])\cdot 2$。

也可以改成 $+\text{ASCII}(s_1[i])$,最后返回时再乘以 $2$。

###py

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n, m = len(s1), len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(s1):
            for j, y in enumerate(s2):
                if x == y:
                    f[i + 1][j + 1] = f[i][j] + ord(x)
                else:
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j])
        return total - f[n][m] * 2

###java

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int total = s1.chars().sum() + s2.chars().sum();

        char[] s = s1.toCharArray();
        char[] t = s2.toCharArray();
        int n = s.length;
        int m = t.length;

        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i] == t[j]) {
                    f[i + 1][j + 1] = f[i][j] + s[i];
                } else {
                    f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]);
                }
            }
        }
        return total - f[n][m] * 2;
    }
}

###cpp

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        int total = reduce(s1.begin(), s1.end(), 0) + reduce(s2.begin(), s2.end(), 0);

        vector f(n + 1, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s1[i] == s2[j]) {
                    f[i + 1][j + 1] = f[i][j] + s1[i];
                } else {
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j]);
                }
            }
        }
        return total - f[n][m] * 2;
    }
};

###go

func minimumDeleteSum(s1, s2 string) int {
n, m := len(s1), len(s2)
total := 0
for _, c := range s1 {
total += int(c)
}
for _, c := range s2 {
total += int(c)
}

f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for i, x := range s1 {
for j, y := range s2 {
if x == y {
f[i+1][j+1] = f[i][j] + int(x)
} else {
f[i+1][j+1] = max(f[i][j+1], f[i+1][j])
}
}
}
return total - f[n][m]*2
}

空间优化:

###py

# 更快的写法见【Python3 手写 max】
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [0] * (m + 1)
        for x in s1:
            ord_x = ord(x)
            pre = 0  # f[0]
            for j, y in enumerate(s2):
                tmp = f[j + 1]
                if x == y:
                    f[j + 1] = pre + ord_x
                else:
                    f[j + 1] = max(f[j + 1], f[j])
                pre = tmp
        return total - f[m] * 2

###py

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [0] * (m + 1)
        for x in s1:
            ord_x = ord(x)
            pre = 0  # f[0]
            for j, y in enumerate(s2):
                tmp = f[j + 1]
                if x == y:
                    f[j + 1] = pre + ord_x
                elif f[j] > f[j + 1]:
                    f[j + 1] = f[j]
                pre = tmp
        return total - f[m] * 2

###java

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int total = s1.chars().sum() + s2.chars().sum();

        char[] s = s1.toCharArray();
        char[] t = s2.toCharArray();
        int m = t.length;

        int[] f = new int[m + 1];
        for (char x : s) {
            int pre = 0; // f[0]
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                if (x == t[j]) {
                    f[j + 1] = pre + x;
                } else {
                    f[j + 1] = Math.max(f[j + 1], f[j]);
                }
                pre = tmp;
            }
        }
        return total - f[m] * 2;
    }
}

###cpp

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s2.size();
        int total = reduce(s1.begin(), s1.end(), 0) + reduce(s2.begin(), s2.end(), 0);

        vector<int> f(m + 1);
        for (char x : s1) {
            int pre = 0; // f[0]
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                if (x == s2[j]) {
                    f[j + 1] = pre + x;
                } else {
                    f[j + 1] = max(f[j + 1], f[j]);
                }
                pre = tmp;
            }
        }
        return total - f[m] * 2;
    }
};

###go

func minimumDeleteSum(s1, s2 string) int {
m := len(s2)
total := 0
for _, c := range s1 {
total += int(c)
}
for _, c := range s2 {
total += int(c)
}

f := make([]int, m+1)
for _, x := range s1 {
pre := 0 // f[0]
for j, y := range s2 {
tmp := f[j+1]
if x == y {
f[j+1] = pre + int(x)
} else {
f[j+1] = max(f[j+1], f[j])
}
pre = tmp
}
}
return total - f[m]*2
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(nm)$,其中 $n$ 是 $s_1$ 的长度,$m$ 是 $s_2$ 的长度。
  • 空间复杂度:$\mathcal{O}(m)$。

专题训练

见下面动态规划题单的「§4.1 最长公共子序列(LCS)」。

分类题单

如何科学刷题?

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

最长公共子序列 (LCS):「模版」&「输出」

如果想要查看作者更多文章,可以点击此处!!!🔥🔥🔥

为了本篇文章更好的观感,可以点击此处!!!

1143. 最长公共子序列

583. 两个字符串的删除操作

712. 两个字符串的最小ASCII删除和


最长递增子序列」针对一个字符串,求出其最长递增子序列 (废话文学!!) 详细介绍可见 动态规划设计:最长递增子序列

最长重复子数组」针对两个数组,求出其最长重复子数组 (子数组必须要连着) 详细介绍可见 最长重复子数组

而我们今天要介绍的是「最长公共子序列」,它是针对两个字符串,求出其最长公共子序列 (子序列可以不用连着)

模版归纳

首先结合题目 最长公共子序列,归纳总结出「最长公共子序列」问题的模版

毫无疑问这种类型的题目需要使用「DP」去解决!!这里给出一个例子 s1 = "abcde", s2 = "ace" ,下面所有分析都围绕该样例展开

先给出 dp[][] 数组的定义:dp[i][j] 表示子串 s1[0..i]s2[0..j] 最长公共子序列的长度

那么「状态转移方程」是什么呢?

  • 如果 s1[i] = s2[j]dp[i][j] = dp[i - 1][j - 1] + 1
  • 如果 s1[i] != s2[j]dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])

为什么就是这样转移的呢?直接看下图:

5.svg

那么「base case」是什么呢?

6.svg

如上图粉色标记出来的就是 base case。橙色标记出来的是相等的情况,其余是不等的情况

完整模版

###java

public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            char c1 = text1.charAt(i - 1);
            char c2 = text2.charAt(j - 1);
            // 相等情况
            if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1;
            // 不等情况
            else dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    return dp[n1][n2];
}

✨ 如何输出最长公共子序列

「最长公共子序列」问题基本都是要求返回一个最值即可,但是有时候面试官喜欢不按常理出牌,让你输出最长公共子序列

我们可以通过构造出来的二维 dp 数组来得到最长公共子序列。如下图所示,从最后一个点开始往左上角的方向遍历

7.svg

如果 s1[i] = s2[j],那么当前字符肯定在最长公共子序列中;否在我们就向左或者向上遍历

至于选择「向左」还是「向上」的方向,这就要和构造 dp 的时候联系起来。我们是挑了一个最大值,所以遍历的方向也是谁大就往谁的方向遍历

###java

public int longestCommonSubsequence(String text1, String text2) {
    
    // 同上面的模版
    
    /* ------- print ------- */
    int i = n1, j = n2;
    StringBuffer sb = new StringBuffer();
    while (i > 0 && j > 0) {
        char c1 = text1.charAt(i - 1);
        char c2 = text2.charAt(j - 1);
        if (c1 == c2) {
            sb.append(c1);
            // 向左上角遍历
            i--; j--;
        } else {
            // 向上
            if (dp[i - 1][j] > dp[i][j - 1]) i--;
            // 向左
            else j--;
        }
    }
    System.out.println(sb.reverse());
    /* ------- end ------- */
    return dp[n1][n2];
}

两个字符串的最小ASCII删除和

题目详情可见 两个字符串的最小ASCII删除和

其实这个题目的底层也是「最长公共子序列」,只是问法稍微变化了一点

「需要被删除的字符 = 原字符串 - 最长公共子序列」

结合这个题目我们把 dp[][] 数组的定义稍微改改:dp[i][j] 表示子串 s1[0..i]s2[0..j] 最小 ASCII 删除和

那么「状态转移方程」是什么呢?(有点逆过程的意思!!!)

  • 如果 s1[i] = s2[j]dp[i][j] = dp[i - 1][j - 1] (不需要被删除)
  • 如果 s1[i] != s2[j]dp[i][j] = Math.min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j])

那么「base case」是什么呢?

8.svg

如上图粉色标记出来的就是 base case,e 表示 e 的 ASCII 值

###java

public int minimumDeleteSum(String s1, String s2) {
    int n1 = s1.length(), n2 = s2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    // base case
    for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
    for (int i = 1; i <= n2; i++) dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            int c1 = s1.charAt(i - 1);
            int c2 = s2.charAt(j - 1);
            // 相等情况
            if (c1 == c2) dp[i][j] = dp[i - 1][j - 1];
            // 不等情况
            else dp[i][j] = Math.min(dp[i][j - 1] + c2, dp[i - 1][j] + c1);
        }
    }
    return dp[n1][n2];
}

LCS的dp解法转化而来 C++

首先给出LCS的模板解法:

int longestCommonSubsequence(string text1, string text2)
{
    int LCS[text1.size() + 1][text2.size() + 1];
    memset(LCS,0, sizeof(LCS));

    for (int i = 1; i <= text1.size(); ++i)
        for (int j = 1; j <= text2.size(); ++j)
        {
            if(text1[i - 1] == text2[j - 1])
                LCS[i][j] = LCS[i - 1][j - 1] + 1;
            else
                LCS[i][j] = max(LCS[i - 1][j],LCS[i][j - 1]);
        }
    return LCS[text1.size()][text2.size()];
}

那么如何改造这个模板来让他适应我们的问题呢?
因为在求LCS的时候我们是按照构造一个dp[i][j]表示以str1的第i项为结尾,str2的第j项为结尾,那么就会有:(LCS(i,j) <=> dp[i][j])

--------------------------------------
 * if(str1.n == str2.m):
 *      LCS(n,m) = LCS(n - 1,m - 1) + 1
 * else
 *      LCS(n,m) = max{LCS(n - 1,m),LCS(n,m - 1)}
--------------------------------------

所以我们就会有一种想法,对这个LCS求解的dp过程在进行一次约数,肯定可以得到我们的目标LCS

int minimumDeleteSum(string s1, string s2)
{
    int len1 = s1.length();
    int len2 = s2.length();

    int dp[len1 + 1][len2 + 1];
    memset(dp,0, sizeof(dp));

    for (int i = 1; i <= len1; ++i)
        for (int j = 1; j <= len2; ++j)
        {
            if(s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + s1[i - 1];
            else
                dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
        }

    int sum = 0;
    for (int i = 0; i < len1; ++i)
        sum += s1[i];
    for (int i = 0; i < len2; ++i)
        sum += s2[i];
    return sum - 2 * dp[len1][len2];
}

别忘了最后返回的值是两个string的ASCII和减去两个LCS的ASCII的sum哦

JavaScript 如何准确判断数据类型?5 种方法深度对比

在写js的时候,很容易因为数据类型没判断好而出错,比如这样的代码:

function calculate(a, b) {
    return a + b;
}
// 我以为是 10 + 20 = 30
calculate(10, 20); // 结果 30 对的 

// 实际上用户输入的是字符串和数字
calculate("10", 20); // 结果为 "1020" 

所以为了避免这种情况的出现,我们还是要去判断好数据类型。

JavaScript中,有几种方式来判断数据类型,以下是常用的方法:

1. typeof 操作符

最常用的类型判断方法,但有一些局限性:

typeof 42;           // "number"
typeof "hello";      // "string"
typeof true;         // "boolean"
typeof undefined;    // "undefined"
typeof null;         // "object" (历史遗留问题)
typeof {};           // "object"
typeof [];           // "object"
typeof function(){}; // "function"
typeof Symbol();     // "symbol"
typeof 42n;          // "bigint"

局限性

  • 无法区分数组、对象和 null
  • 函数返回 function
  • typeof 适合判断基本类型,但遇到对象类型就力不从心了

2. instanceof 操作符

用于检测构造函数的 prototype 属性是否出现在对象的原型链中:

[] instanceof Array;           // true
{} instanceof Object;          // true
new Date() instanceof Date;    // true
function(){} instanceof Function; // true

// 继承关系,数组也是对象
[] instanceof Object;          // true

instanceof 的局限性:

// 基本类型用不了
42 instanceof Number;          // false
"hello" instanceof String;     // false

在跨 iframe 或不同 window 环境下可能失效(因为构造函数不同)


3. Object.prototype .toString.call()

这是最准确、最可靠的方法,能识别所有内置类型!

Object.prototype.toString.call(42);           // "[object Number]"
Object.prototype.toString.call("hello");      // "[object String]"
Object.prototype.toString.call(true);         // "[object Boolean]"
Object.prototype.toString.call(null);         // "[object Null]"
Object.prototype.toString.call(undefined);    // "[object Undefined]"
Object.prototype.toString.call([]);           // "[object Array]"
Object.prototype.toString.call({});           // "[object Object]"
Object.prototype.toString.call(function(){}); // "[object Function]"
Object.prototype.toString.call(Symbol());     // "[object Symbol]"
Object.prototype.toString.call(42n);          // "[object BigInt]"

我们封装一个实用的工具函数:

function getRealType(value) {
    return Object.prototype.toString.call(value)
        .slice(8, -1)          // 截取"[object "和"]"之间的内容
        .toLowerCase();         // 转为小写,更友好
}

console.log(getRealType([]));        // "array"
console.log(getRealType(null));      // "null"
console.log(getRealType({}));        // "object"
console.log(getRealType(new Date())); // "date"

4. 专用方法

对于一些特殊类型,JavaScript提供了专门的判断方法:

判断数组:Array.isArray()

Array.isArray([]);     // true
Array.isArray({});     // false
Array.isArray("123");  // false

判断NaN:Number.isNaN()

// 注意区别!
isNaN("hello");        // true  ← 字符串不是数字,但这样判断容易误解
Number.isNaN("hello"); // false ← 更准确:只有真正的NaN才返回true
Number.isNaN(NaN);     // true

判断有限数字:Number.isFinite()

Number.isFinite(42);     // true
Number.isFinite(Infinity); // false  ← 无穷大不是有限数字
Number.isFinite("42");   // false  ← 字符串不是数字

编写健壮的函数

在实际开发中的应用:

场景1:安全的数字相加

function safeAdd(a, b) {
    // 确保两个参数都是数字类型
    if (typeof a !== 'number' || typeof b !== 'number') {
        throw new Error('参数必须是数字');
    }
    return a + b;
}

safeAdd(1, 2);     // 3
safeAdd(1, "2");   // 报错:参数必须是数字

场景2:处理多种数据类型

function processData(data) {
    // getRealType方法在第3点Object.prototype.toString.call()中有写
    const type = getRealType(data); 
    
    switch(type) {
        case 'array':
            return data.map(item => item * 2);
        case 'object':
            return Object.keys(data).length;
        case 'string':
            return data.toUpperCase();
        case 'number':
            return data * 2;
        default:
            return '不支持的数据类型';
    }
}

console.log(processData([1, 2, 3]));    // [2, 4, 6]
console.log(processData("hello"));      // "HELLO"
console.log(processData({a: 1, b: 2})); // 2

总结:选择合适的方法

场景 推荐方法 示例
判断基本类型 typeof typeof "hello" === "string"
判断数组 Array.isArray() Array.isArray([])
判断自定义对象 instanceof obj instanceof MyClass
精确类型判断 Object.prototype.toString.call() 见上文工具函数
特殊值判断 专用方法 Number.isNaN(), Number.isFinite()

本文首发于公众号:程序员大华,专注分享前后端开发的实战笔记。关注我,少走弯路,一起进步!

📌往期精彩

写前端久了,我用 Node.js 给自己造了几个省力小工具

我也是写了很久 TypeScript,才意识到这些写法不对

ThreadLocal 在实际项目中的 6 大用法,原来可以这么简单

重构了20个SpringBoot项目后,总结出这套稳定高效的架构设计

用changeset来管理你的npm包版本

简单介绍下,changeset是一个版本管理和生成更新日志的工具,超级适用于多包仓库,比如monorepo,可以在提交发布时,自动更新所有包的版本号,创建Tag,并且生成更新日志。

一、安装

进入项目之后执行命令,安装changeset,并且初始化

 pnpm add -D @changesets/cli
 pnpm changeset init

执行完之后,在项目中会新增一个.changeset目录,用于存放配置文件和临时的版本变更描述文件

.changeset/
 ├─ config.json
 └─ README.md

二、使用流程

在通用的版本管理流程中,通常会区分为:

  • 预发布版本(如alpha和beta)
  • 正式版本

预发布版本

预发布阶段的两级为alpha和beta,下面是大致区别:

维度 alpha(内测) beta(公测)
代码稳定性 随时可能大改 功能基本锁定,不会有大的调整
测试人群 团队内部 灰度用户
发布频率 每天/每周都能出包 节奏稍慢,某个阶段的版本
版本号示例 1.0.0-alpha.0 ➜ 1.0.0-alpha.1 … 1.0.0-beta.0 ➜ 1.0.0-beta.1 …
退出条件 达到功能完备 → 进入beta 连续几天无阻塞Bug → 发布正式版

相关命令:

pnpm changeset pre enter alpha   # 进入alpha模式,
pnpm changeset version          # 版本变成0.0.1-alpha.0

pnpm changeset pre enter beta   # 进入beta模式
pnpm changeset version          # 版本变成0.0.1-beta.0

# 结束预发布
pnpm changeset pre exit
pnpm changeset version          # 版本变成0.0.1

正式版本

当你完成某个包的开发,准备发版时,执行:

pnpm changeset

如果是多包仓库,终端会出现一个选择框,让你选择改过的包,

  1. 按空格选中你改过的包(有星号就算选中)→ 回车,

  2. 选包的更新级别,会依次出现major和minor,回车到下一步,如果都没选中,就默认为patch,输入本次更新的描述回车

    • patch:修复小bug(1.0.0→1.0.1)
    • minor:添加新功能(1.0.0→1.1.0)
    • major:破坏性的大版本调整,api级别的调整(1.0.0→2.0.0)

单包仓库就直接到了选择更新级别这一步,同样是输入描述,然后回车;

生成版本号,执行:

pnpm changeset version

你会发现.changeset文件夹中刚才生成的md文件都已经不见了,版本号也升好了。

发布

  • 登录npm
npm login
  • 发版
pnpm changeset publish

成功后,会在git创建对应的git tag,终端会给出每个包的版本号和 npm链接。

三、changeset总结

最后总结下,对changeset的整体感觉

优点

  1. 版本语义化,显式标注变更级别
  2. 每一次变更都会新建个文件,方便review
    • 列出受影响的包
    • 变更的级别,patch/minor/major
    • 变更的内容
  3. 自动生成tag、版本号changelog
  4. Monorepo依赖的自动推导,比如修改了a包,b包依赖了a包,那么b包也会更新版本

缺点

  1. 会有额外心智负担,
    • 每次变更都要执行changeset,会增加操作流程(其实我觉得这个不能算)
    • 思考版本类型
    • 流程容易漏
  2. 单包项目有点多余,没完全发挥作用

CSS 特殊符号 / 英文导致换行问题速查表

一、最推荐通用写法(90% 场景)

.text {
  word-break: normal;
  overflow-wrap: break-word;
  white-space: normal;
}

适用:

  • 中文 + 英文混排
  • URL / 特殊符号
  • 不希望英文被拆成字母

二、常见需求对应写法

以下场景覆盖:不拆单词 / 允许拆单词 / 特殊符号提前换行 等真实业务需求

1️⃣ 不希望单词被拆开

.text {
  word-break: normal;
  overflow-wrap: normal;
}

2️⃣ 单词太长允许必要时换行(推荐)

.text {
  overflow-wrap: break-word;
  word-break: normal;
}

3️⃣ 特殊符号(- _ / .)导致断行

.text {
  word-break: keep-all;
  overflow-wrap: break-word;
}

4️⃣ 完全不换行(一行显示)

.text {
  white-space: nowrap;
}

5️⃣ 一行显示,超出省略号

.text {
  white-space: nowrap;
  overflow: hidden;
  text-overflow: ellipsis;
}

6️⃣ URL / 长链接优雅断行

.text {
  word-break: normal;
  overflow-wrap: anywhere;
}

7️⃣ 代码 / hash / token 强制断行

.code {
  word-break: break-all;
  font-family: monospace;
}

8️⃣ 明确接受单词被拆开(强制任何位置换行)

.text {
  word-break: break-all;
}

适用:

  • 日志内容
  • 长 hash / token / ID
  • 空间极窄但必须完整展示

⚠️ 英文会被拆成字母,属于主动选择的行为


9️⃣ 特殊符号导致“提前换行”(如 - / _ .

.text {
  word-break: normal;
  overflow-wrap: normal;
}

说明:

  • 禁止在符号处断行
  • 让浏览器只在真正需要时换行

🔟 允许在特殊符号处优先换行(比拆字母更友好)

.text {
  overflow-wrap: anywhere;
  word-break: normal;
}

适用:

  • URL / 路径
  • aaa-bbb-ccc-ddd
  • 希望优先在符号处分行,而不是字母中间

---

## 三、Flex / Table 常见坑

### flex 子项内容被异常换行

```css
.item {
  min-width: 0;
  overflow-wrap: break-word;
}

四、不推荐写法(慎用)

⚠️ 以下写法不是不能用,而是必须明确知道后果

word-break: break-all;

❌ 会把英文拆成字母,仅适合日志 / code 场景


五、属性速记表

属性 作用
word-break 是否允许在单词内部断行
overflow-wrap 单词太长时是否允许换行(⭐推荐)
white-space 是否允许换行

📌 记住一句话:

优先用 overflow-wrap: break-word,避免 word-break: break-all

PowerShell 启动卡顿?内存飙升?原来是 800MB 的历史记录在作祟!

PowerShell 启动卡顿?内存飙升?原来是 800MB 的历史记录在作祟!

最近在开发过程中遇到一个非常诡异的问题:PowerShell 一启动,电脑就像被施了定身法一样卡顿。 打开任务管理器一看,好家伙,PowerShell 进程的内存占用像坐火箭一样蹭蹭往上涨,甚至在没有任何手动操作的情况下也是如此。

经过一番侦探式的排查,终于揪出了幕后真凶。今天就把这个排查过程和解决方案分享给大家,如果你的终端也经常卡顿,不妨检查一下这个问题。

🧐 问题现场

现象非常简单粗暴:

  • 双击启动 PowerShell(或者在 VS Code 中打开终端)。
  • 系统明显卡顿,鼠标移动都变得迟缓。
  • 查看任务管理器,PowerShell 进程占用内存极高(甚至达到 GB 级别)。
  • 等待许久后,终端才勉强可以输入命令。

🕵️‍♂️ 抽丝剥茧:排查过程

为了找到原因,我并没有急着重装系统(虽然这是万能大法),而是决定深入系统内部看一看。

1. 进程分析

首先,我使用 Get-Process 命令查看了 PowerShell 进程的状态。果不其然,WorkingSet(工作集内存)数值异常的高。

2. 环境检查

我怀疑是不是某个 Profile 配置文件或者加载的模块有问题。检查了 $PROFILE,发现并没有什么特殊的启动脚本。接着检查已加载的模块,一切似乎都很正常。

3. 关键发现

在排查 PowerShell 的常用模块 PSReadLine 时,我注意到了一个细节。这个模块负责管理我们的命令行历史记录、语法高亮等功能。它会把我们敲过的所有命令都保存在一个文本文件里。

我顺藤摸瓜找到了这个文件,结果让我大吃一惊:

文件路径: %APPDATA%\Microsoft\Windows\PowerShell\PSReadLine\ConsoleHost_history.txt 文件大小: 832 MB

没错,你没看错,一个纯文本的历史记录文件,竟然有 800多兆!这意味着里面可能保存了数百万行的命令历史。

真相大白: PowerShell 在启动时,PSReadLine 模块会尝试加载这个巨大的历史记录文件,以便提供“向上箭头”查找历史命令的功能。这就好比让你一口气背诵一本字典,不卡才怪!

🛠️ 一键解决

既然找到了病灶,治疗方案就非常简单了:让 PowerShell 放弃加载这个文件。

为了保险起见(万一里面有重要的历史命令呢),我没有直接删除它,而是选择了重命名。

操作步骤:

打开你的文件资源管理器,或者直接在命令行执行以下操作:

# 进入 PSReadLine 目录
cd "$env:APPDATA\Microsoft\Windows\PowerShell\PSReadLine"

# 将巨大的历史文件重命名备份
Rename-Item .\ConsoleHost_history.txt -NewName ConsoleHost_history.txt.bak

效果立竿见影: 再次启动 PowerShell,秒开!内存占用恢复到了几十 MB 的正常水平。系统瞬间恢复了丝般顺滑。

💡 避坑指南

问题解决了,但为什么会有这么大的历史文件呢?通常有以下几个原因:

  1. 日积月累: 从来没有清理过,数年的操作记录都在里面。
  2. 自动化脚本: 某些自动化脚本如果在 PowerShell 环境下疯狂循环执行命令,这些命令也会被记录下来。

建议:

  • 定期检查一下 %APPDATA%\Microsoft\Windows\PowerShell\PSReadLine\ 目录下的文件大小。
  • 如果你发现自己不需要保留那么久远的历史记录,可以考虑定期清理。
  • 如果那个 800MB 的备份文件里没有你需要的“传家宝”代码,果断删掉它释放空间吧!

希望这篇文章能帮到遇到同样问题的你。Happy Coding! 🚀

❌