每日一题——April and March(part)

Posted on Edited on In Word count in article: 20k Reading time ≈ 18 mins.

前言

记录一下3月底、4月份每日一题记录，顺便督促自己打卡，仅记录每日一题~

（困难题型是否可以摸鱼呢？）

172. 阶乘后的零

题目描述：给定一个整数 n ，返回 n! 结果中尾随零的数量。提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

自己的解法

最开始想的是阶乘求解之后，再去求末尾0的数量， 例如阶乘后的结果遍历对(10*j)求余，但发现执行到30就走不通了= =，就算给result赋值long类型也不够，因为会溢出。

思路学习

首先末尾有多少个 0 ，只需要给当前数乘以一个 10 就可以加一个 0。

再具体对于 5!，也就是 5 * 4 * 3 * 2 * 1 = 120，我们发现结果会有一个 0，原因就是 2 和 5 相乘构成了一个 10。而对于 10 的话，其实也只有 2 * 5 可以构成，所以我们只需要找有多少对 2/5。

我们把每个乘数再稍微分解下，看一个例子。

11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1

对于含有 2 的因子的话是 1 * 2, 2 * 2, 3 * 2, 4 * 2 …

对于含有 5 的因子的话是 1 * 5, 2 * 5…

含有 2 的因子每两个出现一次，含有 5 的因子每 5 个出现一次，所有 2 出现的个数远远多于 5，换言之找到一个 5，一定能找到一个 2 与之配对。所以我们只需要找有多少个 5。

直接的，我们只需要判断每个累乘的数有多少个 5 的因子即可。

对于一个数的阶乘，就如之前分析的，5 的因子一定是每隔 5 个数出现一次，也就是下边的样子。

n! = 1 * 2 * 3 * 4 * (1 * 5) * … * (2 * 5) * … * (3 * 5) *… * n

因为每隔 5 个数出现一个 5，所以计算出现了多少个 5，我们只需要用 n/5 就可以算出来。

但还没有结束，继续分析。

… * (1 * 5) * … * (1 * 5 * 5) * … * (2 * 5 * 5) * … * (3 * 5 * 5) * … * n

每隔 25 个数字，出现的是两个 5，所以除了每隔 5 个数算作一个 5，每隔 25 个数，还需要多算一个 5。

也就是我们需要再加上 n / 25 个 5。

同理我们还会发现每隔 5 * 5 * 5 = 125 个数字，会出现 3 个 5，所以我们还需要再加上 n / 125 。

综上，规律就是每隔 5 个数，出现一个 5，每隔 25 个数，出现 2 个 5，每隔 125 个数，出现 3 个 5… 以此类推。

最终 5 的个数就是 n / 5 + n / 25 + n / 125 …

写程序的话，如果直接按照上边的式子计算，分母可能会造成溢出。所以算 n / 25 的时候，我们先把 n 更新，n = n / 5，然后再计算 n / 5 即可。后边的同理。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int trailingZeroes(int n) {
      int count = 0;
      while(n > 0){
          count += n / 5;
          n = n/5;
      }
      return count;
    }
}

682. 棒球比赛

思路——模拟栈

使用变长数组对栈进行模拟。

如果操作是 ++，那么访问数组的后两个得分，将两个得分之和加到总得分，并且将两个得分之和入栈。

如果操作是D，那么访问数组的最后一个得分，将得分乘以 2 加到总得分，并且将得分乘以 2入栈。

如果操作是 C，那么访问数组的最后一个得分，将总得分减去该得分，并且将该得分出栈。

如果操作是整数，那么将该整数加到总得分，并且将该整数入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    static int[] nums = new int[1000];
    public int calPoints(String[] ops) {
        int len = ops.length;
        int idx = 0;
        int result = 0 ;
        for(int i = 0; i < len ; i++ , idx++){
            if(ops[i].equals("+")){
                nums[idx] = nums[idx - 1]+nums[idx - 2];
            }else if(ops[i].equals("D")){
                nums[idx] = 2*nums[idx-1];
            }else if(ops[i].equals("C")){
                idx -= 2;
            }else{
                nums[idx] = Integer.parseInt(ops[i]);
            }
        }
        for(int j = 0; j < idx ; j++){
            result += nums[j];
        }
        return result;
    }
}

2028. 找出缺失的观测数据

思路：直接模拟

最开始个人的代码如下所示：

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
class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int len = rolls.length;
        int sum = mean*(len+n);
        int[] res = new int[n];
        for(int i = 0;i<len ; i++ ){
            sum = sum - rolls[i];
        }
        if((sum < n)||(sum > n * 6)){
            return new int[0];
        }else {
            int num = sum/n;
            int end = sum%n;
            if(end != 0){
                res[0] = num+end;
            }else{
                res[0] = num;
            }
            for(int i = 1;i<n ; i++){
                res[i] = num;
            }
        }
        return res;
    }
}

最后发现几次没通过= =，原因出在这个示例：

1
2
3
[4,5,6,2,3,6,5,4,6,4,5,1,6,3,1,4,5,5,3,2,3,5,3,2,1,5,4,3,5,1,5]
4
40

我的输出里面竟然构造了一个11，不符合题目1~6要求。。。

这是因为我把除法之后的余数全都分配在了一个数上面，当余数太大的时候肯定回超过范围，所以肯定要把余数分摊一下~（太蠢了）

以下是修改并优化后的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int len = rolls.length;//
        int sum = mean*(len+n);
        int[] res = new int[n];
        for(int i = 0;i<len ; i++ ){
            sum = sum - rolls[i];
        }
        if((sum < n)||(sum > n * 6)){
            return new int[0];
        }
        int num = sum / n;
        int remain = sum % n;
        for(int i =0 ; i< n ; i++){
            res[i] = num + ( i < remain ? 1 : 0);//关键点！
        }
        return res;
    }
}

假设缺失的部分和是：11，要分配给4个位置。那么11/4 = 2```3，那么4个位置中，分配3个2+1，最后一个分配2+0，即可得到要求，这也是

1
res[i] = num + ( i < remain ? 1 : 0);

这行代码的用处：将很大的余数分配给数组中一定数量的元素。

693. 交替位二进制数

思路——两个条件限制交替位二进制数

  • 1、对输入 n 的二进制表示右移一位后，得到的数字再与 n按位异或得到 a。当且仅当输入 n 为交替位二进制数时，a 的二进制表示全为 1（不包括前导 0）
  • 2、将 a与 a + 1 按位与，当且仅当 a的二进制表示全为 1 时，结果为 0：当且仅当 a 的二进制表示全为 1 时，a + 1可以进位，并将原最高位置为 0，按位与的结果为 0。否则，不会产生进位，两个最高位都为 1，相与结果不为 0。
1
2
3
4
5
6
class Solution {
    public boolean hasAlternatingBits(int n) {
        int a = n ^ (n >> 1);
        return (a & (a+1)) == 0;
    }
}

2024. 考试的最大困扰度

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

每次操作中，将问题的正确答案改为 ‘T’ 或者 ‘F’ （也就是将 answerKey[i] 改为 ‘T’ 或者 ‘F’ ）。
请你返回在不超过 k 次操作的情况下，最大 连续 ‘T’ 或者 ‘F’ 的数目

思路——滑动窗口

题目求修改次数不超过k的前提下，连续段“T” 或“F”的最大长度，也就是等价于：

求一个包含“T”和“F”的个数不超过k的最大长度窗口

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
class Solution {
    String s;
    int n ,_k;
    public int maxConsecutiveAnswers(String answerKey, int k) {
        s = answerKey;
        n = s.length();
        _k = k;
        return Math.max(getCount('T'),getCount('F'));
    }
    public int getCount(char c){//滑动窗口找个数不超过k的最大长度窗口
        int ans = 0;
        for(int i = 0 , j = 0 , count = 0; i < n;i++){
            if(s.charAt(i) == c){
                count++;
            }
            while(count > _k){
                if(s.charAt(j) == c){
                    count--;
                }
                j++;
            }
            ans = Math.max(ans,i-j+1);
        }
        return ans;
    }
}

由于滑动窗口这类题目很多，所以扩展一下以下题目：

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

和刚刚那个题目一样，只不过找T和F中最大的那个变为了只找包含0最大的窗口

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
class Solution {
    int n , _k;
    int[] num ;
    public int longestOnes(int[] nums, int k) {
        num = nums;
        n = nums.length;
        _k = k;
        return getNums();
    }

    public int getNums(){
        int ans = 0;
        for(int i = 0 , j = 0 ,count = 0 ; i < n;i++){
            if(num[i] == 0){
                count++;
            }
            while(count > _k){
                if(num[j] == 0){
                    count--;
                }
                j++;
            }
            ans = Math.max(ans , i-j+1);
        }
        return ans;
    }
}

3. 无重复字符的最长子串

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> myMap = new HashMap<Character,Integer>();
        int max = 0;//用于记录最大不重复子串的长度
        int left = 0;//滑动窗口左指针
        for(int i = 0 ; i<s.length();i++){
        /**
 1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
   此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

 2、如果当前字符 ch 包含在 map中，此时有2类情况：
   1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
   2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
   而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时应该不变，left始终为2，子段变成 ba才对。
	为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
             */
            if(myMap.containsKey(s.charAt(i))){
                left = Math.max(left , myMap.get(s.charAt(i))+1);
            }

            myMap.put(s.charAt(i),i);
            max = Math.max(max , i-left+1);
        }
        return max;
    }
}

728. 自除数

自除数 是指可以被它包含的每一位数整除的数。

例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
自除数 不允许包含 0 。

给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数

思路——直接模拟

关键点在于：

判断一个整数是否为自除数的方法是遍历整数的每一位，判断每一位数是否为 0 以及是否可以整除该整数。

遍历整数的每一位的方法是，每次将当前整数对 10 取模即可得到当前整数的最后一位，然后将整数除以 10。重复该操作，直到当前整数变成 0 时即遍历了整数的每一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
       List<Integer>ans = new ArrayList<>();
       out:for(int i = left ; i <= right ; i++){
           int cur = i ;
           while(cur != 0){
               int t = cur % 10;
               if(t == 0 || i %t != 0){
                   continue out;
               }
               cur /= 10;
           }
           ans.add(i);
       }
       return ans;
    }
}

954. 二倍数对数组

给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。

思路：哈希表+排序

思路没有什么问题，就是不知道如何实现，另外就是排序没有思考到这个电上，下面是我自己的代码= =肯定有问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        int len = arr.length ;
        int num = 0;//要满足的个数
        Map<Integer,Integer> hashtable = new HashMap<Integer,Integer>();
        for(int i = 0 ; i < len ; i++ ){
            if(hashtable.containsKey(arr[i]/2)||hashtable.containsKey(arr[i]*2)){
                num++;
            }
            hashtable.put(arr[i],i);
        }
        if( num == (arr.length>>1)){
            return true;
        }else{
            return false;
        }
    }
}

下面附上学习之后的代码：

依题意，我们首先对每个元素的出现次数用哈希表进行维护，然后用一个 list 存储其中的各个元素。然后遍历各个元素，对于每个元素 key判断是否有足够的 2k ，如果有，更新 2k 的数量；如果没有，返回 false 。

要注意的是，由于map的无序性，会导致遍历时可能会从中间元素开始遍历，此时后面的数就会受到影响。所以，我们要从小的元素开始遍历，以确保元素匹配的正确性。

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
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        //Map是用来维护数组中元素出现的个数的，也就是映射是元素->个数
        for(int x : arr){
            map.put(x , map.getOrDefault(x , 0)+1);//出现重复的则个数+1
        }
        //表用来存map中的key值，也就是元素
        List<Integer> list = new ArrayList<>(map.keySet());
        //例:[10,20,40,80]
        //由于map的无序性,导致遍历时可能会从中间开始遍历(20)
        //此时后面的数(40)就会收到影响
        list.sort((o1,o2) -> Math.abs(o1) - Math.abs(o2));

        for(int key : list){
            //判断是否有足够多的2*key
            if(map.get(key) > map.getOrDefault(2*key,0)){
                return false;
            }
            //维护2*key的数量，每次抵消key相同数量的2*key
            map.put(2*key , map.getOrDefault(2*key,0)-map.get(key));
        }
        return true;
    }
}

744. 寻找比目标字母大的最小字母

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’

思路：二分查找

和之前做的二分查找一样，只不过对象换成了字符而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0 , right = letters.length-1;
        int ans = letters.length;
        while(left <= right){
            int mid = (left + right)>> 1 ;
            char char1 = letters[mid];
            if((char1 - target)>0){
                right = mid -1 ;
                ans = mid;
            }else{
                left = mid+1;
            }
        }
        return ans == letters.length ? letters[0] : letters[ans];
        }
}

796. 旋转字符串

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

例如, 若 s = ‘abcde’，在旋转一次之后结果就是’bcdea’ 。

思路：模拟+拼接

当时做题的时候想的是直接模拟，但是后来发现用拼接的方法简单、粗暴又迅速，一行代码就可以解决~瞬间觉得智商低下= =

由于每次旋转操作都是将最左侧字符移动到最右侧，因此如果 goal 可由 s 经过多步旋转而来，那么 goal 必然会出现在 s + s 中，即满足 (s + s).contains(goal)，同时为了 s 本身过长导致的结果成立，我们需要先确保两字符串长度相等。

1
2
3
4
5
class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length()==goal.length()&&(s+s).contains(goal);
    }
}

357. 统计各位数字都不同的数字个数

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。

1
2
3
输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。

思路1：暴力遍历+哈希

最开始的思路是两层for循环，一层遍历所有数，一层来判断当前数是否含有重复数字，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        int number = 0;
        tab: for(int i = 0;i< Math.pow(10,n);i++){
            String temp = String.valueOf(i);
            Map<Character,Integer> map = new HashMap<Character,Integer>();
            for(int j = 0;j < temp.length();j++){
                if(map.containsKey(temp.charAt(j))){
                    continue tab;
                }else{
                    map.put(temp.charAt(j),j);
                }
            }
            number++;
        }
        return number;
    }
}

最后得出的结果，逻辑没问题，但时间超出了限制。。。在意料之中

正确思路：乘法原理

对于 n = 0的情况较为特殊，特判一下，返回 1。

对于其他情况，由于不能含有前导 0，最高位可选择的数值个数为 9，而从次高位开始到最低位，可选的个数从 9 开始逐一递减。

利用乘法原理，每位数可选的数值个数相乘即是长度为 n 的数的可能方案数 cur，而所有长度[1,n]的方案数累加即是答案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        int ans = 10;
        for(int i = 2 , last = 9 ; i <= n ;i++){
            int cur = last*(10-i+1);
            ans += cur;
            last = cur;
        }
        return ans;
    }
}
  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：38.1 MB, 在所有 Java 提交中击败了51.14%的用户
  • 通过测试用例：9 / 9

这个题发现：刷题不是简单的模拟，还要找规律，看下能否用上数学思想= =

806. 写字符串需要的行数

我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 ‘a’ 需要的单位， widths[1] 代表 ‘b’ 需要的单位，…， widths[25] 代表 ‘z’ 需要的单位。

现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。

示例 1:
输入:
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = “abcdefghijklmnopqrstuvwxyz”
输出: [3, 60]
解释:
所有的字符拥有相同的占用单位10。所以书写所有的26个字母，
我们需要2个整行和占用60个单位的一行。

思路1：哈希表

首先将26个字母的单位存入哈希表中，然后遍历读取字符串的时候从哈希表中get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int row = 1 , column = 0;
        int len = s.length();
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(int i = 0 ; i< 26 ; i++){
           
            map.put((char)('a'+i),widths[i]);
        }
        int sum = 0;
        for(int j = 0;j < len;j++){
            sum += map.get(s.charAt(j));
            while(sum > 100){
                sum = map.get(s.charAt(j));
                row++;
            }
            column = sum;
        }
        return new int[]{row,column};
    }
}
  • 执行用时：1 ms, 在所有 Java 提交中击败了19.23%的用户
  • 内存消耗：39.7 MB, 在所有 Java 提交中击败了22.88%的用户
  • 通过测试用例：27 / 27

时间复杂度有点高

思路2：直接模拟

似乎之前的想法太复杂了= = 。根本没必要用到哈希表，直接用数组即可表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int lines = 1 , width =0;
        for(int i = 0 ; i<s.length(); i++){
            int sum = widths[s.charAt(i)-'a'];
            width += sum;
            if(width > 100){
                lines++;
                width = sum;
            }
        }
        return new int[]{lines,width};
    }
}
  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户，O(n)
  • 内存消耗：39.4 MB, 在所有 Java 提交中击败了55.26%的用户，O(1)
  • 通过测试用例：27 / 27

386. 字典序排数

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

1
2
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

思路1：深度优先搜索

对于一个整数curr，它的下一个字典序整数对应下面的规则：

  • 尝试在curr后面附加一个零，即curr x 10，如果curr x 10 < n，那么说明curr x 10是下一个字典序 整数；
  • 如果curr % 10 == 9 || curr == n，那么说明末尾的数位已经搜索完成，退回上一位，然后继续判断直到curr % 10 == 9 || curr == n为止，那么curr+1是下一个字典序整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>();
        for(int i = 0 ,curr = 1; i< n;i++){
            ans.add(curr);
            if(curr*10 <= n){
                curr *= 10;
            }else{
                while(curr % 10 == 9 || curr == n){
                    curr /= 10;
                }
                curr++;
            }
        }
        return ans;
    }
}

883. 三维形体投影面积

在 n x n 的网格 grid 中，我们放置了一些与 x，y，z 三轴对齐的 1 x 1 x 1 立方体。

每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。

现在，我们查看这些立方体在 xy 、yz 和 zx 平面上的投影。

投影 就像影子，将 三维 形体映射到一个 二维 平面上。从顶部、前面和侧面看立方体时，我们会看到“影子”。

返回 所有三个投影的总面积 。

思路：直接模拟

根据题意，\texttt{x}x 轴对应行，\texttt{y}y 轴对应列，\texttt{z}z 轴对应网格的数值。

因此：

  • xy 平面的投影面积等于网格上非零数值的数目；

  • yz 平面的投影面积等于网格上每一列最大数值之和；

  • zx 平面的投影面积等于网格上每一行最大数值之和。

返回上述三个投影面积之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int projectionArea(int[][] grid) {
        int ans1 = 0,ans2 = 0,ans3 = 0;
        int n = grid.length;
        for(int i = 0 ; i < n; i++){
            int a = 0 , b = 0;
            for(int j = 0 ; j < n ;j++){
                if(grid[i][j]>0)
                    ans1++;
                a = Math.max(a,grid[i][j]);
                b = Math.max(b,grid[j][i]);
            }
        ans2 += a;
        ans3 += b;
        }
        return ans1+ans2+ans3;
    }
}
  • 执行用时：2 ms, 在所有 Java 提交中击败了69.63%的用户,O(n2)
  • 内存消耗：41.2 MB, 在所有 Java 提交中击败了36.20%的用户,O(1)
  • 通过测试用例：90 / 90

905. 按奇偶排序数组

思路1：直接模拟

定义两个指针，一个left，一个right，创建一个相同大小数组，遍历nums的每一个值，如果为偶数则赋给新数组的左边，如果为奇数则赋给新数组的右边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        int a = 0 , b = len-1;
        for(int i = 0 ; i < len ; i++){
            if(nums[i]%2 == 0){
                ans[a] = nums[i];
                a += 1;
            }else{
                ans[b] = nums[i];
                b -= 1;
            }
        }
        return ans;
    }
}
  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户，O（n）
  • 内存消耗：42.5 MB, 在所有 Java 提交中击败了9.86%的用户，O（1）
  • 通过测试用例：285 / 285

思路2：简化，直接交换

使用指针 ii和 j 分别代表未处理区间的左右端点，当 nums[i] 不为偶数时，将 i 和 j 两个位置互换，原有位置 j 边是奇数（已处理好），让 j 自减左移，但原有位置 i 交换后不确保是偶数，需要再次检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int n = nums.length;
        for(int i = 0 , j = n-1; i<j ; i++){
            if(nums[i] % 2 ==1){
                int temp = nums[j];
                nums[j--] = nums[i];
                nums[i--] = temp;
            }
        }
        return nums;
    }
}
  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户，O（n）
  • 内存消耗：42.4 MB, 在所有 Java 提交中击败了27.43%的用户，O（1）
  • 通过测试用例：285 / 285

实际上一个数组空间的提升，似乎很小~

908. 最小差值 I

给你一个整数数组 nums，和一个整数 k 。

在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的整数。对于每个索引 i ，最多 只能 应用 一次 此操作。

nums 的 分数 是 nums 中最大和最小元素的差值。

在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。

1
2
3
输入：nums = [1], k = 0
输出：0
解释：分数是 max(nums) - min(nums) = 1 - 1 = 0。

思路：数学

假设数组的最大值为maxVlue，最小值为minValue，则以下两种情况即可涵盖所有情景：

  • maxValue - minValue <= 2*k，那么我们总可以将整数数组 nums 的所有元素都改为同一个整数，因此更改后的整数数组 nums 的最低分数为 0。
  • maxValue - minValue > 2k，那么更改后的整数数组 nums 的最低分数为maxValue - minValue - 2k 。
1
2
3
4
5
6
7
class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int minValue = Arrays.stream(nums).min().getAsInt();
        int maxValue = Arrays.stream(nums).max().getAsInt();
        return maxValue-minValue <= 2*k?0:maxValue-minValue-2*k;
    }
}