offer
剑指 Offer 56 - II. 数组中数字出现的次数 II
题目链接:剑指 Offer 56 - II. 数组中数字出现的次数 II 方法一:位运算 解题思路 由题意知,其他数值都出现了三次,那么其数值二进制位上的$1$也至少出现了三次,那么我们可以统计数值每一位上$1$的个数的总和,然后遍历每一位上$1$的数量,若某一位上的$1$的数量不能被$3$整除,说 ......
剑指 Offer 49. 丑数
题目链接:剑指 Offer 49. 丑数 方法:动态规划 解题思路 参考:剑指 Offer 49. 丑数(动态规划,清晰图解) 代码 class Solution { public: int nthUglyNumber(int n) { int a = 0, b = 0, c = 0; int dp ......
剑指 Offer 46. 把数字翻译成字符串
题目链接:剑指 Offer 46. 把数字翻译成字符串 方法:回溯、动态规划 解题思路 动态规划是回溯中“归”的过程; 思考回溯: (1)将$num$转换为字符串$s$; (2)对于当前位置$i$,可能有两种操作,将$s[i] => 字符$ 或 将$s[i, i + 1] => 字符$,即$dfs( ......
剑指 Offer 48. 最长不含重复字符的子字符串
题目链接:剑指 Offer 48. 最长不含重复字符的子字符串 方法:同向双指针 解题思路 初始化l = 0, r = 0; 右指针右移,直到[l, r]之间出现重复字符,然后将左指针右移,直到[l, r]之间没有重复字符; 即保证[l, r]窗口无重复字符,然后计算最大的窗口长度。 代码 clas ......
剑指 Offer 52. 两个链表的第一个公共节点
题目链接:剑指 Offer 52. 两个链表的第一个公共节点 方法一:两次遍历 解题思路 将两个单链表的遍历指针先置于同一起跑线(相对于相交的点),然后会同时遍历到相交的节点。 注意:模拟下方代码即可理解,第一次遍历长度为长的链表长度,第二次遍历长度为短的链表长度。 代码 class Solutio ......
剑指 Offer 42. 连续子数组的最大和
题目链接:剑指 Offer 42. 连续子数组的最大和 方法:动态规划 解题思路 参考动态规划详细解析——剑指 Offer 42. 连续子数组的最大和 注意: 很多同学首先会想到同向双指针,实际上本题由于$nums$数组的某一个元素的下一个元素可正可负,导致同向双指针要求的单调性无法满足; 使用$d ......
剑指 Offer 44. 数字序列中某一位的数字
题目链接:剑指 Offer 44. 数字序列中某一位的数字 方法:找规律 解题思路 找第$n$位对应的数为几位数; 找该数的具体值; 找第$n$位在该数中的第几位。 {:style="width:500px"} 代码 class Solution { public: int findNthDigit ......
剑指 Offer 41. 数据流中的中位数
题目链接:剑指 Offer 41. 数据流中的中位数 方法一:插入排序 解题思路 每次添加一个数字时,通过插入排序添加,需要返回中位数时,根据元素个数进行返回。 代码 class MedianFinder { private: vector<int> nums; public: /** initia ......
剑指 Offer 40. 最小的k个数
题目链接:剑指 Offer 40. 最小的k个数 方法:排序 解题思路 基于比较的排序,最低时间复杂度为$O(nlogn)$,空间复杂度为$O(1)$; 哈希计数,时间复杂度为$O(n)$,但需要额外的空间。 代码 // 基于比较的排序 class Solution { public: vector ......
剑指 Offer 37. 序列化二叉树
题目链接:剑指 Offer 37. 序列化二叉树 取巧做法 class Codec { private: TreeNode* root; public: // Encodes a tree to a single string. string serialize(TreeNode* root) { ......
剑指 Offer 36. 二叉搜索树与双向链表
题目链接:剑指 Offer 36. 二叉搜索树与双向链表 方法一:回溯 解题思路 {:width=1000} 代码 class Solution { private: int mx = INT_MIN, mi = INT_MAX; Node* start = NULL, * end = NULL; ......
剑指 Offer 33. 二叉搜索树的后序遍历序列
题目链接:剑指 Offer 33. 二叉搜索树的后序遍历序列 方法:分治 解题思路 首先假设该序列能够构成某个二叉搜索树的后序遍历序列,那么这个序列会被分成3个部分:左子树序列,右子树序列,父节点,其中左右子树节点数可能为0; 现在就可以检查该序列是否符合这个规律,然后递归的判断子树是否符合规律。 ......
剑指 Offer 51. 数组中的逆序对
题目链接:剑指 Offer 51. 数组中的逆序对 方法一:归并排序 解题思路 逆序对:即后面的数大于前面的数; 归并排序: 先分,在此过程中会先递归的将序列分为一段一段序列,并且每段序列之间的先后顺序是不变的。 再治,也即归并,归并的过程中会将两段序列进行比较$(A,B,B在A的后面)$,当出现$ ......
剑指 Offer 20. 表示数值的字符串
题目链接:剑指 Offer 20. 表示数值的字符串 方法:模拟 解题思路 根据题意模拟,详情见代码注释。 代码 class Solution { public: bool isDecimal(string s){ int first_symbol = s.find_first_of('.'); / ......
剑指 Offer 47. 礼物的最大价值
题目链接:剑指 Offer 47. 礼物的最大价值 方法:动态规划 解题思路 $当前位置的最大价值 = max(上方格子的最大价值,左边格子的最大价值) + 当前位置的价值$,即局部最优可以推出全局最优,简单递推即可。 代码 class Solution { public: int maxValue ......
剑指 Offer 19. 正则表达式匹配
题目链接:剑指 Offer 19. 正则表达式匹配 方法:动态规划 解题思路 详情见:逐行详细讲解,由浅入深,dp和递归两种思路 代码 class Solution { public: bool isMatch(string s, string p) { int n = s.size(), m = ......
Leetcode(剑指offer专项训练)——DFS/BFS专项(1)
计算除法 题目 给定一个变量对数组 equations 和一个实数值数组 values 作为已知条件,其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 另有一些以数 ......
剑指offer66(Java)-构建乘积数组(中等)
题目: 给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 示例: 输入: [1,2,3,4,5]输出: ......
剑指offer03(Java)-数组中重复的数字(简单)
题目: 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入:[2, 3, 1, 0, 2, 5, 3]输出:2 或 3 限 ......
力扣---剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]Output: [3,9,20,null,nul ......
剑指 Offer 16. 数值的整数次方
题解链接:剑指 Offer 16. 数值的整数次方 方法一:迭代实现快速幂 解题思路 通过迭代的方法,自下向上实现快速幂求解过程,初始化结果 $res = 1$,底数 $t = x$ ,幂次为 $n$。当 $n$ 为奇数时,$res = res * t$,先乘上一个 $t$,此时还有 $n-1$ 个 ......
剑指 Offer 15. 二进制中1的个数
题目链接:剑指 Offer 15. 二进制中1的个数 方法一:位运算 解题思路 x = n & -n,$x$ 表示 $n$ 的最后一位 $1$ 所对应的值,每减去一次 $x$,相当于有一个 $1$,$res ++$ 。 代码 class Solution { public: int hammingW ......
用 Go 剑指 Offer 29. 顺时针打印矩阵
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 1: 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]输出:[1,2,3,6,9,8,7,4,5]示例 2: 输入:matrix = [[1,2,3,4],[5,6,7, ......
一个人的职业生涯之旅 —— 应届生求职、面试、Offer、跳槽(发展瓶颈、薪资倒挂、职业倦怠、骑驴找马、简历优化)问题分享
一、应届生求职问题1、求职平台1、Boss直聘 2、前程无忧 3、拉勾网 4、应届生求职网站_最新更新校园招聘/实习机会/内推资讯_牛客网_牛客网_牛客网 2、简历怎么写2.1、简历照片 1、要与本人形象相符,不要看上去有较大差别,使用最近半年内的免冠照片,选择能够显示自己气质佳的照片,但不要有太大 ......
用 Go 剑指 Offer 17. 打印从1到最大的n位数
输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: n = 1输出: [1,2,3,4,5,6,7,8,9] 说明: 用返回一个整数列表来代替打印n 为正整数通过次数251,223提交次数323,027 ......
用 Go 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。 示例: 输入:nums = [1,2,3,4]输出:[1,3,2,4] 注:[3,1,2,4] 也是正确的答案之一。 提示: 0 <= nums.length <= 500000 <= ......
用 Go 剑指 Offer 11. 旋转数组的最小数字
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到:若旋转 4 次,则可以得到 [4,5,6,7,0,1,4]若旋转 7 次,则可以得到 [0,1,4,4,5,6,7]注意,数组 [ ......
剑指offer004(Java)-只出现一次的数字(中等)
题目: 给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 示例1: 输入:nums = [2,2,3,2] 输出:3 示例 2: 输入:nums = [0,1,0,1,0,1,100] 输出:100 提示: 1 <= nu ......
剑指 Offer 14- II. 剪绳子 II
题目链接:剑指 Offer 14- II. 剪绳子 II 方法:数论 解题思路 将 $n$ 分为 $m$ 个数的和,使得这 $m$ 个数的乘积最大,那么应该将 $m$ 个数分为 $2$ 和 $3$ 的组合, 尽可能为 $3$。注意大数越界问题。 代码 class Solution { public: ......
剑指 Offer 14- I. 剪绳子
题目链接: 剑指 Offer 14- I. 剪绳子 方法:数论 解题思路 将 $n$ 分为 $m$ 个数的和,使得这 $m$ 个数的乘积最大,那么应该将 $m$ 个数分为 $2$ 和 $3$ 的组合, 尽可能为 $3$。 代码 class Solution { public: int cutting ......