Algorithm
Review
Tips
Share
每周完成一个 ARTS: 至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。(也就是 Algorithm、Review、Tips、Share 简称 ARTS)
Algorithm
这道题目关健就是看数量,看对应的字母出现了几次。比如,上面案例中的 abccccdd 这个内容,如果是类似于 c、d 这种有多个的一般都是可以组成对称的内容。但是还要注意一点,如果是有单独的字母,比如 a 、b 等等,我们也可以用到其中之一,用于构建回文串的。
思路:
- 先拿到每一个 char 有多少个,这里使用 map 的 merge 方法
- 之后根据 char 对应的数量进行判断:
- 如果是偶数的话那么可以自己在最终的 size 加上
- 如果是奇数的话,需要单独进行 - 1 操作(不可能是负数,以为 map 里面存的至少是 1 个),目的是为了凑偶数,这样后续方便计算 size
- 但是奇数的情况下,还需要进行特殊处理,这里需要计算一下是否有单独一个字母的情况,如果有的话后续计算 size 的时候需要 + 1 ,但是不能每一个都进行 + 1,因为这个单独的一个字母最终是放到中间位置的,如果多个的话那么就无法对称了,也就不是回文字符串
Java
class Solution {
public int longestPalindrome(String s) {
HashMap<Character, Integer> strMap = new HashMap<>();
for (char c : s.toCharArray()) {
strMap.merge(c, 1, Integer::sum);
}
int size = 0;
boolean haveSingleChar = false;
for (Map.Entry<Character, Integer> entry : strMap.entrySet()) {
Integer value = entry.getValue();
if (value % 2 != 0) {
haveSingleChar = true;
value = value - 1;
}
if (value <= 0) {
continue;
}
size += value;
}
return haveSingleChar ? ++size : size;
}
}但是这道题目其实也有其他的更节省内存的办法,就是使用 Set 进行判断,而且一次 for 循环就就可以解决:
- 使用 Set 只需要一次循环即可
- 当我们 set 插入的时候可以判断是否存在;true 的话就表示之前没有,false 的话就表示之前插入过
- 最终判断的时候,如果这个 set 的 size 是 0,就表示全部全部都是成对的。如果不是 0 的话就表示有冗余的,之需要 + 1 即可
Java
class Solution {
public int longestPalindrome(String s) {
Set<Character> set = new HashSet<>();
int length = 0;
for (char c : s.toCharArray()) {
boolean ifPresent = set.add(c);
if (!ifPresent) {
set.remove(c);
length = length + 2;
}
}
return set.isEmpty() ? length : length + 1;
}
}
这道题目是相对简单的双指针,也算是我第一道双指针的题目了(之前可能刷过但是忘记了),有一些注意事项:
- 具体例子,还是具体例子,没有具体的例子我真的想不明白
- 外层循环开始的时候就是按照 index 从前向后,因为外层循环是要被匹配的字母,而内层的就是来源字符串。
- 外层循环 0 开始,但是内层循环却不可以,如果内存循环每一次都是从 0 开始的话,那么会导致误判,比如 下面这个例子,aab. acb。并且开始的 index 也有讲究,必须是最后匹配到的 j 的顺序的下一位,因为如果来源字符串中的一个字母已经被匹配到了,那么下一次循环的时候不能再判断当前的字母了
- 不只需要 index 还需要一个变量判断,这个变量的作用就是判断当前的内层循环,是否找到了对应的需要匹配的字母如果一次循环没有找到的话,那么可以直接返回 false 了,因为循环完全的来源字符串都没有对应的字母,直接宣判 false并且这个变量,每一次循环开始的时候需要设置成 false 否则,上一次外层循环判断的「垃圾」数据,就会干扰当前这次循环的判断
Java
public boolean isSubsequence(String s, String t) {
// 双指针解决
if (s.length() > t.length()) {
return false;
}
int index = 0;
boolean isFound = false;
for (int i = 0; i < s.length(); i++) {
isFound = false;
for (int j = index; j < t.length(); j++) {
if (t.charAt(j) == s.charAt(i)) {
index = j + 1;
isFound = true;
break;
}
}
if (!isFound) {
return false;
}
}
return true;
}
Review
平时我们访问一个网站,或者自己的服务器请求另一个服务器的接口,看起来只需要一个 URL。但是请求到底怎么找到对方,数据又是怎么回来的?这篇文章从浏览器访问网站开始,把整个过程串了起来。
1、先通过 DNS 找到目标地址。
假设要访问 https://example.com/hello,其中 example.com 是域名,/hello 是要请求的路径。域名方便人记忆,但机器发送数据包需要目标 IP 地址,所以首先需要通过 DNS 解析域名。
解析时,浏览器、操作系统或者 DNS 服务器可能已经缓存了结果。如果没有找到,递归 DNS 服务器会继续查询,直到获得对应的记录,再把结果返回给请求方。拿到 IP 后,请求方才知道要向哪个地址发送数据。
2、数据经过网关和多个路由器,才能到达目标。
如果目标不在当前网络中,数据包通常会先发给默认网关,比如家里的路由器。对于 IPv4,本机可以通过 ARP 查询网关的 MAC 地址,然后把数据发送给网关。这里需要注意,找到的是下一跳的 MAC 地址,不是直接找到远程服务器的 MAC 地址。
路由器收到数据包后,会根据目标 IP 和路由表决定下一跳。数据可能经过运营商的网络、不同网络之间的连接,再经过多个路由器,最终到达目标服务器所在的网络。每个路由器只需要根据自己的路由信息决定接下来往哪里转发,不需要提前知道整条路径。
文章中还使用了 traceroute 查看数据经过的节点。可以用它观察请求大致经过了哪些网络,不过有的节点不会回应探测,所以出现 * 并不一定代表数据无法通过。
3、建立连接,再发送 HTTP 请求。
文章以 TCP 为例:数据到达目标之后,客户端和服务器会先通过 TCP 三次握手建立连接。如果使用 HTTPS,还需要进行 TLS 握手,验证服务器身份并协商加密通信需要的信息。
连接准备好之后,客户端才发送 HTTP 请求。请求中会包含请求方法、路径和请求头等信息,比如 GET /hello 表示希望获取 /hello 对应的资源。服务器收到请求后,可能读取文件,也可能执行应用程序、查询数据库,再生成响应。
这里说的是 HTTP/1.1 或 HTTP/2 使用 TCP 的情况。HTTP/3 使用的是基于 UDP 的 QUIC,连接建立的过程会有所不同。
4、响应如何回到自己这里?
服务器处理完成后,会把状态码、响应头和响应内容发送回来。响应数据同样会经过多个路由器,逐跳转发到客户端所在的网络,再交给对应的程序。回来的路径不一定和请求过去时完全相同。
如果客户端是浏览器,收到 HTML 后还可能继续请求图片、CSS 和 JavaScript 等资源。如果客户端是自己的服务器,那么它拿到响应后,可能解析 JSON、保存数据或者继续处理业务。
还要注意,请求不一定直接到达提供内容的源服务器:如果前面有 CDN,请求可能先到 CDN 节点,由它返回缓存内容;没有缓存时再向源服务器获取。通过这篇文章,我觉得之前分开学习的 DNS、TCP、路由器和 HTTP,终于可以放在一次实际请求里理解了。
如果想继续看路由器、ARP 和数据包封装的细节,还可以参考 What Happens When… 的 ARP process 和 Opening of a socket 部分。这个项目的部分协议描述比较旧,阅读 TLS 和 HTTP 的内容时需要结合现在的协议版本。
Tips
最近使用 Claude Code 比较多,CLI 可以自定义 statusline,用来显示模型、上下文使用情况和用量信息。配置文件位置是 ~/.claude/settings.json,相关配置如下:
JSON
{
"env": {
"CLAUDE_CODE_DISABLE_1M_CONTEXT": "1"
},
"statusLine": {
"type": "command",
"command": "bash \"$HOME/.claude/statusline.sh\""
}
}- 这里的CLAUDE_CODE_DISABLE_1M_CONTEXT 设为 1 可以禁用 1M 上下文(有效上下文也没有 1M 这么多,不如直接用 200k 的 token)
- statusLine 则指定 Claude Code 刷新状态栏时运行的命令。如果配置文件里已经有其他内容,把这两项合并进去即可。
需要把状态栏脚本放在 ~/.claude/statusline.sh。注意,脚本需要安装 jq,macOS 可以通过 brew install jq 安装。我的脚本内容如下:
Bash
#!/usr/bin/env bash
# Claude Code status line. Requires jq.
set -u
# Claude Code sends one JSON object to stdin on every refresh.
IFS=$'\t' read -r model effort ctx hit used5 reset5 used7 reset7 < <(
jq -r '
def percent:
if type == "number" then ([0, ([100, .] | min)] | max | round)
else "NA" end;
[
(.model.display_name // "Unknown"),
(.effort.level // "N/A"),
(.context_window.used_percentage | percent),
(.prompt_cache.hit_ratio | if type == "number" then (. * 100 | round) else "NA" end),
(.rate_limits.five_hour.used_percentage | percent),
(.rate_limits.five_hour.resets_at // "NA"),
(.rate_limits.seven_day.used_percentage | percent),
(.rate_limits.seven_day.resets_at // "NA")
] | @tsv
'
)
RESET=$'\033[0m'
DIM=$'\033[2m'
MODEL_COLOR=$'\033[1;35m'
CYAN=$'\033[36m'
SEPARATOR=$'\033[38;2;130;130;130m'
TRACK=$'\033[38;2;120;120;120m'
GREEN=$'\033[32m'
YELLOW=$'\033[33m'
RED=$'\033[31m'
percent_text() {
if [[ $1 =~ ^[0-9]+$ ]]; then printf '%d%%' "$1"; else printf '%s' '--%'; fi
}
left_text() {
if [[ $1 =~ ^[0-9]+$ ]]; then printf '%d%%' "$((100 - $1))"; else printf '%s' '--%'; fi
}
reset_after() {
local ts=$1 seconds days hours mins
if [[ ! $ts =~ ^[0-9]+([.][0-9]+)?$ ]]; then printf '%s' '--'; return; fi
seconds=$(( ${ts%%.*} - NOW ))
(( seconds < 0 )) && seconds=0
days=$((seconds / 86400))
hours=$(((seconds % 86400) / 3600))
mins=$(((seconds % 3600) / 60))
if (( days > 0 )); then
printf '%dd %dh' "$days" "$hours"
elif (( hours > 0 )); then
printf '%dh %dm' "$hours" "$mins"
else
printf '%dm' "$mins"
fi
}
# Gradient uses stable, full-width block characters: no fractional glyphs.
context_bar() {
local pct=$1 width=20 filled=0 i pos r g b offset
if [[ $pct =~ ^[0-9]+$ ]]; then filled=$(((pct * width + 50) / 100)); fi
for ((i = 0; i < width; i++)); do
if (( i >= filled )); then
printf '%s░' "$TRACK"
continue
fi
pos=$((i * 100 / (width - 1)))
if ((pos <= 50)); then
r=$(( 0 + 220 * pos / 50 ))
g=200
b=$(( 80 - 80 * pos / 50 ))
else
offset=$((pos - 50))
r=220
g=$(( 200 - 160 * offset / 50 ))
b=$(( 20 * offset / 50 ))
fi
printf '\033[38;2;%d;%d;%dm█' "$r" "$g" "$b"
done
printf '%s' "$RESET"
}
usage_color() {
if [[ ! $1 =~ ^[0-9]+$ ]] || (( $1 < 70 )); then printf '%s' "$GREEN"
elif (( $1 < 90 )); then printf '%s' "$YELLOW"
else printf '%s' "$RED"; fi
}
NOW=$(date +%s)
ctx_label=$(percent_text "$ctx")
hit_label=$(percent_text "$hit")
five_left=$(left_text "$used5")
seven_left=$(left_text "$used7")
five_reset=$(reset_after "$reset5")
seven_reset=$(reset_after "$reset7")
ctx_color=$(usage_color "$ctx")
five_color=$(usage_color "$used5")
seven_color=$(usage_color "$used7")
printf '%s[%s · %s]%s ' "$MODEL_COLOR" "$model" "$effort" "$RESET"
context_bar "$ctx"
printf ' %s%s%s %s│%s %sHit%s %s%s\n' "$ctx_color" "$ctx_label" "$RESET" "$SEPARATOR" "$RESET" "$CYAN" "$RESET" "$CYAN" "$hit_label"
printf '5h %s%s%s left %s·%s reset %s %s│%s 7d %s%s%s left %s·%s reset %s\n' \
"$five_color" "$five_left" "$RESET" "$DIM" "$RESET" "$five_reset" "$SEPARATOR" "$RESET" \
"$seven_color" "$seven_left" "$RESET" "$DIM" "$RESET" "$seven_reset"Share
这周看到 Simon Willison 分享了一个关于 AI Coding 的观点。Simon 是 Django 的共同创建者之一,也一直在实践和分享 AI 编程。他认为,想要有效使用 Coding Agent,需要能够清楚地告诉它要做什么,并且有把握地验证修改是否正确。
1、能描述需求,也需要知道怎么判断结果。
以前自己写代码时,需要考虑怎么实现;使用 Agent 后,我们可以先描述需求,让它去寻找和修改代码。但是,描述得越清楚,后面越容易判断它有没有完成任务。比如,不只是说「做一个双指针动画」,还可以说明两个指针分别代表什么、什么时候移动,以及匹配成功或失败时应该显示什么。
Agent 把功能做出来之后,还需要回到需求本身,确认结果是否符合预期。如果一开始自己也不知道正确结果是什么,就很难判断它交付的东西是否可靠。
2、验证不只有逐行阅读代码。
Simon 提到,逐行检查代码有时是必要的,但验证修改还有其他方法。比如运行程序、查看实际效果、准备测试数据,以及针对容易出错的情况做测试。这些方法可以和代码审查结合使用,具体选择取决于改动的内容和风险。
以这周的子序列动画为例,除了看页面能否打开,还可以输入 aab 和 acb,观察同一个字符会不会被重复匹配;再试试空字符串、完全匹配和不匹配的情况,看看指针移动和最终结果是否符合预期。这样验证的是实际行为,而不只是代码看起来有没有问题。
3、使用 AI 之后,对问题的理解仍然很重要。
这次做动画演示,也是希望通过具体例子帮助自己理解双指针。如果不清楚题目要求和指针应该怎样移动,即使 AI 很快生成了一个页面,也不容易发现演示里的错误。
我觉得 AI 确实让我们可以更快地尝试想法,但做出来只是第一步。之后还要根据用途决定怎么检查:个人学习工具可以先用几个例子验证,涉及真实用户和重要数据的功能,则需要更充分的测试和审查。理解问题、提出要求和验证结果,依然是使用 AI 时需要自己关注的事情。
评论 (1)


