FlareBall's Blog
0%

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;
    }
}

Posted on Edited on In ,

贪心

时间复杂度$O(n)$

空间复杂度$O(1)$

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0, preMin = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            ans = Math.max(ans, prices[i] - preMin);
            preMin = Math.min(preMin, prices[i]);
        }
        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
17
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}