9 小文件

尚未进行身份认证

Night Flight

等级
TA的排名 3w+

[LeetCode]problem 279. Perfect Squares

TAG动态规划;广度优先搜索;深度优先搜索;数论;四平方和定理;三平方和定理题目链接方法不会。不过是一道太有意思的题目了…参见Summary of 4 different solutions (BFS, DP, static DP and mathematics).首先是DP方法,设R[i]表示数i最少可由R[i]个数的完全平方和构成。那么递推关系可以写作:R[i] = min( R[i-j*j]

2016-06-28 19:29:48

[LeetCode]problem 365. Water and Jug Problem

TAG最大公约数; 裴蜀定理;数论; 深搜失败 题目链接方法服了,这个题不是太懂。以前考试的时候考过,是用深搜来做… 于是我就做了,然后发现内存爆了。有个case数太大。然后看了DISCUSS,网上也看了下,发现是这样:问题等价为: m x + n y = z是否有关于m、n的整数解。上述问题即是裴蜀定理, 即是说,只要z是x、y的最大公约数的倍数即可。最后,在装水问题下,又有限制——因为水桶

2016-06-28 14:49:14

[LeetCode]problem 1. Two Sum

TAG找相加为特定和的两个数;HashTable题目链接方法真是智障.只想到3sum了,由于要返回索引,又看到HashTable,于是用unordered_map来预先存所有数的索引,再来用双指针找… 结果发现有重复值,又改用unordered_multimap,感觉已经是无所不用其及。看了DISCUSSAccepted C++ O(n) Solution,其实只需要用map来存已经找过的数,用目标

2016-06-27 20:11:25

[LeetCode]problem 15. 3Sum

TAG三数和为特定值的所有可能题目链接方法首先想到了combinationsum, 这样做会有重复,因为给的数组中有重复数。于是又做了一个set来去重,结果——果然TLE了。默默看了DISCUSS, Concise O(N^2) Java solution 写得太好了。原来是使用2个数的和等于某个值的方法,该方法先升序排序数组,再用一个指针指向头部,一个指针指向尾部,如果小于目标值,则要变大,头部指

2016-06-27 19:10:53

[LeetCode]problem 29. Divide Two Integers

TAG位操作; 二分查找?; 除法就是被除数包含多少个除数题目链接方法没有思路,直接看得DISCUSS,写得太好了。Detailed Explained 8ms C++ solution首先,dividend是被除数,divisor是除数;接着,除法表示被除数中有多少个除数,所以在不让使用乘法、模运算的情况下,我们使用位操作来以2倍的速度增大除数,直到再增大就要大于被除数了。那么此时我们能够直到除数

2016-06-26 20:16:40

[LeetCode]problem 213. House Robber II

TAG受限DP 题目链接方法相比1,又多了一个限制条件 —— 首尾相连!这时,可以认为,首位置和尾位置,其中一个状态确定,最后一个位置必然也确定了。可以按照Simple AC solution in Java in O(n) with explanation所言,将此问题化为I的问题:必然不偷房间1,那么后面所有房间满足的限制与I相同。必然不偷最后一个房间,那么前N-1个房间满足的限制与I相同。

2016-06-26 15:14:40

[LeetCode]problem 198. House Robber

TAG受限DP; 两个状态序列 题目链接方法真是没想到可用设置两个状态序列来解!不能连续偷连续的两件房间。我们可以设置两个状态序列A、B,A[i]表示偷第i间时最大的收益;B[i]表示不偷第i间时的最大收益。对于A[i],由于偷第i间,所以不能偷第i-1间,所以其最大值必然等于 B[i-1] + Num[i],即不偷第i-1间时的最大收益加上此间房间的收益;对于B[i],由于不偷第i间,那么对前1间

2016-06-26 14:04:37

[LeetCode]problem 166. Fraction to Recurring Decimal

TAG循环小数除法 ; Hash记录位置;最小负数的绝对值无法表示!只能提升到更大的类型题目链接方法只说方法:其实很简单,就是把自己手算除法的过程用代码写一遍就好了。我分别处理了结果的整数部分和小数部分。一个是简单一些,另一个是方便处理循环小数。循环小数的处理上,只要发现当前运算的除数是之前出现过的,那么其就进入到了循环。所以用一个hashTable,记录每个除数对应的结果位置。这样发现有循环出现时

2016-06-26 10:59:20

[LeetCode]problem 3. Longest Substring Without Repeating Characters

TAG双指针 ; hashTable ; 快速匹配 题目链接方法这道题,思路还是比较容易想的。双指针,一个指示开始,一直指示结束,同时用一个hashTable表示字符是否出现过。我感觉自己都比较吃惊,自己竟然自动想到了hashTable不仅应该存储是否存在,还应该存储上上一次出现的位置。这样,一遇到重复,可以立即把开始指针设为该重复字符上次出现的位置之后的位置,因为这样新的子串必然包含当前字符,因而

2016-06-25 20:01:32

[LeetCode]problem 34. Search for a Range

TAG二分查找;STL ; lower_bound ; upper_bound ; equal_range ; 题目链接方法STL中相关方法写得实在太好了!!以下直接贴出相关的代码了:lower_bound : 找到已排序数组中第一个**大于等于**target的数的位置;没有则返回最后一个位置;template <class ForwardIterator, class T> ForwardI

2016-06-25 15:25:29

[LeetCode]problem 61. Rotate List

TAG链表循环移位;改变指针指向题目链接方法相当于循环移位。个人觉得先获取长度是必需的,因为先要进行模运算,这是循环移位操作所必须的。接下来就是正常的处理了。还是用父节点来测试,这样好操作next指针。代码class Solution {public: ListNode* rotateRight(ListNode* head, int k) { if(head == nul

2016-06-23 17:50:28

[LeetCode]problem 148. Sort List

TAG归并排序;链表;非递归归并排序 题目链接方法要在O(nlgn)完成排序,对象又是单向链表,应该是优先考虑归并排序(其实感觉快排也是可以的)。按照LeetCode的说法,常数空间就是指非递归,迭代。所以如果采用归并,那就得用非递归版。纠结了一会儿,觉得关键得用一个空的头部节点,这样才能方便交换。迭代版就是递归版的逆过程,从每个大小为1的块开始归并的排,注意把merge后的结果与尚未排序的结果连接

2016-06-23 14:30:54

[LeetCode]problem 77. Combinations

TAG组合; 回溯 ; 递归与迭代题目链接方法与求和为n的所有组合完全类似——如果使用递归版本的话。当时一连做了3个相似的题,记住了递归的方法,非常直观,可是也非常不错。这次看着题还是非常有印象的,迅速做完,只是时间上似乎不是很好。于是看了DISSCUSS上的迭代版,Short Iterative C++ Answer 8ms。所谓8ms的方法,的确非常不错。主要是这样的思想:依次从后往前构建所有可

2016-06-23 14:29:51

[LeetCode]problem 105. Construct Binary Tree from Preorder and Inorder Traversal

TAG二叉树 ; 建树; 先序遍历; 中序遍历; 遍历规律题目链接方法这道题应该是必须要会的吧!之前在编程之美中看到过,这次又遇到,递归的方法会了,但是迭代方法还不是很会。看了DISCUSS中的代码,大致明白了,尝试用更加清晰的代码描述出来。首先说递归版同样从先序遍历递归方法看起:visit(root);visit(root->left);visit(root->right);以上就是对根节点的

2016-06-21 12:21:08

[LeetCode]problem 354. Russian Doll Envelopes

TAG二维元素的最长递增序列 题目链接方法不知怎么,直觉使然,觉得应该使用排序+LIS。然而仅仅是直觉却不能解决问题,有两个问题需要解决:排序策略LIS策略自己之前想的是排序先按w递增,再按h递增;LIS存储数组使用vector的vector,因为每个状态可能有多个值:如下面的情况: [2,3] , [5,8], [6,4] , [6,7] , [7,8]到处理[6,4]时,LIS数组是 [2

2016-06-19 10:53:02

[LeetCode]problem 160. Intersection of Two Linked Lists

TAG求两个无环链表第一个相交节点 题目链接方法MD智障啊。真是不服不行。编程之美上有一个基础的问题,只判断是否相交;然后后续有个问题就是如果需要找第一个相交节点该怎么办?当时我随便一想,觉得应该没有办法,只有用计数了吧。然后,竟然还有这么巧妙的办法,只需要用两个指针分别走一遍A、走一遍B,当到达第一个相交节点时,他们走的路程必然是相同的,即len(linkA)+len(linkB)−len(lin

2016-06-17 20:23:22

[LeetCode]problem 343. Integer Break

TAG分解n得到长度至少为2、和为n的数字序列,使其乘积最大的方法——一直从中分出3。数学 题目链接方法懵逼。按照提示找规律,然而也没有找到。果然智障。看了DISCUZZWhy factor 2 or 3? The math behind this problem , 算是有个勉强的合理解释。首先,我们一个先验是,确定有一个唯一的数(实数域上的实数,非整数),使得n只分解为该数,才能够得到最大乘积。

2016-06-16 23:06:43

[LeetCode]problem 173. Binary Search Tree Iterator

TAG中序遍历二叉查找树得到一个递增序列二叉查找树题目链接方法这道题挺有意思的,在二叉查找树的基础上建立一个迭代器,要求hasnext和next操作要是平均O(1)的,且最大空间消耗是O(h),h是树高。其中next返回二叉查找树当前状态下最小的节点值。这个一想,每次返回当前最小的,能够想到是排序。特别的,中序遍历二叉查找树,能够得到一个递增的序列。而中序遍历,每个节点访问一次,所以每个节点的平均访

2016-06-15 21:51:21

[LeetCode]problem 221. Maximal Square

TAG动态规划 题目链接方法这道题已经是第3遍做了,第一遍是算法作业,第二遍是算法考试,第三遍就是现在了。这是唯一一次真正把可运行代码写出来,终于代码验证了一遍。一次过,没有拼写错误!看来这道题真的是了熟于心了(算法能过,这道题功不可没啊,orz)。我们用R[i][j]表示矩阵中以第i行第j列的小正方形为右下角的全为1的正方形最大边长。有点绕,分开来说,首先表示的是以此位置为由下脚的正方形,其次正方

2016-06-14 22:10:52

[LeetCode]problem 114. Flatten Binary Tree to Linked List

TAG先序遍历找先序遍历上一个节点把二叉树变成一个链表右左根顺序与先序相反题目链接方法要把一棵二叉树变为先序遍历结果的链表,而且是由右子树展开。首先,很直观的想法就是先序遍历,同时记录先序遍历中上一个非空节点,这样只需要访问当前节点时,使上一个节点的右子树指向当前节点即可。但是需要注意的是,常规先序遍历先遍历左子树,所以把前一个节点(父节点)的右孩子设为当前节点后,父节点的右孩子就没有了(还没有被访

2016-06-13 22:16:49

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!