Jack N @ GitHub

Full stack AI Engineer, focus on: React, Next.js, node.js and .Net

Posted on

1. 题目

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

注意「子串」是连续的，区别于「子序列」。

示例:

1
2
3
4
5
6
7
8
9
10
输入: s = "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，长度为 3。

输入: s = "bbbbb"
输出: 1

输入: s = "pwwkew"
输出: 3
解释: 最长子串是 "wke"，注意 "pwke" 是子序列不是子串。

2. 解题思路

标准的滑动窗口问题。维护一个窗口 [left, right]，保证窗口内始终无重复字符。

用 Map<字符, 最近一次出现的下标> 记录每个字符最后出现的位置。右指针 right 逐个字符向右扩展：

  • 如果 s[right] 之前出现过，且其位置在窗口内（>= left），说明加入它会重复，于是把 left 直接跳到「重复字符上次位置 + 1」，一步到位，无需逐个收缩。
  • 更新 s[right] 的位置为 right。
  • 每一步用 right - left + 1 更新最大长度。

关键技巧：left 只能右移不能回退，所以要取 Math.max(left, lastPos + 1)，避免像 abba 这类用例把 left 拉回左边。

  • 时间复杂度：O(n)，每个字符最多被访问一次。
  • 空间复杂度：O(min(n, 字符集大小))。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function lengthOfLongestSubstring(s: string): number {
    const lastPos = new Map<string, number>();
    let left = 0;
    let maxLen = 0;

    for (let right = 0; right < s.length; right++) {
        const ch = s[right];

        // 字符在窗口内出现过，left 跳到重复处之后
        if (lastPos.has(ch)) {
            left = Math.max(left, lastPos.get(ch)! + 1);
        }

        lastPos.set(ch, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

// 测试
console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("bbbbb"));    // 1
console.log(lengthOfLongestSubstring("pwwkew"));   // 3
console.log(lengthOfLongestSubstring("abba"));     // 2

4. 面试延伸

  • 不用 Map 的写法？ 字符集有限（如 ASCII）时用长度为 128 的数组更快；也可用 Set 记录窗口内字符，重复时循环删除 s[left++] 直到不重复。
  • 变形题：至多包含两个不同字符的最长子串（LeetCode 340）、最小覆盖子串（76） 都是滑动窗口的进阶，套路一致：右扩满足条件、左缩优化答案。
  • 记住模板：for right + while 违反条件 then left++，能覆盖绝大多数子串类题目。

难度：中等 | LeetCode 3 题 | 滑动窗口入门必刷

Posted on

概述

HTML/URL中有2个概念，encode和escape，乍一看差不多, 都是用于处理特殊字符（保留字符），其实用于不同场合：

  • encode： 主要针对URL地址中特殊字符（保留字符）的处理， 如针对 &, ?, =等字符
  • escape: 主要针对页面中的特殊字符（保留字符）的处理， 如针对 <, >, ", '字符

Escape

Escape/unescape 没有现成的函数，只能自己实现。实现也很简单，就是对字符串全文替换。

1
2
3
4
5
6
7
8
function escapeHTML(str) {
    return str.replace(/&/g, "&amp;")
      .replace(/</g, "&lt;")
      .replace(/>/g, "&gt;")
      .replace(/"/g, "&quot;")
      .replace(/'/g, "&#039;");
}

Encode/Decode

Javascript 中，针对URL的处理是有通用方法的，encodeURIComponent 和encodeURI，酌情选择所需的函数。

  • encodeURI方法不会对下列字符编码: ASCII字母 数字 ~!@#$&*()=:/,;?+’
  • encodeURIComponent方法不会对下列字符编码: ASCII字母 数字 ~!*()’
  • 所以encodeURIComponent比encodeURI编码的范围更大。实际例子来说，encodeURIComponent会把 http:// 编码成 http%3A%2F%2F 而encodeURI却不会。

Posted on

1. 题目

给你一个整数数组 nums，找出所有满足 nums[i] + nums[j] + nums[k] == 0 的三元组 [i, j, k]，且要求：

  • i、j、k 两两不同。
  • 返回的三元组不能重复。

示例:

1
2
3
输入: nums = [-1, 0, 1, 2, -1, -4]
输出: [[-1, -1, 2], [-1, 0, 1]]
解释: 满足条件的不重复三元组如上，注意 [-1, 0, 1] 和 [0, 1, -1] 视为同一个。

2. 解题思路

暴力三重循环是 O(n³) 且难以去重。经典做法是排序 + 双指针，把复杂度降到 O(n²)。

  1. 排序：nums.sort((a, b) => a - b)，让双指针成为可能，也让重复值相邻便于跳过。
  2. 固定一个数：外层枚举 nums[i]，把问题转化为「在 i 右侧找两数之和等于 -nums[i]」——退化成 [两数之和 II（有序）]。
  3. 双指针夹逼：left = i + 1，right = n - 1：
    • sum === 0 → 记录答案，然后左右指针同时向内移动并跳过重复。
    • sum < 0 → 需要更大的数，left++。
    • sum > 0 → 需要更小的数，right--。
  4. 三处去重：
    • i 与前一个相同则跳过（避免重复的第一个数）。
    • 命中答案后，left、right 各自跳过相同值。

优化剪枝：排序后若 nums[i] > 0，三数之和不可能为 0，直接结束。

  • 时间复杂度：O(n²)。
  • 空间复杂度：O(log n)（排序栈空间，不计输出）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function threeSum(nums: number[]): number[][] {
    const res: number[][] = [];
    const n = nums.length;
    nums.sort((a, b) => a - b);

    for (let i = 0; i < n - 2; i++) {
        // 剪枝：最小值已大于 0，不可能凑出 0
        if (nums[i] > 0) break;
        // 去重：跳过相同的第一个数
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let left = i + 1;
        let right = n - 1;

        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];

            if (sum === 0) {
                res.push([nums[i], nums[left], nums[right]]);
                // 去重：跳过第二个数、第三个数的重复值
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return res;
}

// 测试
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]
console.log(threeSum([0, 0, 0, 0])); // [[0, 0, 0]]

4. 面试延伸

  • 扩展到 k-Sum？ 排序后递归地固定 k-2 个数，最后两数用双指针，通用模板时间 O(n^{k-1})。
  • 最接近的三数之和（LeetCode 16）？ 同样双指针，只是记录过程中 |sum - target| 的最小值。
  • 去重是最大坑点：一定要在push之后跳过重复，而不是用 Set 序列化数组去重（后者能过但脏）。

难度：中等 | LeetCode 15 题 | 双指针标杆题

Posted on

1. 题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

要求：

  • 每种输入只会对应一个答案（保证有且仅有一组解）。
  • 同一个元素不能使用两遍。
  • 可以按任意顺序返回答案。

示例:

1
2
3
输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1]
解释: nums[0] + nums[1] == 9，返回 [0, 1]

2. 解题思路

2.1 暴力法（不推荐）

两层循环枚举所有 (i, j) 组合，判断 nums[i] + nums[j] === target。

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)

面试时可以作为引子，但要立刻说出瓶颈在于「查找另一个数是否存在」这一步是线性的。

2.2 哈希表（最优）

核心转换：对于当前数 x，我们真正想知道的是「数组里有没有 target - x」。

遍历数组时，用 Map 记录「已经看过的数 -> 下标」。对每个 nums[i]：

  1. 计算补数 complement = target - nums[i]。
  2. 若 complement 已在 Map 中，直接返回 [map.get(complement), i]。
  3. 否则把 nums[i] -> i 存进 Map，继续。

因为「先查后存」，天然避免了同一个元素被使用两次。

  • 时间复杂度：O(n)，只需一次遍历。
  • 空间复杂度：O(n)，最坏存 n 个数。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function twoSum(nums: number[], target: number): number[] {
    const seen = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (seen.has(complement)) {
            return [seen.get(complement)!, i];
        }

        seen.set(nums[i], i);
    }

    // 题目保证有解，理论上不会走到这里
    return [];
}

// 测试
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6));      // [1, 2]
console.log(twoSum([3, 3], 6));         // [0, 1]

4. 面试延伸

  • 为什么用 Map 而不是 Object？ 数字做 key 时 Map 无需字符串化，也避免原型链上的键冲突，查找语义更清晰。
  • 如果数组已排序呢？ 可用「双指针」左右夹逼，空间降到 O(1)，这也是 [三数之和] 的基础。
  • 返回所有不重复组合？ 那就需要排序 + 去重，思路升级为 k-Sum 通用解法。

难度：简单 | LeetCode 1 题 | 高频面试开场题

Posted on

1. 概述

位操作是程序设计中对位模式按位或二进制数的一元和二元操作. 在许多古老的微处理器上, 位运算比加减运算略快, 通常位运算比乘除法运算要快很多. 在现代架构中, 情况并非如此:位运算的运算速度通常与加法运算相同（仍然快于乘法运算）。

2. 取反（NOT）~

3. 按位或（OR）|

4. 按位异或（XOR）^

5. 按位与（AND）&

6. 移位 >>, <<, >>>

  • 移动: >>, <<
  • 无符号右移： >>>
  • 无符号左移是不存在的，因为左右在低位补位，而低位没有正负数的概念，因此不存在无符号左移

7. 其他位操作技巧P

7.1. n & (n - 1)

该位运算技巧可以直接将 n 的二进制表示的最低位 1 移除。

  1. 不停的进行 n = n & (n - 1) 操作，直至n为0，可以计算二进制数的1的个数

Posted on

环境：

  • .NET 5
  • ASP.NET Core MVC

1. .NET 5

作为一个资深.NET工程师，说句实话，.NET没落了，在国内更加的没落。之前做过8年node.js/前端，现如今又转回了.NET。也希望.NET能有更好的前景吧。个人觉得.NET还是有一定的市场的（当然，国内算小众了），有几点原因：

  1. .NET5开始，真正做到的跨平台（之前叫.NET CORE)， 而且把那个’CORE’字也拿掉就，就叫.NET5， 可见微软的宏大目标；
  2. 开发效率，.NET软件开发，不管是web还是winForm，效率确实高
  3. 跨平台，从.net core开始，终于跨平台了….
  4. 性能大大提升。 .NET core性能大幅提升，尤其是跑在Linux上的时候；
  5. 有些已有的基于.NET的产品，还需要继续维护、开发，不会换个语言重写；
  6. 微软、以及和微软紧密合作的公司，也提供了不少.NET的应用场景；

工欲善其事必先利其器，既然要接着用.NET，那么下文将列一下开发必备工具，供参考。

2. IDE

2.1. Visual Studio

这个没的说，而且要用最新版的VS!

2.2. Visual Studio Code

微软的开源软件，同时是当前最流行的Web前端开发IDE。

作为备选，支持C#开发，对于简单的代码，或者测试一些语法、看代码什么的，这个足够，而且占用资源很少。

推荐插件：

  • Code Spell Checker, 检查代码中单词拼写错误。声明个变量，后来发现单词拼写错了，尴尬了，使用这个插件，即时提示拼写错误
  • C#, 安装此插件支持C#项目
  • GitLens，如果使用git，一定要装这个，方便查询提交历史，某一行上次代码的提交人、提交备注等；
  • Markdown All in One, markdown文件的插件，很强大，自动生成目录、编号等等。

3. 代码比较

3.1. Beyond Compare

收费软件，但功能确实是强大。

3.2. WinDiff

免费版，将就着用；

4. 图片处理

4.1. paint.net

(这个也是基于.NET开发的哦，因为我们机器必然有.net framework,所以这是还是很小的)；
免费版，功能也很强大，占用资源很少。对于非专业的美工，足够用了！

5. 其他Web工具

5.1. node.js/npm

做前端web开发，不管是否用node.js，环境还是要有的；

5.2. API 测试 - Postman

方便测试API，免费版足够用了，支持账号同步，导入导出等等；

5.3. Color Pick

快速精确地从任何地方取色。

6. 其他工具

6.1. Linux客户端：MobaXterm

还在用putty? 试试MobaXterm吧，免费版支持保存20个session（节点、机器），足够用了；

  1. 集成了sftp，直接拖拽上传、下载文件
  2. 自带windows编辑器，不用vi了
  3. 多窗口模式
  4. 很好很强大… …

6.2. 远程连接： Remote Desktop Connection Manager

如果有大量的虚机、PC等需要远程连接使用，那这个工具就是很必要的。
微软的工具，虽说没什么更新了，但是很实用：

  1. 分组管理、保存用户、密码，支持继承用户名、密码（实验室机器一般用户名、密码都是一样的吧）

RQ

Posted on

ASP.NET Core MVC 入门到精通 - 3. 使用MediatR

环境：

  • .NET 5
  • ASP.NET Core MVC (project)

1. MediatR

MediatR .NET中的简单中介者模式实现，一种进程内消息传递机制（无其他外部依赖）。支持以同步或异步的形式进行请求/响应，命令，查询，通知和事件的消息传递，并通过C#泛型支持消息的智能调度。

Simple mediator implementation in .NET
In-process messaging with no dependencies.
Supports request/response, commands, queries, notifications and events, synchronous and async with intelligent dispatching via C# generic variance.

另：中介者模式 - 定义一个中介对象来封装一系列对象之间的交互，使原有对象之间的耦合松散，且可以独立地改变它们之间的交互。中介者模式又叫调停模式，它是迪米特法则的典型应用。

2. 安装 & 配置

对于.NET5 (.net core), 使用nuget 安装MediatR.Extensions.Microsoft.DependencyInjection.

配置：

1
2
3
4
5
public void ConfigureServices(IServiceCollection services)
{
    services.AddControllersWithViews();
    services.AddMediatR(typeof(Startup));
}

3. MediatR消息类型

3.1. Notifications 通知模式

Notifications 通知模式用于生产者发送通知，消费者（可以多个）接收到通知后，进行后续处理。
例：一个APS.NET 页面，访问时，发送Notifications通知；消费者简单记录收到通知的时间。

3.1.1. 定义基于INotification的通知类

1
public class Ping : INotification { }

3.1.2. 定义消费者（关注通知的处理方法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Pong1 : INotificationHandler<Ping>
{
    public Task Handle(Ping notification, CancellationToken cancellationToken)
    {
        Debug.WriteLine($"Pong1, {DateTime.Now}");
        return Task.CompletedTask;
    }
}

public class Pong2 : INotificationHandler<Ping>
{
    public Task Handle(Ping notification, CancellationToken cancellationToken)
    {
        Debug.WriteLine($"Pong2, {DateTime.Now}");
        return Task.CompletedTask;
    }
}

3.1.3. 发送消息通知

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 基于dotnet core的依赖注入，注入IMediator对象
private readonly IMediator _mediator;
public HomeController(ILogger<HomeController> logger, IMediator mediator)
{
    _logger = logger;
    _mediator = mediator;
}


public async Task<IActionResult> IndexAsync()
{
    // e.g. 访问首页时，发送通知
    await _mediator.Publish(new Ping());
    return View();
}

3.1.4. 输出

1
2
3
Pong1, 5/27/2021 4:37:18 PM
Pong2, 5/27/2021 4:37:18 PM

3.2. Request/Response 请求响应模式

request/response用于命令和查询的场景。

3.2.1. 创建请求类：

1
2
3
public class RequestModel: IRequest<string>
{
}

3.2.2. 创建请求处理类

不同于通知模式，request/response只能有一个请求处理。

1
2
3
4
5
6
7
public class RequestHandeler : IRequestHandler<RequestModel, string>
{
    public Task<string> Handle(RequestModel request, CancellationToken cancellationToken)
    {
        return Task.FromResult($"Pong {DateTime.Now}"); // 测试，返回内容给request
    }
}

3.2.3. 页面中发送请求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private readonly ILogger<HomeController> _logger;
private readonly IMediator _mediator;

public HomeController(ILogger<HomeController> logger, IMediator mediator)
{
    _logger = logger;
    _mediator = mediator;
}

public async Task<IActionResult> IndexAsync()
{
    // send request, and show Response
    var response = await _mediator.Send(new RequestModel());
    Debug.WriteLine("Got response in controller: " +response);

    return View();
}

3.2.4. 输出

1
Got response in controller: Pong 5/28/2021 2:04:26 PM

4. 总结

  • MediatR是一种进程内消息传递机制。
  • 支持以同步或异步的形式进行请求/响应，命令，查询(CQRS)，通知和事件的消息传递，并通过C#泛型支持消息的智能调度。
  • 其核心是消息的解耦。
  • 应用场景: 实现CQRS、EventBus等。

5. 参考 & 代码

ASP.NET Core MVC 入门到精通 - 3. 使用MediatR

RQ

Posted on

算法 - 计算汉明距离

1. 题目

给出两个整数 x 和 y，计算它们之间的汉明距离。

汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以d（x,y）表示两个字x,y之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。
示例:

  • 输入: x = 1, y = 8
  • 输出: 2
  • 解释:
1
2
3
1   (0 0 0 1)
8   (1 0 0 0)
     ↑     ↑

上面的箭头指出了对应二进制位不同的位置。

2. 代码

2.1. C#

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int HammingDistance(int x, int y) {
        var n = x ^ y;

        // 计算1的个数
        var counter = 0;
        while(n>0){
            n = n & (n-1);
            counter ++;
        }
        return counter;
    }
}

2.2. Javascript

1
2
3
4
5
6
7
8
9
var hammingDistance = function(x, y) {
    let n = x^y;
    let counter = 0;
    while(n){
        counter ++;
        n = n & (n-1);
    }
    return counter;
};

3. 另：计算二进制数字中1的个数

一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。
因此，一个整数的二进制有多少个1，就可以进行多少次这样的操作。

1
2
3
4
5
let counter = 0;
while(n){
    counter ++;
    n = n & (n-1);
}

算法 - 计算汉明距离

Posted on

内插字符串

类似于string.Format方法，但使用简单，方便，e.g.

1
string str = $"Hello {name}, NumTimes is: {DateTime.Now}";

NuGet

NuGet 常用命令

  1. Install-Package XXXX

常用包

  1. EF Core: Microsoft.EntityFrameworkCore.SqlServer

Posted on

1. ASP.NET Core MVC 概述

ASP.NET Core MVC 框架是轻量级、开源、高度可测试的演示框架，并针对 ASP.NET Core 进行了优化。

2. ASP.NET Core MVC路由

ASP.NET Core MVC 建立在 ASP.NET Core 的路由之上，是一个功能强大的 URL 映射组件，可用于生成具有易于理解和可搜索 URL 的应用程序。

MVC 中的路由包含下面2中方式

  1. 基于约定的路由
  2. 属性路由

2.1. 注册

所有 ASP.NET Core 模板都包括生成的代码中的路由。 路由在 Startup.Configure 中的中间件管道中进行注册。

1
2
3
4
public void Configure(IApplicationBuilder app, IWebHostEnvironment env)
{
    app.UseRouting();
}

2.2. 基于约定的路由

基于约定的路由，可以全局定义应用程序接受的 URL 格式，并说明每种格式如何映射到给定控制器上的特定操作方法。 接收传入请求时，路由引擎分析 URL 并将其匹配到定义的 URL 格式之一，然后调用关联的控制器操作方法。

Configre 方法中，定义约定路由：

1
2
3
4
5
6
app.UseEndpoints(endpoints =>
{
    endpoints.MapControllerRoute(
        name: "default",
        pattern: "{controller=Home}/{action=Index}/{id?}");
});

{controller=Home}/{action=Index}/{id?}, 含义是默认Controller是Home，默认action为Controller中的Index方法（Action）。

2.3. 属性路由

属性路由，可以通过用定义应用程序路由的属性修饰控制器和操作来指定路由信息。 这意味着路由定义位于与之相关联的控制器和操作旁。

1
2
3
4
5
6
7
8
9
[Route("api/[controller]")]
public class ProductsController : Controller
{
    [HttpGet("{id}")]
    public IActionResult GetProduct(int id)
    {
      // url等同于 api/Products/{id}
    }
}
0%