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 290-918#65

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 3 commits intoLeetCode-in-Python:mainfromThanhNIT:tasks-290-392
Sep 20, 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
36 changes: 36 additions & 0 deletionsREADME.md
View file
Open in desktop

Large diffs are not rendered by default.

20 changes: 20 additions & 0 deletionssrc/main/python/g0201_0300/s0290_word_pattern/Solution0290.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
# #Easy #String #Hash_Table #Data_Structure_II_Day_7_String #Top_Interview_150_Hashmap
# #2025_09_20_Time_0_ms_(100.00%)_Space_17.99_MB_(15.86%)

from typing import Dict

class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
map: Dict[str, str] = {}
words = s.split()
if len(words) != len(pattern):
return False
for i in range(len(pattern)):
if pattern[i] not in map:
if words[i] in map.values():
return False
map[pattern[i]] = words[i]
else:
if words[i] != map[pattern[i]]:
return False
return True
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
import unittest
from Solution0290 import Solution

class SolutionTest(unittest.TestCase):
def test_wordPattern(self):
self.assertTrue(Solution().wordPattern("abba", "dog cat cat dog"))

def test_wordPattern2(self):
self.assertFalse(Solution().wordPattern("abba", "dog cat cat fish"))

def test_wordPattern3(self):
self.assertFalse(Solution().wordPattern("aaaa", "dog cat cat dog"))

def test_wordPattern4(self):
self.assertFalse(Solution().wordPattern("abba", "dog dog dog dog"))
40 changes: 40 additions & 0 deletionssrc/main/python/g0201_0300/s0290_word_pattern/readme.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
290\. Word Pattern

Easy

Given a `pattern` and a string `s`, find if `s` follows the same pattern.

Here **follow** means a full match, such that there is a bijection between a letter in `pattern` and a **non-empty** word in `s`.

**Example 1:**

**Input:** pattern = "abba", s = "dog cat cat dog"

**Output:** true

**Example 2:**

**Input:** pattern = "abba", s = "dog cat cat fish"

**Output:** false

**Example 3:**

**Input:** pattern = "aaaa", s = "dog cat cat dog"

**Output:** false

**Example 4:**

**Input:** pattern = "abba", s = "dog dog dog dog"

**Output:** false

**Constraints:**

* `1 <= pattern.length <= 300`
* `pattern` contains only lower-case English letters.
* `1 <= s.length <= 3000`
* `s` contains only lower-case English letters and spaces `' '`.
* `s` **does not contain** any leading or trailing spaces.
* All the words in `s` are separated by a **single space**.
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
# #Medium #Array #Heap_Priority_Queue #Top_Interview_150_Heap
# #2025_09_20_Time_78_ms_(92.40%)_Space_34.45_MB_(85.02%)

import heapq
from typing import List

class Solution:
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
if not nums1 or not nums2:
return []

heap = []
result = []

# Initialize heap with first k pairs from nums1 and first element of nums2
for i in range(min(len(nums1), k)):
heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))

# Extract k smallest pairs
for _ in range(min(k, len(nums1) * len(nums2))):
if not heap:
break
_, i, j = heapq.heappop(heap)
result.append([nums1[i], nums2[j]])

# Add next pair from nums2 if available
if j + 1 < len(nums2):
heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))

return result
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
import unittest
from Solution0373 import Solution

class SolutionTest(unittest.TestCase):
def test_kSmallestPairs(self):
self.assertEqual(
Solution().kSmallestPairs([1, 7, 11], [2, 4, 6], 3),
[[1, 2], [1, 4], [1, 6]]
)

def test_kSmallestPairs2(self):
self.assertEqual(
Solution().kSmallestPairs([1, 1, 2], [1, 2, 3], 2),
[[1, 1], [1, 1]]
)

def test_kSmallestPairs3(self):
self.assertEqual(
Solution().kSmallestPairs([1, 2], [3], 3),
[[1, 3], [2, 3]]
)
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
373\. Find K Pairs with Smallest Sums

Medium

You are given two integer arrays `nums1` and `nums2` sorted in **ascending order** and an integer `k`.

Define a pair `(u, v)` which consists of one element from the first array and one element from the second array.

Return _the_ `k` _pairs_ <code>(u<sub>1</sub>, v<sub>1</sub>), (u<sub>2</sub>, v<sub>2</sub>), ..., (u<sub>k</sub>, v<sub>k</sub>)</code> _with the smallest sums_.

**Example 1:**

**Input:** nums1 = [1,7,11], nums2 = [2,4,6], k = 3

**Output:** [[1,2],[1,4],[1,6]]

**Explanation:** The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

**Example 2:**

**Input:** nums1 = [1,1,2], nums2 = [1,2,3], k = 2

**Output:** [[1,1],[1,1]]

**Explanation:** The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

**Example 3:**

**Input:** nums1 = [1,2], nums2 = [3], k = 3

**Output:** [[1,3],[2,3]]

**Explanation:** All possible pairs are returned from the sequence: [1,3],[2,3]

**Constraints:**

* <code>1 <= nums1.length, nums2.length <= 10<sup>5</sup></code>
* <code>-10<sup>9</sup> <= nums1[i], nums2[i] <= 10<sup>9</sup></code>
* `nums1` and `nums2` both are sorted in **ascending order**.
* `1 <= k <= 1000`
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
# #Medium #Array #Hash_Table #Math #Design #Randomized #Programming_Skills_II_Day_20
# #Top_Interview_150_Array/String #2025_09_20_Time_90_ms_(96.69%)_Space_57.80_MB_(64.58%)

import random

class RandomizedSet:
def __init__(self):
self.map = {} # value -> index
self.list = [] # values

def insert(self, val: int) -> bool:
if val in self.map:
return False
self.map[val] = len(self.list)
self.list.append(val)
return True

def remove(self, val: int) -> bool:
if val not in self.map:
return False

# Index of element to remove
idx = self.map[val]
last_val = self.list[-1]

# Swap with last element
self.list[idx] = last_val
self.map[last_val] = idx

# Remove last element
self.list.pop()
del self.map[val]

return True

def getRandom(self) -> int:
return random.choice(self.list)

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
import unittest
from RandomizedSet0380 import RandomizedSet

class RandomizedSetTest(unittest.TestCase):
def test_randomizedSet(self):
result = []
randomized_set = None
result.append(str(randomized_set))
randomized_set = RandomizedSet()
result.append(str(randomized_set.insert(1)))
result.append(str(randomized_set.remove(2)))
result.append(str(randomized_set.insert(2)))
random_val = randomized_set.getRandom()
result.append(str(random_val))
result.append(str(randomized_set.remove(1)))
result.append(str(randomized_set.insert(2)))
result.append(str(randomized_set.getRandom()))

expected1 = ["None", "True", "False", "True", "1", "True", "False", "2"]
expected2 = ["None", "True", "False", "True", "2", "True", "False", "2"]

if random_val == 1:
self.assertEqual(result, expected1)
else:
self.assertEqual(result, expected2)
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
380\. Insert Delete GetRandom O(1)

Medium

Implement the `RandomizedSet` class:

* `RandomizedSet()` Initializes the `RandomizedSet` object.
* `bool insert(int val)` Inserts an item `val` into the set if not present. Returns `true` if the item was not present, `false` otherwise.
* `bool remove(int val)` Removes an item `val` from the set if present. Returns `true` if the item was present, `false` otherwise.
* `int getRandom()` Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the **same probability** of being returned.

You must implement the functions of the class such that each function works in **average** `O(1)` time complexity.

**Example 1:**

**Input**

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]

**Output:** [null, true, false, true, 2, true, false, 2]

**Explanation:**

RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

**Constraints:**

* <code>-2<sup>31</sup> <= val <= 2<sup>31</sup> - 1</code>
* At most `2 * `<code>10<sup>5</sup></code> calls will be made to `insert`, `remove`, and `getRandom`.
* There will be **at least one** element in the data structure when `getRandom` is called.
16 changes: 16 additions & 0 deletionssrc/main/python/g0301_0400/s0383_ransom_note/Solution0383.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
# #Easy #String #Hash_Table #Counting #Data_Structure_I_Day_6_String #Top_Interview_150_Hashmap
# #2025_09_20_Time_11_ms_(89.85%)_Space_17.93_MB_(54.38%)

class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
freq = [0] * 26
n = len(ransomNote)
for i in range(n):
freq[ord(ransomNote[i]) - 97] += 1
for i in range(len(magazine)):
if n == 0:
break
if freq[ord(magazine[i]) - 97] > 0:
n -= 1
freq[ord(magazine[i]) - 97] -= 1
return n == 0
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
import unittest
from Solution0383 import Solution

class SolutionTest(unittest.TestCase):
def test_canConstruct(self):
self.assertFalse(Solution().canConstruct("a", "b"))

def test_canConstruct2(self):
self.assertFalse(Solution().canConstruct("aa", "ab"))

def test_canConstruct3(self):
self.assertTrue(Solution().canConstruct("aa", "aab"))
30 changes: 30 additions & 0 deletionssrc/main/python/g0301_0400/s0383_ransom_note/readme.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
383\. Ransom Note

Easy

Given two stings `ransomNote` and `magazine`, return `true` if `ransomNote` can be constructed from `magazine` and `false` otherwise.

Each letter in `magazine` can only be used once in `ransomNote`.

**Example 1:**

**Input:** ransomNote = "a", magazine = "b"

**Output:** false

**Example 2:**

**Input:** ransomNote = "aa", magazine = "ab"

**Output:** false

**Example 3:**

**Input:** ransomNote = "aa", magazine = "aab"

**Output:** true

**Constraints:**

* <code>1 <= ransomNote.length, magazine.length <= 10<sup>5</sup></code>
* `ransomNote` and `magazine` consist of lowercase English letters.
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
# #Easy #String #Dynamic_Programming #Two_Pointers #LeetCode_75_Two_Pointers
# #Dynamic_Programming_I_Day_19 #Level_1_Day_2_String #Udemy_Two_Pointers
# #Top_Interview_150_Two_Pointers #2025_09_20_Time_0_ms_(100.00%)_Space_17.66_MB_(91.76%)

class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
j = 0
n = len(t)
m = len(s)
if m == 0:
return True
while j < n:
if s[i] == t[j]:
i += 1
if i == m:
return True
j += 1
return False
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
import unittest
from Solution0392 import Solution

class SolutionTest(unittest.TestCase):
def test_isSubsequence(self):
self.assertTrue(Solution().isSubsequence("abc", "ahbgdc"))

def test_isSubsequence2(self):
self.assertFalse(Solution().isSubsequence("axc", "ahbgdc"))
Loading
[8]ページ先頭
©2009-2025 Movatter.jp