发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/k-inverse-pairs-array/

　　给你n和k，n代表了1,2,3….n的数组，找出数组排列的个数满足，有且只有k个逆序对

Example 1:

1
2
3
4
Input: n = 3, k = 0
Output: 1
Explanation: 
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.

Example 2:

1
2
3
4
Input: n = 3, k = 1
Output: 2
Explanation: 
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
阅读全文 »

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/course-schedule-iii

　　给了一系列的二元组的数组，第一个元素代表课程花费时间，第二个代表课程deadline。问一共能最多能完成多少门课程，两门课程不允许有交叠。

题目分析

　　从题目明显可以看出来是贪心题，可是没有想出来好的思路，参考了讨论区的一个答案 https://discuss.leetcode.com/topic/93712/python-straightforward-with-explanation 整理一下关键的思路：

  1. 按deadline逆序排序，也就是说优先考虑deadline靠前的课程
  2. 记录一个start值，表示下次课程的起始时间，也就是说start值每次都要加上当前课程的花费时间。但是，当start加上当前course的花费时间以后，如果超过了当前课程的deadline，那么明显是不符合要求的，也就是说此时应该移除之前已经纳入考虑范围的课程，应该移除的是那些花费时间最大的课程，很容易可以理解用大根堆记录课程花费时间，当start加上花费时间大于deadline时，移除大根堆的最大元素，一定可以保证小于deadline了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int scheduleCourse(int[][] courses) {
        int n = courses.length;
        Arrays.sort(courses, (a, b) ->  a[1] - b[1]); // 按endtime倒序排列
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // 大根堆
        int start = 0;
        for (int[] course: courses) {
            start += course[0]; // 先加到start中
            pq.offer(course[0]); // 先加到pq中
            if (start > course[1]) { // 如果start超过deadline，移除堆顶元素，一定可以保证start小于end
                start -= pq.poll();
            }
        }        
        return pq.size();
    }   
}

　　时间复杂度：nlogn

发表于   |   分类于   |  

　　Node.js是事件驱动、异步、单线程、非阻塞I/O、开源跨平台的Javascript语言运行环境。最近用到了Node.js开发一些server端程序，整理了一下常用的涉及文件IO，stream，定时任务等基本操作。

文件流操作

　　本部分涉及文件流按行读取文件，以及文件写入，文件夹相关操作

读取目录

1
2
3
4
5
6
7
8
9
10
var fs = require("fs"); // 依赖fs模块
fs.readdir("/data/", (err, files) => {
   if (err) {
       return console.error(err);
   }
   files.forEach( function (file){
       // ....
   });
});

删除文件

1
2
3
4
5
6
7
8
var fs = require("fs");
fs.unlink('input.txt', (err) => {
   if (err) {
       return console.error(err);
   }
   console.log("delete successfully");
});
阅读全文 »