SnowMoon-Haoyu's Blog

发表于 2021-09-01 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 动态规划

剑指 Offer 42. 连续子数组的最大和难度简单输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例1: 123输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。提示： 1 <= arr.length <= 10^5 -100 <= arr[i] <= 100 注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/ 12345678910111213141516171819202122232425262728293031/* 假设数组为[-2,1,-3,4,-1,2,1,-5,4]，分解每一步问题： [-2,1,-3,4,-1,2,1,-5,4] -> 6 [-2,1,-3,4,-1,2,1,-5] -> 6 [-2,1,-3,4,-1,2,1] -> 6 [-2, ...

剑指offer11——动态规划（简单）

发表于 2021-08-31 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 动态规划

剑指 Offer 10- I. 斐波那契数列难度简单写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下： 12F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。示例 1： 12输入：n = 2输出：1 示例 2： 12输入：n = 5输出：5 提示： 0 <= n <= 100 思路与题解 **状态定义：**F[i]为第i个斐波那契数列的数字转移方程：F[i]=F[i−1]+F[i−2]F[i] = F[i-1]+F[i-2]F[i]=F[i−1]+F[i−2] 初始状态：F[0]=0;F[1]=1F[0]=0;F[1]=1F[0]=0;F[1]=1 **计算顺序：**从0开始向目标迭代代码 12345678910111 ...

动态规划问题的常规解法

发表于 2021-08-30 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 动态规划

前言：最近刷剑指offer刷到了动态规划相关的问题，之前没怎么学过，所以特地抽一天时间来学一下，以下为学习的笔记动态规划题目类型 1. 计数：有多少种方式走到右下角有多少种方法选出k个数使得和为Sum 2. 求最大最小值：从左上角走到右下角路径的最大数字和最长上升子序列长度 3. 求存在性：取石子游戏，先手是否必胜能不能选出k个数使得和是Sum 解题步骤确定状态简单的说，就是解动态规划时需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，类似解数学题中，xyz代表什么一样，具体分为下面两个步骤：研究最优策略的最后一步化为子问题转移方程根据子问题定义直接得到初始条件和边界情况初始条件一般都是a[0]、a[1]这种，多看看边界条件主要是看数组的边界，数组越不越界计算顺序大部分从小到大迭代，精髓在于使用之前计算得到的结果 322. 零钱兑换给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总 ...

剑指offer刷题10——搜索与回溯算法（简单）

发表于 2021-08-29 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 先序遍历

剑指 Offer 26. 树的子结构难度中等输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构，即 A中有出现和B相同的结构和节点值。例如: 给定的树 A: 3 / \ 4 5 / \ 1 2 给定的树 B： 4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。示例 1： 12输入：A = [1,2,3], B = [3,1]输出：false 示例 2： 12输入：A = [3,4,5,1,2], B = [4,1]输出：true 限制： 10 <= 节点个数 <= 10000 思路采用递归判断的方法比较好撸，先序遍历树A的所有节点，判断每个节点的子树是否包含树B recur(A, B) 函数：终止条件：当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ；当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ；当节点 A 和 B 的值不同：说明匹配失败，返回 false ；返回值：继续 ...

剑指offer刷题9——搜索与回溯算法（简单）

发表于 2021-08-28 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 层序遍历

剑指 Offer 32 - II. 从上到下打印二叉树 II 难度简单从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。例如: 给定二叉树: [3,9,20,null,null,15,7], 12345 3 / \9 20 / \ 15 7 返回其层次遍历结果： 12345[ [3], [9,20], [15,7]] 提示：节点总数 <= 1000 注意：本题与主站 102 题相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 解题思路：建议先做面试题32 - I. 从上到下打印二叉树再做此题，两题仅有微小区别，即本题需将每一层打印到一行。 I. 按层打印：题目要求的二叉树的从上至下打印（即按层打印），又称为二叉树的广度优先搜索（BFS）。BFS 通常借助队列的先入先出特性来实现。 II. 每层打印到一行：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。代码 123 ...

剑指offer刷题7——搜索与回溯算法（简单）

发表于 2021-08-27 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 层序遍历

剑指 Offer 32 - I. 从上到下打印二叉树难度中等从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如: 给定二叉树: [3,9,20,null,null,15,7], 12345 3 / \9 20 / \ 15 7 返回： 1[3,9,20,15,7] 提示：节点总数 <= 1000 思路层序遍历。特殊情况：树为空，直接返回一个空容器算法流程：将根节点入队，进入循环队头元素出队的同时队头元素的左右非空节点入队，同时将队头元素的数值推入返回的容器内。代码 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solu ...

剑指offer刷题7——查找算法（中等）

发表于 2021-08-26 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer

剑指 Offer 50. 第一个只出现一次的字符难度简单在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。示例: 12345s = "abaccdeff"返回 "b"s = "" 返回 " " 限制： 10 <= s 的长度 <= 50000 思路建立一个大小为 26 的数组统计字符串中各个字母出现的次数，遍历字符串，将第一个出现次数为1的字母输出，没有则输出空格’ ’ 代码 12345678910111213class Solution {public: char firstUniqChar(string s) { int CHAR[26] = {0}; int i; for( i = 0; i < s.size(); i++ ) CHAR[s[i]-'a']++; for( i = 0 ...

剑指offer刷题6——查找算法（中等）

发表于 2021-08-25 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 二分查找

剑指 Offer 11. 旋转数组的最小数字难度简单把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。示例 1： 12输入：[3,4,5,1,2]输出：1 示例 2： 12输入：[2,2,2,0,1]输出：0 注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/ 思路解题思路：为精简篇幅，本文将数组 numbers 缩写为 nums。如下图所示，寻找旋转数组的最小元素即为寻找右排序数组的首个元素 nums[x] ，称 x 为旋转点。排序数组的查找问题首先考虑使用二分法解决，其可将遍历法的线性级别时间复杂度降低至对数级别。算法流程：初始化：声明 i, j 双指针分别指向 nums 数组左右两端；循环二分：设 m = (i + j) / ...

剑指offer刷题5——查找算法（中等）

发表于 2021-08-24 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 链表 • 二叉搜索树

剑指 Offer 04. 二维数组中的查找难度中等在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。示例: 现有矩阵 matrix 如下： 1234567[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]] 给定 target = 5，返回 true。给定 target = 20，返回 false。限制： 120 <= n <= 10000 <= m <= 1000 思路若使用暴力法遍历矩阵 matrix ，则时间复杂度为 O(NM)O(NM) 。暴力法未利用矩阵 “从上到下递增、从左到右递增” 的特点，显然不是最优解法。刚开始的想法是行内做二分，列内也做二分，每次排除四分之三的数据，然后发现等矩阵小了之后好像就不方便找了， ...

剑指offer刷题4——字符串（简单）

发表于 2021-08-23 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 字符串

剑指 Offer 05. 替换空格难度简单152收藏分享切换为英文接收动态反馈请实现一个函数，把字符串 s 中的每个空格替换成"%20"。示例 1： 12输入：s = "We are happy."输出："We%20are%20happy." 限制： 10 <= s 的长度 <= 10000 思路建立一个大小为3*Size（保证足够用来替换）的新的字符串str，遍历s并复制进入str中，每次遇到空格就复制"%20"，最后新建一个大小为替换后的字符数的字符串STR，把str中有效位复制进STR并返回代码 1234567891011121314151617181920212223class Solution {public: string replaceSpace(string s) { int i,Size,j; Size = s.length(); string str(3*Size,'0' ...

剑指offer刷题3——链表2（简单）

发表于 2021-08-22 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 链表

剑指 Offer 24. 反转链表难度简单定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。示例: 12输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL 限制： 10 <= 节点个数 <= 5000 1.迭代（双指针）考虑遍历链表，并在访问各节点时修改 next 引用指向，算法流程见注释。复杂度分析：时间复杂度 O(N)O(N) ：遍历链表使用线性大小时间。空间复杂度 O(1)O(1) ：变量 pre 和 cur 使用常数大小额外空间。代码 123456789101112131415161718192021222324/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {&# ...

剑指offer刷题2——链表1（简单）

发表于 2021-08-21 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 剑指offer • 链表

剑指 Offer 06. 从尾到头打印链表难度简单输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。示例 1： 12输入：head = [1,3,2]输出：[2,3,1] 限制： 10 <= 链表长度 <= 10000 通过次数277,964 提交次数369,505 思路辅助栈法：遍历整个链表，把所有元素压入堆栈中，最后把堆栈中的元素顺序弹出并存储到 Vector 容器中返回算法流程：入栈：遍历链表，将各节点值 push 入栈。出栈：将各节点值 pop 出栈，存储于Vector并返回。代码 12345678910111213141516171819202122232425262728/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */cl ...

剑指offer刷题1——栈与队列

发表于 2021-08-20 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法 • 堆栈 • 队列 • 剑指offer

剑指 Offer 09. 用两个栈实现队列难度简单用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 ) 示例 1： 1234输入：["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]输出：[null,null,3,-1] 示例 2： 1234输入：["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]输出：[null,-1,null,null,5,2] 提示： 1 <= values < ...

数据结构刷题笔记14

发表于 2021-08-19 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法

11-散列2 Hashing (25 分) The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(k**ey)=k**ey%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions. Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to ...

数据结构刷题笔记13

发表于 2021-08-18 | 更新于 2023-12-01 | SnowMoonの刷题记录 | 数据结构与算法

11-散列1 电话聊天狂人 (25 分) 给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。输入格式: 输入首先给出正整数N（≤105），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。输出格式: 在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。输入样例: 123456413005711862 1358862583213505711862 1308862583213588625832 1808792583215005713862 13588625832//结尾无空行输出样例: 1213588625832 3//结尾无空行代码本篇文章主要代码源自于陈越姥姥的课程里的小白专场 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565 ...