- 博客(31)
- 收藏
- 关注
RSS订阅原创 LC 309. Best Time to Buy and Sell Stock with Cooldown 股票系列之四 状态机 动态规划DP
Say you have an array for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one an...
2018-05-11 15:27:51
303
原创 Best Time to Buy and Sell Stock 买股票系列三连
Leetcode里的买卖股票系列非常有名。之前做过这个系列里面的三道，分别是:121 Best Time to Buy and Sell Stock其中第一道题的要求是只能交易一次，因此就是寻找数组内正向的最大差值，解法是维护一个min变量存储当前遇到的最低股价，维护一个max存储当前可能的最大利润（用当前股价减去min），一次顺序遍历数组最后返回max就ok了。代码：int maxProfit(...
2018-05-11 14:29:48
2249
原创 Contains Duplicate系列三连- set，map的应用
又做完了一个系列，感觉收获良多。一共三道题，第一道和第二道都是easy，第三道是medium，不过我感觉第三道更接近hard。217. Contains DuplicateGiven an array of integers, find if the array contains any duplicates. Your function should return true if any val...
2018-05-01 16:01:20
139
原创 LC 127. Word Ladder 系列之一 BFS
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:Only one letter can be changed at a time...
2018-04-30 23:01:31
122
原创 LC 207 210 Course Schedule I / II BFS 有向图的拓扑排序，并应用于探测是否存在环
什么是拓扑排序？简而言之就是把有向图从复杂的立体的图的表示形式转化为线性的表示形式，对于图中所有的边(u, v)，在拓扑排序后的结果中节点u的位置一定在节点v之前。拓扑排序可以用来解决先修课程、工程施工等常见的实际问题，将这种“要有A必须现有B”的关系抽象为图中A指向B的有向边，将整个问题的解决转化为寻找一条从开始点到结束点的路径。直接看题。207. Course ScheduleThere ar...
2018-04-30 16:27:11
155
原创 LC 198 213. House Robber I / II 动态规划
198. House RobberYou are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is th...
2018-04-30 16:10:29
137
原创 LC 216. Combination Sum III
前几天4.27回杭州，准备5月3号去上海梅龙镇广场办F-1面签。在家闲着无聊，代码状态又还不错，LC基本每天6，7道的进度，而且很多都是一次AC，一眨眼已经完成165道了。LC216很简单，很直接的回溯，但是之前写了一个Combination Sum II，感觉既然是一个系列的那就把这道也写一下吧。另外，我感觉我这样顺序做题有一个好处，就是在做到Combination Sum III的时候可以回看...
2018-04-30 15:55:52
119
原创 LC 86. Partition List 先组建两个子链表最后合并的思路
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.You should preserve the original relative order of the nodes in each of the...
2018-04-24 16:11:38
117
原创 Remove Duplicates in Sorted Array (I /II)
26. Remove Duplicates from Sorted ArrayGiven a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.Do not allocate extra space for anoth...
2018-04-24 16:07:52
82
原创 LC 141，142 Linked List Cycle I / II 链表中的环
链表中的环是很经典的面试题，重要的是掌握链表类题目中快慢双指针的用法，不光可以用来解决环的探测，也可以解决其他的问题，例如查找链表中倒数第N个数，只要让fast比slow指针快N个节点，然后两个指针一起前进，当fast走到链表尽头，slow就指向倒数第N个节点（这道LC题前几天做到了，但是忘记是哪一道了）。LC 141 Linked List Cyclebool hasCycle(ListNode...
2018-04-24 13:10:29
113
原创 LC 136，137 Single Number I / II 数组中几乎所有数都出现了N次，找出唯一一个出现1次的数
LC 136 Single NumberGiven a non-empty array of integers, every element appears twice except for one. Find that single one.Note:Your algorithm should have a linear runtime complexity. Could you impleme...
2018-04-24 11:38:30
165
原创 4月22日 刷题报告 LC128-132
128. Longest Consecutive SequenceGiven an unsorted array of integers, find the length of the longest consecutive elements sequence.Your algorithm should run in O(n) complexity.Example:Input: [100, 4, ...
2018-04-23 12:48:50
152
原创 LC 125 Valid Palindrome 常见cctype库函数
非常简单的题目，判断一个给定的字符串是不是回文字符串，跳过字符串中非数字和字母的字符。具体描述如下：Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.Note: For the purpose of this problem, we...
2018-04-21 17:14:14
133
原创 4月20日 刷题报告 LC108-114
今天下午没去实验室做毕设，一个人跑到图书馆刷题去了。气温微凉，外面下着点小雨，是我非常喜欢的天气。LC108，109 Convert Sorted Array / Sorted List to BSTLC108 将有序的数组转化为BST，LC109 将有序的单链表转化为BST。第一个比较简单，用二分和递归的方法，找到mid作为root，将两侧的子数组循环调用构造BST的递归函数。LC109的思路差...
2018-04-20 21:18:45
207
原创 LC 94，98，230 （栈实现的中序遍历三连）
题意：LC94 中序遍历BST，LC98 Validate BST，LC230 Kth Smallest element in BST。LC 94 中序遍历BST迭代的方法中序遍历BST，依赖栈实现，当前节点不为空时一直将左孩子压栈，当节点为空时说明左孩子为空，此时左子树遍历完毕，元素出栈得到父节点值，然后将右孩子压栈，循环往复。注意大循环的判断条件为while( root || ! st.emp...
2018-04-17 20:07:35
155
原创 LC 78. Subsets 求子集的递归和迭代解法
Given a set of distinct integers, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.For example,If nums = [1,2,3], a solution is:[ [3], [1...
2018-04-12 20:38:44
404
原创 LC 60. Permutation Sequence 排列系列之 求第k个排列
The set [1,2,3,…,n] contains a total of n! unique permutations.By listing and labeling all of the permutations in order,We get the following sequence (ie, for n = 3):"123""132""213""231""312""321"
2018-04-08 21:39:11
123
原创 LC 77. Combinations 回溯 / 改进 求组合数C（n， k）
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.For example,If n = 4 and k = 2, a solution is:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]第一眼就感觉非...
2018-04-06 16:23:32
153
原创 LC 75. Sort Colors 双指针 对只含0、1、2的数组的排序，一次遍历
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.Here, we will use the integers 0, 1...
2018-04-05 21:25:52
265
原创 LC31. Next Permutation 排列系列，数组操作
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.If such arrangement is not possible, it must rearrange it as the lowest possible ord...
2018-04-05 14:51:16
238
原创 LC 48. Rotate Image 矩阵变换
You are given an n x n 2D matrix representing an image.Rotate the image by 90 degrees (clockwise).Note:You have to rotate the image in-place, which means you have to modify the input 2D matrix directl...
2018-04-03 23:07:01
117
原创 LC 43. Multiply Strings 大数乘法 / 字符串操作 / 细节：“000”要转化为“0”输出
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.Note:The length of both num1 and num2 is < 110.Both num1 and num2 contains only digits 0-9....
2018-04-03 20:43:15
128
原创 LC 42. Trapping Rain Water 双指针 求能收集的最多的水的体积
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], retu...
2018-04-03 19:42:13
400
原创 LC168 Excel Sheet Column Title 数学
Given a positive integer, return its corresponding column title as appear in an Excel sheet.For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB...
2018-04-02 20:08:53
190
原创 LC40 Combination Sum II 回溯
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.Each number in C may only be used once in the combination.N...
2018-03-22 19:00:01
128
原创 LC22 General Parentheses 回溯/递归 生产所有有效的括号对
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.For example, given n = 3, a solution set is:[ "((()))", "(()())", "(())()", "()(())", "...
2018-03-21 22:14:39
206
原创 LC46, 47 Permutation I and II 回溯
LC46 PermutationGiven a collection of distinct numbers, return all possible permutations.For example,[1,2,3] have the following permutations:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], ...
2018-03-07 20:10:30
183
原创 LC3 Longest Substring Without Repeating Characters 哈希/双指针
问题描述：Given a string, find the length of the longest substring without repeating characters.Examples:Given "abcabcbb", the answer is "abc", which the length is 3.Given "bbbbb", the answer is "b", with ...
2018-02-14 16:06:28
136
原创 LC134 Gas Station 贪心 巧妙的运用关于循环数组的重要结论
问题描述：There are N gas stations along a circular route, where the amount of gas at station i is gas[i].You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to i...
2018-02-13 16:00:28
200
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人