Добро пожаловать в сообщество Tencent Cloud +, чтобы получить больше обширной технической практики Tencent по галантерее ~
Эта статья была опубликована Falling Shadow
предисловие
Темы на LeetCode — это распространенные вопросы по алгоритмам на собеседованиях в крупных компаниях.Сегодняшняя цель — выиграть 5 вопросов по алгоритмам: Тема 1 — сложение больших чисел на основе связанных списков, которая не только проверяет понимание базовой структуры данных, но и исследует обработку процесса сложения. Граничная обработка; Тема 2 — найти число с наибольшим k до частоты появления массива, чтобы проверить мыслительные способности, а код очень короткий; Тема 3 — выбрать числа из два массива для формирования наибольшего числа и проверки жадных мыслей; первые три предназначены для проверки идей, а реализованные коды относительно просты; вопросы 4 и 5 — это вопросы реализации структуры данных, которые также являются головной болью для большинства людей, потому что требуется больше структур данных и реализация STL, и все еще есть ограничения по времени и пространству.
текст
1. Сложите два числа II
ссылка на тему Тема:
Учитывая два связанных списка, узлы состоят из чисел от 0 до 9, представляющих два числа соответственно; найдите сумму двух чисел и верните их в виде связанных списков.
例如
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
7243 + 564 =7807
Output: 7 -> 8 -> 0 -> 7
Тематический анализ:Смысл названия очевиден, то есть для сложения двух цифр нужно учитывать случай переноса. Поскольку это однонаправленный связанный список, после обхода трудно вернуться назад, поэтому сначала сохраните число в vec. И для удобства обработки самый младший бит vec находится в начале vec. Так что достаточно пройти две веки из 0, обращая внимание на случай последнего переноса.
Анализ сложности: временная сложность — O(N), пространственная сложность — O(N).
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ret = NULL;
vector<int> vec1, vec2;
sum(l1, vec1);
sum(l2, vec2);
int n = vec1.size(), m = vec2.size(), flag = 0;
for (int i = 0; i < n || i < m; ++i) {
int x = 0, y = 0;
if (i < n) {
x = vec1[i];
}
if (i < m) {
y = vec2[i];
}
int s = x + y + flag;
if (s > 9) {
s -= 10;
flag = 1;
}
else {
flag = 0;
}
ListNode *tmp = new ListNode(s);
tmp->next = ret;
ret = tmp;
}
if (flag) {
ListNode *tmp = new ListNode(1);
tmp->next = ret;
ret = tmp;
}
return ret;
}
void sum(ListNode* list, vector<int> &vec) {
if (list->next) {
sum(list->next, vec);
}
vec.push_back(list->val);
}
};
2.Top K Frequent Elements
ссылка на тему Тема:
Дан массив и число k, вернуть первые k чисел по их частоте: 1
example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Тематический анализ:
Вопрос делится на два шага: 1. Подсчитайте количество вхождений каждого числа; 2. Выберите номер с наибольшим количеством K 10 раз;
Простой способ: использовать хеш-таблицу для подсчета количества вхождений каждого числа, составить пару из числа вхождений каждого числа и числа и поставить их в очередь по приоритету;
Таким образом, из приоритетной очереди можно убрать k элементов.
Анализ сложности: временная сложность составляет O(NlogN), в основном в очереди с последним приоритетом.
Другие решения: есть оптимизация O(NlogK); во-первых, очередь превращается в минимальную и конечную очередь, и каждый раз, когда пара помещается в пару с приоритетом, если текущий размер больше k, то выталкивается вершина ; таким образом, каждая операция начинается с O(logN ) и становится O(logK).
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> numsHash;
for (int i = 0; i < nums.size(); ++i) {
++numsHash[nums[i]];
}
priority_queue<pair<int, int>> q;
for (int i = 0; i < nums.size(); ++i) {
if(numsHash[nums[i]]) {
q.push(make_pair(numsHash[nums[i]], nums[i]));
numsHash[nums[i]] = 0;
}
}
vector<int> ret;
for (int i = 0; i < k; ++i) {
ret.push_back(q.top().second);
q.pop();
}
return ret;
}
}leetcode;
3. создать максимальное число
ссылка на тему Тема: Учитывая два массива, массивы включают только десять чисел от 0 до 9, а длины равны n и m соответственно Выберите k чисел из двух массивов, чтобы сформировать число длины k Требования: 1. Из массива n относительное положение числа, выбранного m, остается неизменным 2. Последнее число является наибольшим, выводится последнее число.
Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]
Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]
Тематический анализ:
Если требуется, чтобы последнее число было наибольшим, то поместите наибольшее число впереди как можно дальше; при условии, что все допустимы, 99* должно быть больше, чем 98*; тогда вы можете следовать этой жадной стратегии: сначала перечислить t, t означает из массива nums1 Если в массиве выбрано t чисел, то следует выбрать kt чисел в массиве nums2; все числа в двух массивах образуют наибольшее число, потому что числа между двумя массивами могут быть в любом порядок, так что вам нужно каждый раз выбирать большее число. Просто поместите его впереди.
Задача упрощается до O(N) выбора t самых больших чисел из массива каждый раз; это можно решить жадно: предположим, что массив в настоящее время пронумерован до i и nums[i]=x; обход слева направо число, при встрече с числом t, t ссылка на тему Тема: Реализовать структуру данных, включая следующие три метода: 1. Insert(val): вставить число 2. remove(val): удалить число 3. getRandom: O(1) случайным образом возвращает число; Тематический анализ: Вставка и удаление чисел не проблематичны, подумайте, как вернуть число за время O(1). Легко понять, что его можно поместить в массив, а затем вернуть случайную позицию. Добавление может быть добавлено в конец массива, при удалении числа в середине массива последнее число может быть помещено в удаляемую позицию; Теперь вопрос в том, как быстро найти определенную позицию в массиве для удаления; рассмотрите возможность использования хэша для достижения. Массив имеет вид vector ссылка на тему Тема: Реализуйте структуру данных, требующую: 1. Inc(Key) — вставляет новый ключ со значением 1. Или увеличивает существующий ключ на 1. Ключ гарантированно является непустой строкой 2. Dec(Key) — если ключ значение равно 1, удалите его из структуры данных. В противном случае уменьшает существующий ключ на 1. Если ключ не существует, эта функция ничего не делает. Ключ гарантированно будет непустой строкой. 3. GetMaxKey() — возвращает единицу. ключей с максимальным значением. Если элемента не существует, вернуть пустую строку "". 4. GetMinKey() - Возвращает один из ключей с минимальным значением. Если элемента не существует, вернуть пустую строку "". Временная сложность всех структур данных должна быть O(1); Тематический анализ: Не принимая во внимание сложность, наивный подход состоит в обходе, O(N); простая оптимизация, использование карты для поддержания приоритетной очереди, операции 1 и 2 сначала получают значение ключа и повторно вставляются после обновления; операции 3 и 4 непосредственно взять Очередь сверху, сложность каждой операции O (LogN); Потребность в названии является o (1), то не должно быть древесной структурой типа используемого типа, субъект должен использовать характеристики, а хеш с жадностью достигается. Предположим, что существует хеш-таблица ключей для соответствующего сохраненного значения ключа. Операция 1, посмотреть есть ли ключ keyHash, есть +1, нет вставки, 2 работает, есть посмотреть ключ keyHash, есть -1, значит ничего нет; Чтобы сохранить наибольшую ценность, вводится связанный список, и все элементы в нем от мала до велика; каждый элемент представляет собой ведро, а ведро содержит ключ с одинаковым значением; операция 3, прямое получение значения элемента заголовка списка, операция 4, непосредственно получить значение последнего элемента списка; При этом при операциях 1 и 2 текущее значение ключа нужно удалить из корзины, соответствующей списку, положить в предыдущую или следующую корзинку или отбросить. Чтобы получить доступ O (1) к местоположению ключа, iter-hash можно использовать для поддержки итератора элемента, соответствующего ключу. Если эти пять тем можно пройти самостоятельно, то уровень может быть достаточным, чтобы справиться с аспектами алгоритма крупных отечественных предприятий. Ключом к алгоритму является усердное размышление и больше практики. Бесполезно жаловаться на проблемы с алгоритмом в компании. Это правильный способ потратить больше времени на подготовку. Эта статья была разрешена автором для публикации в сообществе Tencent Cloud + Для получения дополнительных оригинальных текстов, пожалуйстанажмите Найдите и подпишитесь на общедоступную учетную запись «Сообщество Yunjia», получите технические галантереи как можно скорее и ответьте на 1024 после подписки, чтобы отправить вам подарочный пакет технических курсов!class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n = (int)nums1.size(), m = (int)nums2.size();
vector<int> ret(k, 0);
for (int i = max(0, k - m); i <= k && i <= n; ++i) {
vector<int> tmp1 = maxArray(nums1, i);
vector<int> tmp2 = maxArray(nums2, k - i);
vector<int> tmp = merge(tmp1, tmp2, k);
if (greater(tmp, 0, ret, 0)) {
ret = tmp;
}
}
return ret;
}
vector<int> maxArray(vector<int> &nums, int k) {
int n = (int)nums.size();
vector<int> ret(k, 0);
for (int i = 0, j = 0; i < n; ++i) {
while (n - i + j > k && j > 0 && ret[j - 1] < nums[i]) {
--j;
}
if (j < k) {
ret[j++] = nums[i];
}
}
return ret;
}
vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> ret(k, 0);
for (int i = 0, j = 0, r = 0; r < k; ++r) {
ret[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
}
return ret;
}
bool greater(vector<int> &nums1, int i, vector<int> &nums2, int j) {
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
++i;
++j;
}
return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
}
};
4. Вставить Удалить GetRandom O(1) — дубликаты разрешены
Example
插入数字1；
collection.insert(1);
插入数字1：
collection.insert(1);
插入数字2
collection.insert(2);
随机返回数字，要求 2/3可能返回1， 1/3可能返回2；
collection.getRandom();
class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() {
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
bool ret = hashMap.find(val) == hashMap.end();
hashMap[val].push_back(randVec.size());
randVec.push_back(make_pair(val, hashMap[val].size() - 1));
return ret;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
bool ret = hashMap.find(val) != hashMap.end();
if (ret) {
auto last = randVec.back();
hashMap[last.first][last.second] = hashMap[val].back();
randVec[hashMap[val].back()] = last;
hashMap[val].pop_back();
if (hashMap[val].empty()) {
hashMap.erase(val);
}
randVec.pop_back();
}
return ret;
}
/** Get a random element from the collection. */
int getRandom() {
return randVec[rand() % randVec.size()].first;
}
private:
unordered_map<int, vector<int>> hashMap;
vector<pair<int, int>> randVec;
}leetcode;
5. Универсальная структура данных
struct Bucket {
int value;
unordered_set<string> keys;
};
class AllOne {
public:
list<Bucket> buckets;
unordered_map<string, list<Bucket>::iterator> bucketOfKey;
/** Initialize your data structure here. */
AllOne() {
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if (bucketOfKey.find(key) == bucketOfKey.end()) {
bucketOfKey[key] = buckets.insert(buckets.begin(), {0, {key}});
}
auto next = bucketOfKey[key], bucket = next++;
if (next == buckets.end() || next->value > bucket->value + 1) {
next = buckets.insert(next, {bucket->value+1, {}});
}
next->keys.insert(key);
bucketOfKey[key] = next;
bucket->keys.erase(key);
if (bucket->keys.empty()) {
buckets.erase(bucket);
}
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if (bucketOfKey.find(key) == bucketOfKey.end()) {
return ;
}
auto pre = bucketOfKey[key], bucket = pre;
if (pre != buckets.begin()) {
--pre;
}
bucketOfKey.erase(key);
if (bucket->value > 1) {
if (bucket == buckets.begin() || pre->value < bucket->value - 1) {
pre = buckets.insert(bucket, {bucket->value - 1, {}});
}
pre->keys.insert(key);
bucketOfKey[key] = pre;
}
bucket->keys.erase(key);
if (bucket->keys.empty()) {
buckets.erase(bucket);
}
}
/** Returns one of the keys with maximal value. */
string getMaxKey() {
return buckets.empty() ? "" : *(buckets.rbegin()->keys.begin());
}
/** Returns one of the keys with Minimal value. */
string getMinKey() {
return buckets.empty() ? "" : *(buckets.begin()->keys.begin());
}
}leetcode;
Суммировать