poj题目分类 小媛在努力原创

标签（空格分隔）： oa

[TOC]

初期:

一.基本算法:

(1)枚举. (poj1753,poj2965)

(2)贪心(poj1328,poj2109,poj2586)

(3)递归和分治法.

(4)递推.

(5)构造法.(poj3295)

(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

(1)图的深度优先遍历和广度优先遍历.

(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)

(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)

(3)最小生成树算法(prim,kruskal)

(poj1789,poj2485,poj1258,poj3026)

(4)拓扑排序 (poj1094)

(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

(6)最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

(1)串 (poj1035,poj3080,poj1936)

(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

(3)简单并查集的应用.

(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)

(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)

(5)哈夫曼树(poj3253)

(6)堆

(7)trie树(静态建树、动态建树) (poj2513)

四.简单搜索

(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

(1)背包问题. (poj1837,poj1276)

(2)型如下表的简单DP(可参考lrj的书 page149):

1. E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2. E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
*3. C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)

六.数学

(1)组合数学:

1.加法原理和乘法原理.

2.排列组合.

3.递推关系.

(POJ3252,poj1850,poj1019,poj1942)

(2)数论.

1.素数与整除问题

2.进制位.

3.同余模运算.

(poj2635, poj3292,poj1845,poj2115)

(3)计算方法.

1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)

七.计算几何学.

(1)几何公式.

(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)

(poj1408,poj1584)

(4)凸包. (poj2187,poj1113)

中级:

一.基本算法:

(1)C++的标准模版库的应用. (poj3096,poj3007)

(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

(1)差分约束系统的建立和求解. (poj1201,poj2983)

(2)最小费用最大流(poj2516,poj2516,poj2195)

(3)双连通分量(poj2942)

(4)强连通分支及其缩点.(poj2186)

(5)图的割边和割点(poj3352)

(6)最小割模型、网络流规约(poj3308, )

三.数据结构.

(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

(2)静态二叉检索树. (poj2482,poj2352)

(3)树状树组(poj1195,poj3321)

(4)RMQ. (poj3264,poj3368)

(5)并查集的高级应用. (poj1703,2492)

(6)KMP算法. (poj1961,poj2406)

四.搜索

(1)最优化剪枝和可行性剪枝

(2)搜索的技巧和优化 (poj3411,poj1724)

(3)记忆化搜索(poj3373,poj1691)

五.动态规划

(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)

(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)

(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)

(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

(1)组合数学:

1.容斥原理.

2.抽屉原理.

3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).

4.递推关系和母函数.

(2)数学.

1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)

2.概率问题. (poj3071,poj3440)

3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)

(3)计算方法.

1.0/1分数规划. (poj2976)

2.三分法求解单峰(单谷)的极值.

3.矩阵法(poj3150,poj3422,poj3070)

4.迭代逼近(poj3301)

(4)随机化算法(poj3318,poj2454)

(5)杂题.

(poj1870,poj3296,poj3286,poj1095)

七.计算几何学.

(1)坐标离散化.

(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).

(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)

(3)多边形的内核(半平面交)(poj3130,poj3335)

(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级:

一.基本算法要求:

(1)代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

(2)保证正确性和高效性. poj3434

二.图算法:

(1)度限制最小生成树和第K最短路. (poj1639)

(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)

(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446

(3)最优比率生成树. (poj2728)

(4)最小树形图(poj3164)

(5)次小生成树.

(6)无向图、有向图的最小环

三.数据结构.

(1)trie图的建立和应用. (poj2778)

(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法

(RMQ+dfs)).(poj1330)

(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的

目的). (poj2823)

(4)左偏树(可合并堆).

(5)后缀树(非常有用的数据结构,也是赛区考题的热点).

(poj3415,poj3294)

四.搜索

(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

(1)需要用数据结构优化的动态规划.

(poj2754,poj3378,poj3017)

(2)四边形不等式理论.

(3)较难的状态DP(poj3133)

六.数学

(1)组合数学.

1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.

(2)博奕论.

1.极大极小过程(poj3317,poj1085)
2.Nim问题.

七.计算几何学.

(1)半平面求交(poj3384,poj2540)

(2)可视图的建立(poj2966)

(3)点集最小圆覆盖.

(4)对踵点(poj2079)

八.综合题.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

• N00t大神的recursion出神入化
• LC中大量的recursion解法
• recursion的关键在于代码结构, 以及param/return.

recursion的种类

1. 简单的按照结构分的有

1个rec. 以及简单三明治关系.

1
2
3
4
5

void rec(){
    codeTD;
    rec();
    codeBU;
    }

• 这里面的codeTD可以看作是walk DOWN the tree, codeBU理解为walk UP the tree.

1个rec. 但是在for loop里面的话, 会更有意思.

1
2
3
4
5
6
7
8

void rec(){
    if (lastRow)
        res.add(path + s);
    for(i = 1; i < path.size(); i++){
        rec(path.append, res);
        path.delete;
    }
}

• 这在restore IP的N00t的第一个解法中遇到.

1个recursion, 这次是在for each() 括号里面. 更有意思啦

1
2
3
4
5
6
7
8
9
10

List<List<?> segmentRec(String s) {
    // do something
    for ( i ) {
        rest = s.substring(i)
        for (List<?> seg : segmentRec(rest)) {
            // do something
        }
    }
    return result;
}

• 这个是在word segment里面用到.

2个连续rec call. 有param, 有return

在triangle Path Sum中的N00t的第一个解法.

• 注意这里的minSum既是recursion method的param, 又是param的返回值. 这在recursion中很常用. 可以记录在触底反弹的时候不断update这个值.
• 因为rec有返回值, 而且复制给同一个var(minSum). 因为2个recursion的话, 第二个rec中的param会在第一个rec算完后update. 所以这一套组合拳就能在Traversal tree中不断update. 也就相当于brute force的找所有组合的极值.

• 这就体现出recursion的意义: 有目的, 有结构的遍历符合规则的结构的所有path. 例如triangle Path Sum就是想要找DFS path的最小路径. 而不是随便一个乱序的路径.

  1 2 3 4 5 6 7 8 9

  int DFS(a, sum, minSum) { sum += a; // walking down the tree. if (lastRow && sum < minSum) return sum; else { minSum = DFS(a, sum, minSum); // 注意这里的赋值是minSum, 而不是其他var name. 所以跟着的第二条recursion中的minSum才会update. minSum = DFS(a, sum, minSum); // 这里的minSum用于DFS的return. } return minSum; // walking up the tree. }

还有个很好的例子就是flatten Binary Tree的九章算法模版.

• recursion中有param不一定必须return. 主要修改就OK了.
• 关键在于2个recursion的时候, 第二个recursion计算的root

还有很经典的是Maximum Subarray的divid and conquer解法.

• 2个连续的rec. 一个左子树, 一个右子树. 然后下面的code是向上走. 即合并的时候做的. 干什么呢? 自然是用来合并左右子树计算得到的结果. 一天一学的Java分析很到位.

2个不连续的rec call. 中间有code. 注意N00t和programCreek的一点区别

1
2
3
4
5
6
7

Node rec(l, h) {
  mid = lo + (hi-lo)/2;
  leftNode = rec(lo, mid-1);
  middleCode;
  rightNode = rec(mid+1, hi);
  return root;
}

• 这在Sorted list to Binary Tree里面用到了.

  2个不连续的recur call. 中间有code, 而且使用的return.

• 经典案例: Recover Binary Search Tree —- N00t的方法. 这才是真正的使用in-order. 注意每一次的rec call里面的param都变化. 而不是像dummy in-order那样对称.

  1 2 3 4 5 6 7 8 9 10 11

  private TreeNode inorder(TreeNode root, TreeNode[] nodes, TreeNode pre) { if (root == null) return pre; // left subtree TreeNode last = inorder(root.left, nodes, pre); // visit if (last != null && root.val < last.val) { // some code } // right subtree return inorder(root.right, nodes, root); }

3个rec call, 中间有code, 有param, 有返回.

1
2
3
4
5
6
7
8
9
10

DFS(tri, row, col, HashMap){
    // base condition
    return min;
    if(Map.contains())
        min+= Math.min(DFS(Hashmap), DFS(Hashmap));
    else 
        min+= Math.min(map.get(), DFS(HashMap));
    map.put(row, min);
    return min;
}

• 在Triangle Path Sum的DFS recursion解法里面用到. 注意这里的Math.min()里面的第二个DFS的map已经在在第一个DFS中改变了.
• 记住: java永远是call by value.
  • 所以primitive 的话不会改变. 于是必须return. 所以在Triangle Path Sum中的第一个解法必须return, 然后第二个recursion的minSum才是改动过的.
  • 如果是object, call-by-value的是地址. 所以可以改动. 于是不需要return. 就如Triangle Path Sum里面的DFS解法的map. 这里的map是重复使用(update)的.
  • 其实这里就是段公子说的用HashMap来代替array保存DP结果更有通用性. array其实是最简单的HashMap, 即key是index, value则是a[i].

2. 按照DFS中使用的分

• 根据leetcode summary的博客
• 还有就是CS的关键: 抽象抽象再抽象. 并不一定要真的是一个Tree放在那里让你traverse. 而是题目可以按照tree的结构分析分解和理解. 比如说word segment, word ladder, Graph, 乃至2-SAT->SCC. 等等.

例如NP问题: Subsets I/II

NP问题: Permutation I/II

虽然退役了，但是整理一下，供小弟小妹们以后切题方便一些，但由于近来考试太多，顾退役总结延迟一段时间再写！先写一下各种分类和题集，欢迎各位大牛路过指正。

• 转载于671coder的专栏

ACM入门

• 杭州电子科技大学(hdu)ACM题目
• 关于acm的帮助
• 北京大学(poj)题目
• 浙江大学(zoj)题目
• uva题目
• 青理工大学acm宣传ppt(据说就是耀哥的魅力害了好多人来搞ACM)

水题

• hdu水题分类之耀哥版
• poj题目分类 小媛在努力原创
• 算法竞赛入门经典》刘汝佳白皮书 第五章题目
• 算法竞赛入门经典》刘汝佳白皮书 第六章题目
• 算法竞赛入门经典》刘汝佳白皮书 第七章题目
• 算法竞赛入门经典》刘汝佳白皮书 第八章题目
• 算法竞赛入门经典》刘汝佳白皮书 第九章题目
• 算法竞赛入门经典》刘汝佳白皮书 第十章题目
• 算法竞赛入门经典》刘汝佳白皮书 第十一章题目

搜索

• 图的搜索分类 夏天的风原创
• 范围搜索简介
• 高级搜索题集
• 极大极小搜索题集

图论

• poj图论综合题集
• 并查集&最小生成树题集
• 最短路&差分约束题集
• 欧拉回路&特殊图下的哈密顿回路题集
• 欧拉路&欧拉回路
• 拓扑排序题集
• 二分匹配题集
• 连通&LCA题集
• 网络流题集
• 2-SAT题集
• KM匹配题集
• Dancing Links 题集
• 一般图的匹配题集

数据结构

• 线段树题集
• AC自动机题集
• 树状数组题集
• 树状数组小结

动态规划

• 经典讲解：
  • 背包九讲
  • 状态压缩DP 属性DP
  • 100个动规方程
• 题集：
  • 背包DP专辑
  • 树形DP专辑
  • 概率DP专辑
  • 区间DP专辑
  • 数位DP专辑

数论

• 博弈题集

计算几何

• poj计算几何入门推荐
• 另一个题集

  模拟

各种大牛退役帖合集

各种YY合集

20150122

Length of Last Word

• 额, 简单题…

Same Tree

Maximum Depth of Binary Tree

• DFS或者BFS都能解决. 其中BFS的N00t的写法是queue+Null nod作为该level的结束, 并且只有while没有内层的for loop

Minimum Depth of Binary Tree

• 还是DFS跟BFS都能解决. 但是BFS在这里效率更高, 因为只要找到第一个leaf就返回.

Word Ladder II

Longest Common Prefix

Pascal’s Triangle

Pascal’s Triangle II

20150120

Best Time to Buy and Sell Stock II

• 参考CSDN的FightForDream分析DP

Best Time to Buy and Sell Stock III

ZigZag Conversion

3Sum Closest

Longest Valid Parentheses

Permutation Sequence

• 数学找规律题目. N00t的例子加上Ganker的解释. 很容易理解. 关键是code要写的快.

20150115

Substring with Concatenation of All Words

• 这道题目和Longest non-repeated subsequence都是用Ganker大大的双pointer窗口大法.
• 看了N00t的才知道原来Ganker这种双指针法原来就是简化的KMP string match算法. 并不是. KMP的关键在于preprocess了一个DFA, 所以能够实现O(n).

Simplify Path

• 先读懂Unix中的path的op意义. 发现阿猫阿狗blog的解释最清晰易懂. 我也测试了一下: 确实就是很简单的规则: /.表示当前目录，/..表示上级目录，/表示根目录. 如下图所示:
  . cd /MOOC/./../MOOC. 以/为分界来认识就是: cd /(回到根目录); MOOC(去根目录下的MOOC文件夹); /..(返回上一级, 即回到c:); /.(表示当前目录, 所以还是在c:); /MOOC. 又去到MOOC文件夹. 所以执行完后表示还是去到了MOOC文件夹中. 而在command里的第二行则直接cd MOOC是找不到的, 因为pwd是c:\MOOC\NodeJS_Intro. 题目已经说了给的是absolute path, 即从根目录开始的path. 所以打头是/.

• 这里再复习一下Stack/Queue:

  1. 虽然Stack在Java.util已经实现了stack class, 但最好不要用, 因为很多问题. 参考lmu课件. 所以Ganker也是使用的LinkedList来instantiate, 而且要注意, 这时候是: LinkedList<Integer> stack = LinkedList<Integer>(), 只是这个list叫做stack而已. 其实看了SOF stack/deque, 讲了Stack在JavaDoc里面也是推荐用Deque来当作stack用: Deque<Integer> stack = new ArrayDeque<Integer>();
  2. Queue更彻底, 是interface. 根本不能instantiate. 所以也可以使用LinkedList来实现: Queue<Integer> queue = new LinkedList<Integer>().

• 细节在于Java里面的split(regex, limit)是split pattern之前和之后的. 所以splits[0]是””. 一个空的string. 参见SOF: java split leading empty string. 即: split之后会出现的值是: “”, “a”, “.”, “..”. 所以当stack不空且”..”的时候pop(). 当split的值是有效的char, 换句话说: 不是无效的char: “”, “.”, “..”的时候就push().

Unique Binary Search Trees I

• 这是一个很有意思的题, 因为在于解题思路可以有2个方向
  1. 想明白之后可以直接是公式解法. 这个是数学的解法. 而且这个数学解法的Sigma的处理也学到了:就是loop里面res+= func(i).
  2. 利用水中的鱼所说的BST的性质: lchild<root<rchild. 所以如下图所示: . 这里参考的SophieJ递归解法. 这里的rec(i)让我思考了半天, 他的含义并不是: 以i为root的解, 而是有效的node为i个的解. 譬如在for loop到2, 即以2为root的情况下, lway只能是1个有效的node, rway则是有2个有效的node. 所以lway = rec(2-1); rway = rec(4-2).
• 所以我觉得这个题目相当有意思. 而且思路很清晰.

Unique Binary Search Trees II

• 目前只看到N00t是用了recursion和DP来解决.

  recursion解法

• 和分析的一样, 遍历l->r, 让每一个都有机会做root, 然后Divide递归左右子树的所有可能性(所以返回值是List<TreeNode>, 即以TreeNode的有效的BST). 然后Conquer遍历所有有效左右子树, 并接上Node(i).
• 有几点要注意:
  1. 正如Effective java item 43所说: return empty list rather than null.
     • 这是一般情况下的trick. 而且这里还有她的实际意义: 即空树的root. 这样在接上Node(i)的时候, 是接上空树. 因为for each的时候一定要能see到空树. 而如果在l>r的时候返回null, 而不是res.add(null)的话, 就直接忽略了空树的情况. 更重要的是: 根源上避免了判断Null pointer. 如果我return null的话, 会出现Exception in thread "main" java.lang.NullPointerException
  2. 在Conquer的时候, 要记住每一组left/right subtree要接上一个new TreeNode(i). 因为是一个新的以i为root的BST.
  3. 设计return value为List. 例如n=3的话, 最终返回的结果是[1,1,2,3,3]. 实际上是5个不同的BST. 这里我call了writeBST. 果然可以看到返回了5个serialize的BST: [1, #, 3, 2, #, #, #]

DP解法

• 注意到recursion的时候, 例如n=4的情况. [1,2]就给recursion了好几次: [1,2,3], [1,2]. 所以明显是可以保存计算过的结果来DP.
• 但是具体怎么写呢? 先搞懂N00t的思路. 但实际写起来很多地方要注意:
  • 虽然说是T[i,l]. 但实际上N00t是用的list>>来写. 原因很简单. 就是前2个保存i和l. 最后一个保存T[i,l], 即满足这个range的BST的root和合集. 因为有了root, 就能得到tree(所以我在main里面最后call了writeBST()来serialize每个BST).
  • 边界条件很简单, 就是l=0.
  • 那么打表是怎么个打法. 在interleaving string的DP的设计是T[i][j]. 分别是2个string的坐标, 所以无所谓哪个是外层,哪个是内层循环. 但是这里是T[i][l]. 这个l是长度. N00t的设计是外层是l, 内层是i. 所以是按照starting point分类的. 为什么这样loop呢?

Serialize/De-serialize Binary Tree

• 先是什么是serialize/deserialize. 可以看水中的鱼的图解: 水中的鱼花树
• pre-order traverse的一个应用. 从而可以解决isValidBST. 而且这个在Leetcode的Binary Tree很常见.
• 为什么Deserialize也是用pre-order呢? 这个顺序不会反吗? 感觉上觉得应该使用serialize的相反的traverse—>post-order. 但这样其实是不对的. 见ITeye的分析. 这里我一开始做的方法也是使用的index来判断是读取list中的第几个字符. 但这里我就搞混了: 到底对于right subtree的index该用多少.
  • 水中的鱼使用了一个int[1]. 然后java当作object, 可以传值. 而且也就避免了return.
  • 我则是用的int, 所以必须return. 所以在left算完之后return的cnt必须是对应left subtree的最后一个node. return之后, right recursion的时候这个index还要再加一. 并且右子树结束后还要return给他的parent(注意这就是recursion后的code的意义: 往上走)
  • 1337原帖后面又一个Java写的. 我改了一点. 使用了stringTokenizer. 也是对的, 而且他并没有使用index来定位这个char, 而是使用了boolean left. 然后每次就是nextToken(). 也是可以的.

Binary Tree Level Order Traversal II

Triangle

20150512

• 这个博客一直有更新Leetcode新题的题解报告不错: 一丝凉意

20150508

今天做Scramble string的时候看到了很多很好的分析.

• 武大的wangyi大牛. 不但是很好的Leetcode题解. 而且还是FLAG面经大牛.
• Unieagel的leetcode题解博客
• Fightingforyourdream题解CSDN

20150507

• fgdsb大牛做的在Leetcode122题和不在Leetcode的题目153题blog

20150426

• ACM之家的Leetcode题解和很多算法题目的分析/题解(Java) link
• 刚去了Google的大牛的题集link. 看看她的Google面试准备帖子.

20150421

• CSDN fightfordream的Leetcode整理. 而且他还有DP/Recursion/Backtracking题集. 等等. 挺不错的.

20150324

• 2个月刷完LC的blog. 要向别人学习努力.

20150317

• Ganker大神的lc解题报告 要做到这个程度: 算法的分析和比较. 题目类型要心中有数, 信手拈来!

20150311

• okckd的leetcode 175/CC150题解合集以及大量OOP问题整理: 而且有个bonus就是他的题目加了编号和link, 所以方便我在freq里面找.

20150301

• 主页君的LC解答分析了他人的做法, 也有总结. Java.主页君的Leetcode/Lintcode解答

20150228

• 看了很多多人有不同的解法. 思路来说, 还是官方自己的答案最好, 每道题都有详细的分析和图解. 1337c0d3r的答题贴

20150215

• 当然还有LeetCode官方出的clean code handbook. 今天是1.0.3. 只有50题的答案和分析, 但是也有善良点. 比如edit distance分析了答案和经典DP algs的优劣.

20150129

• 200题Leetcode Java解答, 而且还有题解报告和github连接
• 200题Leetcode C++11解答, 左耳朵耗子大神的github解答

20141111

• Leetcode总结提炼
• codeMonkey九章算术Leetcode, Design分析, CC150题解

20141102

• leetcode答案总结(Java)
• leetcode答案分析

20141029)

• leetcode总结
• leetcode分类
• leetcode分析
• leetcode分类
• leetcode总结
• leetcode答案
• leetcode总结
• leetcode答案(分析详细)
• leetcode答案

20141006:

• 1p3a今天有人问答案，然后大牛门的回答: http://yucoding.blogspot.com

20140928

• 米群网的刷题汇总贴
• 1p3a上面CMU ebiz的Leetcode/CC150 java合集

20140424

• 段公子的编程笔记
• [段公子的励志贴](http://www.mitbbs.com/article_t/JobHunting/32594745.html
• Leetcode Github 答案1 c++
• Leetcode Github 答案2 C++
• Leetcode 水中的鱼 c++
• n00tc0d3r博客(多种解法) java
• github starforever

Introduction

This is an addition to the well done awesome courses by Prakhar1989-github. And here is for the algorithm specifically.

Table of Contents

• Systems
• Programming Languages / Compilers
• Algorithms
• CS Theory
• Introduction to CS
• Machine Learning
• Misc

Good courses

• cs.washington.CSE373.
  • this is a undergrad level data structure class, so not much algs, but I found the sorting is useful. And as Code Ganker said, a lot of important algs ideas lies behind basic sorting algs: recursion, DP, D&C, trade-off, etc, you name it.

20150519

怎么更好的贴代码?

• 我想在每一个解题报告里面加入github, 有什么好的办法呢? 主要是想能在作业部落里面好改的.

  • gist-it. —->但是悲催的不支持有中文的代码文件…
  • <script url-to-gist /script> ——> 只支持gist
  • data-file-folder —->不知道怎么用, 这样不好移植…
  • 自带的. 地址设置参考link

• 加入Github代码:

  1 2	_.compact([0, 1, false, 2, '', 3]); => [1, 2, 3]

• 测试gist:

• 使用gist-it: 保存所有.java代码为utf8就OK了.

• 内嵌代码: 悲催的不支持中文. 看来以后还是得使用英文 并不是, 而是必须所有文件使用UTF-8 without BOM保存. 这样gist-it跟include_code都能正常识别. 因为js/python不支持其他保存格式

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

  package freq2_tony; import java.util.*; /** * 还是二分的思想解决大问题. */ public class FourSum { /** * * @param num * @param target * @return */ public List<List<Integer>> fourSumN00t(int[] num, int target) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (num == null || num.length < 4) return res; Arrays.sort(num); for (int i = 0 ; i < num.length-3 && num[i] <= target; ++i) { if (i > 0 && num[i] == num[i-1]) continue; for (int j = i+1; j < num.length-2; ++j) { if (j > i+1 && num[j] == num[j-1]) continue; int l = j+1, r= num.length-1; while (l < r) { int sum = num[i] + num[j] + num[l] + num[r]; if (sum < target) { l++; } else if (sum > target) { r--; } else { List<Integer> cur = new ArrayList<Integer>(); cur.add(num[i]); cur.add(num[j]); cur.add(num[l]); cur.add(num[r]); res.add(cur); do { l++; } while (l < r && num[l] == num[l-1]); do { r--; } while (l < r && num[r] == num[r+1]); } } } } return res; } public FourSum() { int[] input = {-8, -5, 0, 3, 0, 1, 4, 4, 4}; List<List<Integer>> res = fourSumN00t(input, 4); // ArrayList<ArrayList<Integer>> res = twoSum(input, input.length-1, 4); System.out.println(res); } public static void main(String[] args) { FourSum fs = new FourSum(); } }

总结一下贴代码

• 还是得用github来host代码, 因为gitlab不支持.
• 使用gist-it还是直接内嵌额?
  • 其实都是使用的本地代码. 因为github只支持embed gist文件.
  • 如果只是使用_codes来保存代码, 然后在git, 在embed的话, 其实很麻烦. 以为除了hexo d之外, 还要单独git source branch.还不如直接git所有代码到github一个project里面. 不管怎么样, 都是要另外git source branch. 这和单独开一个git repo有区别吗? 有的. 一来: 单独的git repo容易看到, git push简单. 而且和gitpage decouple了.
• 批量转换western到utf-8, 我使用的是: GB/BIG5/UTF-8 文件编码批量转换程序 1.3. 挺好用的.
• 在Eclipse里面就设置了default encoding为utf-8. 这样以后就不用写完后, 在转换了. 可以参考一下: Encoding Eclipse osx

20150513

• 因为主要还是在zybuluo里面写markdown. 写完之后放到Hexo并deploy. 所以就直接用img的链接. 一开始试了一下google drive, 分享链接不太好用(要选择是public的程度). 所以还是使用了七牛. 发现还挺方便的. 而且1G空间很够用了. 而且读取很快. 不错.
• 所以以后就是图片本地还是放在img文件夹里面. 不过同时上传到七牛. 最好还是压缩一下. 有的图片大于1M了.

20150508

• 今天主要的任务是把我的github.io从wiki-in-box搬到了Hexo-Freemind. 感受到了强大的Hexo.
• 不过其中遇到了不少问题. 所以也用了挺长时间做:
  1. disque怎么弄? 原来是名字是’abc123’, 而不是’‘. 所以造成了无法和我在disqus里面注册的.
  2. RSS/SiteMap怎么弄? 我本来是按照教程直接npm install这2个plugin. 但是hexo g之后并没有产生atom.xml/sitemap.xml. 然后才发现这个plugin应该安装在hexo/tonyhexo里面, 而不是安装到C:\MOOC\NodeJS_Intro\下面. 所以又倒来倒去.
• 主要参考的:
  • 如何搭建一个独立博客. 这里还讲了如何DNS,
  • Hexo博客优化. 这个讲了如何使用google analytics和sitemap的用法.
• 但是发现Hexo还是有些缺陷:
  • 例如N00t的博客, 她的search可以实时先是match的blog, 而且还能多种显示博客的形式.
  • 这个markdown和作业部落的不太一样, 不过差别不大就是了.
• 方式:
  • 主要是在作业部落上面写好, 然后再放到这个Hexo上面. 因为作业部落确实是markdown很友好. 不过Hexo是我的个人博客. 更大自由.

Leetcode Freq 4-5

标签（空格分隔）： leetcode

目录

[TOC]

20141111

Remove Element

Roman to Integer

Swap Nodes in Pairs

• List的经典操作: 交换nodes. 注意这里什么不变, 什么变. 以及如何处理边界条件. 头脑要清晰. 意乱就麻烦.
• follow up就是freq 2的reverse Nodes K-group

  Add Binary

  Sum Root to Leaf Numbers

  Add Two Numbers

  Integer to Roman

20141108

Word Search

Decode Ways

Binary Tree Level Order Traversal

Palindrome Partitioning

Sqrt(x)

Generate Parentheses

Merge k Sorted Lists

20141105：

1. word ladder

• 为什么wordladder用linkedlist来保存distanct？为什么要在for loop加distance并enqueue？为什么!isEmpty的时候pop出来的distance就是对的。
  • a. ANS: 可以参考Algs Princeton的BFS正确性证明。每次wordQ 在enqueue的时候都是同样深度的。而且queue的pop（remove and return）保证了distance的正确性。
    eg：ab->aa的最短距离。虽然az的话。loop会把distanceQ+1. 但是不同的word话要pop distance。如果不同的话又返回到aa了。
    • b. 不过还是觉得不太对劲。如果运气不好一直网az,dz,zz方向走不就成了DFS了？而不是BFS（一层一层的走吗？）.
      ANS：BFS是搜完距离1的继续搜距离2的。当全部搜完之后call distTo来输出start到end的最近距离。

1
2
3
4
5
6
7

  ab
 /   \
aa   az
         \
         dz
           \
           zz

20141103:

0. BFS

• 联系看pseudocode来写java。比如Wiki page的BFS (link).
• 还是学习一下regex方便些。因为Java的replaceall支持regex。而且今天在删除eclipse里面的空行也是用的regex: ^\s*\n

1. Word Ladder

• 怎么想到本质一个graph的shortest path呢？
  • a. 先是看了yutianzuijin的csdn博客（link）他先是想到2d matrix 然后再想到graph的2种表示方法：
    • 一. adjacent matrix
    • 二.adjacent list. 然后就可以用graph的BFS来解决。但是时间复杂度又太大了，是O(mdict_size). 其实可以做到O(26m)
  • b. 鱼的（link）讲了可以用bi-directional BFS，也可以看作是夹逼方法和k-Sum问题类似。
  • c. n00tc0d3r比较详细的分析并给出不同解法。而且说了hashset/hashmap在Java和C++里面的区别：在Java中map快，在C++中set快。

20141102:

finish freq 5

1. set Matrix Zeros.

• 这又是一道：达到目的可以改变方式。为了in place.
• 必须要有2组set来记录行列为0的info。既然有matrix给我们。就可以改变它。为什么不用第一行列作为这个row/col set. 当然如果第一行列有zero怎么回忆起来呢？虽说inplace不能用additional set. 但是flag还是可以的。因为O(1)=in place。

2. Merge sorted array/list.

复习一下java里面的lnkedlist和指针了。

20141101:

1. Pow(x,n):

我看了n00tc的答案，他是用n>>1 和 n&1来代替除法和取余数。但是我直接把pow2的计算换成bit后答案就错了。为什么呐？我测试了一下>>1 跟 &1. 发现如果是正数当然没问题。但如果是负数则除法跟取模都会得到意外的答案。

1. I got yu shu: 1 vs 1
2. I got remainder: 1 vs 1
3. I got yu shu: -1 vs -2
4. I got remainder: -1 vs 1
   注意到N00tc0d3r一开始就把指数n取了绝对值。

2. Validate BST

很好的题目。可以复习到recursion跟iteration的转化。其实traverse里面的迭代版本不好想。邓俊辉的教材分析得很详细。而且recursion里面的每个return只是结束当前的stack，从而可以继续之前保存的stack。觉得CMU-ebiz的答案最好懂。这里面的lastVisit = root.val放到if(root.val<=lastVisit)之后。这个顺序也是一个高潮。要真正理解recursion才能想出来这点。

3. kd-Tree.

• 参见Coursera Algo4th 的作业五：在一堆点里面找能用一个unit square抱住的点群。这就需要用2d tree来search了。link

4. Palindrome

• 做palindrome之前先看一下java的replaceall用的regex: link
• 这里要了解的就是[^a-z], [a-z0-3]的意思。前者是除了a到z以外。后者表示a到z和0到3.所以这里就是先把输入的string的非字母数字的字符都换成”“。

5. Valid Number

• 居然说Valid Number是难度2的题目。。。跪了。第一次面试做compiler的parser就是一个automa。然后不会写Java的状态机。这次一定要搞懂。记得moore和mooley FSM最难的就是设计states。就连最简单的判断100101都容易写错。可以参考这个link看看这个状态图是怎么画的。N00tc0d3r只给了图….
• 注意switch case的格式：要在每个case最后加break或者return。而且case只能是每一个值而不能给范围。所以a-zA-Z0-9就呆了。还是if else好用些。

6. setMatrixZeros

• 做setMatrixZeros看到用的hashset，为什么呢？hashmap不行吗？为什么用Set<Integer> rows = new HashSet<Integer>();
  然后看到了一片总结：link。
  可以看看我在CS108里面贴的那个java collection framework关系图。
  注意在jdk里面set.class和hashset.class. 前者是interface后者是implementation。

20141030:

0. climb chairs

这题和数硬币组合类似。不过前者是permutation后者为combination。

1. 2 sum:

首先把题意搞清楚:
输入是一组未排序的可重复数组，以及一个目标数。且一组数组只有一组解。求这两个数的index。

ANS:
一开始想是：

1
2
3
4

for i: array
     for: j: rest of array
          if (i+j==target)
               return.

但是这样就会得到O(n^2)!

记得quick sort之类的排序算法是O(nlgn)。可以得到吗。
唉。想不出来。
看网上答案也就n00tc03r和lexi女的博客有思路分析。还有CMU-ebiz的java整个打包但是答案质量一般。不过也可以看看。programcreek的也很好。

但最主要还是像段公子说的那样要总结分析出pattern而不是一题一题的解决。这样永远会有不会做“新题”的可能。

比如这里面一般C++的都会用头尾指针，如CMU的做法。这里有个分析点很重要：首位指针如果大于target则可以把大的元素永远排除！也很容易想：因为这个最大的数加上最小的那个数都超了，那他就不可能和任意其他元素相加得到target。但是小的那个数却可以保留。因为他还有机会。这里和merge 2个排好序的数组要从最后排起。以及删除一个linked list的node却只给了前一个pointer一样。要脑子拐过弯！

所以先写第二种解法：头尾指针往中间靠。这样的时间复杂度是多少呢？
仔细看一下。CC里面的2sum是return 满足条件的2个element的值。所以可以用java的sort。
但因为leetcode是要求index。所以要多一个O(N)空间复杂度来保存index。
九章和CMU_ebiz都给了这个答案。

第三种解法：用hashmap。则可以O(1)+O(n)=O(n)
一个for loop, 搜索map里面有没满足的数，途中把target-input[i] 放到map里面。
这个最好。用到了java的library。又快又方便啊！而且HashTable解决所有搜索问题啊。

2. 3 sum：

还是要把题目理解：
找到一组未排序的可重复数组里面的所有 不重复的满足sum为0的triplets。
艹，搞了一上午，为什么Java ArrayList> remains empty when I add an ArrayList. 原来是ret.add(each)的不是copy而是reference。在each.clear()后，前一句的2D list add就是add了一个空的ArrayList。正如Core Java里面讲的：“parameters to java methods are always passed by value. The value of any object variable is a reference to an object that stored elsewhere.
中饭回来查了一发现stack overflow上有这个解答：link
所以有2个方法解决clear就把之前added的删去的问题：
a. 用add new（each） 也就是copy过来。
b. 每次在inner loop里面new一个each。

3. 3 sum closest

4. 4 sum

5. k-sum.

6.pow(x,n)：

先是naive做法。直接循环。但是傻了，忘了负指数是取倒数了。
到了用naive的recursion做法，Programcreek是说：’a recursive solution can easily be written.’。。。好容易弄混。要好好分类。其实就3类，先按N的奇偶正负分，同时和x的正负。而且记住是recursion，所以三个case都是互相调用，每次调用都是pow*pow*pow！而不是pow一次。
但是naive的recursion还是不够快，而且recursion的重复计算总是不好的。

Leetcode 高频题 频率表

标签（空格分隔）： leetcode

[TOC]

学习资料

• Stanford CS 97: ICPC培训课程