原题: http://codeforces.com/contest/577/problem/A 题目大意: 给两个数字,n和k, 找出等于k的个数在n*n的table中, table中每一位是i*j, where i and j are row and column 分析: 这个暴不了, 所以考的是观察. 观察题中给的example: 我们可以发现, 在一个n=6的表中, k=12 出现在6 4 3 2. 这些数字都是12的除数, 可是少了几个啊, 12本身也是除数,1 也是除数, 而且在n=10,k=5中, 我们发现答案是2(1和5). 那么上边的1和12 为什么不算? 因为 12/1 = 12 , 12不在表中. 所以我们得到另一个条件, 除完的余数要小于等于n. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int k […]
public class Solution extends VersionControl { public int firstBadVersion(int n) { int i = 1; int j = n; while(i<=j) { int m = i + (j-i) / 2; if(isBadVersion(m)) j = m – 1; else i = m + 1; } return i; } }
public class Solution { public int hIndex(int[] citations) { int l = 0; int r = citations.length – 1; while(l<=r) { int m = l + (r-l) / 2; if(citations[m] < citations.length – m) l=m+1; else r=m-1; } return citations.length – l; } }
public class Solution { public int hIndex(int[] citations) { if(citations == null || citations.length == 0) return 0; Arrays.sort(citations); // 0 1 3 5 6 for(int i = 0; i < citations.length; i++){ int index = citations.length – i; if(citations[i] >= index) return index; } return 0; } }
原题: http://www.spoj.com/problems/ONP/ 题目大意: 一个代数表达式转换成Reverse Polish Notation. 分析: wiki上就有规则. 其实这个题只有三个规则: 看到(, 忽略 看到操作符(加减乘除)入栈 看到), 出栈,打印 其余直接打印 public class ONP { public void solve(int testNumber, InputReader in, OutputWriter out) { String s = in.readLine(); out.printLine(infixToPostfix(s)); } public String infixToPostfix(String infix) { Stack<Character> st = new Stack<>(); StringBuffer sb = new StringBuffer(); String opt = “+-*/^”; for (int i […]
原题: http://www.spoj.com/problems/FAVDICE/ 题目大意: 给一个n面的骰子, 问扔多少次至少每个面出现一次 分析: Coupon collector’s problem 假设有6个面, 那么第一次扔的面肯定是我们想要的, 这时可以看成是6/6,即6个面中出现6个我们都想要的, 其中的一个面出现的概率是1/(6/6) = 1, 因为这时候没有其他面出现过. 第二次扔的面有两种情况, 一种是已经出现过, 1/6, 另一种是没有出现过5/6, 那么我们当然要没有出现过的, 就是5/6中选一个, 1/(5/6), 以此类推就是n*(h(n)), 然后算下调和函数h的值就好了 public class FAVDICE { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); out.printFormat(“%.2f\n”,n*calculateH(n)); } private double calculateH(int n) { double res = 0.0; for (double i = […]
一亩三分地上看的一道题. 给两个string,A和B A = XYZ A^2 = XXYYZZ ….. B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh return k = 2, 因为b中有A^2的subsequence. 我用的run-length encode做的, 先找下a的count, 然后找下b的count, 这里的技巧是把在b但是不在a的字符存成负数. 这样encode的时候, 我们只encode a和b中共同的字符. 然后走一下数字的最小值就好了, 时间o(n). package Interview; /** * Created by chenguanghe on 9/2/15. */ public class Zenefits { public int findK(String a, String b) { int[] count_a = new int[256]; int[] count_b = […]
原题: http://www.spoj.com/problems/FCTRL/ 题目大意: 给一个数字n,问你n!后边有多少个0. 分析: 这就是Leetcode那个Factorial Trailing Zeroes 我们看n!是由多少个5的倍数组成的. 就知道后边有几个0. 纯数学题. 没意思 public class FCTRL { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int sum = 0; while(n != 0) { sum += n / 5; n = n / 5; } out.printLine(sum); } }
原题: http://www.spoj.com/problems/HASHIT/ 题目大意:设计个一个hash函数, 可以insert, exist 和 delete. 然后通过执行一系列命令, 返回key的数量和table的内容. 分析: 这里需要注意的是nextpos的函数需要mod 101, public class hashit { final int mod = 101; final int num = 19; int count = 0; String[] hash = new String[mod]; public void solve(int testNumber, InputReader in, OutputWriter out) { reset(); int m = in.readInt(); for (int i = 0; i < […]