# LeetCode Weekly Contest 38解题思路

## Leetcode 628. Maximum Product of Three Numbers

Problem:

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3] Output: 6

Example 2:

Input: [1,2,3,4] Output: 24

Note:

• The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
• Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

    public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int max = Integer.MIN_VALUE;
int n = nums.length;
max = Math.max(max, nums[0] * nums[1] * nums[2]);
max = Math.max(max, nums[n-1] * nums[n-2] * nums[n-3]);
max = Math.max(max, nums[0] * nums[1] * nums[n-1]);
return max;
}

## Leetcode 630. Course Schedule III

Problem:

There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day. Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] Output: 3 Explanation: There’re totally 4 courses, but you can take 3 courses at most: First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day. Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:

• The integer 1 <= d, t, n <= 10,000.
• You can’t take two courses simultaneously.

OKAY，有了这些就可以设计我们的代码了，如果成功加入第n门课，说明最大上课数变动了，所以只要更新now即可，而当第n门课未加入成功，则需要根据这第n门课求出最小的now。如下：

[6,7] [2,10],[4,11]

n = 2
now = 6 + 2 = 8
n = 3

now = 6 + 2 + 4 - 6 = 6

now{n} 表示在集合n中，当前now的最小值,{}表示集中，当然这是我自己的表达方式

b. now{n-1} + courses[n][0] > courses[n][1]

now{n} = now{n-1} + courses[n][0]

c. now{n} = now{n-1} + courses[n][0] - courses[j][0]

c1. n == j

c2. n != j
now{n} - now{n-1} = courses[n][0] - courses[j][0]

courses[j][0] > courses[n][0]

public int scheduleCourse(int[][] courses) {
Arrays.sort(courses, (a, b) -> a[1] - b[1]);
Queue<Integer> q = new PriorityQueue<>();
int n = courses.length;
int now = 0;
for (int i = 0; i < n; ++i) {
now += courses[i][0];
q.offer(-courses[i][0]);
while (now > courses[i][1]) {
now += q.poll();
}
}
return q.size();
}

## Leetcode 629. K Inverse Pairs Array

Problem:

Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it’s an inverse pair; Otherwise, it’s not. Since the answer may very large, the answer should be modulo 109 + 7.

Example 1:

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:

Input: n = 3, k = 1 Output: 2 Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Note:

• The integer n is in the range [1, 1000] and k is in the range [0, 1000].

dp[5][4] = dp[5][4] + dp[4][1]; if pos所在的位置的逆序对个数为3

dp[5][4] = dp[5][4] + dp[4][2]

    static int MOD = 1000000000 + 7;
public int kInversePairs(int n, int k) {
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; ++i)
dp[i][0] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
for (int l = Math.min(i - 1, j); l >= 0; --l) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - l]) % MOD;
}
}
}
return dp[n][k];
}

TLE，时间复杂度为O(n2⋅k)O(n^2 \cdot k)，基本思想有了，就看怎么优化了。可以参考Leetcode官方提供的教程https://leetcode.com/articles/k-inverse-pairs-array/，其中在解法4中，用到的就是上述更新过程，观察下移动的性质，你会发现它实际就是一种滑动窗口的更新模式，所以解法五，利用了dp[i][j-1]的值，在其基础上加上dp[i-1][j]再减去dp[i-1][j-1]即可。

static int MOD = 1000000000 + 7;
public int kInversePairs(int n, int k) {
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; ++i) dp[i][0] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
int val = (dp[i-1][j] - ((j - i < 0) ? 0 : dp[i-1][j-i]) + MOD) % MOD;
dp[i][j] = (dp[i][j-1] + val) % MOD;
}
}
return dp[n][k];
}

## Leetcode 631. Design Excel Sum Formula

Problem:

Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions: Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from ‘A’ to ‘Z’. It represents that the width is the number of characters from ‘A’ to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from ‘A’. void Set(int row, char column, int val): Change the value at C(row, column) to be val. int Get(int row, char column): Return the value at C(row, column). int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula. numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, “F7” represents the cell at (7, F). If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.

Example 1:

Excel(3,”C”); // construct a 3*3 2D array with all zero. // A B C // 1 0 0 0 // 2 0 0 0 // 3 0 0 0 Set(1, “A”, 2); // set C(1,”A”) to be 2. // A B C // 1 2 0 0 // 2 0 0 0 // 3 0 0 0 Sum(3, “C”, [“A1”, “A1:B2”]); // set C(3,”C”) to be the sum of value at C(1,”A”) and the values sum of the rectangle range whose top-left cell is C(1,”A”) and bottom-right cell is C(2,”B”). Return 4. // A B C // 1 2 0 0 // 2 0 0 0 // 3 0 0 4 Set(2, “B”, 2); // set C(2,”B”) to be 2. Note C(3, “C”) should also be changed. // A B C // 1 2 0 0 // 2 0 2 0 // 3 0 0 6

Note:

• You could assume that there won’t be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
• The test cases are using double-quotes to represent a character.
• Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

public class Excel {

int[][] table;
Map<String, String[]> mem = new HashMap<>();

public Excel(int H, char W) {
table = new int[H][W - 'A' + 1];
}

public void set(int r, char c, int v) {
table[r-1][c - 'A'] = v;
if (mem.containsKey(""+c+r)) mem.remove(""+c+r);
}

public int get(int r, char c) {
if(mem.containsKey(""+r+c)) sum(r,c,mem.get(""+r+c));
return table[r - 1][c - 'A'];
}

public int sum(int r, char c, String[] strs) {
mem.put(""+c+r,strs);
int sum = 0;
for (int i = 0; i < strs.length; ++i){
String cell = strs[i];
if (cell.contains(":")){
String[] cells = cell.split(":");
char topC = cells[0].charAt(0);
char botC = cells[1].charAt(0);
int topR = 0;
for (int j = 1; j < cells[0].length(); ++j) topR = topR * 10 + cells[0].charAt(j) - '0';
int botR = 0;
for (int j = 1; j < cells[1].length(); ++j) botR = botR * 10 + cells[1].charAt(j) - '0';
for (int k = topR; k <= botR; ++k){
for (char l = topC; l <= botC; ++l){
sum += get(k, l);
}
}
}
else{
char col = cell.charAt(0);
int row = 0;
for (int j = 1; j < cell.length(); ++j) row = row * 10 + cell.charAt(j) - '0';
sum += get(row, col);
}
}
return table[r-1][c - 'A'] = sum;
}
}

0 条评论

• ### Antenna Placement

思路： 看了discuss，咋有那么多人纠结无向图和有向图的区别。而且我也并没有理解所谓的答案： 顶点数 - 最大匹配数 / 2，说说我的思路吧。首先在二维...

• ### POJ 刷题系列：1789. Truck History

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LeetCode Weekly Contest 31解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 一道有趣的树状数组题

Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social ga...

• ### HDOJ 1019 Least Common Multiple(最小公倍数问题)

Problem Description The least common multiple (LCM) of a set of positive integ...

• ### F2. Animal Observation (hard version)

time limit per test：3 seconds memory limit per test：512 megabytes inputstandard ...

• ### POJ--1699 Best Sequence（DP+dfs）

Best Sequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions...

• ### PAT 甲级 1068 Find More Coins（0，1背包）

1068. Find More Coins (30) 时间限制 150 ms 内存限制 65536 kB 代码长度限制 16000 B ...

• ### HUST 1354 - Rubiks (DP)

1354 - Rubiks 时间限制：1秒 内存限制：64兆 452 次提交 102 次通过 题目描述 Isun is a genius. Not on...

• ### PAT 甲级 1003Emergency(Dijkstra最短路)

1003. Emergency (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序...