# LeetCode Weekly Contest 37解题思路

## Leetcode 624. Maximum Distance in Arrays

Problem:

Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.

Example 1:

Input: [[1,2,3], [4,5], [1,2,3]] Output: 4 Explanation: One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Note:

• Each given array will have at least 1 number. There will be at least two non-empty arrays.
• The total number of the integers in all the m arrays will be in the range of [2, 10000].
• The integers in the m arrays will be in the range of [-10000, 10000].

• 把每一行的最大值放入一个数组中，对其排序，得到一个降序排列的max集合。
• 遍历每一行，取每一行的最小值，更新ans，如果最大值在当前行，则取次大的。

```class Pair{
int index;
int value;
Pair(int index, int value){
this.index = index;
this.value = value;
}
}

public int maxDistance(int[][] arrays) {
if (arrays == null || arrays.length == 0) return 0;
int row = arrays.length;
Pair[] p = new Pair[row];
for (int i = 0; i < row; ++i){
p[i] = new Pair(i,arrays[i][arrays[i].length - 1]);
}
Arrays.sort(p,(a,b) -> b.value - a.value);
int max = 0;
for (int i = 0; i < row; ++i){
int x = arrays[i][0];
int c = p[0].index != i ? p[0].value : p[1].value;
max = Math.max(max, Math.abs(c - x));
}
return max;
}```

```public int maxDistance(int[][] arrays) {
if (arrays == null || arrays.length == 0) return 0;
int min = arrays[0][0];
int max = arrays[0][arrays[0].length-1];

int diff = 0;
for (int i = 1; i < arrays.length; ++i){
int tail = arrays[i][arrays[i].length - 1];
diff = Math.max(diff, Math.abs(max - head));
diff = Math.max(diff, Math.abs(tail - min));
max = Math.max(max, tail);
}
return diff;
}```

```tail - min{i+1} > tail - min{i}

max{i+1} - min{i-1} > tail - min{i+1}
min{i+1} - max{i-1} > head - max{i+1}

## Leetcode 623. Add One Row to Tree

Problem:

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1. The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N’s left subtree root and right subtree root. And N’s original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

```public TreeNode addOneRow(TreeNode root, int v, int d) {
if (d == 1){
TreeNode r = new TreeNode(v);
r.left = root;
return r;
}
dfs(root,v,d,1);
return root;
}

private void dfs(TreeNode root, int v, int d, int layer) {
if (root == null)
return;

if (layer == d - 1){
TreeNode left = root.left;
TreeNode right = root.right;
root.left = new TreeNode(v);
root.right = new TreeNode(v);
root.left.left = left;
root.right.right = right;
}
dfs(root.left, v, d, layer + 1);
dfs(root.right, v, d, layer + 1);
}```

## Leetcode 625. Minimum Factorization

Problem:

Given a positive integer a, find the smallest positive integer b whose multiplication of each digit equals to a. If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.

Example:

Input: 48 Output: 68 Input: 15 Output: 35

```public int smallestFactorization(int a) {
if (a < 9) return a;
String ans = "";
while (a > 9){
int i = 9;
for (; i >= 1; --i){
if (a % i == 0){
ans += i;
break;
}
}
if (i == 1){
return 0;
}
a = a / i;
}
ans += a;
char[] array = ans.toCharArray();
Arrays.sort(array);
String small = new String(array);
try {
int num = Integer.parseInt(small);
return num;
} catch (NumberFormatException e) {
return 0;
}
}```

```public int smallestFactorization(int a) {
if (a < 9) return a;
int[] res = new int[32];
int j = 0;
while (a > 9){
int i = 9;
for (; i >= 1; --i){
if (a % i == 0){
res[j++] = i;
break;
}
}
if (i == 1){
return 0;
}
a = a / i;
}
res[j] = a;
long ans = 0;
while (j >= 0){
ans = 10 * ans + res[j--];
if (ans > Integer.MAX_VALUE) return 0;
}
return (int)ans;
}```

```public int smallestFactorization(int a) {
if (a < 10) return a;
int[] res = new int[32];

int j = 0;
for (int i = 9; i >= 2; --i){
while (a % i == 0){
res[j++] = i;
a = a / i;
}
}
if (a != 1) return 0;
long ans = 0;
for (int i = j - 1; i >= 0; --i){
ans = 10 * ans + res[i];
if (ans > Integer.MAX_VALUE) return 0;
}
return (int)ans;
}```

Problem:

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle. You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example :

Input: tasks = [‘A’,’A’,’A’,’B’,’B’,’B’], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

• The number of tasks is in the range [1, 10000].

```eg:
A A A A B B B C C  n = 1

o o o o o o o o o o
0 1 2 3 4 5 6 7 8 9

A = 4
B = 3
C = 2

A o A o A o A o o o

A B A B A B A o o o

A B A B A B A C o C

A B A C A B A B C o

• 一定选择最高频次进行分配。（反证法，如果选择较低频次的任务分配，它的最小长度为【(频次 - 1) * (n + 1) + 1】，那么较高频次的任务是不可能被放在这个长度的数组内，所以数组长度至少是【(最大频次 - 1) * (n+1) + 1】），所以先分配最高频次咯。
• 其次，我们可以从模拟的角度来看，这也是长度不是最优的真正原因，第一条性质只是帮助我们筛选策略罢了，如果先选择较低频次的任务分配，那么在后续任务分配当中，最高频次的任务一定会留到最后分配，如果这样，因为没有其他任务占位，系统只能idle处理，白白浪费资源。

```    class Pair{
char key;
int freq;
public Pair(char key, int freq){
this.key = key;
this.freq = freq;
}
}

public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < tasks.length; ++i){
}
Queue<Pair> pq = new PriorityQueue<>((a,b) -> (b.freq - a.freq));
for (char key : map.keySet()){
pq.offer(new Pair(key, map.get(key)));
}

int cnt = 0;
while (!pq.isEmpty()){
int k = n + 1;
List<Pair> tmp = new ArrayList<>();
while (k != 0 && !pq.isEmpty()){
Pair p = pq.poll();
p.freq--;
cnt++;
k--;
}

for (Pair p : tmp){
if (p.freq != 0){
pq.offer(p);
}
}
if (pq.isEmpty()) break;
cnt = cnt + k;
}
return cnt;
}```

A和A必须保持在n间隔之外

```    public int leastInterval(char[] tasks, int n) {
int[] map = new int[26];

for (int i = 0; i < tasks.length; ++i){
}
Arrays.sort(map);
int j = 25;
while (j >= 0 && map[j] == map[25]) j--;
return Math.max(tasks.length, (map[25] - 1) * (n + 1) + 25 - j);
}```

346 篇文章47 人订阅

0 条评论