Monthly Archives: October 2016

  1. Trapping Rain Water

    Leave a comment

    October 31, 2016 by oneOokay

    和这个极其相似:Largest rectangle in histogram Largest rectangle in historgram 是在维护一个单调递增的栈,对于当前i需要找出i向左的第一个小于它的数和i向右的第一个小于它的数。 Trapping Rain Water则需要维护一个单调递减的栈,对于当前i需要找出i向左的第一个大于大的数和i向右的第一个大于它的数。(i为bottem). 初次写的代码如下:注意栈里面存的是index public int trap(int[] height) { if (height …
    Continue reading

  2. Rotate Image

    Leave a comment

    October 31, 2016 by oneOokay

    普通的array操作。 “剥洋葱”法一层一层的旋转。注意旋转的坐标的对应改变以及offset的用法。 public class Solution { public void rotate(int[][] matrix) { int start = 0;  //行 int end = matrix.length …
    Continue reading

  3. Letter Combinations of a Phone Number

    Leave a comment

    October 31, 2016 by oneOokay

    两种方法:DFS+backtracking和Queue. DFS的已经能够顺利做出来了. 两个java基本的知识点: StringBuffer: sb.deleteCharAt(sb.length() – 1) 或者 sb.setLength(sb之前的length) 把一个char形式的数字转换回真正的数字的方法: char – ‘0’ Character.getNumericValue(char) Integer.parseInt(String.valueOf(d.charAt(index))) :这个比较绕还是不用比较好. 以及能用array存就尽量用array,不要用hashmap. array在这个index取值方面高一些??? 来看一下queue的方法: e.g.: …
    Continue reading

  4. Copy list with Random Pointer

    Leave a comment

    October 31, 2016 by oneOokay

    A linked list is given such that each node contains an additional random pointer which could point to any node …
    Continue reading

  5. Sliding Window Maximum

    Leave a comment

    October 30, 2016 by oneOokay

    写了个暴力解法O(mk)过了。暴力解法大家应该都能写到,但是这个题目考的是另外的优化解法,有两种:max heap和双向队列(DEQUE)。https://segmentfault.com/a/1190000003903509 所以暴力解法的两个for-loop,要想办法只用一个for-loop,那么在求整个window中的max这里,就需要是一个O(1)。 发现以前做过一个最小栈,跟这个可能没什么关系,但是可以看一下刷新一下记忆。 MAX HEAP: “堆”是priority queue based on priority heap. 默认排序是最小值为head,位于顶端。priority queue里不允许null。PriorityQueue O(logn)的enqueue dequeue时间。所以一下的时间复杂度是O(nlogn).空间复杂度是O(n). public int[] maxSlidingWindow(int[] nums, …
    Continue reading

  6. Serialize and Deserialize Binary Tree

    Leave a comment

    October 30, 2016 by oneOokay

    Serialization is the process of converting a data structure or object into a sequence of bits so that it can …
    Continue reading

  7. Product of Array Except Self

    Leave a comment

    October 30, 2016 by oneOokay

    DP肯定不行O(n)就达不到。我能做到的只是两个for loop,初始化ans[i]都为1. 然后TLE了。O(n)的时间复杂度上来看,只能对array进行一次扫描。想不出其他的解法了。 for (int i = 0; i < nums.length; i ++) { int tmp = nums[i]; for (int …
    Continue reading