Menu Sidebar
Menu

sorting

Two City Scheduling

这题可有点绕,开始直接想的就是动态规划,然后琢磨了一下,觉得easy应该有greedy的做法,于是想到比较两个人去A和B之间的差的abs,即B[1]-A[1](去B点cost的差)和B[0]-A[0](去A点的cost的差),然后排序,再求和。 最后翻了翻答案, 看到以下解法,真是更巧妙。 举例[[10,20],[30,200],[400,50],[30,20]],因为只有A,B两个点,所以我们假设所有人都去一个点B,那么就是 20 + 200 + 50 + 20. 然后我们数组的两个数相减,得出如果去A,那么哪些人优先去?[20-10], [200-30], [50-400],[20-30] -> [10], [170], [-350], [-10], 然后排序,[170], [10], [-10], [-350]. 这个数组序列是按照最应该去A的人。最后是最巧妙的一点, 我们因为已知n个人要去A,所以只需取前两个,[170], [10]., 然后是我们如何加到最开始的数组? 首先,我们把[170], [10] 还原成 [200-30], [20-10], 然后我们用20 + 200 + 50 + 20 – (200-30) – (20 – 10).就可以消去B并且加回A。

Height Checker

一脸懵逼的看完题, 按题意写就是o(n) space o(n) time. 想了一会儿,感觉不知道怎么优化,如果这个能优化,那么就需要知道每个元素的rank,如果rank()这个函数好像需要用一个元素比较所有元素才能知道结果,毕竟非排序数组,不比较所有元素怎么知道那个比那个大,排序也是rank的一种,这也是排序nlgn的速度下限的一种证明吧

Maximum Gap

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 […]

Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) B. Order Book

原题: http://codeforces.com/contest/572/problem/B 题目大意: 对n个股票操作进行排序, 最后生成一个Order Book. 操作有两种, buy 和 sell, 后边是股票标号和价钱. 要求对相同操作的相同股票进行合并操作. 然后输出排序后前s个sell和buy的股票. 这里的排序要求是, 对于sell, 先对编号递增排序, 然后取前s (没有s个取所有). 然后再对编号递减排序. 对于buy直接递减排序即可. 分析: 用Java的TreeMap一下就出来了. 因为TreeMap本身就是有序的, 用Collections.reverseOrder()可以改变顺序. 然后取前s个的时候, 可以把set变成stream, 然后limit一下就可以 public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int s = in.readInt(); int cb = 0; int cs = 0; Map<Integer, Integer> BMap = […]

Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) A. Arrays

原题: http://codeforces.com/contest/572/problem/A 题目大意: 给两个数组, 问是否能在第一个数组找到k个数,在第二个数组找到m个数, 使得所有在第一个数组找到的数小于第二个数组找到的数. 数组已排序. 分析: 因为数组已经排序, 所以如果在第一个数组前k个数字小于第二个数组后m个数字, 那么打印YES.如果不是, 打印NO public void solve(int testNumber, InputReader in, OutputWriter out) { int na = in.readInt(); int nb = in.readInt(); int k = in.readInt(); int m = in.readInt(); int[] naAry = IOUtils.readIntArray(in, na); int[] nbAry = IOUtils.readIntArray(in, nb); if (naAry[k – 1] >= nbAry[nb – m]) out.print(“NO”); […]

[LintCode] Merge Intervals

public List<Interval> merge(List<Interval> intervals) { // write your code here List<Interval> res= new ArrayList<Interval>(); if(intervals.size() == 0 || intervals == null) return res; Collections.sort(intervals, new IntervalComparator()); Interval first = intervals.get(0); for(int i = 1; i < intervals.size(); i++) { Interval cur = intervals.get(i); if(cur.start <= first.end) { first.end = Math.max(cur.end, first.end); }else{ res.add(first); first = […]

[LintCode] 3 Sum

public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(numbers.length == 0 || numbers == null) return res; Arrays.sort(numbers); for(int i = 0 ; i < numbers.length – 2; i++) { if(i != 0 && numbers[i] == numbers[i-1]) continue; int l = i+1; int r = numbers.length – 1; […]

[LintCode] 3 Sum Closest

public int threeSumClosest(int[] numbers ,int target) { // write your code here Arrays.sort(numbers); if(numbers.length == 0 || numbers == null) return 0; int close = Integer.MAX_VALUE; for(int i = 0; i < numbers.length – 2; i++) { int j = i + 1; int k = numbers.length – 1; while(j < k) { int sum […]

[SPOJ] SBANK – Sorting Bank Accounts

原题: 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; […]

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

February 2023
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728