文档章节

Leetcode日记8

fxdhdu
 fxdhdu
发布于 2016/02/18 20:11
字数 2841
阅读 113
收藏 1

(2015/2/3)

LeetCode 4 Median of Two Sorted Arrays

题目大意:找到两个已排序数组的median。

median:中间位置的值。

 

算法:

参考:https://leetcode.com/discuss/15790/share-my-o-log-min-m-n-solution-with-explanation

1)理解什么是median:

   1. median将一个集合,分成两个相同长度的子集。

   2.其中一个子集所有的数都大于等于另一个子集。

2)

    结合题目,将median的两个条件在程序中表现出来。

3)

    使用二分查找,查找满足条件的分割点。

4)

    边界条件的判断。(保证数组下标的正确性)

5)

    注意哪个数据较长,对计算有影响。

 

 


(2015/2/5)

LeetCode 89 Gray Code

题目大意:生成n位格雷码。

算法:(格雷码的递归生成算法)

 

    1)1位格雷码有两个码字

    2)(n+1)位格雷码中的前2n个码字等于n位格雷码的码字,按顺序书写,加前缀0

    3)(n+1)位格雷码中的后2n个码字等于n位格雷码的码字,按逆序书写,加前缀1

 

 


 

(2015/2/6)

LeetCode 151 Reverse Words in a String

注意:

1)删除字符串的前缀空格和后缀空格

2)删除两个word之间多于的空格

 

3)使用string中的erase操作删除多于的空格。

 

 


 

(2015/2/9)

LeetCode 216 Combination Sum III(多看)

递归实现回溯算法。

使用到的C++知识及技巧:

1)vector的back、empty、pop_back等操作。

2)使用一个形参表示余下还要加上多少数,而不是总数。

 

 


 

(2015/2/16)

LeetCode 230 Kth Smallest Element in a BST

二叉搜索树的中序遍历。

 


 

(2015/2/18)

LeetCode 39 Combination Sum

回朔法

1)push_back() 和 pop_back()操作要对称。

 

 

LeetCode 40 Combination Sum II

回朔法:同39,加一句判断跳过重复。 

 

LeetCode 43 Multiply Strings

字符串表示的数字的乘法。

1)

string::find_first_not_of('0');    //找到第一个非'0'的字符。

string::npos    //表示不存在的位置。可用于判断位置是否找到。

string::substr    //用于表示string的子字符串。

 

2)把两个字符串的下标都表示出来,则可以清晰地理解其原理。

 

LeetCode 50 Pow(x, n)

1)使用乘法的结合律,减少乘法的次数。

2)注意处理指数为INT_MIN的情况。

 

 


 

(2015/2/19)

LeetCode 54 Spiral Matrix

一步一步走,找到一个坐标,插入一个数。

 

LeetCode 55 Jump Game

1)

参考:https://leetcode.com/discuss/15567/linear-and-simple-solution-in-c

使用两个下标:一个表示当前位置,一个表示我当前能达到的最远位置。

2)

使用递归遍历所有的情况会超时。

 

 


 

(2015/2/24)

LeetCode 181 Employees Earning More Than Their Managers

数据库:

1)自联结

2)AND关键字

 

LeetCode 182 Duplicate Emails

1)GROUP BY

2)HAVING

3)COUNT

 

LeetCode 183 Customers Who Never Order

1)子查询

2)NOT IN

3)DISTINCT

 

LeetCode 197 Rising Temperature

1)自联结

2)DateDiff函数:计算两个日期之差。

 

LeetCode 176 Second Highest Salary

参考:https://leetcode.com/discuss/21751/simple-query-which-handles-the-null-situation

1 )MAX函数

2)子查询

 

 


(2015/2/26)

LeetCode 175 Combine Two Tables

1)外部联结:联结包含了那些在相关表中没有关联的行。

 

 


 

(2015/2/27)

LeetCode 180 Consecutive Numbers

1)联结3个表

2)使用DISTINCT关键字。

 

 


 

(2015/2/28)

LeetCode 309 Best Time to Buy and Sell Stock with Cooldown(多看)

参考:https://leetcode.com/discuss/71354/share-my-thinking-process

动态规划:

The key for dp is to find the variables to represent the states and deduce the transition function.

1)3种动作:sell、buy、rest

2)以某种动作结束的交易序列的最大利益。

3)方程推导。

4)设计算法时可暂时不考虑时间和空间,编程实现时再考虑就行。

 

 


(2015/2/29)

LeetCode 300 Longest Increasing Subsequence(多看)

(OK)参考:http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

(超时)参考:http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/

1)递归+DP:超时

2)二分查找+一种用数组表示链表尾元素的算法。(OK)

 

LeetCode 64 Minimum Path Sum

因为只能向右和向下走,所以比较简单。

1)建立一个到每一个格子的最小步数的二维数组。

 

 


(2015/3/1)

LeetCode 178 Rank Scores

1)外层查询的表命名为s

2)子查询计算名次(与外层查询进行比较)。

 

LeetCode 184 Department Highest Salary

1)联结两个表,用where子句过滤出同一部门拥有最高工资的是哪些人。

 

 

LeetCode 177Nth Highest Salary

1)使用LIMIT限制输出第几行后多少个行。

2)注意相同的Salary排名相同。所以要使用DISTINCT;

 

 


(2015/3/2)

LeetCode 49 Group Anagrams

自己的方法:

1)计算一个字符串每一个字符出现的次数作为标识。(击败2%)

参考别人的方法:(击败30%)

1)复制一个vector<string>

2)对副本中的每一个string进行排序。排序后的string作为标识,并保存具有相同string的下标值,来引用未排序的string。

 

 


 

(2015/3/3)

LeetCode 71 Simplify Path

1)把绝对路径进行分解

"/a/./b/../../c/"可以分解为:

        "/a"    

        "/." 

        "/b" 

        "/.." 

        "/.." 

        "/c"     

        "/"

2)对各种情况加以处理即可。

 

LeetCode 195 Tenth Line

1)awk工具:设计用于数据流。可以对列和行进行操作。

2)变量NR:表示记录数量,在执行过程中对应于当前行号。

 

LeetCode 63 Unique Paths II

1)建立二维数组

2)若遇到障碍,则到达相应格子的步数为0。

 

LeetCode 73 Set Matrix Zeroes

1)O(m + n) space:保存需要清零的行和列。

2)考虑只使用常量空间的算法

 

 


(2015/4/16)

200. Number of Islands

1)自己实现的BFS效率较低

2)用 {1, 0} 表示一个vector<int> 对象

 

 


(2015/4/17)

130. Surrounded Regions

1)BFS效率较低

 

 


(2015/4/18)

279. Perfect Squares

1)递归实现dfs

 

326. Power of Three

判断一个数是否是3的幂

1)使用对数的方法,当n = 243时出现错误。因为double型不精确。

2)可以使用 3^19 % 3 ^ n == 0 

 

 


(2015/4/19)

342. Power of Four 

判断一个数是否是4的幂

1)可以使用对数的方法。

2)不能用 4^15 % 4^n == 0。因为 4^15 % (非4的幂) 也可能 == 0,如2和8。


162. Find Peak Element

1)按顺序查找

2)二分查找(较难理解)

 

240. Search a 2D Matrix II

1)判断元素是否在某一行,然后进行二分查找。(效率较低)

 

 


(2015/4/20)

198. House Robber

参考:http://blog.csdn.net/lu597203933/article/details/44810981

1)动态规划:

    两个状态:没有偷当前房子的最大值;偷了当前房子的最大值。

    这两个状态的转移。

 

172. Factorial Trailing Zeroes

参考:https://leetcode.com/discuss/19847/simple-c-c-solution-with-detailed-explaination

 


(2015/4/21)

209. Minimum Size Subarray Sum

1)two point

 

289. Game of Life

题意参考:http://my.oschina.net/Tsybius2014/blog/514447

1)in-place的算法:除了0表示dead、1表示live外添加两种状态。10表示live to dead,101表示dead to live。

 

 


(2015/4/24)

152. Maximum Product Subarray (多看,理解)

参考:https://leetcode.com/discuss/11923/sharing-my-solution-o-1-space-o-n-running-time

动态规划:

定义变量:

1)包括当前元素的最大乘积

2)包括当前元素的最小乘积

3)包括前一个元素的最大乘积

4)包括前一个元素的最小乘积

5)当前全局最大乘积

 

338. Counting Bits

一遍循环完成计算

 

Hint:

1)You should make use of what you have produced already.

2)Divide the numbers in ranges like [2-3](两位二进制数), [4-7](3位), [8-15](4位) and so on. And try to generate new range from previous.

计算3位的二进制数包含多少1,只需对1位和2位的相应二进制数加1即可。

例如:

1位    2位        3位

0        10        100

1        11        101

                      110
                      111

 

343. Integer Break

动态规划:4 = 2 + 2 --> 2 * 2 = 4; 2 = 1 + 1 -- 1 * 1 = 1; 所以 4 不应该是 2  + (1 + 1);

 

120. Triangle

动态规划:到达某层某个数的最短距离是,他上一层相邻的两个数中较小的,加上这个数。


(2015/4/29)

221. Maximal Square

参考:https://leetcode.com/discuss/38489/easy-solution-with-detailed-explanations-8ms-time-and-space

1)动态规划的关键:找到状态方程

2)定义状态:the maximal size of the square that can be achieved at point (i, j), denoted as P[i][j]

3)状态转换方程:分别对第一行、第一列、其他下标定义状态转换方程。转移方程根据矩阵中为‘0’或‘1’而定。

304. Range Sum Query 2D - Immutable

1)较简单。


(2015/5/4)

213. House Robber II

根据是否选择最后一个房间,把问题转化为House Robber I的情况。

91. Decode Ways

考虑是否全面。什么情况下无解。不同位置上的0的情况。


(2015/5/6)

264. Ugly Number II

动态规划:每次添加一个ugly number,添加哪一个?


(2015/5/10)

347. Top K Frequent Elements

使用multimap


(2015/5/13)

227. Basic Calculator II  

1)使用队列

345. Reverse Vowels of a String

1)two point


(2015/5/17)

93. Restore IP Addresses

深度优先遍历+剪枝

string:substr(起点,长度)


(2015/5/20)    

47. Permutations II

与Permutations I相似:用字典序法计算全排列。
1)对nums排序,得到字典序中的第一个字符串。
2)从排列的右端开始,找出第一个比右边数字小的数字。序号记为a。
3)在序号为a的右边的数字中,找出所有比nums[a]大的数中最小的数字。序号记为b。(此过程对nums中元素是否重复,无影响)
4)对换nums[a]和nums[b]。
5)对nums[a + 1]到最后的元素排序。


(2015/5/29)    

10. Regular Expression Matching    正则表达式匹配

参考:https://leetcode.com/discuss/9405/the-shortest-ac-code

1)子函数:匹配两个字符串的第一个字符

2)递归


(2016/6/11)   

77. Combinations

78. Subsets

79. Word Search


(2016/6/16)   

80. Remove Duplicates from Sorted Array II

1)two pointers

2)in place


(2016/6/17)   

33. Search in Rotated Sorted Array 旋转数组中查找一个元素

二分查找,注意区分元素可能出现在哪一段。


(2016/6/19)   

81. Search in Rotated Sorted Array II

在33题的基础上,添加相等的判断。若相等则扫描。


(2016/6/20) 

82    Remove Duplicates from Sorted List II

用三个指针

 

86. Partition List

思路:遍历,找到一个比x小的节点,改变此节点在链表中的位置

用3个指针

1)一个表示比x小的最后一个节点,之后比x小的节点在此节点后插入

2)一个用于寻找比x小的节点,一个是此节点的前驱

 

349. Intersection of Two Arrays


(2016/6/21) 

90. Subsets II (想不到)

参考:https://leetcode.com/discuss/34975/accepted-solution-backtracking-only-lines-easy-understand

1)回溯法

2)递归

 

92. Reverse Linked List II

自己构造测试用例,以完善代码。

 

131. Palindrome Partitioning

回溯法:弹进,弹出


(2016/6/22) 

109. Convert Sorted List to Binary Search Tree

递归

 

129. Sum Root to Leaf Numbers

二叉树的先序遍历


(2016/6/23) 

134. Gas Station(不会)

参考:https://leetcode.com/discuss/4159/share-some-of-my-ideas


(2016/6/24) 

142. Linked List Cycle II

参考:《剑指offer纪念版》面试题56

 

139. Word Break(多理解)

参考:https://leetcode.com/discuss/18904/java-implementation-using-dp-in-two-ways(20ms)

参考:https://leetcode.com/discuss/21709/dynamic-programming-simple-fast-solution-with-optimization(4ms,同样的算法,遍历顺序相反)


(2016/6/26) 

143. Reorder List

分3步做


(2016/6/27) 

147. Insertion Sort List

用插入排序来排序链表


(2016/6/29)

148. Sort List

链表的归并排序算法。

1)如何找到链表的中点?使用快慢指针,一个指针走1步,一个指针走两步,当快指针到达终点时,慢指针到达链表的中点。

2)递归实现归并排序。

3)归并排序的思想:1)将所要排序的链表分为长度相同的两个子链表,2)分别对左右子链表进行归并排序,3)合并左右子链表为一个有序的链表。

© 著作权归作者所有

fxdhdu
粉丝 6
博文 50
码字总数 38322
作品 0
杭州
程序员
私信 提问
LeetCode日记2

LeetCode-5 思路: (1)最后用子字符串操作返回string。 return s.substr(startpos, maxlength); (2)回文串的判断: 1)首先找出回文串中间连续的重复的字符。 2)再向两边进行判断 (3...

fxdhdu
2015/10/19
81
0
Leetcode日记6

(2015/11/28) LeetCode 303 Range Sum Query - Immutable:(Easy) 1)超时的算法:每次调用sumRange函数进行一次累加运算。 2)不超时的算法:改变数组的内容,存储从0下标到当前下标所有...

fxdhdu
2015/11/28
106
1
Leetcode日记7

(2015/1/2) LeetCode 318 Maximum Product of Word Lengths 题目: 1)求一个字符串数组中,两个不同的字符串的长度乘积的最大值。 2)这两个字符串不能共同拥有同一个字符。(两个字符串的...

fxdhdu
2016/01/03
52
0
LeetCode日记1

第一题 错误思路: (1)不能直接用双重for循环判断两个数相加等于target,会超时。 正确思路: (1)用一个结构体记录数字和数字的index。 (2)用qsort对结构体的vector排序。 (3)双重f...

fxdhdu
2015/10/18
34
0
LeetCode | 机器人能否返回原点

放假的时间已经过去一半了,每天坚持看一个多小时的书,时间虽然不多,但是能专心把书看进去就可以了。今天分享的是 LeetCode 上面的第 657 题,题目是《机器人能否返回原点》,这也是一道简...

tosser
10/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

一个yuanbeth
今天
4
0
总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
今天
5
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
今天
4
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部