FlareBall's Blog
0%

Posted on Edited on In ,

模拟

题目已经把罗马数字的规则给得很清楚了，普通情况就是把每个字符对应的数值累加，特殊情况则是六种固定的双字符组合，因此可以直接按照题意模拟转换过程。

遍历字符串时，优先判断当前位置和下一位置能否组成特殊组合，如果可以就加上对应数值并跳过下一位，否则按单个字符进行转换即可。

时间复杂度 $O(n)$

空间复杂度 $O(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
class Solution {
    private static final Map<String, Integer> map = new HashMap<>();
    static {
        map.put("IV", 4);
        map.put("IX", 9);
        map.put("XL", 40);
        map.put("XC", 90);
        map.put("CD", 400);
        map.put("CM", 900);
    }
    public int romanToInt(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i + 1 < n && map.containsKey(s.substring(i, i + 2))) {
                ans += map.get(s.substring(i, i + 2));
                i++;
            } else {
                switch (s.charAt(i)) {
                    case 'I' -> ans += 1;
                    case 'V' -> ans += 5;
                    case 'X' -> ans += 10;
                    case 'L' -> ans += 50;
                    case 'C' -> ans += 100;
                    case 'D' -> ans += 500;
                    case 'M' -> ans += 1000;
                }
            }
        }
        return ans;
    }
}

也可以不专门判断六种特殊组合，而是从规则本身出发。

如果当前字符对应的数值小于右边字符，那么它在答案中应当被减去，例如 $IV$ 中的 $I$，$IX$ 中的 $I$，$CM$ 中的 $C$。反之，如果当前字符大于等于右边字符，那么它就正常加到答案中。

这样只需要一次遍历，就能把普通情况和特殊情况统一处理掉。

时间复杂度 $O(n)$

空间复杂度 $O(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
class Solution {
    private static final Map<Character, Integer> map = new HashMap<>();
    static {
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
    }
    public int romanToInt(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; ++i) {
            int cur = map.get(s.charAt(i));
            if (i + 1 < n && cur < map.get(s.charAt(i + 1))) {
                ans -= cur;
            } else {
                ans += cur;
            }
        }
        return ans;
    }
}

Posted on Edited on In ,

前后缀最大值

对于位置 $i$ 而言，它最终能接多少雨水，取决于它左侧最高柱子和右侧最高柱子中较矮的那个，减去当前位置柱子高度。因为水位不可能超过两侧挡板中的短板。

因此可以预处理每个位置右侧的最高柱子高度，再在遍历数组时维护左侧最高柱子高度，这样就能在 $O(1)$ 时间内计算当前位置的积水量。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int trap(int[] height) {
        int ans = 0, n = height.length;
        int[] suf = new int[n];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = Math.max(suf[i + 1], height[i + 1]);  // 位置i右侧最高的高度
        }
        int pre = 0;  // 位置i左侧最高的高度
        for (int i = 0; i < n; ++i) {
            ans += Math.max(Math.min(pre, suf[i]) - height[i], 0);
            pre = Math.max(pre, height[i]);
        }
        return ans;
    }
}

双指针

也可以进一步优化空间。

接雨水的本质仍然是看当前位置两侧最大值中的较小者。设左右指针分别为 $left$ 和 $right$，同时维护左侧最大值 $pre$ 与右侧最大值 $suf$。

如果 $pre < suf$，说明此时左侧当前位置能接多少水已经可以确定，只由 $pre$ 决定；因为右侧一定存在一个不小于 $suf$ 的挡板，它比 $pre$ 更高，短板就是 $pre$。同理，如果 $pre \ge suf$，则右侧当前位置能接多少水已经可以确定，只由 $suf$ 决定。

这样每次只结算较矮一侧即可。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int trap(int[] height) {
        int ans = 0, suf = 0, pre = 0, left = 0, right = height.length - 1;
        while (left < right) {
            pre = Math.max(pre, height[left]);
            suf = Math.max(suf, height[right]);
            if (pre < suf) {
                ans += pre - height[left];
                left++;
            } else {
                ans += suf - height[right];
                right--;
            }
        }
        return ans;
    }
}

Posted on Edited on In ,

贪心

题目要求相邻的孩子较多一方那个获得更多糖果，也就是说糖果发放取决于数组走势（上升or下降），因此可以将数组分为若干相似得山峰并分组求解，每座山中从两端山脚开始糖果依次递增，最多糖果为山峰。

双向遍历，分别满足山峰大于左边和山峰大于右边即可。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                ans[i] = ans[i - 1] + 1;
            }
        }
        for(int i = n - 2; i >= 0; --i) {
            if(ratings[i] > ratings[i + 1]) {
                ans[i] = Math.max(ans[i], ans[i + 1] + 1);
            }
        }
        return Arrays.stream(ans).sum();
    }
}

也可以考虑一次遍历，考虑可能出现共享波谷，如1 4 5 2 0 1 4 5 2 中的0，他应该分应1颗糖果，如果直接统计1 4 5 2 0和 0 1 4 5 2两座山会导致0分配1颗糖果重复计算，所以事先为每人先分1颗糖果，这样在分组求解时山脚分0颗即可，避免了重复计算。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

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 candy(int[] ratings) {
        int n = ratings.length, ans = n;  // 每人先分一颗
        for (int i = 0; i < n; ++i) {
            int start = i > 0 && ratings[i - 1] < ratings[i] ? i - 1 : i;
            while (i + 1 < n && ratings[i] < ratings[i + 1]) { // 严格递增段
                i++;
            }
            int top = i;
            while (i + 1 < n && ratings[i] > ratings[i + 1]) { // 严格递减段
                i++;
            }
            int increase = top - start;  // 严格递增得步数
            int decrease = i - top;  // 严格递减得步数
            int num1 = increase * (0 + increase - 1) / 2;
            int num2 = decrease * (decrease - 1 + 0) / 2;
            ans += num1 + num2 + Math.max(increase, decrease);
        }
        return ans;
    }
}

Posted on In ,

贪心

首先，总油量 ≥ 总消耗量是存在解得充分必要条件。

证明：

设 net[i] = gas[i] - cost[i]（每个加油站的净收益）

条件1：必要性

如果总油量 < 总消耗量，即 Σnet[i] < 0

那么无论如何选择起点，总油量都不够绕一圈

必要条件成立

**条件2：充分性

假设 Σnet[i] ≥ 0，但不存在任何起点可以完成环路。

这意味着：对于每一个可能的起点 k，在绕行过程中都会在某个点出现油量不足。

假设从起点 k出发，在到达点 m时第一次出现油量不足，那么：

  • 从 k到 m的净收益总和 < 0
  • 由于总净收益 ≥ 0，那么从 m回到 k的净收益总和必须 > 0
  • 矛盾！因为如果从 m回到 k的净收益 > 0，那么从 m出发应该能够完成环路

充分条件成立

因此，只需要

  • 1 统计总油量 ≥ 总消耗量

  • 2 满足 1 的时候找到起点，实现方式为当我们发现某段路程总消耗量 ≥总油量为负时候把下一个当作起点即可

时间复杂度：$O(n)$

空间复杂度：$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length, sumGas = 0, curGas = 0, start = 0;
        for (int i = 0; i < n; ++i) {
            sumGas += gas[i] - cost[i];
            curGas += gas[i] - cost[i];
            if (curGas < 0) {
                curGas = 0;
                start = i + 1;
            }
        }
        return sumGas >= 0 ? start : -1;
    }
}

Posted on In ,

前缀和

时间复杂度：$O(n)$

空间复杂度：$O(1)$，返回值不计入返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        ans[n - 1] = 1;
        for (int i = n - 2; i >= 0; --i) {
            ans[i] = ans[i + 1] * nums[i + 1];
        };
        int pre = 1;
        for (int i = 0; i < n; ++i) {
            ans[i] *= pre;
            pre *= nums[i];
        }
        return ans;
    }
}

Posted on In ,

哈希表

题目要求插入、删除、随机删除复杂度均为$O(1)$，其中需要判断元素是否在集合中，所以查询特定值的复杂度也需要达到$O(1)$，常见数据结构中：

数据结构 插入复杂度 删除复杂度 查询特定值 随机查找
数组 末尾$O(1)$，中间与首部$O(n)$ 末尾$O(1)$，中间与首部$O(n)$ $O(n)$ 支持
列表 $O(1)$ 在已经找到节点的情况下为$O(1)$ $O(n)$ 不支持
哈希表 $O(1)$ $O(1)$ $O(1)$ 不支持

没有任何一种可以直接满足要求，所以需要组合使用。

此处选取的思路为底层用数组存储数据，支持随机查找需求，插入直接向末尾插入以实现$O(1)$复杂度，删除时交换到数组末尾来达到$O(1)$需求，哈希表采用val-index映射负责维护查询特定值所需的$O(1)$复杂度。

实现中下面的代码给数组预分配了内存并维护指向第一个可用位置的tail指针，这部分可以使用ArrayList代替。

时间复杂度：所有函数均为$O(1)$

空间复杂度：$O(n)$，$n$ 为最大元素数量

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class RandomizedSet {
    private Map<Integer, Integer> map = new HashMap<>();
    private int[] cnt = new int[200001];
    private int tail = 0;
    private Random random = new Random();
    public RandomizedSet() {

    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        map.put(val, tail);
        cnt[tail++] = val;
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int idx = map.get(val);
        if (idx != tail - 1) {
            swap(cnt, idx, tail - 1);  // 交换到数组末尾
            map.put(cnt[idx], idx);  // 末尾元素索引更新
        }
        map.remove(val);
        tail--;
        return true;
    }
    
    public int getRandom() {
        return cnt[random.nextInt(tail)];
    }

    private void swap (int[] a, int l, int r) {
        int tmp = a[l];
        a[l] = a[r];
        a[r] = tmp;
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Posted on In ,

计数排序+后缀和

时间复杂度$O(n)$

空间复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] cnt = new int[n + 1];
        for (int x : citations) {
            x = x > n ? n : x;  // 截断
            cnt[x]++;
        }
        int ans = 0, sufSum = 0;
        for (int i = n; i > 0; --i) {
            sufSum += cnt[i];
            ans = Math.max(ans, Math.min(i, sufSum));  // 引用书和论文量均不小于
        }
        return ans;
    }
}

Posted on Edited on In ,

贪心

时间复杂度$O(n)$

空间复杂度$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int jump(int[] nums) {
        int ans = 0, n = nums.length, right = 0, newRight = 0;
        for (int i = 0; i < n; ++i) {
            if (right >= n - 1) {
                break;
            }
            newRight = Math.max(newRight, i + nums[i]);
            if (i == right) {
                right = newRight;
                ans++;
            }
        }
        return ans;
    }
}

Posted on Edited on In ,

贪心

时间复杂度$O(n)$

空间复杂度$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {
        int right = 0, n = nums.length;
        for (int i = 0; i < n && i <= right; ++i) {
            right = Math.max(right, i + nums[i]);
            if (right >= n - 1) {
                break;
            }
        }
        return right >= n - 1;
    }
}

Posted on Edited on In ,

贪心

时间复杂度$O(n)$

空间复杂度$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0, pre = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            int cur = prices[i];
            if (cur > pre) {
                ans += cur - pre;
            }
            pre = cur;
        }
        return ans;
    }
}