/programmer_practices

algorithm practices

Primary LanguageJava

programmer_practices

algorithm practices

最优解Book:

  1. 双栈实现getMin Stack. Link
  2. 双栈实现Queue. Link
  3. 递归和栈实现逆序操作一个栈. Link
  4. 仅用一个栈排序另一个栈. Link
  5. 打印两个有序链表的公共部分. Link
  6. 删除单双链表倒数第K个Node. Link
  7. 换钱的方法数. Link

HDU-DP:

  1. 牛生牛
  2. 蜜蜂寻路
  3. 数塔

jzOffer:

  1. 二维数组中的查找

2018_xz

  1. 最大乘积
  2. 大整数相乘
  3. 分巧克力
  4. 彩色砖块
  5. 交错01串
  6. 操作序列
  7. 水果与房子
  8. 堆棋子
  9. 疯狂队列
  10. 循环数比较
  11. DNA序列
  12. 猜判断题
  13. 删除重复字符
  14. 回文素数
  15. 字符串价值
  16. 拼凑正方形
  17. 区间表达

LeetCode

  1. Two_Sum
  2. 2_Add_Two_Numbers
  3. 3_Longest_SubString
  4. 4_Median_Two_Array
  5. 5_ZigZag_Conversion
  6. 7_Inverse_Integer
  7. 8_String_to_Integer
  8. 10_Water_container
  9. 101_Symmetric_Tree
  10. 12_Integer_to_Roman
  11. Roman_To_Integer
  12. Longest_Common_Prefix

2019/5/7:

18. 4Sum
19. Remove Nth Node From End of List
20. Valid Parentheses
21. Merge Two Sorted Lists
22. Generate Parentheses
  • 18 3 sum 扩展版, 外层多套一个循环即可。注意判断重复及细节优化
  • 19 细节:nodelist前插入一个dummy node. 删除倒数第n 等于正数查到len - n
  • 20 用stack 最后stack应该是空的
  • 21 遍历直到二list之一为空
  • 22 递归解决 每次传递四个变量:list, string, rightNeed, leftRest

2019/5/8:

23. Merge k Sorted Lists
24. Swap Nodes in Pairs
  • 23 归并法实现21题O(NlogN)
  • 24 链表相邻交换,while循环iterate

2019/5/9:

25. Reverse Nodes in k-Group
26. Remove Duplicates from Sorted Array
27. Remove Element    		
28. Implement strStr()    		
29. Divide Two Integers    
  • 25 这题逆转k有个典型method,之后不断iterate
  • 26 不断抓取新元素到当前index即可,之后index++
  • 27 和上题一个思路
  • 28 【重看】答案写法很巧妙,要点是不写循环条件 内层循环是index==needle时return 结果
  • 29 【重看】 用shift operator,之后shift 除法专门有个trick 正负号用long和abs处理

2019/5/10:

30. [HARD] Substring with Concatenation of All Words
  • 30 【重看!!!】这题做了一天,最后也只是20%左右,github答案90%多

2019/5/11:

31. Next Permutation

1.先找出最大的索引 k 满足 nums[k] < nums[k+1],如果不存在,就翻转整个数组;
2. 再找出另一个最大索引 l 满足 nums[l] > nums[k];
3. 交换 nums[l] 和 nums[k];
4. 最后翻转 nums[k+1:]。
  • 31 这题维基百科有固定公式。中文版参考: LeetCode_31

2019/5/12:

32. Longest Valid Parentheses
33. Search in Rotated Sorted Array
34. Find First and Last Position of Element in Sorted Array
  • 32 这题两个方法 第一个:用stack 找出所有配对括号的index,之后找出最长的连续index串,这里有个trick可以省去排序使最后为O(N). 第二个方法: dp,dp[i]代表该位置作为结尾最长valid括号是多少,'(' 的dp 全为0, 之后分dp[i-1] = '(' 和 dp[i=1] = ')' 讨论。详情见这里: 32. 最长有效括号
  • 33 先用二分法找分割点,之后用常规二分法查找,只不过real_mid = (mid + shift) % len.
  • 34 2个思路 1. 普通二分法,之后向左右延展,速度一般。 2. 二分法找左右分界,<=(或>=)都要继续移动边界,但=target时要记录index. 最后返回的index即为边界. (最快最省空间)

2019/5/13:

35. Search Insert Position
36. Valid Sudoku
37. Sudoku Solver
  • 35 终于一次AC就过了。就是简单的二分查找,判断好停止位置. 小于target就在后方insert, 大于就在当前index insert.
  • 36 这题答案巧。只用一个set就可以搞定,key定义成string: "5 in row 0" 形式就行了,省时间省空间. box序号用i,j算出来
  • 37 这题的答案太强了。。链接: LeetCode37. 思路是先扫面一遍,靠rows,cols,boxs,三个约束进行枚举,用递归来完成。真实体现递归之美,答案太强了。。

2019/5/15:

38. Count and Say
39. Combination Sum
40. Combination Sum II
41. First Missing Positive
42. Trapping Rain Water
  • 38 无脑递归题
  • 39 【重做】凑钱问题。回溯法,递归。这个题自己递归没想出来,看了答案也没完全理解好,最后还是相当于背下来的,必须重做。
  • 40 【重做】遗憾。上一题几乎都是背完了这题还是没做出来,跟上一个题几乎一模一样,只要每次index往后移动一位就行了。唯一注意的就是去重和及时break。啥都不说了。菜是原罪
  • 41 这题的**是遍历一遍nums, 把nums[i]放在i位置上,再遍历一遍nums,若i != nums[i] - 1, 说明这个数缺失。不过这个条件不完全,如果nums中有重复的数字那么就会无限循环, nums[i] != nums[nums[i - 1]] 可以忽略重复元素的情况。
  • 42 和之前做过的蓄水池题类似。每个column积累的雨水量等于左右两边较小的max_barrier_height减去当前height. 3个方法:1. dp 求出每个column's left_max & right_max; 2. stack【还没看这个】 3. 左右两个pointer,每次移动交低height的一端,不断update max_left/right height,并积累面积值。

2019/5/16:

43. Multiply Strings
44. Wildcard Matching
  • 43 校招做过的一道题 然而还是没记住。反转两个字符串, i,j位置乘积累加进arr[i + j], 之后遍历arr, 留下%10, carry进位传到arr[i+1]. 最后从末尾往前加进result的string,注意去0即可。注意额外判断0*0.
  • 44 经典题 通配符匹配 两个方法,一个贪心法,一个dp,还是算是背下来的,肯定要重做了。dp法,两种讨论。1. s[i] == p[i] || p[i] == '?' 2. p[i] == '*', dp[i][j-1] == true || dp[i-1][j-1] == true

2019/5/18:

45. Jump Game II   
46. Permutations
47. Permutations II
48. Rotate Image
  • 45 贪心法,每次在当前步伐范围内搜索能到达的最远的点
  • 46 回溯法经典题 - 无重复元素排列
  • 47 回溯法经典题 - 有重复元素排列
  • 48 翻转matrix. 两个方法: (1) 对于每一圈,都进行的是4个元素间的swap (2) 先上下翻转,再按对角线翻转

2019/5/19:

49. Group Anagrams    
50. Pow(x, n)    
  • 50 乘方,一道经典递归

2019/5/20:

51. N Queens I
52. N Queens II
53. Maximum Subarray
54. Spiral Matrix
55. Jump Game 
  • 51 52, N皇后,回溯法两道经典题. 大体上大家都用的回溯法,时间节约在于isValid的检查。用空间换时间,recur中传递matrix记录可以使俩俩比较的O(N^2) -> O(N)
  • 53 dp 入门题,书上都看过了,看完等于白看 记住吧
  • 54 简单的螺旋打印序列,循环边界玩不好的都gg。-_-
  • 55 jump game 行吧 前一天做完今天就忘了 记住吧 咋整

2019/5/22:

56. Merge Intervals    
57. Insert Interval
58. Length of Last Word
59. Spiral Matrix II
  • 56 没啥新意。就是先按首项排序,然后再从前到后合并,逃脱不了O(nlogn). 值得注意的就是arrays.sort中lambda排序的写法。
  • 57 和上个题一样,巧用Math.min, Math.max可以大幅简化code。从0开始iterate, 分3段处理即可
  • 58 IQ不行,没啥说的。自己的方法还要检查空格和下一个的关系,麻烦的一匹,正解使直接从后往前check就行了。
  • 59 又是一个螺旋题,终于一条过了一个,把握好边界条件就完事儿了。

2019/5/28: 宕工5天。。不能再咸鱼下去了 继续更新

60. Permutation Sequence
61. Rotate List
62. Unique Paths
  • 60 看起来像是个回溯法题,其实是个除法找规律的题,找准边界条件一击ko
  • 61 自己KO的一个题,边界终于靠自己搞对了
  • 62 竟然是1036学的一个组合题。。组合就完事儿了,麻烦地方在于组合公式的优化,直接写成阶乘函数会越界,类型用long.

2019/5/31:

63. Unique Paths II
64. Minimum Path Sum
65. Valid Number
  • 63 一个dp的典型题
  • 64 一个简单的dp
  • 65 这是一道极繁琐的题。。血雨腥风,没想到自己竟然耐着性子做出来了。。

2019/6/1: 惭愧啊,第一个月计划只完成了65%,继续努力吧。

66. Plus One
67. Add Binary
68. Text Justification
  • 66 只判断digit是否等于9就行了,没什么难的
  • 67 简单二进制加法,没啥新意
  • 68 又是一个考验脑力的繁琐题,最后还是磨出来了,但是效率实在太低,35%左右 68_My_Solution

2019/6/2:

69. Sqrt(x)
  • 69 二分法或牛顿法,二分法注意边界,mid = left + (right - mid) / 2, if (mid = x / mid)

2019/6/3-11: 办签证,defer 断更

2019/6/12:

70. Climbing Stairs
71. Simplify Path
  • 70 上台阶 简单的一道dp
  • 71 这题输在自己没文化了。split函数稳准狠。

2019/6/16: Weekly Contest 141 总结:

  • 第一题,最后用的是stringbuffer。第一名uwi大佬方法是复制array,然后keep两个指针
  • 第二题,我先用了个冒泡排序,同时操作两个array,之后再用hashmap检查使用次数。后来发现arrays.sort里可以规定comparator, 这样就可以把两个array copy到一个新array里,再排序新array。之后uwi用的是一个大数组检查使用次数,空间换时间吧
  • 第三题 没做出来,还以为是dp,想错了,以为只能new cell只能来源于上或者左。这题是个典型BFS,读了一遍大佬的code,赛后最后AC了。

2019/6/17:

119. Pascal's Triangle II
  • MySolution
  • 119 这题让我再度怀疑自己智商。写了半天还没写对,最后看大神方法过的。不过有两个巧妙的点,1个是靠arraylist的set函数不断更新上一行的值,最后append一个1, 第二个是利用了杨辉三角公式。不过直接用组合公式会超范围,观察后发现C(N,i) = C(N,i-1) * (row - i) / (i + 1). 另外注意下long.

2019/6/18:

72. Edit Distance
73. Set Matrix Zeroes
74. Search a 2D Matrix
  • 72 Edit Distance 一道经典的dp题,最后也没完全理解. min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1. 注意dp数组代表的是第几个字符,dp[0][0]代表两个空字符串,所以数组大小要注意加1,判断字符相等时也要注意index-1。
  • 73 Set Matrix Zeroes用第一行第一列track矩阵中出现的0,第一行第一列要单独记录0出现的情况,否则后续全matrix都会被set成0.
  • 74 Search a 2D Matrix 二分法,没啥说的

2019/6/19:

190. Reverse Bits
1. Two Sum (Review) 
75. Sort Colors
  • 190 Reverse Bits 看了下大神的神级bit-wise解法,跪了。
  • 75 三指针问题,有点像quicksort

2019/6/20:

912. Sort an Array
929. Unique Email Addresses
  • 912
  • 929 hashmap暴力解决,没啥说的

2019/6/21:

67. [Review]
1073. Adding Two Negabinary Numbers
  • 67 还不如之前写的 怎么还退步了。。
  • 1073 这题我吐血了.脑子真的不好使,没啥说的了,参考一下大神的吧。

2019/6/22:

76. Minimum Window Substring
209. Minimum Size Subarray Sum
9, 13 Review
83. Remove Duplicates from Sorted List
  • 76 code解答看了好几个小时 最后也不能保证下次一定写对。这个系列多练b吧。
  • 209 76同类型。
  • 83 easy-peasy

2019/6/23: weekly contest 142 血崩。第二题还傻了吧唧用sort加priority queue,后来发现一个数组就解决了,智商差距。

2019/6/24:

203
237
77. Combinations
78. Subsets
79. Word Search
784. Letter Case Permutation
  • 777879784 四道回溯题。 79看大佬code过的。 79要【重做】。

2019/6/25:

19.(review)
206. Reverse Linked List
234. Palindrome Linked List

2019/6/26:

876. Middle of the Linked List
24. Swap Nodes in Pairs
143. Reorder List

2019/6/27:

160. Intersection of Two Linked Lists
142. Linked List Cycle II
21. (Review)

2019/6/28:

148. Sort List
2. (Review)
445. Add Two Numbers II
82. Remove Duplicates from Sorted List II

2019/6/29:

92. Reverse Linked List II
  • 92 这题一条过,爽!边界条件也考虑了!双100%!

2019/6/30:

weekly contest 143唉 还是只有两道

2019/7/1:

  • gg 咋就突然7月了
104. Maximum Depth of Binary Tree
110. Balanced Binary Tree
543. Diameter of Binary Tree
80. Remove Duplicates from Sorted Array II
81. Search in Rotated Sorted Array II
1105. Filling Bookcase Shelves
  • 104, 110, 543
  • 81 唉 这题最后还是背下来的【重做】
  • 1105 contest143 第三题,dp, 思路就是比较两种方案:(1) 新书直接放到新的一层h = dp[i-1] + h; (2) 新书放在新的一层,同时从上面往下拽旧书,超过width立刻break。每拽下来一本书,计算当前的总高度值: dp[i] = dp[j-1] + maxHeight(j...i), 如果更小了,就update

2019/7/2:

872. Leaf-Similar Trees
94. Binary Tree Inorder Traversal
897. Increasing Order Search Tree
114. Flatten Binary Tree to Linked List
  • 114 这题最后也没想太明白,背的估计明天就得忘了。【重做】
  • 872, 94, 897, 114

2019/7/3:

105. Construct Binary Tree from Preorder and Inorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
  • 105, 106 这俩题看了一晚上,核心**是利用pre的head是root, post的tail是root,在inorder中定位root,分割后不断递归添加node及其left&right child. 难点是分割数组长度,注意要保证每次递归的时候传递的数组长度应该相同,把握这点就容易很多了。

2019/7/5:

173.  Binary Search Tree Iterator
100. Same Tree
101. Symmetric Tree
951. Flip Equivalent Binary Trees
889. Construct Binary Tree from Preorder and Postorder Traversal

2019/7/6:

450. Delete Node in a BST
145. Binary Tree Postorder Traversal
102. Binary Tree Level Order Traversal
987. Vertical Order Traversal of a Binary Tree

2019/7/7:

662. Maximum Width of Binary Tree
103. Binary Tree Zigzag Level Order Traversal
113.Path Sum II
  • Weekly Contest 144 (1266 / 4358), 这周挺简单的,tree也做出来了。。不过跟大神比还是太菜了。。
  • 662这题跟level-order traversal差不多,思路都是用queue横向迭代,差异就是多了个坐标,不断计算并更新即可。
  • 103还是level-order traversal, 加的时候顺反序交替就行了。
  • 113 回溯法,这个题注意满足sum条件后仍要删除tmp.get(n-1),因为helper调用了两次(left,right),right还会用到,所以tmp必须控制相同

2019/7/8:

222. Count Complete Tree Nodes
236. Lowest Common Ancestor of a Binary Tree
99. Recover Binary Search Tree

2019/7/8:

129. Sum Root to Leaf Numbers
297. Serialize and Deserialize Binary Tree
979. Distribute Coins in Binary Tree

2019/7/9:

507. Perfect Number
50. Pow(x,n) - review
704. Binary Search
475. Heaters

2019/7/10:

215. Kth Largest Element in an Array
973. K Closest Points to Origin
1046. Last Stone Weight

2019/7/11:

969. Pancake Sorting

2019/7/12:

324. Wiggle Sort II

2019/7/13:

  • Biweekly Contest 4, 最后一题被HARD标签唬住了,难受。

2019/7/14:

15. 3 Sum
324. Wiggle Sort II
162. Find Peak Element
1095. Find in Mountain Array
  • Weekly Contest 145. 第三题01子序列差1,没搞出来,记得搞一下。
  • 15 排序后,以第一个首字母为基准,负数才开始挑,否则pass, 两指针向中间移动
  • 324 zigzag数组排序. 先找中位数,小于中位数的从高往低偶数位排列,大于中位数的从低往高奇数位排列。
  • 162 只需要比较和后一个元素的大小即可。 3种情况: 全递增,全递减,在peak。 二分法: 找index条件用(l < r), return index 用(l <= r). 二分法直接返回index.
  • 1095 先找peak, 前半部分则为递增序列,后半部分为递减序列,用两次二分。

2019/7/16:

240. Search a 2D Matrix II

2019/7/19:

264. Ugly Number II
313. Super Ugly Number
496. Next Greater Element I
503. Next Greater Element II

2019/7/21:

16. 3Sum Closest - Review
31. Next tPermutation - Review
239. Sliding Window Maximum
  • weekly 146 惨败。
  • 为了做480题先做295, 为了做295先做293...
  • 16, 31, 239

2019/7/22:

295. Find Median from Data Stream
480. Sliding Window Median
871. Minimum Number of Refueling Stops

2019/7/25:

875. Koko Eating Bananas
1011. Capacity To Ship Packages Within D Days
778. Swim in Rising Water

2019/7/26:

668. Kth Smallest Number in Multiplication Table

2019/7/28:

Weekly Contest 147

2019/7/29:

419. Battleships in a Board
547. Friend Circles

2019/8/12:

841.Keys and Rooms
200. Number of Islands

2019/8/14:

529.Minesweeper
79. Word Search (Review)
994. Rotting Oranges

2019/8/15:

1091. Shortest Path in Binary Matrix

2019/8/16:

785. Is Graph Bipartite?

2019/8/22:

127. Word Ladder
990. Satisfiability of Equality Equations

2019/8/22:

  • S4E7 Linked List II (Round 2)
19,206,234. Reiview
1054. Distant Barcodes