双指针. 找环 public class FloydsCycleDetection { public static int floyd(int[] a){ int s = a[0]; int f = a[0]; do { s = a[s]; f = a[a[f]]; } while (s!=f); s = a[0]; while (s != f){ s = a[s]; f = a[f]; } return f; } public static void main(String[] args) { int[] t […]
原题: http://codeforces.com/contest/579/problem/A 题目大意: 繁殖细菌, 细菌每天翻倍, 每天都可以添加任意个数的细菌. 问最后得到n个细菌, 需要加多少个细菌. 分析: 倍数增加, 就是二进制的1的个数, 每过一天, 前一天的细菌个数都增加 <<1 个, 所以找一下n中有几个1就可以了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); out.print(countOne(n)); } private int countOne(int x) { int count = 0; for (int i = 0; i <= 31; i++) { if ((x & (1 << i)) […]
今天面BB, 面傻了..第一题: 翻转,打印链表, 不能用任何数据结构, 不能改变指针和值 我用了20分钟想怎么不改变指针翻转链表, 用了10分钟证明了必须改变指针, 或者用stack存值, 但是面试官(ydr)依然不满意, 而且也没任何提示, 就说不行不行不行……以至于最后10分钟才知道还有下一道题. 然后, 然后我才明白, 原来不是翻转打印, 是print in reverse order..只要print就行….我当时就哭出来了, 这个用内存压,会爆栈的啊… 还不如用stack…算了.. 第二题是在一个string后边加上最少的字符, 使得string成为回文, 这个面试见过. 10分钟就秒掉, 回头再看第一题还是不会…. 本来特别想去bb的…哎..好好准备下周g家加面吧 public class ReverseList { static class ListNode{ int val; ListNode next; public ListNode(int x) { val = x; } } public static void reverse(ListNode head) { if (head == […]
How to swap two integer without temportary variable ? 可以用XOR: public class SwapTwoIntegerWithoutVariable { public static void main(String[] args) { int a = Integer.MAX_VALUE; int b = Integer.MIN_VALUE; a = a^b; b = a^b; a = a^b; System.out.println(“a “+a); System.out.println(“b “+b); } }
Given random generator from 1 – 5 with equal possibility. Design Random generator 1 – 7 设计一个5×5矩阵, 然后把1-7放进去, 多的地方放0. 随机选i和j, 如果选0 就重新选, 如果没有 就返回. import java.util.*; public class RandomGenerator { public int rnd5(){ return new Random().nextInt(5)+1; } public int rnd7() { int[][] m = new int[][]{ {1,2,3,4,5}, {6,7,1,2,3}, {4,5,6,7,1}, {2,3,4,5,6}, {7,0,0,0,0} }; int result = 0; […]
public class Solution { public int maximumGap(int[] nums) { int n = nums.length; if(n <= 1) return 0; int max = Integer.MIN_VALUE; for(int i : nums){ max = Math.max(max, i); } int min = Integer.MAX_VALUE; for(int i : nums) { min = Math.min(min, i); } int len = (int)Math.ceil((double)(max-min) / (n – 1)); int[] maxnum […]
public class Solution { public String minWindow(String s, String t) { int[] needtofind = new int[256]; int[] hasfound = new int[256]; for(int i = 0 ; i < t.length(); i++) { needtofind[t.charAt(i)]++; } int start = 0; int count = 0; int min = Integer.MAX_VALUE; String window = “”; for(int end = 0; end < […]
import java.util.LinkedHashMap; import java.util.Map; public class LRUCache { private Map<Integer, Integer> map; private int capacity; public LRUCache(int capacity) { map=new LinkedHashMap<Integer, Integer>(capacity, 1, true); //set access order to true this.capacity = capacity; } public int get(int key) { if (!map.containsKey(key)) return -1; return map.get(key); } public void set(int key, int value) { if (!map.containsKey(key) && […]
原题: http://codeforces.com/contest/577/problem/C 题目大意: 给一个数字n, 一个人猜这个n是多少, 他可以提问: n是不是整除x, 问你最少提问多少次,问的是什么可以猜出n. 分析: 算术基本定理(https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic). 可以证明,我们需要猜出每个n前边的的质数p, 对于每个p,我们还要猜出其不大于n的倍数, 才能确保n的唯一. 所以答案先晒质数, 再求倍数. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); boolean[] prime = new boolean[n+1]; Arrays.fill(prime, 2, n + 1, true); for (int i = 2; i * i <= n; i++) if (prime[i]) for (int j = […]
原题: http://codeforces.com/contest/577/problem/B 题目大意: 给n个数, 问能不能找到其中的subsequence的合可以整除k. 分析: 额..这题开始做的时候考虑不周, 老是过不了, 后来加了个mod k 就过了. 看了答案后, 感觉思路差不多, 首先,当n>k时, 因为鸽巢原理, n个数,每个贡献1,肯定能找到合整除k的. 而当n<=k时, 我们可以通过记录数组当前数字与前一个数组合的模来判断是不是是否可以整除, 即: 如果合的模是0, 那么找到了答案返回YES. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int k = in.readInt(); int[] nums = IOUtils.readIntArray(in, n); boolean[] mod = new boolean[k]; for (int i = 0; i < n; […]