Monthly Archives: March 2017

  1. Union Find

    Leave a comment

    March 19, 2017 by oneOokay

    这里讲的超级详细: https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf Union Find主要是用于: “Network connectivity” 给你N个点和一些边的集合edges[][]: 用Union Find可以判断 图是否存在环 某两点之间是否是联通的(两点间是否存在一条通路): Find 一空有多少个联通的区域(区域之间互相不连通): 如果只有一个的话,那么该图就是一个连通图 给两个点,如果存在通路的话把他们联通起来….Union 还能够建树. 基本的数据结构是: 一个数组:int[] ids: size为n(点的个数).i代表lable为i的点.ids[i]代表这个label == …
    Continue reading

  2. 01背包及优化

    Leave a comment

    March 16, 2017 by oneOokay

    01背包:(对于一个物品,取或者不取(取0次和取1次)) 一个背包能够给装总重量为W的物品 总共N个物品: 第i个物品的重量为w[i] 第i个物品的价值为v[i] 每个物品可取可不取.(取1次或取0次) 求:背包所能够装的所有物品的最大的总价值为多少. 二维数组 空间优化:一维数组 值的初始化: (背包恰好装满的情况下,背包内所有物品的最大的总价值为多少) 常数的优化: 对于物品进行排序优化 输出路径 假设背包能够装重量为10, 总共5个物品:#0-#4.重量为:{2,2,6,5,4},价值为:{6,3,5,4,6}.开始填这样一个表: header的0-10代表此时背包能够装的总重量W 空的格子里面([n][W])填:当背包能装的总重量为W的时候,考虑装前n个物品(包含n)所能够得到的最大的总价值. Object NO# Weight …
    Continue reading

  3. Sparse Matrix Multiplication

    Leave a comment

    March 13, 2017 by oneOokay

    Given two sparse matrices A and B, return the result of AB. You may assume that A‘s column number is …
    Continue reading

  4. Bit Manipulation

    Leave a comment

    March 10, 2017 by oneOokay

    我真的是一直在刻意回避做这种类型的题目… Hamming Distance : 异或 ^; 与 &; 右移 >>= N Total Hamming Distance Hamming Distance The Hamming distance between two integers …
    Continue reading

  5. The Skyline Problem

    Leave a comment

    March 9, 2017 by oneOokay

    只需要考虑critical points: 哪些是critical points?每一个building的left和right. 从小到大遍历每一个critical point: 当前点的高度应该是覆盖该点的building的height的最大值. 用Set/Tree来存这些critical points. 但是不一定把当前点和它的高度加入到res里面.看后面. 如何判断/找到覆盖某一点的building的height? 一个building的覆盖功能在经过这个building left的时候开始,right的时候结束. 所以用一个按照height排序的MaxHeap. 如何loop?从小到大遍历点还是遍历所有的building? 从小到大遍历点. 对于这个点,我们怎么知道它属于哪个building?它属于的building的height是多少?是start点还是end点? 所以用一个TreeMap<Integer, List<int[]>>: key为点的坐标值,value …
    Continue reading

  6. Subarray Sum related

    Leave a comment

    March 4, 2017 by oneOokay

    Subarray Sum Subarray Sum closest Maximum Subarray I II IV Minimum Subarray  Maximum Subarray Difference Maximum Size Subarray Sum Equals …
    Continue reading