☻Blog("Laziji")

System.out.print("辣子鸡的博客");

发表于 更新于 分类于

题目地址

https://leetcode-cn.com/problems/jump-game-ii/

解题

题目咋一看可以用动态规划来做, 第i个位置到终点的位置f(i) = min(f(i+1),f(i+2)...f(k)) + 1 其中f(n-1) = 0, i 从 n-2 -> 0。这样的时间复杂度O(N^2), 数据量一大就不行了, 例如: [9999,9999,....9999]十万个9999
不过只要稍微优化一下就能达到很好的效果, 上面的解法很多时间是花在求[i,k]区间内的最小值, 这里我们可以利用线段树高效求解, 线段树每次插入, 查询花费O(logN), 优化后时间复杂度为O(NlogN) 可以轻松应对大型测试用例了

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
class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        n = len(nums)
        self.init(n)
        self.update(n-1, 0)
        for i in range(n-2, -1, -1):
            a = i + 1
            b = i + nums[i] + 1
            if b > n:
                b = n
            p = self.query(a, b, 0, 0, self.n) + 1
            self.update(i, p)

        return self.query(0, 1, 0, 0, self.n)

    def init(self, n):
        self.INT_MAX = n
        self.n = 1
        
        while self.n < n:
            self.n *= 2

        self.dat = [self.INT_MAX for i in range(2 * self.n - 1)]

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1],self.dat[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.INT_MAX

        if a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)

print(Solution().jump([2, 3, 1, 1, 4]))

发表于 更新于 分类于

题目地址

https://leetcode-cn.com/problems/trapping-rain-water/

解题

把柱子按高度分成不同组, 从高到低开始取, 每组取完后计算hi hn(下一组的高度)之间存在多少块水, 数量为(maxi - mini + 1 - (i + 1)) * (hi - hn), 其中i从0开始, maxi - mini + 1表示宽度, i+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:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        ihs = [(i,height[i]) for i in range(len(height))]
        ihs.sort(key = lambda x : x[1], reverse = True)
        ans = 0
        maxi = -1
        mini = -1
        for i in range(len(ihs)):
            idx, h = ihs[i]
            if maxi == -1 or idx>maxi:
                maxi = idx
            if mini == -1 or idx<mini:
                mini = idx
            
            dh = 0
            if i == len(ihs)-1:
                dh = 1
            else:
                dh = h - ihs[i+1][1]
            if dh:
                ans += (maxi - mini - i) * dh
        
        return ans


print(Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1]))
0%