水塘抽样是一组解决数据流取样的方法, 有很多的变种. 它适用的问题有如下特点: 对象为无法在内存中放下的数据, 如不间断数据流, 或者巨大的文件, 数组等. 样本集的大小为k, 并且要求每个样本的取样概率相等. 取样概率可以通过添加权重(weight)来改变取样概率. 一般(无weight)水塘抽样的每个样本的取样概率为: k/(n+1) 水塘抽样的算法实现非常简单, 而且证明简练. 算法如下: 预设数组A, 大小为k. 先取样k个元素. 放入A中. 从k+1元素开始, 每次取得随机数r, 范围为(0,k+1). 如果r <= k, A[r] = S[k+1], S是当前数据流.
原题: http://codeforces.com/contest/567/problem/C 题目大意: 给一个n大小数组, 问其中的子序列(非连续)能组成多少个已p为公比的等比序列, 且长度为3. 分析: 这题卡了好久, 我用找等差数列的方法改的. 后来总是过不了test. 可是怎么看我的是O(nlgn)的复杂度, 所以过不了大的test case 肯定是有O(n)的. 于是开始想啊想啊….最后想到了是用等比中项的性质. 首先上一个过不了的code: public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int p = in.readInt(); IntPair[] nums = new IntPair[n]; for (int i = 0; i < nums.length; i++) { nums[i] = new IntPair(in.readInt(),i); } Arrays.sort(nums); int count […]
原题:http://codeforces.com/contest/567/problem/B 题目大意: 一个计数器, +号代表一个人进入图书馆, -号代表一个人出去图书馆. 给一个log, 问这个log中能知道的这个图书馆最小的可能容量是多少, log是片段, 在program运行前可能图书馆已经有人, 在运行后也可能人还没出去? 分析: 因为log不能完全记录图书馆的信息, 有可能第一条就是-号,所以我们需要用个数组记录一下人来往的信息. 但是当发现有人出去但是没有进入的信息, 我们就知道在当前时候, 图书馆的容量应该比记录的容量多1. 换句话说, 当发现一个人走出来但是没有被记录进去, 我们只能认为这个人一直在图书馆里. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); boolean[] t = new boolean[1000010]; int cap = 0; int cur = 0; for (int i = 0; i < n; i++) { […]
原题: http://codeforces.com/contest/567/problem/A 题目大意: 给一个数组, n个数, 有正有负, 已经排序好了, 让你输出每个数和数组中其他数的最大差和最小差. 分析: 已经排好, 所以遍历一遍,最小就是比较当前数字的左边或右边的差的绝对值, 最大就是比较当前数字和数组的头和数组的尾的差的绝对值, 就可以了, 注意第一个数和最后一个数没有左边或者右边. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] ary = IOUtils.readIntArray(in, n); out.printLine(Math.abs(ary[1] – ary[0]) + ” ” + Math.abs(ary[0] – ary[ary.length – 1])); for (int i = 1; i < ary.length-1; i++) { out.printLine(Math.min(Math.abs(ary[i] – […]
对表达式添加括号,能有几种不同答案 Example 1 Input: “2-1-1”. ((2-1)-1) = 0 (2-(1-1)) = 2 Output: [0, 2] Example 2 Input: “2*3-4*5” (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10 Output: [-34, -14, -10, -10, 10] 这题可以换个思路考虑, 其实在每个数字和符号之间都可以添加括号, 而且题目没有要求符号的数量. 这个其实就是在问, 有多少个Valid Parentheses, 和领一道Leetcode的题一样. 求解卡特兰数的组成个数. public class Solution { public List<Integer> diffWaysToCompute(String input) […]
给一个数组, 找数组中的一个点, 使在这点的左边数的和,等于右边的和. 注意: 这里不是sorted数组. 所以我们用meet in middle的做法. 而且数组会有负数, 对于负数, 我们需要在另一边加上这个数. public int find (int[] nums) { int l = 0; int r = nums.length – 1; int suml = 0; // sum of left side int sumr = 0; // sun of right side while (l <= r) { if (l == r && […]
Google电面的Bit操作题, 问你能不能用一个O(1)的方法, 判断n是不是4的倍数. 既然是O(1), 所以不能用循环, 先把n对n-1取&, 假设n = 16, 即10000. n-1=15,即01111. 但是我们还需要判断这个数是不是0. 所以我们让n对一个比它小的质数取mod. 比如4%3==1, 这样就可以判断n是不是4的倍数了. public static boolean isPowerof4(int n) { return (n&n-1)+n%3==1; } 下边是power of 8 public static boolean isPowerof8(int n) { return (n&n-1)+n%7==1; }
Bit操作的题, 给一个整数+1,不能用加号. 其实很简单,扫一下整数的每个bit(从低位到高位), 对它做&操作, 如果结果是0, 证明此位是0, 那么我们在这位+1, 如果是1, 那么我们清空此位. public class addBinaryNumberBy1WithoutPlus { public int add(int n) { for(int i = 0; i < 32; i++) { if (((1 << i) & n) == 0){ //until we find the first 1 bit n = n | (1 << i); break; } else n = n […]
1. 给个数组, 已经排序了, 找到第一个比n大的数. 如果没有, 返回-1. 二分搜索一下就可以, 注意一下返回-1的条件. public static int fixBox(int[] nums, int product) { int n = nums.length; int l = 0; int r = nums.length – 1; while (l <= r) { int mid = l + (r – l) / 2; if (nums[mid] < product) l = mid + 1; else […]