Peak Index in a Mountain Array
给一个数组, 找一个index,比左大比右小, 这个题前提是这个index一定存在, 省去很多corn cases的判断, 直接二分找
binary search
Educational Codeforces Round 3 D – Gadgets for dollars and pounds
链接: https://codeforces.com/contest/609/problem/D 这题好tricky, 好几个test都是c++的ll类型的, java做着好头疼. 首先根据题意可以看出来, 能在x天完成任务(从m中买到k个item), 在剩下的x+1天也能完成, 所以具有单调性, 可以在排序(根据买东西的实际价格排序, 这里的实际价格是第i天的汇率*单价). 其次我们的目标是买k个东西, 那么如果给定某天x, 如何用同样的钱(假设), 买更多的东西?, 肯定是先买便宜的啊. 所以是贪心算法. 既然是贪心算法, 我们就要找到算法的关键, 那就是如何在m天中的第i天买到更便宜的东西? 显然, 我们知道汇率和单价是乘法关系, 就要分别找到前i天的两种货币的最低汇率minD和minP, 然后我们要测试一下在cur天的时候, 我们能否买够所需的k个物品. 这里我们用minD和minP分别乘以m个物品, 然后得到的价格就是cur天实际价格, 然后通过排序并且提取前k个物品, 我们就可以测试能否在cur天购买到k个物品.
First Bad Version
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; } }
H-Index II
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; } }
Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections
原题: http://codeforces.com/contest/574/problem/A 题目大意: 给一个n的数的数组, 问如何让第一个数拿最少数组中别的数字的数,使得第一个数变成这个数组最大的数. 分析: 这题的做法很多, 我开始的时候暴了一下, 发现过不了, 暴的复杂度是O(n2), 看来能有lgn的做法. 后来想想, 假设第一个数是数组中最大的数, 那么就可以不用拿别的数, 如果第一个数不是数组中最大的数, 那么它最多拿的数, 应该是数组中最大的数. 假设数组: 5 1 11 2 8. 第一个数5不是数组中最大的数字, 那么我们可以假设, 最坏情况下, 我们最多拿11(11为数组中最大的数字), 使得5变成数组中最大的数字, 当然这个情况是最坏情况. 其次, 上面例子中的5 1 11 2 8的结果是4, 那么我们可以证明, 任何大于4的数字都是可以的. 因此, 我们可以通过二分搜索的办法, 搜索这个数字. 复杂度是o(nlgn), n是每次检查搜索结果的正确性, lg是二分. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] […]
[LintCode] Copy Books
public int copyBooks(int[] pages, int k) { // write your code here int l = 0; int r = 9999999; while( l <= r){ int mid = l + (r – l) / 2; if(search(mid,pages,k)) r = mid-1; else l = mid+1; } return l; } public boolean search(int total, int[] page, int k) { […]
[LintCode] Search a 2D Matrix
public boolean searchMatrix(int[][] matrix, int target) { // write your code here if(matrix == null || matrix.length == 0) return false; int i = 0; int j = matrix[0].length-1; while(i < matrix.length && j >=0) { if(target == matrix[i][j]) return true; else if(target < matrix[i][j]) j–; else i++; } return false; }
[SPOJ] DIVSUM – Divisor Summation
原题: 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 […]
[SPOJ] NOTATRI – Not a Triangle
原题:http://www.spoj.com/problems/NOTATRI/ 题目大意:给一个数组, 找到其中不能组成三角形的3-tuple的个数. 分析:睡前A一道. 简单的计算. 两边之和<第三边, 先排序一下数组, 然后把第三边取数组最后一个, 也是最大一个数. 然后两个指针left和right, meet in middle, 个数是 right-left, 因为每次当满足条件时, 所有在right和left中的元素, 都可以看成以当前i为第三边和当前的left为一条边时, 移动right往left靠拢,这些可能的组合, 都是满足条件的, 因为right靠谱left是一个递减的过程. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); while (t != 0){ int[] nums = IOUtils.readIntArray(in,t); out.printLine(solve(nums)); t = in.readInt(); } } private int solve(int[] nums){ int res = […]
[SPOJ] FACVSPOW – Factorial vs Power
原题:http://www.spoj.com/problems/FACVSPOW/ 题目大意: 给正整数a, 求最小的正整数n, 使得n!>a^n 分析: 我看下面留言都说不计算fact, 用数学方法. 我就想两边取log, 左边的阶乘就是log(1)+log(2)….log(n), 右边的power就是n*log(a), 然后我写了下面的code public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); double power = 0; double fact = 0; int cur = 2; double temp = Math.log(n); while (true) { fact += Math.log(cur); // power = temp * cur; if (fact […]