HespethornのBlog

33. Search in Rotated Sorted Array题目Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of O(log n). Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums...

28. Find the Index of the First Occurrence in a StringGiven two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: 1234Input: haystack = "sadbutsad", needle = "sad"Output: 0Explanation: "sad" occurs at index 0 and 6.The first occurrence is at index 0, so we return 0. Example 2: 123Input: haystack = "leetcode", needle = "leeto"Output: -1Explanation:...

27. Remove Element给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。 返回 k。 用户评测： 评测机将使用以下代码测试您的解决方案： 123456789101112int[] nums = [...]; // 输入数组int val = ...; // 要移除的值int[] expectedNums = [...]; // 长度正确的预期答案。 // 它以不等于 val 的值排序。int k = removeElement(nums, val); // 调用你的实现assert k == expectedNums.length;sort(nums, 0, k); // 排序...

26. Remove Duplicates from Sorted Array给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过： 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 判题标准: 系统会用下面的代码来测试你的题解: 123456789int[] nums = [...]; // 输入数组int[] expectedNums = [...]; // 长度正确的期望答案int k = removeDuplicates(nums); // 调用assert k == expectedNums.length;for (int i = 0; i < k; i++) { assert...

25. K 个一组翻转链表给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 示例 1： 12输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5] 示例 2： 12输入：head = [1,2,3,4,5], k = 3输出：[3,2,1,4,5] 解题思路：「K 个一组翻转链表」的核心思路是： 分组遍历：每次取 K 个节点作为一组，若不足 K 个则停止。 翻转每组：对当前 K 个节点进行翻转。 连接各组：将翻转后的组与前一组连接，更新指针继续处理下一组。 具体步骤： 用 dummy 虚拟头节点简化边界处理（避免头节点特殊逻辑）。 用 pre 记录上一组的尾节点（翻转后作为连接点）。 用 end 遍历并检查当前组是否有 K 个节点。 翻转当前组后，重新连接 pre 与翻转后的组，并更新 pre 和...

引言：字符串性能的关键挑战在 C++ 开发中，std::string作为最常用的容器之一，其性能直接影响整体程序效率。传统字符串实现采用动态内存分配策略，无论字符串长度如何，都需要在堆上分配空间，这会带来： 内存分配 / 释放的开销 缓存局部性不佳 小字符串场景下的效率低下 短字符串优化（Short String Optimization, SSO）正是为解决这些问题而生的关键技术，已成为现代 C++ 标准库（如 libstdc++、libc++）的标配实现策略。 一、SSO 的核心原理1.1 传统字符串实现的缺陷传统std::string（C++11 之前）通常采用 "胖指针" 结构： 123456// 传统字符串实现（概念模型）struct String { char* data; // 指向堆内存的指针 size_t length; // 字符串长度 size_t capacity; // 已分配容量}; 这种结构对短字符串极不友好，例如存储 "hello"...

24. Swap Nodes in PairsGiven a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.) Example 1: Input: head = [1,2,3,4] Output: [2,1,4,3] Explanation: Example 2: Input: head = []$ Output: [] Example 3: Input: head = [1] Output: [1] Example 4: Input: head = [1,2,3] Output: [2,1,3] 题目大意给定一个链表，要求两两交换相邻节点（如 1→2→3→4 变为...

Python的交互式编程是学习和实验Python代码的强大工具。通过Python的交互式解释器（REPL），开发者可以逐行执行代码、即时查看结果，非常适合初学者入门和快速原型开发。 一、Python交互式解释器1. 启动交互式解释器在终端或命令行中直接输入python或python3即可启动： 1234$ pythonPython 3.11.0 (default, ...)Type "help" for more information.>>> 2. 基本操作12345678910111213# 直接计算>>> 2 + 24# 变量赋值>>> x = 10>>> y = 20>>> x + y30# 调用函数>>> print("Hello, World!")Hello, World! 3. 退出交互式解释器1234>>> exit()# 或者>>> quit()# 或者按...

23. 合并 K 个升序链表给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1： 12345678910输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6 示例 2： 12输入：lists = []输出：[] 示例 3： 12输入：lists = [[]]输出：[] 题目大意多个有序链表的合并，使用归并排序整理有序链表，更优秀的思考是采用优先级队列（小根堆）来排序。归并可以看21题。 解题思路解法一：分治法（两两合并）思路核心借鉴「归并排序」的分治思想，将 K 个链表逐步拆分为成对的子问题，合并后再递归 / 迭代合并结果，减少重复比较次数。 步骤拆解边界处理：若 lists 为空，直接返回...

22. Generate Parentheses题目Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] 题目大意给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。 解题思路 这道题乍一看需要判断括号是否匹配的问题，如果真的判断了，那时间复杂度就到 O(n * 2^n)了，虽然也可以 AC，但是时间复杂度巨高。 这道题实际上不需要判断括号是否匹配的问题。因为在 DFS 回溯的过程中，会让 ( 和 )...

21. 合并两个有序链表将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： 12输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4] 示例 2： 12输入：l1 = [], l2 = []输出：[] 示例 3： 12输入：l1 = [], l2 = [0]输出：[0] 题目大意需要将两个升序排列的链表合并成一个新的升序链表，新链表由原两个链表的所有节点组成，且保持升序排列。 解题思路 使用虚拟头节点（dummy node）简化边界情况处理 双指针遍历两个链表，比较当前节点值，将较小的节点接入结果链表 当一个链表遍历完毕后，将另一个链表的剩余部分直接接入结果链表 这种方法的时间复杂度为 O (n + m)，其中 n 和 m 分别是两个链表的长度，空间复杂度为 O (1)，仅使用了常数个额外节点。 1234567891011121314151617181920212223242526272829303132333435363738/** * Definition for...

20. Valid ParenthesesGiven a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. 题目大意给定一个只包含 '('、')'、'{'、'}'、'[' 和...

一、写时复制核心概念写时复制 (简称 COW) 是一种资源管理优化技术，其核心思想是：当多个对象需要共享同一资源时，直到其中一个对象需要修改资源前，都不需要真正复制资源，仅在修改时才创建资源的私有副本。 这种机制通过延迟复制操作，减少了不必要的内存分配和数据拷贝，从而提高程序性能，尤其适用于： 频繁复制但很少修改的场景 内存资源宝贵的环境 大型数据结构的共享访问 二、写时复制实现三要素1. 共享数据存储需要一个独立的共享数据结构，存储实际的数据内容。 1234567template <typename T>struct SharedData { T* data; // 实际数据指针 size_t size; // 数据大小 size_t ref_count; // 引用计数 // 其他元数据...}; 2. 引用计数机制通过引用计数跟踪当前有多少对象共享该资源： 当新对象共享资源时，引用计数 + 1 当对象销毁或不再共享时，引用计数 - 1 当引用计数为 0...

19. Remove Nth Node From End of ListGiven the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: 12Input: head = [1,2,3,4,5], n = 2Output: [1,2,3,5] Example 2: 12Input: head = [1], n = 1Output: [] Example 3: 12Input: head = [1,2], n = 1Output: [1] 题目大意给定一个链表的头节点，要求删除链表的倒数第 N 个节点，并返回删除后的链表头节点。 解题思路可以使用双指针法高效解决这个问题，只需一次遍历： 定义两个指针 fast 和 slow，初始都指向虚拟头节点 先让 fast 指针向前移动 N 步 然后让 fast 和 slow 同时向前移动，直到 fast 到达链表末尾 此时 slow...

17. Letter Combinations of a Phone Number题目Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example: 12Input: "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although...

16. 3Sum Closest题目Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example: 123Given array nums = [-1, 2, 1, -4], and target = 1.The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 题目大意给定一个数组，要求在这个数组中找出 3 个数之和离 target 最近。 解题思路 初始值优化： 原代码中it初始化为...

Python的字符串方法是非常强大的工具，其中strip()系列方法是处理用户输入和字符串清洗时最常用的函数之一。本文将详细介绍Python字符串的strip()方法以及其他常用的字符串处理方法。 一、strip()方法详解1. 基本用法strip()方法用于移除字符串首尾两端的空白字符： 1234567891011# 基本用法text = " Hello, World! "print(f"'{text.strip()}'") # 输出：'Hello, World!'# 移除换行符text = "\nHello\n"print(f"'{text.strip()}'") # 输出：'Hello'# 移除制表符text = "\tHello\t"print(f"'{text.strip()}'") ...

15. 3Sum题目Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. Example: 1234567Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:[ [-1, 0, 1], [-1, -1, 2]] 题目大意给定一个数组，要求在这个数组中找出 3 个数之和为 0 的所有组合。 解题思路用 map 提前计算好任意 2 个数字之和，保存起来，可以将时间复杂度降到...

14. Longest Common Prefix题目Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: strs = ["flower","flow","flight"] Output: "fl" Example 2: Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. Constraints: 1 <= strs.length...

12. Integer to Roman题目Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. 12345678Symbol ValueI 1V 5X 10L 50C 100D 500M 1000 For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. Roman numerals are usually written largest to smallest from...