- 博客(98)
- 收藏
- 关注
RSS订阅原创 Leetcode之 扰乱字符串
题目描述题目思路递归，首先判断两个字符串长度是否相等，若相等则记录字符串中字母出现次数是否相等，最后分两种情况判断：Case 1: S1左右两部分未交换，则分别判断S1和S2的前后两部分是否为扰动所得；Case 2: S1左右部分发生交换，则判断S1的前半部分和S2的后半部分是否为扰动所得，S1的后半部分和S2的前半部分是否为扰动所得动态规划代码方法一：class Solut...
2020-04-08 20:49:52
109
原创 Leetcode之 柱状图中最大的矩形
题目描述给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。思路暴力遍历，果然超时了分治法：代码方法一：class Solution {public: int largestRectangleArea(vector<int>& heights) { i...
2020-04-07 20:51:25
89
原创 Leetcode动态规划之 最大矩形
题目描述给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。思路动态规划：定义dp[i][j]表示以第i+1行第j+1字符结尾的只包含1的最大长度。若matrix[i][j]是0，则对应的dp为0，否则dp[i][j] = dp[i][j-1]+1。至此则再向上回溯，找到以第i+1行第j+1字符结尾的只包含1的最大矩形面积代码方法一：class ...
2020-04-07 04:25:42
373
原创 leetcode之 编辑距离
题目描述给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符思路动态规划，用dp[i][j]表示使得word1中第1-i位和word2中第1-j位相同的最少操作数，若word1[i-1] == word2[j-1]，则dp[i-1][j-1] = dp[i][j...
2020-04-02 05:06:36
94
原创 Leetcode之生命游戏
题目描述给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；如果活细胞周围八个位...
2020-04-02 04:30:54
61
原创 Leetcode动态规划之 最小路径和
题目描述给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。思路动态规划: dp[i][j] = grid[i][j] + min(dp[i-1][j]+dp[i][j-1])代码class Solution {public: int minPathSum(vector<vector...
2020-03-30 23:36:24
75
原创 Leetcode动态规划之 不同路过II
题目描述一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？思路动态规划: dp[i][j] = dp[i-1][j] + dp[i][j-1]若A[i][j]不是障碍，否则dp=0代码...
2020-03-30 23:25:40
60
原创 Leetcode动态规划之 不同路径
题目描述一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？思路动态规划：dp[i][j] = dp[i-1][j]+dp[i][j-1]排列组合：Cm+n−2m−1C_{m+n-2}^{m-1}Cm+n−2m−1代码cl...
2020-03-30 22:43:22
74
原创 Leetcode之 单词的压缩编码
题目描述给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表。那么成功对给定单词列表...
2020-03-28 03:27:59
141
原创 Leetcode之 删除排序数组中的重复项
题目描述给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。思路用count记录非重复数字，count_dup记录重复数字，从nums[1]开始遍历，若nums[i] == nums[i-1]，则count_dup++，并将nums[i]删掉，...
2020-03-26 20:41:42
64
原创 Leetcode之 车的可用捕获量
题目描述在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车...
2020-03-26 19:36:25
57
原创 Leetcode之 K个一组翻转链表
题目描述给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。思路递归法：首先从起点出发，找到第k个结点，若寻找途中链表到了NULL，则返回Head即可，不做修改；找到第k个结点定义为end，先保存end的下一个结点和head的下一个结点，之后将head->...
2020-03-26 05:12:28
68
原创 Leetcode之两两交换链表中的节点
题目描述给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。思路双指针法，一个指向奇数节点，一个指向偶数节点，定义一个新的链表，按照先偶后奇的顺序逐个插入（利用count来计数当前要插入奇数还是偶数）。需要注意的是，当两个指针都为NULL之后才终止代码class Solution {public: ListN...
2020-03-26 04:03:52
99
原创 Leetcode之合并K个排序链表
题目描述合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。思路首先遍历所有链表，将对应的数值保存到数组中，之后遍历数组创建新的链表即可分治：每个链表先与下一个链表融合，这样讲链表总数从k将至k/2，重复直至链表总数为1，返回头部指针即可代码方法一：class Solution {public: ListNode* mergeKLists(vector...
2020-03-25 23:59:57
846
原创 Leetcode之 括号生成器
题目描述给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。思路首先创建基本括号组合"((()))"，之后对该括号调换顺序获得更多组合：首先找到第一个右括号，将其向前一步一步移动直至第一个左括号后，生成的字符串均符合要求，可生成2个，即"(()())“和”()(())"对第一步生成的字符串，找到第二个右括号，同理，将其向前移动，最终能运动到的位置取...
2020-03-25 09:37:53
203
原创 Leetcode之 有效的括号
题目描述给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。思路第一感觉就是要用栈，左括号压入，右括号应当和栈顶的左括号匹配并弹出，否则返回false，若最终栈不为空也返回false代码方法一：class Solutio...
2020-03-25 05:37:23
60
原创 Leetcod之 删除链表的倒数第N个节点
题目描述给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。思路首先遍历链表记录长度，重新遍历至删除位置前一位，跳过删除位即可。这种方法需要遍历2次双指针遍历，一个指针A指向起点，当指针A前进n+1步时，指针B开始指向起点，当A到达结尾时，B恰巧指向待删除节点的前一位代码方法一：class Solution {public: ListNode* remov...
2020-03-24 20:16:52
57
原创 Leetcode之 电话号码的字母组合
题目描述给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。思路回溯：循环与递归的嵌套队列：首先压入第一个数字对应的字符，从第二个数字开始，将队列中的首字母逐个剔除并加上第二个数字对应的字符后加到队列尾部即可代码方法一：class Solution {public: vector&l...
2020-03-24 19:09:59
81
原创 Leetcode之 最接近的三数之和
题目描述给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。思路与三数之和思路类似，只不过加一个误差判断，返回最小误差代码方法一：class Solution {public: int threeSumClosest(vector<i...
2020-03-24 18:42:40
49
原创 Leetcode之 按摩师
题目描述一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。思路逆推法，从结尾往前推，定义一个数组sum_max，其中sum_max[i]表示从i位置之后的最长总预约时长，我们发现:sum_max[i] = nums[i] + m...
2020-03-24 01:45:37
78
原创 Leetcode之 整数转罗马数字
题目描述给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。思路首先将数字转化为字符串，逐个处理，调用help函数即可代码class Solution {public: string Help(string s, int i, int len) { string record = "IVXLCDMT"; string ...
2020-03-24 00:51:44
55
原创 Leetcode之盛最多水的容器
题目描述给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。思路双指针法，分别指向首位，计算出此时首位围成的面积，若首大于尾，则尾部移动，否则移动首部代码方法一：class Solution...
2020-03-23 22:02:14
62
原创 Leetcode之 字符串转换整数 (atoi)
题目描述请你来实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字...
2020-03-23 02:09:59
51
原创 Leetcode之 链表的中间结点
题目描述给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。思路利用栈，先压入统计链表大小，之后弹出至中间位利用数组，先统计大小，然后返回中间位快慢指针法，用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。代码方法一：c...
2020-03-23 01:07:02
50
原创 Leetcode之 Z字形变换
题目描述将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：L C I RE T O E S I I GE D H N之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。思路...
2020-03-22 07:27:43
68
1
原创 Leetcode之 使数组唯一的最小增量
题目描述给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。返回使 A 中的每个值都是唯一的最少操作次数。思路暴力解法：从前到后遍历数组，利用Hash统计当前数字出现的次数，若不为0则该数字++直至该数字第一次出现。考虑到数组长度和值都不超过40000，则Hash数组的大小应该为80000,（考虑极限情况，所有数字都是40000）先排序，然后从头到尾遍历，若当...
2020-03-22 05:36:06
48
原创 Leetcode之 最长回文子串
题目描述给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。思路暴力解法：将s翻转后得到rev，将s从头开始于rev中元素匹配，匹配得到后验证从匹配位开始直至不匹配或到达字符串结尾，得到匹配段字符串，此时需要判断这个字符串是否是回文串，若是则记录，若不是则跳出。显然这种方法复杂度是O(n^3)，部分案例会超时动态规划，建立一个矩阵来描述从字符串的某个位...
2020-03-21 08:13:23
57
原创 Leetcode之 寻找两个有序数组的中位数
题目描述给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。思路双指针，一个指向nums1，一个指向nums2，若nums1小或者nums2的指针到末尾了，则压入nums1，否则压入nums2。时间复杂度O(m+n)要想达到lo...
2020-03-21 05:53:34
50
原创 Leetcode之 最小的k个数
题目描述输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。思路哈希表，题目中给定arr.length<10000,arr[i]<10000，则建立一个Hash数组记录每个数字出现的次数，之后从Hash[0]开始输出，若Hash[i]>0，则循环输出直至Hash[i]0 或 k0堆的思想...
2020-03-20 20:21:16
101
原创 Leetcode之 无重复字符的最长子串
题目描述给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。思路哈希+双指针：定义一个Hash来保存字符出现的位置，定义begin表示子串的起点，count来表示子串的长度遍历字符串，若字符已经出现，则调整begin位置为max（begin，字符上次出现的位置+1），若未出现，则保存期Hash位置，count++。解释如下：示例：wobgrovwi = 0, w进，未出现，...
2020-03-20 08:14:04
51
原创 Leetcode之 两数相加
题目描述给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。思路最初始的思路是将两个链表专为int或long类型，求和之和再展开成链表，可惜系统给的范围要多大有多大，直接越界了递归...
2020-03-20 04:50:49
67
原创 Leetcode之 三数之和
题目描述给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。思路首先将nums排序得到cp_nums，然后将cp_nums的数字依次压入，将三数之和专为两数之和的问题，需要注意的是压入数字时若出现重复则需要跳过，如上次压入的是-1，这次则不...
2020-03-20 03:52:53
53
原创 Leetcode之 两数之和
题目描述给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。思路暴力解法：遍历哈希表可以分为两遍哈希和一遍哈希代码方法一：class Solution {public: vector<int> twoSum...
2020-03-19 21:11:34
48
原创 Leetcode之 最长回文数
题目描述给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。回文串：对称的字符串思路Hash，首先统计字符串中各个字符的出现次数，若为偶数则可进入回文串，若为奇数，则-1后可以进入回文串。若有奇数出现，则需要最后补一个1作为中央字符，若没有奇数出现，则不需要补1代码class Solut...
2020-03-19 19:01:01
140
原创 剑指offer之 剪绳子
题目描述给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。思路动态规划求解问题的四个特征：①求一个问题的最优解；②整体的问题的最优解是依赖于...
2020-03-15 23:06:17
62
原创 剑指offer之 机器人的运动范围
题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？思路从(0,0)开始走，每成功走一步标记当...
2020-03-15 22:22:07
51
原创 剑指offer之 矩阵中的路径
题目描述请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。题目代码class Solution {public: /* 大家好，我是yishuihan，这个题目是回溯法的典型题目； ...
2020-03-15 21:34:50
51
原创 剑指offer之 滑动窗口的最大值
题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5...
2020-03-15 21:19:26
53
原创 剑指offer之 数据流中的中位数
题目描述如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。思路通过insert函数将数据流从小到大排序通过GetMedian()输出对应中位数代码class...
2020-03-15 20:15:49
52
原创 二叉搜索树的第k个结点
题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。思路利用中序遍历，结合二叉搜索树左子树<跟<右子树的特点，则中序遍历得到的顺序即为从小到大的排列顺序代码方法一：遍历之后再输出class Solution {public: vector<TreeNode*> I...
2020-03-15 19:53:02
53
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人