public int longestCommonSubstring(String A, String B) { // write your code here int max = 0; int[][] dp = new int[A.length()+1][B.length()+1]; for(int i = 1 ; i <= A.length(); i++) { for(int j = 1 ; j <= B.length(); j++) { if(A.charAt(i-1) == B.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = 0; max = […]
public List<String> anagrams(String[] strs) { // write your code here List<String> res = new ArrayList<String>(); if(strs.length == 0 || strs == null) return res; HashMap<Integer,ArrayList<String>> maps = new HashMap<Integer,ArrayList<String>>(); for(int i = 0 ; i < strs.length; i++) { String s = strs[i]; int[] count = new int[26]; for(int j = 0; j < s.length(); […]
/** * Returns a index to the first occurrence of target in source, * or -1 if target is not part of source. * @param source string to be scanned. * @param target string containing the sequence of characters to match. */ public int strStr(String source, String target) { //write your code here if(target == […]
public boolean compareStrings(String A, String B) { // write your code here int[] count_A = new int[26]; for(int i = 0; i < A.length(); i++) count_A[A.charAt(i)-‘A’]++; int[] count_B = new int[26]; for(int i = 0; i < B.length(); i++) count_B[B.charAt(i)-‘A’]++; for(int i = 0 ; i < 26; i++) { if(count_A[i]<count_B[i]) return false; } return […]
public boolean anagram(String s, String t) { // write your code here s = s.toLowerCase(); t = t.toLowerCase(); int[] count_s = new int[26]; for(int i = 0; i < s.length(); i++){ if(s.charAt(i) == ‘ ‘) continue; count_s[s.charAt(i)-‘a’]++; } int[] count_t = new int[26]; for(int i = 0; i < t.length(); i++){ if(t.charAt(i) == ‘ ‘) […]
原题: http://www.spoj.com/problems/PALIN/ 题目大意: 给任意一个数, 找到比这个数大的最小的一个回文数字. 分析: 这题要考虑的情况很多, 比如例子中的808, 我们需要把0改成1, 因为如果我们改动最后的8, 前边的8也要增加, 所以改变的总量会更大, 只能改变0. 所以第一条就是, 我们要从数字的中间改. 另一个是2133变成2222. 这个改变的过程是2133->2132->2112->2222, 这里, 我们用的是meet in mid的策略, 我们要比较前边和后边的数字, 如果他们是一样的, 那么就忽略, 如果他们不一样, 前边比后边大, 就把后边改成前边的, 这样相当于增加了,所以就结束了. 如果后边大, 把前边赋值后边, 但是继续程序.最后一种情况是, 99999->100001. 我们把所有的9变成0, 然后最后的9变成1,然后前边加1. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); for (int i = 0; i < t; i++) […]
原题: http://www.spoj.com/problems/DIVSUM/ 题目大意: 给一个数n,找到它所有的除数的合. 比如number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22. 分析: 第一次提交的时候, 老老实实找每个divisor, 结果tle了. 后来想想20/2 = 10, 一次可以把2和10都找到, 所以lgn就可以有. 先上第一次代码: public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); for (int […]
原题: http://www.spoj.com/problems/SBANK/ 题目大意: 给n个银行交易帐号信息, 要求排序, 并且统计出现次数, 输出要有序,并且输出次数. 分析: 其实就是设计一个数据结构, 是Key-Value的, 并且有序. Key-Value就是Map了, 有序 自然就是TreeMap. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); for (int p = 0; p < t; p++) { int n = in.readInt(); Map<String, Integer> map = new TreeMap<String, Integer>(); for (int i = 0; i < n; […]
原题: http://www.spoj.com/problems/PRIME1/ 题目大意: 给一个范围1 <= m <= n <= 1000000000, n-m<=100000, 找这个范围内的所有质数. 分析: spoj真是卡时间也卡空间. 做了起码五六次, 不是tle就是heap爆了. 观察了一下, 发现取值范围实在太大了, 1*10^9. 后来怀疑是不是用aks test, 试了, 还是不行. 发现问题是在方法上. 首先不能求1~n的所有质数, 然后打印出大于等于m的, 这样太慢, 其次Sieve of Eratosthenes(SoE)求的是[2,n]的. 我们需要使用的是[m,n]的.这里需要观察一下,对于每个[2,sqrt(n)]的质数p, 都有以下特点: 对于m,我们可以找到一个lower bound, 这个bound是m前边最大的能被p整除的数.比如m=5,p=2, 那么5/2 = 2(取整), 2*2 =4, 那么4就是我们要找的lower bound. 这个bound有一个特性, 就是我们用过lower bound + k*p 就可以知道p在[m,n]中出现的位置. 比如刚才的例子, m=5, n=10, 那么lower bound = 4, 4+2 […]
原题: http://www.spoj.com/problems/TEST/ 题目大意: 输出序列, 直到42 分析: 开始刷spoj. 最后一个学期也没TA了, 最后一个学期, 各种老师不给Master TA/RA. 烦恼 烦恼. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); while (n != 42){ out.printLine(n); n = in.readInt(); } }