小文件-CSDN博客

原创 [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 580

原创 [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 609

原创 [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 519

原创 [LeetCode]problem 15. 3Sum

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

2016-06-27 19:10:53 393

原创 [LeetCode]problem 29. Divide Two Integers

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

2016-06-26 20:16:40 334

原创 [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 362

原创 [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 391

原创 [LeetCode]problem 166. Fraction to Recurring Decimal

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

2016-06-26 10:59:20 393

原创 [LeetCode]problem 3. Longest Substring Without Repeating Characters

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

2016-06-25 20:01:32 465

原创 [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 325

原创 [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 300

原创 [LeetCode]problem 148. Sort List

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

2016-06-23 14:30:54 483

原创 [LeetCode]problem 77. Combinations

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

2016-06-23 14:29:51 390

原创 [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 336

原创 [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 411

原创 [LeetCode]problem 160. Intersection of Two Linked Lists

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

2016-06-17 20:23:22 404

原创 [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 445

原创 [LeetCode]problem 173. Binary Search Tree Iterator

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

2016-06-15 21:51:21 366

原创 [LeetCode]problem 221. Maximal Square

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

2016-06-14 22:10:52 325

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

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

2016-06-13 22:16:49 448

原创 [LeetCode]problem 60. Permutation Sequence

TAG类·进制转换数学；枚举；找规律题目链接方法首先，第一眼看过去，没看出来规律。看第二眼，找到了规律：第高位往低位看，整个随机序列的最高位从1到n的，看某一确定高位下的序列，会发现次高位也是由低到高，只不过不断跳过之前位上已经出现过的单词。从递归的角度来说，这个n位排序随机序列的产生过程如下：NUM_SEQ = {}NUM_LEN = kdef GENERATE(num_prefix):

2016-06-12 21:29:24 371

原创 [LeetCode]problem 151. Reverse Words in a String

TAG字符串反转块反转题目链接方法题目要求O(1)空间，不知怎么，立即想到了《编程之美》上“将一个数循环移位k位”的题目。如此可以满足时间为O(n),且空间复杂度为O(1).具体步骤将字符串中每个单词单独反转整个字符串反转由此就得到了反转字符串，其中每个单词都是正序，但是单词至今是一个反序过程。这是因为每个单词都反转了两次，所谓负负得正，所以单词正序，而单词之间只反转了一次，所以保证了反序。上

2016-06-11 21:46:51 575

原创 [LeetCode]problem 145. Binary Tree Postorder Traversal

TAG二叉树非递归后序遍历基础；重要link方法不使用递归方法，就记得有一个关键，但是怎么都想不起来了。又想着给每个节点加个标志位了….看了维基百科，知道了答案。首先，后序遍历下，要访问该节点，必然是在从右孩子回来的回溯阶段。且一个重要的事实是——如果右孩子不为空，那个访问右孩子后必然访问该节点。由此，我们有了一个简单的方法来区分当前回溯阶段是从左边回溯还是右边。定义一个变量lastVisitedN

2016-06-10 22:05:31 416

原创 [LeetCode]problem 94. Binary Tree Inorder Traversal

TAG二叉树中序非递归遍历基础；重要link方法非常基本的、非常重要的、必须熟练掌握的技能！非递归中序遍历二叉树，需要结合栈作为回溯，同时记住读取的时机。中序遍历要求：先左、再当前、再右边。所以读取一个节点的时机是从左边孩子节点回溯时！压栈时机：当遍历指针不空，此时该节点还不能被读取，故压栈；读取时机当遍历指针为空时，说明需要回溯！此时从栈中去栈顶元素，作为回溯的节点。问题是——只有在从左边孩子回溯

2016-06-10 22:03:33 276

原创编译原理—语法分析

PS 多年前写的了，放在草稿箱里… 现在发出来了上周完成了编译实验课程的语法分析部分，周末玩去了，今天稍稍整理一下。首先我们是采用语法制导翻译来做的编译，书上对于语法制导翻译的解释是，将静态检查和中间代码生成结合到语法分析中进行的技术。大概就是指把词法分析、语义分析都结合到语法分析中来，一切都围绕着语法分析展开吧。所以，完整的语法分析程序，应该是将词法分析的输出作为输入，在进行每一次归

2016-06-10 00:52:18 1970

原创 [LeetCode]problem 62. Unique Paths

TAG动态规划组合link方法就使用动态规划而言，这道题与爬梯子很像，就是到达当前位置的不同路径数等于到达上边、左边位置的路径和。这道题可以直接从数学角度求解——mxn的格子，从左上到右下，只能向右或下，那么其路径必然是m-1个“右”，n-1个“下”构成的序列。所以不同的路径，就是求所有m-1个“右”和n-1个“下”组合的方法数，即 C(m-1 + n -1 , m-1) 。然而上面这个算式如果暴力

2016-06-10 00:44:18 445

原创 [LeetCode]problem 63. Unique Paths II

TAG动态规划link方法如果说Unique Path I还会考虑直接用组合数的方法去做的话（虽然并不会很简单），加入了障碍后，这道题才真正有了动态规划的优势。相比之下，有以下两点：边界上，从原点分别向右和向下初始化边界，只要未遇到1，则将方法数初始为1；如果遇到1，则说明有障碍，后面都不能再通过，初始化为0；DP过程，如果位置值为1，则说明有障碍，不能通过，方法数为0；否则，依然是左方和上方的

2016-06-10 00:42:29 304

原创 [LeetCode]problem 117. Populating Next Right Pointers in Each Node II

TAG层序遍历 - 常量空间，通过next指针二叉树link方法有了Populating next right pointers in each node I的铺垫，这道题就显得没有任何思维上的限制了。在上道题（完全二叉树）条件上，左孩子的右边必然是右孩子，右孩子的右边必然是下一个节点的左孩子，下一层的首节点必然是当前层首节点的左孩子。当不是完全二叉树后，只需要把上面的假设全部换为一个find函数即

2016-06-10 00:38:39 294

原创 [LeetCode]problem 216. Combination Sum III

TAG递归回溯组合数和link方法与Combination Sum1和Combination Sum2相比，就是上述两个问题的综合，再稍有限制：候选集是set (1-9)每个数字只能用一次(组合中各数字是unique)限制：必须是k个数。想想，还是很简单的。加上必要的判断和剪枝即可。代码class Solution {public: vector<vector<int>> comb

2016-06-08 08:46:15 332

原创 [LeetCode]problem 40. Combination Sum II

TAG递归回溯组合数和link方法与Combination Sum 相比，每个数仅能被使用一次候选集不再是set，而是collections，就是可以包含重复数字了怎么办呢？针对第一个，非常简单，只需要把开始递归的开始下标设为当前位置的下一个位置即可。重复？想象一下重复的组合时怎么来的：input : [1,1,3,4,5]如果对第一个1，我们在[3,4,5]中能够找到候选数字，那么对第二个1

2016-06-08 08:45:07 344

原创 [LeetCode]problem 39. Combination Sum

TAG递归回溯组合数和link方法首先，需要使用递归，使用一个容器去存储当前已经选择的数，同时，在递归时，选择一个数后，就将目标值减去选择的数，作为下次递归的目标数。递归需要传递的参数（保持的状态）有：已选择的数集合，候选集，目标值，结果集，递归开始的下标。题目的一个要求是同一个数可以多次选择，但选择的组合之间不能重复。上面的参数递归开始的下标就是完成这个功能的。我们每次递归时，将递归的开始下标

2016-06-08 08:43:55 501

原创 [LeetCode]problem 164. Maximum Gap

TAG桶排序浮点数不精确link方法一眼看过去完全不知道该怎么做。看了题解觉得很高端的样子，再后来多看了下，发现本质其实就是一个线性时间排序的问题！线性时间排序，有计数排序、桶排序、基数排序。计数排序时间复杂度与最大值与最小值差值有关。桶排序可以分桶，如果能够把问题转化到只计算桶间间距，那么时间复杂度就能是与输入个数成线性的了。基数排序没有尝试。这道题官方题解是使用桶排序，每个桶只记录落到这个桶的最

2016-06-07 00:19:43 434

原创 [LeetCode]problem 174. Dungeon Game

TAG动态规划link方法标准DP问题，没有太大思考难度。不过还是在纸上画了一会了，写出了需要满足的条件，结果觉得还是直接直观理解更加简单。明显需要倒推。首先是最后一个格子。到达这个格子之前，K至少有1点HP，设当前地牢值为d，若当前地牢如果为战斗（d为负），设则为了保证战斗后剩余1，则至少需要的HP为d+1；如果为补药（d大于0），则只要需要HP为1。接着是处理两边的边界，边界是任意情况的特例，故

2016-06-06 12:26:22 383

原创 [LeetCode]problem 116. Populating Next Right Pointers in Each Node

TAG层序遍历 - 常量空间，通过next指针二叉树link方法看到题，想了一下，得用层序遍历！做法是：用两个vector，第一个vector用来依次存当前层的父节点，另一个vector用来依次存下一层的孩子节点。初始时将root节点放入第一个vector，然后只要第一个vector不空，则循环：对第一个vector中每个节点，把非空孩子节点依次放入第二个vector中；放完后，连接第二个v

2016-06-04 23:43:50 381

原创 [LeetCode]problem 80. Remove Duplicates from Sorted Array II

linkTAG双指针思维方式容器的end()调用耗时显著性方法算是很容易想到的题，然而写起来却很纠结…还得多练啊..我的思路是，记录重复的次数，初始为0，如果相等一次，则首先+1，然后判断是否小于2，如果是，则继续移动双指针并赋值；如果否，则只需移动遍历指针即可。如果不等，则清零重复次数，移动双指针并赋值。纠结的问题有：遍历指针从哪里开始？uniq指针不得不从第一个开始，那么遍历指针如果从第一个

2016-06-02 00:39:29 339

原创 [LeetCode]problem 70. Climbing Stairs

linkTAG动态规划类-斐波拉切方法之前写算法作业时做过，所以现在看起来就很简单了…满足以下递推式：A(1) = 1A(2) = 2A(n) = A(n-1) + A(n-2) 其中A(n)表示到第n步梯子时有多少中不同的爬法。记得以前高中时也考过这个题.. 当时也不会。想想，其实自己以前也不够聪明的… 想来聪明也可来自强大的记忆力和广博的经历。多多刷题啊..代码class Solution

2016-05-31 20:45:00 277

原创 [LeetCode]problem 191. Number of 1 Bits

TAG位操作汉明重量 HammingＷeightlink方法非常有背景的一道题。讨论见stack-overflow详细见维基百科-汉明重量 or Wikipedia-Hamming Weight总的来说，这是经典的“汉明距离(Hamming Weight)”问题，由于在密码学、编码理论、信息论中常用到计算数据位中1的个数，所以有的CPU(X86)是有单独的指令(popcnt)来做这个操作的，GCC下

2016-05-31 15:44:15 321

原创 [LeetCode]problem 35. Search Insert Position

problem 35. Search Insert PositionlinkTAG二分查找插入方法能够比较快的明确思路——就是二分查找的应用。然而写起来还是很费劲，之前那道找最长递增序列的长度其实就需要用到这道题的算法来实现快速查找插入位置（完全一样好吗！当时就写出来了啊…但是现在又忘了…）。直接看了DISCUSS的代码.记住了两点关键：循环条件是low<=high，其中high初始为size

2016-05-31 10:00:06 365

原创 nginx运行过程中删除log文件无效

场景服务器空间快爆了，连把日志压缩的空间都没有了。只有把日志删除了。但是可怕的事，明明都/bin/rm *.log了，而且ls -a都看不见文件了，但是df看到磁盘空间就是不变大。而且试图写文件也失败，看来磁盘空间真的没有被释放！但是明明目录下已经没有日志文件了啊？解决猜测肯能是Nginx运行着，这个文件句柄一直处于打开状态没有关闭，因此系统把目录下的文件所有删除了，但是真正的文件因为有连接的存在还

2016-05-12 14:16:28 3414

原创同一作用域下函数名（变量名）可以覆盖类、结构体名

我们要定义一个使用默认构造函数构造的对象，有时可能出现下面的错误：className co() ;上面其实并没有定义对象co , 而是定义了一个名为co，类型为className ()的函数。之前也仅仅到此了，今天要用<sys/stat.h>下的stat函数，却突然发现其第二参数竟然是同名的stat ，为了区分二者，需要显式地定义参数为struct stat buf 。由此，查询了下，这才反应过来

2016-05-10 19:08:21 1152

HIT_OS_LAB

自助投胎机源文件

空空如也