- 博客(264)
- 收藏
- 关注
RSS订阅原创 Longest Valid Parentheses
Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, w...
2018-04-09 17:17:45
297
原创 数字和为sum的方法数
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 输入描述: 输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000) 第二行为n个正整数Ai，以空格隔开。 输出描述: 输出所求的方案数 ...
2018-04-09 11:08:06
741
1
原创 数字游戏
小易邀请你玩一个数字游戏，小易给你一系列的整数。你们俩使用这些整数玩游戏。每次小易会任意说一个数字出来，然后你需要从这一系列数字中选取一部分出来让它们的和等于小易所说的数字。 例如： 如果{2,1,2,7}是你有的一系列数，小易说的数字是11.你可以得到方案2+2+7 = 11.如果顽皮的小易想坑你，他说的数字是6，那么你没有办法拼凑出和为6 现在小易给你n个数，让你找出无法从n个数中选取部...
2018-04-08 09:46:18
407
原创 跳石板
小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3……. 这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。 例如： N = 4，M = 24： ...
2018-04-04 11:04:38
380
原创 数列还原
题目描述 牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。 输入描述: 每个输入包含一个测试用例。每个测试用例的第一行包含...
2018-04-02 09:50:15
346
原创 合唱团
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？ 输入描述: 每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每...
2018-03-31 11:37:36
212
原创 Find Bottom Left Tree Value
leetcode第513题，给定一个二叉树，找出最后一层最左边的元素。 首先，牵扯到二叉树的层结构，第一反应就是广搜。基本思路就是，每次从左到右遍历节点形成一层，到最后的时候如果为空的层，代表循环结束。 这里存在一个问题，当遍历到空层的时候，实际我们已经丢失了最后一层的信息，所以这里需要我们提前判断一下是不是到了最后一层。# Definition for a binary tree n...
2018-03-27 10:32:49
212
原创 Evaluate Reverse Polish Notation
leetcode第150题，求解逆波兰表达式。 这个题套路很清楚，用栈进行模拟就可以了，但是这里面有几个需要注意的地方。因为是要依次把token入栈，所以遍历token数组是大循环的条件。最后结果返回也是在token数组用完之后。除法和减法要注意操作数有先后关系。没有操作符的时候，直接返回最后一个操作数python中的除法有点奇怪，需要做一定的修改class Solution...
2018-03-27 09:19:26
164
原创 Sum of Two Integers
leetcode第371题，不用加减法实现加法。 不用运算符的题目多半就要靠位运算去解决。考虑两个二进制数相加，第一步是用异或，得到相加的原始结果，此时并没有考虑进位。按照二进制加法原则，进位就是两个1碰到一起，所以可以用与运算来模拟，注意这里还需要左移一位，让进位加到后面的一位上才可以。class Solution {public: int getSum(int a, int...
2018-03-27 08:55:23
204
原创 move zero
leetcode第283题，把所有的0移动数组后半部，其余元素的相对顺序不改变，要求原地操作。 其余元素相对顺序不能变，就意味着双指针法只能一前一后的使用，而不能一头一尾的使用。与数组去重题类似，i为游标指针，start为指向0数组第一个元素的指针，i放过所有为0的元素，遇到不为0的元素时，和start位置的进行交换，交换后start后移继续指向0数组第一个元素，这是与数组去重不同的地方。sta...
2018-03-26 19:59:26
299
原创 Coin Change
leetcode第332题，硬币找零，使用最少数量的指定硬币凑出目标数。 深度搜索，逐个加入硬币，当数额与目标数相等时，记录一下所用的硬币数，找出其中最小的就好了，但是这样做目标数很大的时候就会超时。class Solution(object): def coinChange(self, coins, amount): """ :type coins:...
2018-03-23 11:25:02
382
原创 Sort Colors
leetcode第75题，打乱的0，1，2排序 可以先用计数排序，由于只有0，1，2这三个数字，因此完全可以先统计各有多少个，然后在数组中重写一遍即可。class Solution: def sortColors(self, nums): """ :type nums: List[int] :rtype: void Do not r...
2018-03-13 09:59:40
189
原创 Redundant Connection
leetcode 684题，一个图是由一棵树多一条边，要求删去那条边，然后形成一棵树。 此题可用并查集来做，思路是，遍历所有的边，并用并查集来做归属划分，如果一个边的两个node分属于不同的集合，说明这条边不是多余的，是起到了联通作用的，相反，如果node已经被前面的边连入到一个集合中了，那么说明这条边是多余的了。class Solution: def findRedundant...
2018-03-13 09:20:50
281
原创 word search
leetcode 第79题，图上的深搜题。 第一步，先要写个遍历循环，找到搜索的起点，也就是首字母。 第二步，从起点出发开始搜索，搜索时主要要记录已经走过的地方，这里可以使用一个二维的数组单独来记录，或者走过的地方标识为‘#’，搜索后恢复这个位置的字符。 注意，每次搜索时，都要比较word和当前路径已经遍历到的字符，这里可以使用增量式的比较方法，每次比较一个字符即可。class So...
2018-03-09 10:18:37
566
原创 Odd Even Linked List
leetcode第328题，要求把一个单链表的奇数偶数位置分开，把奇数位置的节点串联起来后放在偶数位置节点的串联之前。 一开始的想法是，走两遍循环，一个把奇数位置串起来，另外一个把偶数位置串起来，然后奇数位置后面加挂上偶数串的头部即可。但这样做的问题是，第一遍把奇数位置串起来之后，改变了原始链表，所以后面那个循环就不正确了。 正确的做法是，在一个循环里搞定这个事情。首先，拿到奇数头部和偶数头部...
2018-02-28 10:09:36
190
原创 两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。剑指offer有两种思路，思路一是用栈把节点存起来，然后依次弹出，直到最后一个相同的为止，这种方法比较简单，时间和空间复杂度都是O(m+n)。 思路二是先求两个链表的长度，求出长度差，先让长的链表走长度差那几步，这样就可以拉齐两个链表的进度了，这样两个链表一直走下去就会同时会和。ListNode* FindFirstCommonNode( L
2018-01-29 09:31:01
188
原创 逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P简单思路是，挨个遍历数组中的元素，每遍历到一个元素之后和后面的元素再逐一比较，这样的复杂度是O(n^2)。 这里时间都花费在了逐一比较上，这样一个个找逆序对显然是比较耗时的。归并排序的思路就是一次性的找出一串来，所以复杂度会低很多，本质就是归并排序的复杂度O(nlog
2018-01-29 09:08:00
261
原创 字符串反转问题
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？主要思路是，先整个反转字符串数
2018-01-28 19:36:05
338
原创 和为S的连续正数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!双指针法，一个指向小数，一个指向大数，如果大小数
2018-01-28 10:49:33
173
原创 数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。思路详见剑指offer，这里值得注意的地方时位运算的操作。 如果检查一个int数的第n位是不是1，可以先把这个数右移n位，这样第n位就落到了最右端，这时候与1操作，如果不是1，那么与操作结果就是0.int isBit(int x, int index){ return (x>>ind
2018-01-23 15:42:58
183
原创 平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。深搜，每次带着一个深度信息搜索，深搜的返回值就是是否平衡。 每次遍历到某一个节点的时候，先判断之前子树是不是平衡，如果平衡，深度自增，交到上一层去比较是否满足平衡条件。 递归的出口条件是，遍历到空值时，说明已经到叶子节点的下一层，深度值设置为0，同时返回true，这是返回true的原因和计算二叉树深度的原因类似。 另外深度增加的时候，只有在
2018-01-23 10:53:53
151
原创 约瑟夫环
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋
2018-01-23 10:09:44
183
原创 扑克牌顺子
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌
2018-01-23 09:29:51
211
原创 二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。最先想到的就是深搜，设置一个值维护当前访问的深度，遇到叶子结点就和全局最大值比较更新。void TreeDepthCore(TreeNode* pNode, int currDep, int &maxDep){ if(pNode->right == NULL
2018-01-22 16:56:54
487
原创 排序数组中寻找k的个数
统计一个数字在排序数组中出现的次数。 既然数组有序，考虑二分查找。记录一下实现细节，剑指offer中使用的递归形式，我的代码用循环实现。循环的条件用start和end相对大小来控制，这也是二分查找的原始控制条件。在寻找第一个k的时候，如果mid已经是k，但是这个数之前也是k，说明这并不第一个k，此时应该向数组左半部去查，寻找最后一个k正好反过来，应该向右半部去查。int
2018-01-22 16:30:45
448
原创 不使用四则运算实现加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。 首先想到使用位运算去模拟，那么下一步就是怎么模拟。 二进制的按位相加实际等效于异或。 二进制的每位的进位计算等效于按位与，然后左移。 进位加上按位相加结果就是最终结果。 注意，上一步还可能会有进位，不过没关系，还可以重复使用前两步，直到没有进位为止。int Add(int num1,
2018-01-22 15:27:23
542
原创 铺砖之斐波那契数列
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？这个题的分析详见剑指offer，这里记录一点实现细节。测试数据里有0这个数，代表一块地砖也没有，方法数自然为0事实上，真正的斐波那契序列是从1开始的，有1块地砖，只有一种铺法，2块地砖就有2种了，后面以此类推。因此这就需要我们代码单独处理0，然后按照常规写
2018-01-10 18:48:49
1129
原创 寻找旋转数组中的最小数
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。使用二分查找的思路去做。思路详见剑指offer，在此记录一下实现细节。与书中代码不同，为了结构更加清晰，单独处
2018-01-10 18:47:37
183
原创 队列与栈
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。栈是先进后出，队列是先进先出。 要想实现先进入的元素先出去，其实很简单，就是把把压入第一个栈的元素在反过来压到第二个栈里，这样顺序就正好反过来了。 原理简单，实现时还要考虑几个细节。从第一个栈压入第二个栈什么时候操作？简单，当第二个栈被弹空了，或者刚开始什么都没有，就需要从第一个栈里拿数据了。也就是
2018-01-10 11:15:52
165
原创 替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。典型的从尾至头遍历的题目，明显可以看出，如果从头到尾扫，每次遇到空格再插入%20，需要移动后面的数字，而且会重复移动多次。 不如先扫一遍，拿到空格的数目，这样就可以计算替换完成后的数组长度，ok，有了这个长度，就可以从尾至头依次把原数组的
2018-01-08 15:29:41
160
原创 倒序输出单链表
输入一个链表，从尾到头打印链表每个节点的值。注意，不是反转链表，只需要逆序打印即可，其实这相当于降低了难度。 首先最简单的办法就是扫一遍单链表，压倒栈里，然后一个个弹出来就可以了。vectorint> printListFromTailToHead(ListNode* head) { stackint> s; vectorint> ans; ListNo
2018-01-07 19:30:51
2027
原创 二维数组的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。找规律，以右上角的数为基准，如果这个数比目标数大，那么右上角同列的数字就可以不考虑搜索了，因为列从上到下依次递增。同理，如果右上角的数字比目标数小，那么右上角同行的数不考虑搜索。因为行是从左至右递增的。bool Find(i
2018-01-07 18:32:42
123
原创 快速排序
快速排序总结一下如何写一个快速排序的代码实现。 实现一个快速排序要首先准备好以下几个模块的内容。交换函数随机选择函数分割数组函数快速排序函数其中第三第四部分数快排的核心代码。 交换函数很简单，实现的是在数组内交换两个位置上的value。注意这里要传入vector的引用，才可以原地修改数组的值。void swap(vectorint> &data, int p1,
2018-01-07 15:13:44
186
原创 Triangle
LeetCode第120题，数字三角形，DP基本题，一般来说，在一个图或者树结构上的最优化问题，DP结构是很明显的。 我们在自底向上遍历，并不断加上正下方和右下方的数字，每个节点记录一下最小值。到达顶端之后自然就是全局最小值了。 这个代码只要把判断部分最小换成最大，就可以求解最大数字三角形问题，思路完全一样。class Solution(object): def minimumTotal
2017-11-13 20:56:33
189
原创 N-Queens
leetcode第51题，n皇后问题，在n*n的格子中防止n个皇后，使得每一行每一列和对角线都不能出现两个以上的皇后。 这其实就是著名的八皇后问题。 简单一点切入，假设我们放置第一个皇后，我们可以任意去选择位置，一共有n^2个位置，之后就是n^2-1个可能，以此类推，之后检查每种可能性是否合法，显然这个办法复杂度太高了。 换个角度，在放置的时候，我们就先验地加入规则限制。放置第一个皇后，可以在
2017-11-05 09:32:10
203
原创 Increasing Triplet Subsequence
leetcode第334题，要求在一串无序的数组中是否存在一个递增的三元组。 其实这个题有点像寻找最长增长子序列，但是是一个简化版，因此可以不用DP。基本思路是，寻找当前最小值记作x1，次小值记作x2，如果遍历发现比这两个数大的，就一定存在递增三元组。 思考一下为什么这么做是对的。第一，本题只是问存不存在，并不需要找出所有的满足要求的子序列。第二，上述方法其实是最容易找到递增三元组的情况。 具
2017-11-04 20:58:35
202
原创 Longest Consecutive Sequence
LeetCode第128题，在一个序列中找最长的连续序列。要求在O(n)复杂度下完成。 排序是可以完成的，但是复杂度最低也是O(nlogn)，因此考虑hash。 hash可以先把每个数存起来，然后遍历这些数，往两边扩展寻找连续的数，如果找到了就在hash里删除这个数。 这里删除操作是核心，因为如果一个数在这个连续序列当中，那么以这个数为中心扩展，找到的仍然是这个连续序列，因此完全不需要再以这个
2017-10-31 19:16:34
448
原创 Find Peak Element
leetcode第162题，二分查找，要求在一个数组中找出尖峰元素，也就是大约相邻位置上数字的元素。 第一反应，线性查找，扫一遍数组，复杂度o（n）。 题目要求是logn的复杂度，就说明肯定是要用二分查找，二分查找的问题是，如何根据中间元素的情况来判断继续搜索哪一边。这里重要的前提条件是边界都是负无穷，只要中间元素大于其后继元素，左半部包含中间元素，肯定存在着一个峰值，因为即使是一路递增到了中...
2017-04-15 15:21:55
481
原创 Best Time to Buy and Sell Stock
leetcode第121题，简单题，要求寻找一个最好的买入卖出时机，使得两个数字相差最大，即获益最多。 题目提示是动态规划，但实际好像没那么复杂。首先，一种最直接的思路，两边循环搞定，外循环遍历买入时机，内循环遍历卖出时机。 能不能简化一下呢，假设只用一次循环，就是遍历卖出时机，什么时候卖出呢，当然是与之前的所有值中最小值差距最大的时候，这就很明显了，我们可以一边遍历卖出点，一遍记录卖出点之前的
2017-04-14 09:55:14
431
原创 Simplify Path
leetcode第71题，要求化简linux风格的路径。这里首先要明确linux路径的表示形式，一般而言，“.”代表当前目录，所以不用做处理，“..”代表返回上一次目录，因此就需要跳到前面那一层目录下。很明显，这个题用栈来做会很简单，先用“/”分割字符串，然后凡是遇到“.”的情况，一律越过，不作处理，遇到字符则加入栈，遇到“..”则弹出栈，最后连接一下就可以了。class Solution(obje
2017-03-14 10:27:28
621
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人