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

    我真的是一直在刻意回避做这种类型的题目… Total Hamming Distance The Hamming distance between two integers is the number of positions at which the corresponding bits …
    Continue reading

  5. The Skyline Problem

    Leave a comment

    March 9, 2017 by oneOokay

    TODO:

  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