Menu Sidebar
Menu

Archive: July 14, 2015

[Google] Given an array of Integer, return all valid triangles 给一个int数组, 返回所有可能的三角形

这个题目好像有很多变种, 比如给一个int数组, 返回所有的不重复数字组成的三角形, 或者返回所有等腰/直角三角形. 反正就是多几个限制和少几个限制. 我遇到的这个是返回所有的可能的三角形, 这其中包含:等边,等腰等等, 只要是Valid就可以. 传统解法就是O(n^3)的暴力, 当然, 这肯定不是我们想要的. 就不多说了. 说到三角形,基本看懂中文的都知道两个特性: 两边之和大于第三边 两边之差小于第三边 对于一个已经排序的数组, 我们用第一条就可以了. 证明: Assume,x,y,z are three int, 0<x<=y<=z, if z < x-y, then y+z < x (against to 1), so z < x-y false 最后, 我们还要去重, 因为数组会有{4,4,4}, 所以要把选出的三边排序一下, 然后用HashSet的原理去重. public static HashSet<ArrayList<Integer>> findAllTriAngle(int[] A) { HashSet<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>(); […]

[Google]Return all divisors of n 返回n的所有除数

Google电面: 这个算电面的简单题了. 没帕金森的基本都能写… 其实就是Prime Factorization, 只是code略有不同.  然后这个不是O(n) 算法, 是伪多项式的算法, 因为input和n本身的大小有关系. public static List<Integer> getAllDivisors(int n) { List<Integer> divisors = new ArrayList<Integer>(); for (int denominator = 1; denominator <=Math.sqrt(n); denominator++) if (n % denominator == 0) { divisors.add(denominator); if (denominator * denominator != n) divisors.add(n / denominator); } Collections.sort(divisors); return divisors; } 与Prime Factorization的区别就是中间第二个if, 多加了个除数, 仅此而已

Calculate Pi 计算n次Pi

一般常用计算Pi的公式有2个, 一个是Nilakantha序列, 另一个是Leibniz序列. 先介绍后一个,Leibinz序列, Leibinz是个神牛, 有多神呢..如果一个人在一个领域到了极限, 我们称之为大牛, 然而神牛是通吃 – -. 到底有多通吃..请自行Wiki..(他的wiki的长度有10个下拉页之长).前言毕. Leibinz给出一个非常简单的计算π的方式, 有多简单呢:请看code public double Leibniz(int times){ double sum = 0; for (int i = 0; i < times; i++) { sum += Math.pow(-1,i) * (double) 4/(2*i+1); } return sum; } 注意, 这里的input是次数. 对应的通项公式为: Nilakantha,是Nilakantha Somayaji发明的, 这人一直研究无穷序列, 贡献嘛…最出名的就是这个公式了, 不过在实际运算中, Nilakantha的速度要比Leibinz快. public double Nilakantha(int times){ double denominator […]

[Google] Serialization and Deserialization BST 二叉树编码和解码

这是一道Google的面试题. 当我第一次看到这题的时候, 第一个感觉, 树, 编码,解码, 那不就是Prufer Code么. 拿起笔就开始写, 后来感觉电面不应该这么复杂, 而且Prufer code对象是Labeled Tree, 这里并没有使用到BST的特殊性质. 于是赶紧回想刷过的题, 突然想起Leetcode上面的编码方式: 这个编码的特点是: Inorder Traversal. Null = # Code容易写. 所以编码的code是: public static String serialize (TreeNode root) { StringBuilder sb = new StringBuilder(); if (root == null) sb.append(“#”); else { sb.append(root.val); sb.append(serialize(root.left)); sb.append(serialize(root.right)); } return sb.toString(); } 解码的特点是: 因为已知编码是Inorder, 所以解码也是Inorder 要注意如果解码到#, 需要return null. […]

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

July 2015
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031