8000 8 nov · khemssharma/leetcode@4e38427 · GitHub
[go: up one dir, main page]
Skip to content

Commit 4e38427

Browse files
khemssharmakhemssharma
committed
8 nov
1 parent 0bffc19 commit 4e38427

File tree

2 files changed

+216
-40
lines changed

2 files changed

+216
-40
lines changed

‎Blind 75

Lines changed: 187 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,50 +1,50 @@
1-
class ArrayAndHashmap{
2-
containsDuplicate = function(nums) {
1+
class ArrayAndHashmap {
2+
containsDuplicate = function (nums) {
33
const map = new Map()
4-
for (let char of nums){
5-
map.set(char, (map.get(char)||0)+1)
4+
for (let char of nums) {
5+
map.set(char, (map.get(char) || 0) + 1)
66
}
7-
for (let [key, value] of map){
8-
if (value>1)return true
7+
for (let [key, value] of map) {
8+
if (value > 1) return true
99
}
1010
return false;
1111
};
1212

13-
isAnagram = function(s, t) {
14-
if (s.length !== t.length)return false
13+
isAnagram = function (s, t) {
14+
if (s.length !== t.length) return false
1515
let map = new Map()
16-
for (let char of s){
17-
map.set(char, (map.get(char)||0)+1);
18-
}//you have map now compare with t
19-
for (let char of t){
20-
if (!map.has(char))return false
21-
map.set(char, map.get(char)-1);
22-
if (map.get(char)===0)map.delete(char)
23-
}
24-
return map.size===0
16+
for (let char of s) {
17+
map.set(char, (map.get(char) || 0) + 1);
18+
} //you have map now compare with t
19+
for (let char of t) {
20+
if (!map.has(char)) return false
21+
map.set(char, map.get(char) - 1);
22+
if (map.get(char) === 0) map.delete(char)
23+
}
24+
return map.size === 0
2525
};
2626

2727
twoSum = function (nums, target) { // Find two numbers which are two-sum of target in nums
28-
const map = new Map(); // create a new map
29-
for (let i = 0; i < nums.length; i++) { // now iterate over nums
30-
const complement = target - nums[i] // find complement of target to current
31-
if (map.has(complement)) { // if there's complement in map
32-
return [map.get(complement), i] // return complement and current index
28+
const map = new Map(); // create a new map
29+
for (let i = 0; i < nums.length; i++) { // now iterate over nums
30+
const complement = target - nums[i] // find complement of target to current
31+
if (map.has(complement)) { // if there's complement in map
32+
return [map.get(complement), i] // return complement and current index
33+
}
34+
map.set(nums[i], i) // map current number to current index otherwise
3335
}
34-
map.set(nums[i], i) // map current number to current index otherwise
35-
}
3636
};
3737

38-
groupAnagrams = function(strs) {
38+
groupAnagrams = function (strs) {
3939
const map = new Map()
40-
for (let str of strs){
40+
for (let str of strs) {
4141
const sorted = str.split('').sort().join('')
4242
if (!map.has(sorted)) map.set(sorted, [])
4343
map.get(sorted).push(str)
4444
}
4545
return Array.from(map.values())
4646
};
47-
47+
4848
topKFrequent = function (nums, k) {
4949
const frequencyMap = new Map()
5050
const buckets = Array.from({ // bucket sort
@@ -57,7 +57,7 @@ class ArrayAndHashmap{
5757
for (const [num, freq] of frequencyMap.entries()) {
5858
buckets[freq].push(num)
5959
}
60-
for (let i = buckets.length-1; i >= 0; i--) {
60+
for (let i = buckets.length - 1; i >= 0; i--) {
6161
for (const num of buckets[i]) {
6262
result.push(num)
6363
if (result.length === k) {
@@ -67,15 +67,16 @@ class ArrayAndHashmap{
6767
}
6868
return result
6969
}
70-
71-
EncodeDecode = function() { // Encode and decode string
70+
71+
EncodeDecode = function () { // Encode and decode string
7272
function encode(strs) {
7373
let encoded = ''
7474
for (let str of strs) {
7575
encoded += str.length + "#" + str
7676
}
7777
return encoded;
7878
}
79+
7980
function decode(str) {
8081
let decoded = []
8182
let i = 0;
@@ -89,7 +90,7 @@ class ArrayAndHashmap{
8990
return decoded
9091
}
9192
}
92-
93+
9394
productExceptSelf(nums) {
9495
const n = nums.length;
9596
const result = Array(n).fill(1)
@@ -105,7 +106,7 @@ class ArrayAndHashmap{
105106
}
106107
return result
107108
}
108-
109+
109110
longestConsecutive = function (nums) { // longest coonsecutive subsequence
110111
if (nums.length === 0) return 0
111112
let longest = 0;
@@ -125,12 +126,12 @@ class ArrayAndHashmap{
125126
};
126127
}
127128

128-
class Twopointer{
129+
class Twopointer {
129130
isPalindrome = function (s) { // Check if a string is a palindrome
130131
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
131132
return cleaned === cleaned.split('').reverse().join('');
132133
};
133-
134+
134135
threeSum = function (nums) {
135136
const result = []; // result
136137
nums.sort((a, b) => a - b) // sort the array
@@ -171,19 +172,19 @@ class Twopointer{
171172
};
172173
}
173174

174-
class SlidingWindow{
175-
maxProfit = function(prices) { // Best time to buy and sell stocks
175+
class SlidingWindow {
176+
maxProfit = function (prices) { // Best time to buy and sell stocks
176177
let maxProfit = 0;
177178
let minPrice = Infinity;
178-
for (let price of prices){
179+
for (let price of prices) {
179180
minPrice = Math.min(minPrice, price);
180181
const profit = price - minPrice;
181182
maxProfit = Math.max(maxProfit, profit);
182183
}
183184
return maxProfit;
184185
};
185-
186-
lengthOfLongestSubstring = function (s) {
186+
187+
lengthOfLongestSubstring = function (s) { // without repeating characters
187188
let left = 0;
188189
let max_length = 0;
189190
const map = new Map();
@@ -196,5 +197,151 @@ class SlidingWindow{
196197
max_length = Math.max(max_length, right - left + 1)
197198
}
198199
return max_length;
199-
};
200+
};
201+
202+
characterReplacement = function(s, k) { //Longest repeating character replacement
203+
let left = 0, freq = {}, maxFrequency = 0, maxLength = 0;
204+
for (let right = 0; right < s.length; right++){
205+
const char = s[right];
206+
freq[char] = (freq[char] || 0)+1
207+
maxFrequency = Math.max(maxFrequency, freq[char])
208+
while ((right-left+1)-maxFrequency > k) {
209+
freq[s[left]]--
210+
left++
211+
}
212+
maxLength = Math.max(maxLength, right-left+1)
213+
}
214+
return maxLength
215+
};
216+
217+
minWindow(s, t) { // minimum window substring
218+
if (s.length < t.length) return "";
219+
220+
const requiredChars = new Map();
221+
for (const char of t) {
222+
requiredChars.set(char, (requiredChars.get(char) || 0) + 1);
223+
}
224+
225+
let left = 0;
226+
let right = 0;
227+
let formed = 0;
228+
const windowCounts = new Map();
229+
const required = requiredChars.size;
230+
231+
let minLength = Infinity;
232+
let minWindowStart = 0;
233+
234+
while (right < s.length) {
235+
const char = s[right];
236+
windowCounts.set(char, (windowCounts.get(char) || 0) + 1);
237+
238+
if (requiredChars.has(char) && windowCounts.get(char) === requiredChars.get(char)) {
239+
formed += 1;
240+
}
241+
242+
while (left <= right && formed === required) {
243+
if (right - left + 1 < minLength) {
244+
minLength = right - left + 1;
245+
minWindowStart = left;
246+
}
247+
248+
const leftChar = s[left];
249+
windowCounts.set(leftChar, windowCounts.get(leftChar) - 1);
250+
251+
if (requiredChars.has(leftChar) && windowCounts.get(leftChar) < requiredChars.get(leftChar)) {
252+
formed -= 1;
253+
}
254+
left += 1;
255+
}
256+
right += 1;
257+
}
258+
259+
return minLength === Infinity ? "" : s.slice(minWindowStart, minWindowStart + minLength);
260+
}
261+
}
262+
263+
class Stack {
264+
isValid(s) { // valid parantheses
265+
const stack = [];
266+
const map = {
267+
')': '(',
268+
'}': '{',
269+
']': '['
270+
};
271+
272+
for (let char of s) {
273+
if (char === '(' || char === '{' || char === '[') { // Push opening brackets onto the stack
274+
stack.push(char);
275+
} else { // If the stack is empty or the top of the stack does not match the current closing bracket, return false
276+
if (stack.length === 0 || stack.pop() !== map[char]) {
277+
return false;
278+
}
279+
}
280+
}
281+
282+
return stack.length === 0; // If the stack is empty at the end, all parentheses are closed properly
283+
}
284+
}
285+
286+
class BinarySearch{
287+
findMin(nums) { // find minimum in rotated sorted array
288+
let left = 0;
289+
let right = nums.length - 1;
290+
291+
if (nums[left] < nums[right] || nums.length === 1) { // If the array is not rotated or has one element, return the first element
292+
return nums[left];
293+
}
294+
295+
while (left <= right) {
296+
let mid = Math.floor((left + right) / 2);
297+
298+
if (nums[mid] > nums[mid + 1]) { // Check if mid element is the smallest
299+
return nums[mid + 1];
300+
}
301+
302+
if (nums[mid - 1] > nums[mid]) { // Check if the element before mid is the smallest
303+
return nums[mid];
304+
}
305+
306+
if (nums[mid] > nums[left]) { // Adjust search range
307+
left = mid + 1;
308+
} else {
309+
right = mid - 1;
310+
}
311+
}
312+
}
313+
314+
search(nums, target) { // search in rotated sorted array
315+
let left = 0;
316+
let right = nums.length - 1;
317+
318+
while (left <= right) {
319+
let mid = Math.floor((left + right) / 2);
320+
321+
if (nums[mid] === target) { // Check if the target is found at the mid index
322+
return mid;
323+
}
324+
325+
if (nums[left] <= nums[mid]) { // If the left part is sorted
326+
if (target >= nums[left] && target < nums[mid]) { // Check if target is in the left part
327+
right = mid - 1; // Target is in the left part
328+
} else {
329+
left = mid + 1; // Target is in the right part
330+
}
331+
}
332+
else { // If the right part is sorted
333+
if (target > nums[mid] && target <= nums[right]) { // Check if target is in the right part
334+
left = mid + 1; // Target is in the right part
335+
} else {
336+
right = mid - 1; // Target is in the left part
337+
}
338+
}
339+
}
340+
341+
return -1; // Target not found
342+
}
343+
}
344+
345+
class LinkedList{
346+
200347
}

‎Python/nQueens.py

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
def solveNQueens(n):
2+
def backtrack(row, cols, diagonals1, diagonals2, board):
3+
if row == n:
4+
result.appe C74E nd(["".join(row) for row in board])
5+
return
6+
7+
for col in range(n):
8+
if col in cols or (row - col) in diagonals1 or (row + col) in diagonals2:
9+
continue
10+
11+
# Choose
12+
board[row][col] = 'Q'
13+
cols.add(col)
14+
diagonals1.add(row - col)
15+
diagonals2.add(row + col)
16+
17+
# Explore
18+
backtrack(row + 1, cols, diagonals1, diagonals2, board)
19+
20+
# Un-choose
21+
board[row][col] = '.'
22+
cols.remove(col)
23+
diagonals1.remove(row - col)
24+
diagonals2.remove(row + col)
25+
26+
result = []
27+
board = [["."] * n for _ in range(n)]
28+
backtrack(0, set(), set(), set(), board)
29+
return result

0 commit comments

Comments
 (0)
0