Задача: 593. Valid Square
Сложность: medium
Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат.
Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке.
Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов).
Пример:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true
👨💻 Алгоритм:
1⃣Определите функцию для вычисления расстояния между двумя точками.
2⃣Проверьте, равны ли все стороны и диагонали для трех уникальных случаев перестановки точек.
3⃣Верните true, если хотя бы одна из проверок проходит.
😎 Решение:
var dist = function(p1, p2) {
return (p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2;
};
var check = function(p1, p2, p3, p4) {
return dist(p1, p2) > 0 &&
dist(p1, p2) === dist(p2, p3) &&
dist(p2, p3) === dist(p3, p4) &&
dist(p3, p4) === dist(p4, p1) &&
dist(p1, p3) === dist(p2, p4);
Сложность: medium
Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат.
Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке.
Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов).
Пример:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true
👨💻 Алгоритм:
1⃣Определите функцию для вычисления расстояния между двумя точками.
2⃣Проверьте, равны ли все стороны и диагонали для трех уникальных случаев перестановки точек.
3⃣Верните true, если хотя бы одна из проверок проходит.
😎 Решение:
var dist = function(p1, p2) {
return (p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2;
};
var check = function(p1, p2, p3, p4) {
return dist(p1, p2) > 0 &&
dist(p1, p2) === dist(p2, p3) &&
dist(p2, p3) === dist(p3, p4) &&
dist(p3, p4) === dist(p4, p1) &&
dist(p1, p3) === dist(p2, p4);
Задача: 291. Word Pattern II
Сложность: medium
Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.
Пример:
Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"
👨💻 Алгоритм:
1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.
2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.
3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `
😎 Решение:
class Solution {
wordPatternMatch(pattern, s) {
const symbolMap = new Map();
const wordSet = new Set();
return this.isMatch(s, 0, pattern, 0, symbolMap, wordSet);
}
isMatch(s, sIndex, pattern, pIndex, symbolMap, wordSet) {
if (pIndex
if (pIndex === pattern.length) {
return sIndex === s.length;
}
const symbol = pattern[pIndex];
if (symbolMap.has(symbol)) {
const word = symbolMap.get(symbol);
if (!s.startsWith(word, sIndex)) {
return false;
}
return this.isMatch(s, sIndex + word.length, pattern, pIndex + 1, symbolMap, wordSet);
}
for (let k = sIndex + 1; k <= s.length; k++) {
const newWord = s.substring(sIndex, k);
if (wordSet.has(newWord)) {
continue;
}
symbolMap.set(symbol, newWord);
wordSet.add(newWord);
if (this.isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
return true;
}
symbolMap.delete(symbol);
wordSet.delete(newWord);
}
return false;
}
}
JavaScript // чат
Сложность: medium
Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.
Пример:
Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"
👨💻 Алгоритм:
1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.
2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.
3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `
😎 Решение:
class Solution {
wordPatternMatch(pattern, s) {
const symbolMap = new Map();
const wordSet = new Set();
return this.isMatch(s, 0, pattern, 0, symbolMap, wordSet);
}
isMatch(s, sIndex, pattern, pIndex, symbolMap, wordSet) {
if (pIndex
if (pIndex === pattern.length) {
return sIndex === s.length;
}
const symbol = pattern[pIndex];
if (symbolMap.has(symbol)) {
const word = symbolMap.get(symbol);
if (!s.startsWith(word, sIndex)) {
return false;
}
return this.isMatch(s, sIndex + word.length, pattern, pIndex + 1, symbolMap, wordSet);
}
for (let k = sIndex + 1; k <= s.length; k++) {
const newWord = s.substring(sIndex, k);
if (wordSet.has(newWord)) {
continue;
}
symbolMap.set(symbol, newWord);
wordSet.add(newWord);
if (this.isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
return true;
}
symbolMap.delete(symbol);
wordSet.delete(newWord);
}
return false;
}
}
JavaScript // чат
LeetCode
Word Pattern II - LeetCode
Can you solve this real interview question? Word Pattern II - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
Задача: 293. Flip Game
Сложность: easy
Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список [].
Пример:
Input: currentState = "++++"
Output: ["--++","+--+","++--"]
👨💻 Алгоритм:
1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода.
2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса:
Если символы на позициях index и index + 1 равны '+':
Создайте новую строку nextState, заменив две последовательные '+' на '--'.
Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--"
Сложность: easy
Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список [].
Пример:
Input: currentState = "++++"
Output: ["--++","+--+","++--"]
👨💻 Алгоритм:
1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода.
2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса:
Если символы на позициях index и index + 1 равны '+':
Создайте новую строку nextState, заменив две последовательные '+' на '--'.
Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--"
Наконец-то, пополнение всех популярных сервисов в одном месте в Телеграм!
— Apple ID
— Steam
— Spotify, YouTube Premium,
— ESIM
— Claude, ChatGPT
Моментальное исполнение заказа, попробуйте прямо сейчас
— Apple ID
— Steam
— Spotify, YouTube Premium,
— ESIM
— Claude, ChatGPT
Моментальное исполнение заказа, попробуйте прямо сейчас
Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard
Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия:
Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).
Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].
Пример:
Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]
👨💻 Алгоритм:
1⃣Постройте карту. Для каждого слова в списке words:
Преобразуйте его в битовую маску его символов. Если эта битовая маска не была ранее встречена, сохраните ее в качестве ключа в карте со значением 1. Если она была ранее встречена, увеличьте счетчик для этой битовой маски на 1.
2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles:
Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки.
3⃣Для каждой подмаски увеличивайте счетчик на количество слов, соответствующих подмаске. Мы можем найти количество слов, соответствующих подмаске, используя карту, построенную на предыдущем шаге.
😎 Решение:
var bitmask = function(word) {
let mask = 0;
for (let letter of word) {
mask |= 1 << (letter.charCodeAt(0) - 'a'.charCodeAt(0));
}
return mask;
};
var findNumOfValidWords = function(words, puzzles) {
let wordCount = new Map();
for (let word of words) {
let mask = bitmask(word);
wordCount.set(mask, (wordCount.get(mask) || 0) + 1);
}
let result = [];
for (let puzzle of puzzles) {
let first = 1 << (puzzle[0].charCodeAt(0) - 'a'.charCodeAt(0));
let count = wordCount.get(first) || 0;
let mask = bitmask(puzzle.slice(1));
for (let submask = mask; submask > 0; submask = (submask - 1) & mask) {
count += wordCount.get(submask | first) || 0;
}
result.push(count);
}
return result;
};
JavaScript // чат
Сложность: hard
Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия:
Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).
Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].
Пример:
Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]
👨💻 Алгоритм:
1⃣Постройте карту. Для каждого слова в списке words:
Преобразуйте его в битовую маску его символов. Если эта битовая маска не была ранее встречена, сохраните ее в качестве ключа в карте со значением 1. Если она была ранее встречена, увеличьте счетчик для этой битовой маски на 1.
2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles:
Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки.
3⃣Для каждой подмаски увеличивайте счетчик на количество слов, соответствующих подмаске. Мы можем найти количество слов, соответствующих подмаске, используя карту, построенную на предыдущем шаге.
😎 Решение:
var bitmask = function(word) {
let mask = 0;
for (let letter of word) {
mask |= 1 << (letter.charCodeAt(0) - 'a'.charCodeAt(0));
}
return mask;
};
var findNumOfValidWords = function(words, puzzles) {
let wordCount = new Map();
for (let word of words) {
let mask = bitmask(word);
wordCount.set(mask, (wordCount.get(mask) || 0) + 1);
}
let result = [];
for (let puzzle of puzzles) {
let first = 1 << (puzzle[0].charCodeAt(0) - 'a'.charCodeAt(0));
let count = wordCount.get(first) || 0;
let mask = bitmask(puzzle.slice(1));
for (let submask = mask; submask > 0; submask = (submask - 1) & mask) {
count += wordCount.get(submask | first) || 0;
}
result.push(count);
}
return result;
};
JavaScript // чат
LeetCode
Number of Valid Words for Each Puzzle - LeetCode
Can you solve this real interview question? Number of Valid Words for Each Puzzle - With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:
* word contains the first letter of puzzle.
* For each letter in word…
* word contains the first letter of puzzle.
* For each letter in word…
Задача: 1669. Merge In Between Linked Lists
Сложность: medium
Вам даны два связанных списка: list1 и list2 размером n и m соответственно.
Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.
Синие ребра и узлы на рисунке в вверху поста указывают на результат:
Пример:
Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.
👨💻 Алгоритм:
1⃣Инициализация и добавление узлов из list1 до узла a в массив:
Инициализировать переменную index равную 0 и current1 равную list1.
Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index.
2⃣Добавление узлов из list2 в массив:
Инициализировать current2 равную list2.
Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next.
3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка:
Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1.
Добавлять узлы из current1 в массив, пока current1 не станет null.
Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его.
😎 Решение:
class Solution {
mergeInBetween(list1, a, b, list2) {
let mergeArray = [];
let index = 0;
let current1 = list1;
while (index < a) {
mergeArray.push(current1.val);
current1 = current1.next;
index++;
}
let current2 = list2;
while (current2 !== null) {
mergeArray.push(current2.val);
current2 = current2.next;
}
while (index < b + 1) {
current1 = current1.next;
index++;
}
while (current1 !== null) {
mergeArray.push(current1.val);
current1 = current1.next;
}
let resultList = null;
for (let i = mergeArray.length - 1; i >= 0; i--) {
resultList = new ListNode(mergeArray[i], resultList);
}
return resultList;
}
}
JavaScript // чат
Сложность: medium
Вам даны два связанных списка: list1 и list2 размером n и m соответственно.
Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.
Синие ребра и узлы на рисунке в вверху поста указывают на результат:
Пример:
Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.
👨💻 Алгоритм:
1⃣Инициализация и добавление узлов из list1 до узла a в массив:
Инициализировать переменную index равную 0 и current1 равную list1.
Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index.
2⃣Добавление узлов из list2 в массив:
Инициализировать current2 равную list2.
Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next.
3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка:
Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1.
Добавлять узлы из current1 в массив, пока current1 не станет null.
Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его.
😎 Решение:
class Solution {
mergeInBetween(list1, a, b, list2) {
let mergeArray = [];
let index = 0;
let current1 = list1;
while (index < a) {
mergeArray.push(current1.val);
current1 = current1.next;
index++;
}
let current2 = list2;
while (current2 !== null) {
mergeArray.push(current2.val);
current2 = current2.next;
}
while (index < b + 1) {
current1 = current1.next;
index++;
}
while (current1 !== null) {
mergeArray.push(current1.val);
current1 = current1.next;
}
let resultList = null;
for (let i = mergeArray.length - 1; i >= 0; i--) {
resultList = new ListNode(mergeArray[i], resultList);
}
return resultList;
}
}
JavaScript // чат
LeetCode
Merge In Between Linked Lists - LeetCode
Can you solve this real interview question? Merge In Between Linked Lists - You are given two linked lists: list1 and list2 of sizes n and m respectively.
Remove list1's nodes from the ath node to the bth node, and put list2 in their place.
The blue edges…
Remove list1's nodes from the ath node to the bth node, and put list2 in their place.
The blue edges…
Задача: 168. Excel Sheet Column Title
Сложность: easy
Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.
Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28
Пример:
Input: columnNumber = 1
Output: "A"
👨💻 Алгоритм:
1️⃣Инициализация пустой строки ans:
Создайте пустую строку ans, которая будет хранить заголовок столбца.
2️⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26
3️⃣Переворот и возврат результата:
Так как символы добавляются в начало строки, то по завершению цикла строка ans содержит заголовок столбца в обратном порядке. Переверните строку ans, чтобы представить её в правильном порядке.
Верните полученный заголовок столбца.
😎 Решение:
var convertToTitle = function (columnNumber) {
let ans = "";
while (columnNumber > 0) {
columnNumber--;
ans =
String.fromCharCode((columnNumber % 26) + "A".charCodeAt(0)) + ans;
columnNumber = Math.floor(columnNumber / 26);
}
return ans;
};
JavaScript // чат
Сложность: easy
Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.
Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28
Пример:
Input: columnNumber = 1
Output: "A"
👨💻 Алгоритм:
1️⃣Инициализация пустой строки ans:
Создайте пустую строку ans, которая будет хранить заголовок столбца.
2️⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26
3️⃣Переворот и возврат результата:
Так как символы добавляются в начало строки, то по завершению цикла строка ans содержит заголовок столбца в обратном порядке. Переверните строку ans, чтобы представить её в правильном порядке.
Верните полученный заголовок столбца.
😎 Решение:
var convertToTitle = function (columnNumber) {
let ans = "";
while (columnNumber > 0) {
columnNumber--;
ans =
String.fromCharCode((columnNumber % 26) + "A".charCodeAt(0)) + ans;
columnNumber = Math.floor(columnNumber / 26);
}
return ans;
};
JavaScript // чат
LeetCode
Excel Sheet Column Title - LeetCode
Can you solve this real interview question? Excel Sheet Column Title - Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Example…
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Example…
ПЛАТНЫЕ НЕЙРОСЕТИ — ТЕПЕРЬ БЕСПЛАТНО
В Telegram появился канал, где ребята регулярно выискивают абузы платных нейросетей, ключи активации, бесплатные кредиты, промокоды и всевозможные лазейки, позволяющие пользоваться ИИ на халяву.
💬 Claude 🐋 DeepSeek
💬 ChatGPT 🤖 Qwen
🤖 Cursor 💬 Grok
🤖 Gemini 🤖 Midjourney
🤖 Suno 💬 Perplexity
🤖 Kling AI 🤖 ElevenLabs
и десятки других AI-сервисов...
Настоящие Робин Гуды эпохи ИИ
Забирайте тут: @NeuralToday
В Telegram появился канал, где ребята регулярно выискивают абузы платных нейросетей, ключи активации, бесплатные кредиты, промокоды и всевозможные лазейки, позволяющие пользоваться ИИ на халяву.
и десятки других AI-сервисов...
Настоящие Робин Гуды эпохи ИИ
Забирайте тут: @NeuralToday
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 1198. Find Smallest Common Element in All Rows
Сложность: medium
Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.
Если общего элемента нет, верните -1.
Пример:
Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5
👨💻 Алгоритм:
1⃣Инициализация переменных:
Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями.
2⃣Итерация по строкам матрицы:
Для каждой строки:
- увеличивайте позицию в строке, пока значение не станет равным или больше текущего максимума.
- если достигли конца строки, возвращайте -1.
- если значение равно текущему максимуму, увеличивайте счетчик.
- в противном случае, сбросьте счетчик до 1 и обновите текущий максимум.
3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.
😎 Решение:
class Solution {
smallestCommonElement(mat) {
const n = mat.length;
const m = mat[0].length;
const pos = new Array(n).fill(0);
let cur_max = 0;
let cnt = 0;
while (true) {
for (let i = 0; i < n; ++i) {
while (pos[i] < m && mat[i][pos[i]] < cur_max) {
++pos[i];
}
if (pos[i] >= m) {
return -1;
}
if (mat[i][pos[i]] !== cur_max) {
cnt = 1;
cur_max = mat[i][pos[i]];
} else if (++cnt === n) {
return cur_max;
}
}
}
}
}
JavaScript // чат
Сложность: medium
Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.
Если общего элемента нет, верните -1.
Пример:
Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5
👨💻 Алгоритм:
1⃣Инициализация переменных:
Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями.
2⃣Итерация по строкам матрицы:
Для каждой строки:
- увеличивайте позицию в строке, пока значение не станет равным или больше текущего максимума.
- если достигли конца строки, возвращайте -1.
- если значение равно текущему максимуму, увеличивайте счетчик.
- в противном случае, сбросьте счетчик до 1 и обновите текущий максимум.
3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.
😎 Решение:
class Solution {
smallestCommonElement(mat) {
const n = mat.length;
const m = mat[0].length;
const pos = new Array(n).fill(0);
let cur_max = 0;
let cnt = 0;
while (true) {
for (let i = 0; i < n; ++i) {
while (pos[i] < m && mat[i][pos[i]] < cur_max) {
++pos[i];
}
if (pos[i] >= m) {
return -1;
}
if (mat[i][pos[i]] !== cur_max) {
cnt = 1;
cur_max = mat[i][pos[i]];
} else if (++cnt === n) {
return cur_max;
}
}
}
}
}
JavaScript // чат
LeetCode
Find Smallest Common Element in All Rows - LeetCode
Can you solve this real interview question? Find Smallest Common Element in All Rows - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.