一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
把贵司信息放这里
查看: 257|回复: 9
收起左侧

[打卡] 在职刷题打卡

[复制链接] |试试Instant~ |打卡, 打卡组队
我的人缘0

分享帖子到朋友圈
annig | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
激励自己坚持每天打卡,刷题不能断!


上一篇:[第五期活动] 在职刷题打卡,目标工作日一天2题,周末一天5题
下一篇:【求组队】IBM GBS - entry level DS - Finish Line
我的人缘0
 楼主| annig 2019-11-9 02:46:58 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
11/7
387. First Unique Character in a String, String, use count array to store freq of each char.
339. Nested List Weight Sum, Recursive: DFS, call helper function recursively with d + 1 when current NestedInteger is list, otherwise add n * d into res.
                                                 Iterative: BFS, level order traversal.
364. Nested List Weight Sum II, BFS, use prev to store sum of all prev levels and total of current level, and use res to store total res += prev;
766. Toeplitz Matrix, always compare (i, j) with (i - 1, j - 1)
463. Island Perimeter, loop each (i, j), if current is islands, res += 4, then check neighbor, if one neighbor is island, res -= 2. Note: only check right and down directions to avoid duplicate
695. Max Area of Island, BFS, maximum connected component最大连通分量, Note: if grid[i][j] ==1 && !v[i][j]
378. Kth Smallest Element in a Sorted Matrix, PQ, only add right and down position into pq as potential next minimum value.
                                                                          !!!binary search, use count of numbers <= mid to decide how to move l and r, 因为row和col都是排序的,计算count的方法很巧,类似287
287. Find the Duplicate Number, !!!BS using count to decide how to move l and r, (count of numbers <= mid), 太社会了这方法, 需要加强
                                                     Two pointers, 快慢指针, 类似Linked List Cycle II. Note: must use do-while
733. Flood Fill, BFS, use boolean[][] v to track visited to avoid duplicate, or before BFS, we check if oldColor == newColor, directly return image
回复

使用道具 举报

我的人缘0
 楼主| annig 2019-11-10 02:48:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
11/8
496. Next Greater Element I, 单调递减栈 + HashMap, use stack to store decreasing numbers, when nums2[i] is greater than peek(), which means nums2[i] if next greater element of peek, it forms pair as (peek(), nums2[i]), store pair in hashmap, for every number remain in the stack, it has no next greater.
739. Daily Temperatures, 单调递减栈, similar to 496, use stack to store the index, then compare T[s.peek()] and T[i]
824. Goat Latin, String
896. Monotonic Array, Array, One pass
953. Verifying an Alien Dictionary, HashMap to store the order pairs, then check adjacent two words, helper check function: find first index of two chars are different, check the order, if no diff, return i == w1.length()
405. Convert a Number to Hexadecimal, 进制转换, if num < 0, long n += Math.pow(2, 32); (将负数+32个1)转换成正数,必须用long, Integer.MAX_VALUE = 2^31-1, Integer.MIN_VALUE = -2^31
414. Third Maximum Number, must use Integer to initialized max as null, for final check whether there exists a third max. We cannot use Integer.MIN_VALUE, since it may also be considered as third max. When compare two object types(Integer), not primitive value(int), we use equals to compare whether the value are the same. Before we compare nums[i] with max value, we must convert the nums[i] into Integer, and use equals() fn
回复

使用道具 举报

我的人缘0
 楼主| annig 2019-11-11 02:25:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
11/9
复习Quick select, Quick sort, Merge sort, 重点刷Tree和BFS
973. K Closest Points to Origin, PQ, max heap to keep K elements.
912. Sort an Array, quick sort
104. Maximum Depth of Binary Tree, D&C
404. Sum of Left Leaves, preorder traversal, when root.left != null && root.left.left == null && root.left.right == null, add val into res
226. Invert Binary Tree, D&C
Path Sum系列
112. Path Sum, D&C, if root == null, return false; if root is leaf && root.val == target, return true;
113. Path Sum II, DFS, if root is a leaf, check if sum == root.val, add root.val into cur, add cur into res, remember to remove the last from cur list and return; recursion part: add root.val into cur list, try to find in the left subtree, try to find in the right subtree, remove;
437. Path Sum III, D&C, for each subtree, countStartFrom(root) + pathSum(root.left) + pathSum(root.right), Note: in countStartFrom function, can't return 1 when root.val == sum, since if return, it won't cover the case of a path which contains another valid path before.
666. Path Sum IV, HashMap + DFS, store (index, val) pair in hashmap, if cur node at level l and pos p, then left at level + 1, p * 2 - 1, right at level + 1, p * 2;
124. Binary Tree Maximum Path Sum
回复

使用道具 举报

我的人缘0
 楼主| annig 2019-11-12 01:13:58 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
11/10
442. Find All Duplicates in an Array, 难点: O(1) space and O(n) time. Since 1<= nums[i] <= n, so we can map value as index, each time, find the according index, update the value as negative, if we reach any index with negative value already, which means it's duplicate
151. Reverse Words in a String, 正则表达式, regular expression, s.trim().split("\\s+"); \\s means space or line break, + means multiple
153. Find Minimum in Rotated Sorted Array, Binary Search, if nums[m] > nums[r], means the rotate point in the right half, then r = m, else, l = m; This covers the corner cases like [1,2,3] or [3,2,1];
154. Find Minimum in Rotated Sorted Array II, BS, 153 follow up with duplicate values.
33. Search in Rotated Sorted Array, BS, check which half is not rotated, in the not rotated range, if the target value is in the half range, then narrow down the range into that half.
81. Search in Rotated Sorted Array II, BS, 81 follow up with duplicate values.
938. Range Sum of BST, only go further if still in range.
162. Find Peak Element, BS, At the end, we only need to compare nums[l] and nums[r], return the larger one.
852. Peak Index in a Mountain Array, Similar to 162
31. Next Permutation, find first descending index1 from the end, find the first larger index2 than the index1, swap index1 and index2, then reverse index1 + 1 to the end. Remember when find the first desc and the first larger index, do not forget to break!!!
419. Battleships in a Board, if cur value is 'X', check if i > 0 && b[i - 1][j] == 'X' or if j > 0 && b[i][j - 1] == 'X', continue, otherwise, res ++
647. Palindromic Substrings, DFS or 区间型DP, boolean[][] dp = new dp[n][n]; dp[i][j] means from index i to index j is a valid palindrome. 1. len == 1, dp[i][i] = true, res ++; 2. len == 2, if s.charAt(i) == s.charAt(i + 1), dp[i][i + 1] = true, res ++; loop from len = 3 to len == n, loop start index i from 0 to i == n - len; int end index j would be j = i + len - 1; dp[i][j] is valid only if dp[i + 1][j - 1] is valid and s.charAt(i) == s.charAt(j).
987. Vertical Order Traversal of a Binary Tree, PQ, Point prev = null, when prev == null || prev.x != cur.x, which means we need to new another array list to save the cur value, res.add(new ArrayList<>()); update prev i=with cur. add cur.val into the last array list in res.
767. Reorganize String, HashMap + PQ + Greedy, first check if any character has freq > (n + 1) / 2, then it's impossible to reorganize string, return ""; add char with max freq first, then second max freq first, update freq for both, add back to queue if freq > 0.
540. Single Element in a Sorted Array, BS, use the odd or even position of mid to check whether the first half has unique value
回复

使用道具 举报

我的人缘0
 楼主| annig 2019-11-13 09:15:55 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
11/11
1219. Path with Maximum Gold, DFS, cur is the max value of 4 directions, cur = Math.max(cur, dfs(grid, nx, ny, dx, dy, v)); return cur + grid[i][j]. Remember to reset v[i][j] = false;
1110. Delete Nodes And Return Forest, pass Parent node to dfs, if cur need to be deleted, updateParent(root, parent) to delete current node, then call further dfs with parent as null. If not to be deleted, check if parent is null, add root.val into res, call dfs with root as parent
1091. Shortest Path in Binary Matrix, BFS
1087. Brace Expansion, DFS, use HashSet to save all the possible characters in {} pairs, then call further dfs
1057. Campus Bikes, PQ
621. Task Scheduler, PQ + HashMap
825. Friends Of Appropriate Ages
311. Sparse Matrix Multiplication, 矩阵乘法要加强
1165. Single-Row Keyboard, HashMap
回复

使用道具 举报

我的人缘0
 楼主| annig 2019-11-19 02:19:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
11/12
只看了一些题并没有刷,太罪恶了=,=

11/13
701. Insert into a Binary Search Tree
1249. Minimum Remove to Make Valid Parentheses
951. Flip Equivalent Binary Trees

11/14
放飞自我的一天。。。

11/15
865. Smallest Subtree with all the Deepest Nodes

11/16
各种借口颓废了好几天。。。得好好反省一下!
56. Merge Intervals, sort by start time, use list to store intervals after merge, loop from the second one, always compare with the last one in the list, if merge, update the last one in the list, otherwise, add into list.
42. Trapping Rain Water, Stack, find the nearest greater one from each side and calculate area

11/17
Anagram系列
242. Valid Anagram, int[] count to store frequency of each character
49. Group Anagrams, hashMap, getAnnotate(), eg, a1e1t1, use annotate as key of map and list to store all String which has the same annotate
760. Find Anagram Mappings, HashMap, store all value and index pairs from B in hashmap, then loop A to get each index
438. Find All Anagrams in a String, Sliding Window, 最优解多复习!int[] c1 to store character frequency for s, int[] c2 to store freq for p, int[] d to store delta value for each character, int abSum to check the current absolute sum of delta array
128. Longest Consecutive Sequence, HashSet, store everything in hashset, then when the set does not have i + 1, calculate the count of i - 1, update res
回复

使用道具 举报

我的人缘0
 楼主| annig 2019-11-20 02:49:59 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
11/18
71. Simplify Path, Stack, Note: directly pass an array into hashset to store all the spacial cases, new HashSet<>(Arrays.asList(".", "..", "")); when append the final result, can use insert sb.insert(0, "/" + st.pop());
881. Boats to Save People, Sort + Two pointers, Note: one boat can only seat 2 people, so compare each pair of i and j, if fit, then move both index, if not, move bigger one
785. Is Graph Bipartite, BFS, Sparse Graph means not all node connected, then we must add one more loop outside the bfs to make sure we check each node, each time, if the node is not colored and it has neighbor add into queue for checking
129. Sum Root to Leaf Numbers, DFS, dfs(root, 0), each recursive call, pass the previous sum
回复

使用道具 举报

我的人缘0
 楼主| annig 前天 05:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
11/19
12. Integer to Roman
523. Continuous Subarray Sum, HashMap, Math problem, be cautious on corner cases. if prefix sum of subarray A sumA % k = q, and another larger prefix sum of subarray B has the same q, which means the subarray in the middle is n * k; 找两个除以k余数相同的子串
1004. Max Consecutive Ones III, Sliding window
1008. Construct Binary Search Tree from Preorder Traversal, DFS
1053. Previous Permutation With One Swap, Similar with Next Permutation. Find the index needs to be swapped, then find the possible largest value which is smaller than the index from the end, find the very first one of that value.
1094. Car Pooling, TreeMap, Similar with Meeting Room II, save the number of +ppl and -ppl for each stop, then loop the values in the treemap, check any stop has negative capacity
回复

使用道具 举报

我的人缘0
 楼主| annig 昨天 03:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
感恩节放假出去浪 心太浮躁了 很多天没有学习打卡。。。新的起点,慢慢来比较快!

12/7 BFS专题
Lintcode 726. Check Full Binary Tree
958. Check Completeness of a Binary Tree, use global boolean flag to track whether there is null node before cur, if cur is not null, if flag, then return false, otherwise, add left and right children into queue
102. Binary Tree Level Order Traversal, BFS level order traversal
107. Binary Tree Level Order Traversal II, BFS, arraylist add at the first index, res.add(0, level);
103. Binary Tree Zigzag Level Order Traversal, BFS, boolean leftRight to track direction on current level, then set it to !leftRight.
429. N-ary Tree Level Order Traversal, BFS

contest
1281. Subtract the Product and Sum of Digits of an Integer
1282. Group the People Given the Group Size They Belong To, HashMap
1283. Find the Smallest Divisor Given a Threshold, Binary Search
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-12-10 20:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表