Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Added tasks 172-191#60

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
javadev merged 1 commit intoLeetCode-in-Python:mainfromThanhNIT:tasks-172-191
Sep 14, 2025
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
19 changes: 19 additions & 0 deletionsREADME.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -298,6 +298,7 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
|-|-|-|-|-|-
| 0108 |[Convert Sorted Array to Binary Search Tree](src/main/python/g0101_0200/s0108_convert_sorted_array_to_binary_search_tree/Solution0108.py)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Tree, Binary_Tree, Binary_Search_Tree, Divide_and_Conquer | 0 | 100.00
| 0230 |[Kth Smallest Element in a BST](src/main/python/g0201_0300/s0230_kth_smallest_element_in_a_bst/Solution0230.py)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
| 0173 |[Binary Search Tree Iterator](src/main/python/g0101_0200/s0173_binary_search_tree_iterator/Solution0173.py)| Medium | Tree, Binary_Tree, Stack, Design, Binary_Search_Tree, Iterator | 2 | 92.39

#### Day 10 Graph/BFS/DFS

Expand DownExpand Up@@ -377,6 +378,7 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
| 0136 |[Single Number](src/main/python/g0101_0200/s0136_single_number/Solution0136.py)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, LeetCode_75_Bit_Manipulation, Big_O_Time_O(N)_Space_O(1) | 0 | 100.00
| 0007 |[Reverse Integer](src/main/python/g0001_0100/s0007_reverse_integer/Solution0007.py)| Medium | Top_Interview_Questions, Math, Big_O_Time_O(log10(x))_Space_O(1) | 37 | 69.51
| 0009 |[Palindrome Number](src/main/python/g0001_0100/s0009_palindrome_number/Solution0009.py)| Easy | Math, Big_O_Time_O(log10(x))_Space_O(1) | 4 | 80.28
| 0172 |[Factorial Trailing Zeroes](src/main/python/g0101_0200/s0172_factorial_trailing_zeroes/Solution0172.py)| Medium | Top_Interview_Questions, Math | 0 | 100.00

#### Udemy Strings

Expand DownExpand Up@@ -521,6 +523,8 @@ Python-based LeetCode algorithm problem solutions, regularly updated.

| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
|-|-|-|-|-|-
| 0191 |[Number of 1 Bits](src/main/python/g0101_0200/s0191_number_of_1_bits/Solution0191.py)| Easy | Top_Interview_Questions, Bit_Manipulation | 0 | 100.00
| 0190 |[Reverse Bits](src/main/python/g0101_0200/s0190_reverse_bits/Solution0190.py)| Easy | Top_Interview_Questions, Bit_Manipulation, Divide_and_Conquer | 36 | 75.17
| 0338 |[Counting Bits](src/main/python/g0301_0400/s0338_counting_bits/Solution0338.py)| Easy | Dynamic_Programming, Bit_Manipulation, LeetCode_75_Bit_Manipulation, Big_O_Time_O(num)_Space_O(num) | 3 | 94.51

#### Udemy Design
Expand DownExpand Up@@ -639,6 +643,7 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
| 0112 |[Path Sum](src/main/python/g0101_0200/s0112_path_sum/Solution0112.py)| Easy | Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree | 0 | 100.00
| 0129 |[Sum Root to Leaf Numbers](src/main/python/g0101_0200/s0129_sum_root_to_leaf_numbers/Solution0129.py)| Medium | Depth_First_Search, Tree, Binary_Tree | 0 | 100.00
| 0124 |[Binary Tree Maximum Path Sum](src/main/python/g0101_0200/s0124_binary_tree_maximum_path_sum/Solution0124.py)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Dynamic_Programming, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(N)_Space_O(N) | 11 | 91.40
| 0173 |[Binary Search Tree Iterator](src/main/python/g0101_0200/s0173_binary_search_tree_iterator/Solution0173.py)| Medium | Tree, Binary_Tree, Stack, Design, Binary_Search_Tree, Iterator | 2 | 92.39
| 0236 |[Lowest Common Ancestor of a Binary Tree](src/main/python/g0201_0300/s0236_lowest_common_ancestor_of_a_binary_tree/Solution0236.py)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, LeetCode_75_Binary_Tree/DFS, Big_O_Time_O(n)_Space_O(n) | 41 | 97.74

#### Top Interview 150 Binary Tree BFS
Expand DownExpand Up@@ -725,6 +730,8 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
|-|-|-|-|-|-
| 0067 |[Add Binary](src/main/python/g0001_0100/s0067_add_binary/Solution0067.py)| Easy | String, Math, Bit_Manipulation, Simulation | 0 | 100.00
| 0190 |[Reverse Bits](src/main/python/g0101_0200/s0190_reverse_bits/Solution0190.py)| Easy | Top_Interview_Questions, Bit_Manipulation, Divide_and_Conquer | 36 | 75.17
| 0191 |[Number of 1 Bits](src/main/python/g0101_0200/s0191_number_of_1_bits/Solution0191.py)| Easy | Top_Interview_Questions, Bit_Manipulation | 0 | 100.00
| 0136 |[Single Number](src/main/python/g0101_0200/s0136_single_number/Solution0136.py)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, LeetCode_75_Bit_Manipulation, Big_O_Time_O(N)_Space_O(1) | 0 | 100.00
| 0137 |[Single Number II](src/main/python/g0101_0200/s0137_single_number_ii/Solution0137.py)| Medium | Array, Bit_Manipulation | 0 | 100.00

Expand All@@ -734,6 +741,7 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
|-|-|-|-|-|-
| 0009 |[Palindrome Number](src/main/python/g0001_0100/s0009_palindrome_number/Solution0009.py)| Easy | Math, Big_O_Time_O(log10(x))_Space_O(1) | 4 | 80.28
| 0066 |[Plus One](src/main/python/g0001_0100/s0066_plus_one/Solution0066.py)| Easy | Top_Interview_Questions, Array, Math | 0 | 100.00
| 0172 |[Factorial Trailing Zeroes](src/main/python/g0101_0200/s0172_factorial_trailing_zeroes/Solution0172.py)| Medium | Top_Interview_Questions, Math | 0 | 100.00

#### Top Interview 150 1D DP

Expand All@@ -756,6 +764,7 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
| 0097 |[Interleaving String](src/main/python/g0001_0100/s0097_interleaving_string/Solution0097.py)| Medium | String, Dynamic_Programming | 37 | 90.93
| 0072 |[Edit Distance](src/main/python/g0001_0100/s0072_edit_distance/Solution0072.py)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, LeetCode_75_DP/Multidimensional, Big_O_Time_O(n^2)_Space_O(n2) | 23 | 98.84
| 0123 |[Best Time to Buy and Sell Stock III](src/main/python/g0101_0200/s0123_best_time_to_buy_and_sell_stock_iii/Solution0123.py)| Hard | Array, Dynamic_Programming | 232 | 75.22
| 0188 |[Best Time to Buy and Sell Stock IV](src/main/python/g0101_0200/s0188_best_time_to_buy_and_sell_stock_iv/Solution.java)| Hard | Array, Dynamic_Programming | 1 | 99.73
| 0221 |[Maximal Square](src/main/python/g0201_0300/s0221_maximal_square/Solution0221.py)| Medium | Array, Dynamic_Programming, Matrix, Big_O_Time_O(m\*n)_Space_O(m\*n) | 129 | 64.49

### Data Structure I
Expand DownExpand Up@@ -956,6 +965,7 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
|-|-|-|-|-|-
| 0230 |[Kth Smallest Element in a BST](src/main/python/g0201_0300/s0230_kth_smallest_element_in_a_bst/Solution0230.py)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
| 0173 |[Binary Search Tree Iterator](src/main/python/g0101_0200/s0173_binary_search_tree_iterator/Solution0173.py)| Medium | Tree, Binary_Tree, Stack, Design, Binary_Search_Tree, Iterator | 2 | 92.39

#### Day 18 Tree

Expand DownExpand Up@@ -1059,11 +1069,13 @@ Python-based LeetCode algorithm problem solutions, regularly updated.

| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
|-|-|-|-|-|-
| 0191 |[Number of 1 Bits](src/main/python/g0101_0200/s0191_number_of_1_bits/Solution0191.py)| Easy | Top_Interview_Questions, Bit_Manipulation | 0 | 100.00

#### Day 14 Bit Manipulation

| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
|-|-|-|-|-|-
| 0190 |[Reverse Bits](src/main/python/g0101_0200/s0190_reverse_bits/Solution0190.py)| Easy | Top_Interview_Questions, Bit_Manipulation, Divide_and_Conquer | 36 | 75.17
| 0136 |[Single Number](src/main/python/g0101_0200/s0136_single_number/Solution0136.py)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, LeetCode_75_Bit_Manipulation, Big_O_Time_O(N)_Space_O(1) | 0 | 100.00

### Algorithm II
Expand DownExpand Up@@ -1512,6 +1524,7 @@ Python-based LeetCode algorithm problem solutions, regularly updated.

| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
|-|-|-|-|-|-
| 0191 |[Number of 1 Bits](src/main/python/g0101_0200/s0191_number_of_1_bits/Solution0191.py)| Easy | Top_Interview_Questions, Bit_Manipulation | 0 | 100.00

#### Day 3 Conditional Statements

Expand DownExpand Up@@ -1659,6 +1672,7 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
| <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
|-|-|-|-|-|-
| 0061 |[Rotate List](src/main/python/g0001_0100/s0061_rotate_list/Solution0061.py)| Medium | Two_Pointers, Linked_List | 0 | 100.00
| 0173 |[Binary Search Tree Iterator](src/main/python/g0101_0200/s0173_binary_search_tree_iterator/Solution0173.py)| Medium | Tree, Binary_Tree, Stack, Design, Binary_Search_Tree, Iterator | 2 | 92.39

#### Day 17

Expand DownExpand Up@@ -1717,7 +1731,12 @@ Python-based LeetCode algorithm problem solutions, regularly updated.
| 0206 |[Reverse Linked List](src/main/python/g0201_0300/s0206_reverse_linked_list/Solution0206.py)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Linked_List, Recursion, LeetCode_75_LinkedList, Data_Structure_I_Day_8_Linked_List, Algorithm_I_Day_10_Recursion_Backtracking, Level_1_Day_3_Linked_List, Udemy_Linked_List, Big_O_Time_O(N)_Space_O(1) | 0 | 100.00
| 0200 |[Number of Islands](src/main/python/g0101_0200/s0200_number_of_islands/Solution0200.py)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Depth_First_Search, Breadth_First_Search, Matrix, Union_Find, Algorithm_II_Day_6_Breadth_First_Search_Depth_First_Search, Graph_Theory_I_Day_1_Matrix_Related_Problems, Level_1_Day_9_Graph/BFS/DFS, Udemy_Graph, Top_Interview_150_Graph_General, Big_O_Time_O(M\*N)_Space_O(M\*N) | 234 | 82.73
| 0198 |[House Robber](src/main/python/g0101_0200/s0198_house_robber/Solution0198.py)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Dynamic_Programming, LeetCode_75_DP/1D, Algorithm_I_Day_12_Dynamic_Programming, Dynamic_Programming_I_Day_3, Level_2_Day_12_Dynamic_Programming, Udemy_Dynamic_Programming, Top_Interview_150_1D_DP, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
| 0191 |[Number of 1 Bits](src/main/python/g0101_0200/s0191_number_of_1_bits/Solution0191.py)| Easy | Top_Interview_Questions, Bit_Manipulation, Algorithm_I_Day_13_Bit_Manipulation, Programming_Skills_I_Day_2_Operator, Udemy_Bit_Manipulation, Top_Interview_150_Bit_Manipulation | 0 | 100.00
| 0190 |[Reverse Bits](src/main/python/g0101_0200/s0190_reverse_bits/Solution0190.py)| Easy | Top_Interview_Questions, Bit_Manipulation, Divide_and_Conquer, Algorithm_I_Day_14_Bit_Manipulation, Udemy_Bit_Manipulation, Top_Interview_150_Bit_Manipulation | 36 | 75.17
| 0189 |[Rotate Array](src/main/python/g0101_0200/s0189_rotate_array/Solution0189.py)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Math, Two_Pointers, Algorithm_I_Day_2_Two_Pointers, Udemy_Arrays, Top_Interview_150_Array/String, Big_O_Time_O(n)_Space_O(1) | 3 | 74.65
| 0188 |[Best Time to Buy and Sell Stock IV](src/main/python/g0101_0200/s0188_best_time_to_buy_and_sell_stock_iv/Solution.java)| Hard | Array, Dynamic_Programming, Top_Interview_150_Multidimensional_DP | 1 | 99.73
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Fix Solution.java

| 0173 |[Binary Search Tree Iterator](src/main/python/g0101_0200/s0173_binary_search_tree_iterator/Solution0173.py)| Medium | Tree, Binary_Tree, Stack, Design, Binary_Search_Tree, Iterator, Data_Structure_II_Day_17_Tree, Programming_Skills_II_Day_16, Level_2_Day_9_Binary_Search_Tree, Top_Interview_150_Binary_Tree_General | 2 | 92.39
| 0172 |[Factorial Trailing Zeroes](src/main/python/g0101_0200/s0172_factorial_trailing_zeroes/Solution0172.py)| Medium | Top_Interview_Questions, Math, Udemy_Integers, Top_Interview_150_Math | 0 | 100.00
| 0169 |[Majority Element](src/main/python/g0101_0200/s0169_majority_element/Solution0169.py)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Sorting, Counting, Divide_and_Conquer, Data_Structure_II_Day_1_Array, Udemy_Famous_Algorithm, Top_Interview_150_Array/String, Big_O_Time_O(n)_Space_O(1) | 7 | 56.72
| 0167 |[Two Sum II - Input Array Is Sorted](src/main/python/g0101_0200/s0167_two_sum_ii_input_array_is_sorted/Solution0167.py)| Medium | Array, Binary_Search, Two_Pointers, Algorithm_I_Day_3_Two_Pointers, Binary_Search_I_Day_7, Top_Interview_150_Two_Pointers | 3 | 80.89
| 0162 |[Find Peak Element](src/main/python/g0101_0200/s0162_find_peak_element/Solution0162.py)| Medium | Top_Interview_Questions, Array, Binary_Search, LeetCode_75_Binary_Search, Algorithm_II_Day_2_Binary_Search, Binary_Search_II_Day_12, Top_Interview_150_Binary_Search | 0 | 100.00
Expand Down
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
# #Medium #Top_Interview_Questions #Math #Udemy_Integers #Top_Interview_150_Math
# #2025_09_14_Time_0_ms_(100.00%)_Space_17.76_MB_(53.50%)

class Solution:
def trailingZeroes(self, n: int) -> int:
base = 5
count = 0
while n >= base:
count += n // base
base = base * 5
return count
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
import unittest
from Solution0172 import Solution

class SolutionTest(unittest.TestCase):
def test_trailingZeroes(self):
self.assertEqual(Solution().trailingZeroes(3), 0)

def test_trailingZeroes2(self):
self.assertEqual(Solution().trailingZeroes(5), 1)

def test_trailingZeroes3(self):
self.assertEqual(Solution().trailingZeroes(0), 0)
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
172\. Factorial Trailing Zeroes

Medium

Given an integer `n`, return _the number of trailing zeroes in_ `n!`.

Note that `n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1`.

**Example 1:**

**Input:** n = 3

**Output:** 0

**Explanation:** 3! = 6, no trailing zero.

**Example 2:**

**Input:** n = 5

**Output:** 1

**Explanation:** 5! = 120, one trailing zero.

**Example 3:**

**Input:** n = 0

**Output:** 0

**Constraints:**

* <code>0 <= n <= 10<sup>4</sup></code>

**Follow up:** Could you write a solution that works in logarithmic time complexity?
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
# #Medium #Tree #Binary_Tree #Stack #Design #Binary_Search_Tree #Iterator
# #Data_Structure_II_Day_17_Tree #Programming_Skills_II_Day_16 #Level_2_Day_9_Binary_Search_Tree
# #Top_Interview_150_Binary_Tree_General #2025_09_14_Time_2_ms_(92.39%)_Space_25.20_MB_(18.38%)

from typing import Optional

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self._push_left(root)

def _push_left(self, node):
# Push all left children
while node:
self.stack.append(node)
node = node.left

def next(self) -> int:
# Smallest available node
node = self.stack.pop()
# If node has a right child → push its left subtree
if node.right:
self._push_left(node.right)
return node.val

def hasNext(self) -> bool:
return len(self.stack) > 0




# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
import unittest
from Solution0173 import BSTIterator, TreeNode

class BSTIteratorTest(unittest.TestCase):
def test_iteratorBST(self):
left = TreeNode(3)
right = TreeNode(15)
right.left = TreeNode(9)
right.right = TreeNode(20)
root = TreeNode(7, left, right)
iterator = BSTIterator(root)
self.assertEqual(iterator.next(), 3)
self.assertEqual(iterator.next(), 7)
self.assertTrue(iterator.hasNext())
self.assertEqual(iterator.next(), 9)
self.assertTrue(iterator.hasNext())
self.assertEqual(iterator.next(), 15)
self.assertTrue(iterator.hasNext())
self.assertEqual(iterator.next(), 20)
self.assertFalse(iterator.hasNext())
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
173\. Binary Search Tree Iterator

Medium

Implement the `BSTIterator` class that represents an iterator over the **[in-order traversal](https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR))** of a binary search tree (BST):

* `BSTIterator(TreeNode root)` Initializes an object of the `BSTIterator` class. The `root` of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
* `boolean hasNext()` Returns `true` if there exists a number in the traversal to the right of the pointer, otherwise returns `false`.
* `int next()` Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to `next()` will return the smallest element in the BST.

You may assume that `next()` calls will always be valid. That is, there will be at least a next number in the in-order traversal when `next()` is called.

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/12/25/bst-tree.png)

**Input** ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

**Output:** [null, 3, 7, true, 9, true, 15, true, 20, false]

**Explanation:**

BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False

**Constraints:**

* The number of nodes in the tree is in the range <code>[1, 10<sup>5</sup>]</code>.
* <code>0 <= Node.val <= 10<sup>6</sup></code>
* At most <code>10<sup>5</sup></code> calls will be made to `hasNext`, and `next`.

**Follow up:**

* Could you implement `next()` and `hasNext()` to run in average `O(1)` time and use `O(h)` memory, where `h` is the height of the tree?
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
package g0101_0200.s0188_best_time_to_buy_and_sell_stock_iv;

// #Hard #Array #Dynamic_Programming #Top_Interview_150_Multidimensional_DP
// #2025_03_09_Time_1_ms_(99.73%)_Space_41.76_MB_(82.48%)

public class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
int[] dp = new int[k + 1];
int[] maxdp = new int[k + 1];
for (int i = 0; i <= k; i++) {
maxdp[i] = Integer.MIN_VALUE;
}
for (int i = 1; i <= n; i++) {
maxdp[0] = Math.max(maxdp[0], dp[0] - prices[i - 1]);
for (int j = k; j >= 1; j--) {
maxdp[j] = Math.max(maxdp[j], dp[j] - prices[i - 1]);
dp[j] = Math.max(maxdp[j - 1] + prices[i - 1], dp[j]);
}
}
return dp[k];
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
# #Hard #Array #Dynamic_Programming #Top_Interview_150_Multidimensional_DP
# #2025_09_14_Time_50_ms_(80.74%)_Space_17.88_MB_(83.54%)

from typing import List

class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
dp = [0] * (k + 1)
maxdp = [float('-inf')] * (k + 1)

for i in range(1, n + 1):
maxdp[0] = max(maxdp[0], dp[0] - prices[i - 1])
for j in range(k, 0, -1):
maxdp[j] = max(maxdp[j], dp[j] - prices[i - 1])
dp[j] = max(maxdp[j - 1] + prices[i - 1], dp[j])

return dp[k]
Loading
[8]ページ先頭
©2009-2025 Movatter.jp