6.22号刷题

发表于 | 分类于 | 0 comments

第一题 537. Complex Number Multiplication

题目描述

求两复数相乘的结果

注意：

  1. 输入字符串不包含额外空格
  2. 输入字符串以a+bi给出，其中a与b都是[-100, 100]范围的整数。输出采用同样形式

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public String complexNumberMultiply(String a, String b) {
    String result = "";
    String[] A = a.split("\\+");
    String[] B = b.split("\\+");
    int a1 = Integer.parseInt(A[0]);
    int b1 = Integer.parseInt(A[1].replace("i",""));
    int a2 = Integer.parseInt(B[0]);
    int b2 = Integer.parseInt(B[1].replace("i",""));
    int a1a2 = a1 * a2;
    int b1b2 = b1 * b2;
    int a1b2a2b1 = (a1 * b2) + (b1 * a2);
    String afinal = (a1a2 + (-1 * b1b2)) + "";
    String bfinal = a1b2a2b1 + "i";
    result = afinal+"+"+bfinal;
    return result;        
    }
}

第二题 553. Optimal Division

题目描述

给定一组正整数，相邻整数之间使用除号连接。例如，[2,3,4] -> 2 / 3 / 4

在其中加入括号可以改变运算顺序，求运算结果最大时的加括号方案，返回表达式。

注意：

  1. 输入整数长度范围[1, 10]
  2. 元素范围[2, 1000]
  3. 输入确保有唯一解

算法

这道题没什么意思，不管输入是什么，我们的第一个永远是除数的位置，后面的都是被除数。由于都是整数，被除之后只会越来越小，因此我们只需要保证后面的数字最小即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public String optimalDivision(int[] nums) {
        StringBuilder builder = new StringBuilder();
        builder.append(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (i == 1 && nums.length > 2) {
                builder.append("/(").append(nums[i]);
            } else {
                builder.append("/").append(nums[i]);
            }
        }
        
        return nums.length > 2 ? builder.append(")").toString() : builder.toString();        
    }
}

第三题 296. Best Meeting Point

题目描述

在一个2维矩阵中，每个点的值分别为0或1。1代表住了人，需要在矩阵中找到一个点，使得到所有的住人的点的距离最小。距离是用曼哈顿距离进行计算

算法

在绝对值相加的计算中，最小值的点即为中位数的点。利用这点，就可以简单的解除这道题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public int minTotalDistance(int[][] grid) {
        if (grid.length <= 0 || grid[0].length <= 0) return 0;
        int m = grid.length, n = grid[0].length;
        List<Integer> x = new ArrayList<>();
        List<Integer> y = new ArrayList<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1)
                    x.add(i);
            }
        for (int j = 0; j < n; j++)
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 1)
                    y.add(j);
            }
        return countMin(x) + countMin(y);
    }
    public int countMin(List<Integer> nums) {
        int low = 0, high = nums.size() - 1;
        int sum = 0;
        while (low < high) {
            sum += nums.get(high--) - nums.get(low++);
        }
        return sum;
    }
}

第四题 453. Minimum Moves to Equal Array Elements

题目描述

给定一个长度为n的非空整数数组，计算最少需要多少次移动可以使所有元素相等，一次移动是指将n - 1个元素加1。

算法

sum为所有值的和， m为移动的次数，x为移动后的值

sum + m * (n - 1) = x * n
x = minNum + m
x = minNum + m

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE, sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            min = Math.min(min, nums[i]);
        }
        
        return sum - nums.length * min;        
    }
}

第五题 462. Minimum Moves to Equal Array Elements II

题目描述

给定非空整数数组，求使得数组中的所有元素均相等的最小移动次数，一次移动是指将某个元素加1或者减1。

你可以假设数组长度不超过10000。

算法

与之前相遇问题一样，都是在中位数的点所有移动的次数是最小的

1
2
3
4
5
6
7
8
9
10
public class minMovesII462 {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int low = 0, high = nums.length - 1, sum = 0;
        while (low < high) {
            sum += nums[high--] - nums[low++];
        }
        return sum;
    }
}

第六题 258. Add Digits

题目描述

给定一个非负整数num，重复地将其每位数字相加，直到结果只有一位数为止。

例如：

给定 num = 38，过程像这样：3 + 8 = 11, 1 + 1 = 2。因为2只有一位，返回之。

进一步思考：

你可以不用循环，在O(1)运行时间内完成题目吗？

算法

in  out  in  out
0   0    10  1
1   1    11  2
2   2    12  3
3   3    13  4
4   4    14  5
5   5    15  6
6   6    16  7
7   7    17  8
8   8    18  9
9   9    19  1

可以看出，最后的结果为(num - 1) % 9 + 1

1
2
3
4
5
public class addDigits258 {
    public int addDigits(int num) {
        return 1 + (num - 1) % 9;
    }
}

第七题 573. Squirrel Simulation

题目描述

二维格子高度height，宽度width。其中包含一棵树tree，一个松鼠squirrel，以及一些坚果nuts。

求松鼠将所有坚果运送至树的位置所需的最小距离之和。

注意：

  1. 所有位置不会重叠
  2. 松鼠一次运送只能携带一枚坚果
  3. 给定坚果位置是无序的
  4. 高度和宽度是正整数，并且 3 <= height * width <= 10,000
  5. 给定位置包含至少一枚坚果，只有一棵树和一只松鼠

算法

我们注意到，由于一次只能运送一枚坚果。sum1是出生点在坚果上要运送的距离，sum2是在其余地方。

2a1 + 2a2 + ...... + 2an = sum1
2a1 + 2a2 + ... + ai + bi + ... + 2an = sum2
=>

我们希望sum2能最小
即

sum1 - sum2 = ai - bi
sum2 = sum1 - (ai - bi)

由于sum1是固定的，因此只需要ai - bi最大，那么sum2即为最小

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        if (tree.length != 2 || squirrel.length != 2 || nuts.length < 1) return 0;
        
        int sum = 0, max = Integer.MIN_VALUE;
        for (int[] nut : nuts) {
            int distance = Math.abs(tree[0] - nut[0]) + Math.abs(tree[1] - nut[1]);
            sum += 2 * distance;
            max = Math.max(max, distance - (Math.abs(squirrel[0] - nut[0]) + Math.abs(squirrel[1] - nut[1])));
        }
        return sum - max;        
    }
}

第八题 598. Range Addition II

题目描述

给定m * n矩阵M，初始为0，然后执行一些更新操作。

数组ops表示一组更新操作，每一个操作(a, b)，表示将矩阵0 <= i < a 并且 0 <= j < b的区域值+1。

进行若干操作后，求矩阵的最大值。

注意：

  1. m和n的范围[1, 40000]
  2. a的范围[1, m]，b的范围[1, n]
  3. 操作不超过10000个

算法

求最小值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class maxCount598 {
    public int maxCount(int m, int n, int[][] ops) {
        if (ops.length == 0) return m * n;
        int numX = Integer.MAX_VALUE, numY = Integer.MAX_VALUE;
        for (int[] op : ops) {
            int x = op[0];
            int y = op[1];
            if (x < numX) numX = x;
            if (y < numY) numY = y;
        }
        numX = numX == 0 ? 1 : numX;
        numY = numY == 0 ? 1 : numY;
        return numX * numY;
    }
}