合并区间

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

题目

• 给定一个数12445和一个数组[1,2,4]，可以重复使用，求能组成的 小于给定数 n 的最大整数

golang
package main

import (
	"fmt"
	"sort"
	"strconv"
)

func maxLessThan(n int, digits []int) int {
	sort.Ints(digits)

	s := []byte(strconv.Itoa(n))
	m := len(s)

	res := make([]byte, m)

	for i := 0; i < m; i++ {
		cur := int(s[i] - '0')

		// 找 <= cur 的最大数字
		idx := upperBound(digits, cur) - 1

		if idx >= 0 {
			res[i] = byte(digits[idx] + '0')

			// 当前位已经小于 n，后面全部填最大数
			if digits[idx] < cur {
				fillMax(res, i+1, digits[len(digits)-1])
				return toInt(res)
			}
		} else {
			// 当前位放不了，向前回退
			return backtrack(res, i, digits)
		}
	}

	// res == n，需要继续回退，保证严格小于 n
	return backtrack(res, m, digits)
}

func backtrack(res []byte, pos int, digits []int) int {
	for i := pos - 1; i >= 0; i-- {
		cur := int(res[i] - '0')

		idx := lowerBound(digits, cur) - 1
		if idx >= 0 {
			res[i] = byte(digits[idx] + '0')
			fillMax(res, i+1, digits[len(digits)-1])
			return toInt(res)
		}
	}

	// 无法组成同位数，只能少一位
	if len(res) == 1 {
		return -1
	}

	ans := 0
	for i := 0; i < len(res)-1; i++ {
		ans = ans*10 + digits[len(digits)-1]
	}
	return ans
}

func fillMax(res []byte, start int, maxDigit int) {
	for i := start; i < len(res); i++ {
		res[i] = byte(maxDigit + '0')
	}
}

func toInt(res []byte) int {
	ans, _ := strconv.Atoi(string(res))
	return ans
}

// 第一个 > target 的位置
func upperBound(arr []int, target int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := l + (r-l)/2
		if arr[mid] <= target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

// 第一个 >= target 的位置
func lowerBound(arr []int, target int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := l + (r-l)/2
		if arr[mid] < target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

func main() {
	fmt.Println(maxLessThan(2533, []int{2, 3, 5})) // 2525
	fmt.Println(maxLessThan(1000, []int{1, 2, 9})) // 999
	fmt.Println(maxLessThan(345, []int{3, 4, 5}))  // 344
	fmt.Println(maxLessThan(111, []int{1}))        // 11
	fmt.Println(maxLessThan(5, []int{7, 8}))       // -1
}

最长递增子序列

什么是最长递增序列

• 比如给定的list是[10,9,2,5,3,7,101,18] 那么最大的最长递增序列是[2,3,7,101]
  • 想要实现就要知道这个递增，并非要求连续递增，也就是说，中间不符合的
• 给定[0,1,0,3,2,3]，那么最长递增子序列[0,1,2,3]
• 最后返回值，给定对应的最长子序列的长度即可

具体实现

方法一：相对更优（贪心 + 二分查）

• 实现思路
  • 初始化子序列列表
  • 遍历给定列表
    • 每个数判断在子序列中的位置
    • 超出已有位置，追加到子序列
    • 小于子序列中某个位置的值，替换该位置即可
• 时间复杂度： nlogn

golang
func longestList(arr []int) int {
    list := []int
    for _, num := range arr {
        l,r := 0, len(list)
        for l < r {
            mid = l + (r-l)/2
            if list[mid] < num {
                l = mid + 1
            }else{
                r = mid
            }
        }

        if l = len(list) {
            list = append(list, num)
        }else{
            list[l] = num
        }
    }
    return len(list)
}

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

实现思路

• 维护双指针从左到右
• 同时维护更新最大值
• 移动短板方式
  • 左边小则往左移
  • 右边移则往右移

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解题思路

• 先排序
• 双层循环
  • 外层遍历作为第一个数的选择
  • 内层通过左右指针往内靠，找到另外两个数
• 不管是内外层，重复的出现的数都跳过不计算

算法：无重复字符的最长连续子串

通过滑动窗口实现，但需要注意是窗口内不能出现重复字符

实现思路

• 通过双指数构建一个滑动窗口，以及map集合判断重复性
• 将string转化为[]rune, 兼容字符串可能包含汉字的问题
• 窗口更新条件
  • 无重复字符时，right一直向右移动
  • 出现重复字符时，需要判断重复字符的旧key是否存在于窗口内
    • 存在窗口内，才被判断为当前窗口内的重复
  • 一旦窗口变大，直接更新窗口最大值或者最大窗口的起始结束位置

代码实现

js
func lengthOfLongestSubstring(s string) int {
    runes := []rune(s) // 支持 Unicode（中文等）
    lastIndex := make(map[rune]int)

    left := 0
    maxLen := 0

    for right, ch := range runes {
        if prev, exists := lastIndex[ch]; exists && prev >= left {
            left = prev + 1
        }

        lastIndex[ch] = right

        if currLen := right - left + 1; currLen > maxLen {
            maxLen = currLen
        }
    }

    return maxLen
}

rag篇

如何评估一个rag系统的好坏

• 首先是检索相关性（找到的内容是否包含答案）
• 其次是生成质量，这又可以细分为
  • 语义准确性（回答的意思是否正确）
  • 词汇匹配度（专业术语是否使用得当）

如果优化rag

• 在性能层面，可以通过以下方式来提升效率和能力边界。
  • 索引分层（对高频数据启用缓存）
  • 多模态扩展（支持图像/表格检索）
• 在架构层面，简单的线性流程正在被更复杂的设计模式所取代

  • 通过分支模式并行处理多路检索

  • 或通过循环模式进行自我修正

embedding 模型的作用是什么

将文本映射到一个能够表达语义信息的向量空间中，使语义相似的文本在向量空间中的距离更近。

• 示例解释
  • 苹果手机多少钱和iphone的价格是多少
  • 虽然文字字面不同，但是语义是相同的
  • 转为向量后，向量距离会很近

prompt、rag、skill和微调的区别

• promt 的目标是如何用好llm现有的能力
• rag 是通过外部知识库，来解决llm 无法获取实时信息的问题
• 微调 是调整底层具备的能力、风格，是模型群众的重塑
• skill 的话是行为能力的一种延伸

如何选择

• 当你在工程落地中面临选择时，可以依次问自己以下几个问题：
• 模型现有的知识和能力够用吗？
  • 够用 ➡️ 提示工程。
• 不够用，是因为缺乏特定/实时的垂直知识吗？
  • 是，需要看文档 ➡️ RAG。
• 不够用，是因为需要做数学计算、数据库查询等具体动作吗？
  • 是，需要连外部系统 ➡️ Skill / Tool Calling。
• 模型什么都知道，但怎么和它说它都不听话、格式总是对不齐、或者想要极致的特定文风？
  • 是，必须改造行为 ➡️ 微调。