В интервью много алгоритмических вопросов, не требующих поддержки сложной структуры данных. Просто используя массивы, вы можете исследовать множество вещей. На самом деле, классические задачи сортировки, бинарный поиск и другие проблемы решаются в самой базовой структуре массивов Сегодня мы в основном учимся решать задачи в обычных массивах.
Проблемы с массивами на самом деле самые распространенные.
- Сортировка: сортировка выбором, сортировка вставками, сортировка слиянием, быстрая сортировка
- Найти: бинарный поиск
- Структуры данных: стек, очередь, куча
Как написать правильную программу методом бинарного поиска
- Создайте фундаментальную основу
- какова правильная процедура
бинарный поиск
- Идея метода бинарного поиска была предложена в 1946 году.
- Первый безошибочный метод бинарного поиска появился в 1962 году.
- Для упорядоченных рядов можно использовать метод бинарного поиска (роль сортировки)
Проблемы, о которых следует знать
- При объявлении переменной уточняйте значение переменной, а при написании всей логики следует тщательно поддерживать значение переменной.
- проблема с начальным значением
- краевая задача
template<typename T>
int binarySearch( T arr[], int n, T target ){
int l = 0, r = n-1; // 在[l...r]的范围里寻找target：前闭后闭
while( l <= r ){ // 只要还有可以查找的内容。当 l == r时,区间[l...r]依然是有效的
int mid = l + (r-l)/2;
if( arr[mid] == target ) return mid;
//mid已经判断过了
if( target > arr[mid] )
l = mid + 1; // target在[mid+1...r]中; [l...mid]一定没有target
else // target < arr[mid]
r = mid - 1; // target在[l...mid-1]中; [mid...r]一定没有target
}
return -1;
}
** Инвариант цикла. Заявление остается без изменений. Границы контроля. **
int l = 0, r = n-1; // 在[l...r]的范围里寻找target：前闭后闭
Измените определение переменной и по-прежнему напишите правильный алгоритм
template<typename T>
int binarySearch( T arr[], int n, T target ){
int l = 0, r = n; // target在[l...r)的范围里，这样设置才能保证长度为n
while( l < r ){ // 当 l == r时,区间[l...r)是一个无效区间 [42,43)
int mid = l + (r-l)/2;
if( arr[mid] == target ) return mid;
if( target > arr[mid] )
l = mid + 1; // target在[mid+1...r)中; [l...mid]一定没有target
else// target < arr[mid]
r = mid; // target在[l...mid)中; [mid...r)一定没有target
}
return -1;
}
Уведомление
- Чтобы найти среднее значение, используйте (l + r)/2, чтобы легко сформировать переполнение.
- Возьмем mid = l + (r-l)/2;
Как написать правильную программу?
- Уточнить значение переменных
- инвариант цикла
- Отладка небольших наборов данных (от 4 до 6 данных) пустой набор, граница (как код работает с небольшими наборами данных)
- Будьте терпеливы, чтобы найти ошибки и определить, где возникает ошибка.
- Тест большого объема данных (производительность)
Решение проблемы LeetCode: переместить нули
Интуитивные идеи решения проблем
- вынуть ненулевые элементы
- Выньте ненулевые элементы, а затем заполните пустое место 0
class Solution {
public:
// 时间复杂度 O(n)
// 空间复杂度 O(n) 新创建数组
void moveZeroes(vector<int>& nums) {
vector<int> nonZeroElements;
// 将vec中所有非0元素放入nonZeroElements中
for( int i = 0 ; i < nums.size() ; i ++ )
if( nums[i] )
nonZeroElements.push_back( nums[i] );
// 将nonZeroElements中的所有元素依次放入到nums开始的位置
for( int i = 0 ; i < nonZeroElements.size() ; i ++ )
nums[i] = nonZeroElements[i];
// 将nums剩余的位置放置为0
for( int i = nonZeroElements.size() ; i < nums.size() ; i ++ )
nums[i] = 0;
}
};
int main() {
int arr[] = {0, 1, 0, 3, 12};
//根据生成的数据创建vector：传入头指针和尾指针
vector<int> vec(arr, arr + sizeof(arr)/sizeof(int));
Solution().moveZeroes(vec);
for( int i = 0 ; i < vec.size() ; i ++ )
cout<<vec[i]<<" ";
cout<<endl;
return 0;
}
Даже простые алгоритмы могут быть дополнительно оптимизированы.
- Нет дополнительного места
- k - [0...k) сохранить все пройденные в данный момент ненулевые элементы
class Solution {
public:
// 时间复杂度 O(n)
// 空间复杂度 O(1)
void moveZeroes(vector<int>& nums) {
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
for(int i = 0 ; i < nums.size() ; i ++ )
if( nums[i] )
nums[k++] = nums[i];
// 将nums剩余的位置放置为0
for( int i = k ; i < nums.size() ; i ++ )
nums[i] = 0;
}
};
int main() {
int arr[] = {0, 1, 0, 3, 12};
vector<int> vec(arr, arr + sizeof(arr)/sizeof(int));
Solution().moveZeroes(vec);
for( int i = 0 ; i < vec.size() ; i ++ )
cout<<vec[i]<<" ";
cout<<endl;
return 0;
}
дальнейшая оптимизация
-
Ненулевые присваивания не нужно обрабатывать.
-
Не-0 напрямую заменяется на 0.
class Solution {
public:
// 时间复杂度 O(n)
// 空间复杂度 O(1)
void moveZeroes(vector<int>& nums) {
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
// 同时, [k...i] 为0
for(int i = 0 ; i < nums.size() ; i ++ )
if( nums[i] )
swap( nums[k++] , nums[i] );
}
};
**Крайний случай: если оба отличны от 0, каждый меняет местами сам с собой**
class Solution {
public:
// 时间复杂度 O(n)
// 空间复杂度 O(1)
void moveZeroes(vector<int>& nums) {
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
// 同时, [k...i] 为0
for(int i = 0 ; i < nums.size() ; i ++ )
if( nums[i] )
//
if( k != i )
swap( nums[k++] , nums[i] );
else// i == k
k ++;
}
};
похожие темы
- leetcode 27
- leetcode 26
- leetcode 80
Вопросы внимания
- Как определить удаление? удалить из массива? Или в конце массива?
- Гарантирует ли расположение остальных элементов первоначальный относительный порядок?
- Есть ли требования к сложности пространства? О(1)
Применение основных идей алгоритма
75 Sort Colors
сортировка по основанию
// 时间复杂度: O(n)
// 空间复杂度: O(k), k为元素的取值范围
// 对整个数组遍历了两遍
class Solution {
public:
void sortColors(vector<int> &nums) {
int count[3] = {0}; // 存放0,1,2三个元素的频率
for( int i = 0 ; i < nums.size() ; i ++ ){
assert( nums[i] >= 0 && nums[i] <= 2 );
count[nums[i]] ++;
}
int index = 0;
for( int i = 0 ; i < count[0] ; i ++ )
nums[index++] = 0;
for( int i = 0 ; i < count[1] ; i ++ )
nums[index++] = 1;
for( int i = 0 ; i < count[2] ; i ++ )
nums[index++] = 2;
// 小练习: 更加自使用的计数排序
}
};
int main() {
int nums[] = {2, 2, 2, 1, 1, 0};
vector<int> vec = vector<int>( nums , nums + sizeof(nums)/sizeof(int));
Solution().sortColors( vec );
for( int i = 0 ; i < vec.size() ; i ++ )
cout<<vec[i]<<" ";
cout<<endl;
return 0;
}
Могу ли я просто отсканировать его один раз?
Трехсторонняя быстрая строка
Установите три индекса: ноль два i
Быстрая гребля втроем
// 时间复杂度: O(n)
// 空间复杂度: O(1)
// 对整个数组只遍历了一遍
class Solution {
public:
void sortColors(vector<int> &nums) {
int zero = -1; // [0...zero] == 0
int two = nums.size(); // [two...n-1] == 2
for( int i = 0 ; i < two ; ){
if( nums[i] == 1 )
i ++;
else if ( nums[i] == 2 )
swap( nums[i] , nums[--two]);
else{ // nums[i] == 0
assert( nums[i] == 0 );
swap( nums[++zero] , nums[i++] );
}
}
}
};
int main() {
int nums[] = {2, 2, 2, 1, 1, 0};
vector<int> vec = vector<int>( nums , nums + sizeof(nums)/sizeof(int));
Solution().sortColors( vec );
for( int i = 0 ; i < vec.size() ; i ++ )
cout<<vec[i]<<" ";
cout<<endl;
return 0;
}
похожие темы
- 88 Merge Sorted Array
- 215 Kth Largest Element in an Array
Техника двойного индекса — столкновение указателей
167 Сумма двух чисел II - Входной отсортированный массив
вопросы для рассмотрения
- А если решения нет? Гарантированное решение
- Что делать, если есть несколько решений? вернуть любое решение
решение
-
Самое прямое мышление: насильственное решение. Двухуровневый обход, O(n^2)
- Решение грубой силы не использует в полной мере свойства исходного массива — упорядочено: упорядочено? Бинарный поиск?
-
бинарный поиск
- Для каждого i найдите значение target-nums[i] в оставшемся массиве.
- Временная сложность O(NlogN)
-
указатель столкновения
- Обычно больше или меньше.
- Если большой i++ маленький j--
- Два индекса идут посередине. указатель столкновения.
Код
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
assert( numbers.size() >= 2 );
// assert( isSorted(numbers) );
int l = 0, r = numbers.size()-1;
while( l < r ){
if( numbers[l] + numbers[r] == target ){
int res[2] = {l+1, r+1};
return vector<int>(res, res+2);
}
else if( numbers[l] + numbers[r] < target )
l ++;
else // numbers[l] + numbers[r] > target
r --;
}
throw invalid_argument("the input has no solution");
}
};
похожие темы
- 125 Valid Palindrome
- Что делать с пустыми строками?
- Определение персонажей?
- дело проблема
- 344 Reverse String
- 345 Reverse Vowels of a String
- 11 Container With Most Water
Технология двойной индексации — скользящее окно
209 Наименьший подмассив длины
что такое подмассив
- Как правило, не требуют непрерывного
- И в этой теме оговаривается, что подмассив должен быть непрерывным.
- Если нет решения как быть? Возврат 0
Насильственное решение O (N ^ 3)
- Вычислите его сумму и проверьте, что сумма >= s
- Временная сложность O (n ^ 3)
Код
int minSubArrayLen(int s, vector<int>& nums) {
assert(s > 0);
int res = nums.size() + 1;
for(int l = 0 ; l < nums.size() ; l ++)
for(int r = l ; r < nums.size() ; r ++){
int sum = 0;
for(int i = l ; i <= r ; i ++)
sum += nums[i];
if(sum >= s)
res = min(res, r - l + 1);
}
if(res == nums.size() + 1)
return 0;
return res;
}
Оптимизация решения грубой силы составляет O (N ^ 2)
int minSubArrayLen(int s, vector<int>& nums) {
assert(s > 0);
// sums[i]存放nums[0...i-1]的和
vector<int> sums(nums.size() + 1, 0);
for(int i = 1 ; i <= nums.size() ; i ++)
sums[i] = sums[i-1] + nums[i-1];
int res = nums.size() + 1;
for(int l = 0 ; l < nums.size() ; l ++)
for(int r = l ; r < nums.size() ; r ++){
// 使用sums[r+1] - sums[l] 快速获得nums[l...r]的和
if(sums[r+1] - sums[l] >= s)
res = min(res, r - l + 1);
}
if(res == nums.size() + 1)
return 0;
return res;
}
решение для раздвижных окон
-
Если текущий подмассив недоступен, посмотрите на другой
-
Окно продолжает двигаться вперед.
// 滑动窗口的思路
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
//nums[l...r]为我们的滑动窗口
int l = 0, r = -1;
int sum = 0;
int res = nums.size() + 1;
while(l < nums.size()){
if(r+1 < nums.size() && sum < s){
r++;
sum += nums[r];
}else{
sum -= nums[l];
l++;
}
if(sum >= s){
res = min(res, r - l + 1);
}
}
if(res == nums.size() + 1)
return 0;
return res;
}
};
Делайте заметки в скользящем окне
самая длинная подстрока без повторяющихся символов
Уведомление
набор символов? Только буквы? Цифры + буквы? ASCII?
Это чувствительно к регистру?
идеи
- j++ Если нет повторяющихся элементов, окно j продолжается до конца.
- Если есть повторяющиеся элементы, i++ удаляет дубликаты.
- freq[256] записывает элементы в окне
код реализации
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int freq[256] = {0};
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
// 整个循环从 l == 0; r == -1 这个空窗口开始
// 到l == s.size(); r == s.size()-1 这个空窗口截止
// 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
while( l < s.size() ){
if( r + 1 < s.size() && freq[s[r+1]] == 0 )
freq[s[++r]] ++;
else //r已经到头 || freq[s[r+1]] == 1
freq[s[l++]] --;
res = max( res , r-l+1);
}
return res;
}
};
int main() {
cout << Solution().lengthOfLongestSubstring( "abcabcbb" )<<endl;
cout << Solution().lengthOfLongestSubstring( "bbbbb" )<<endl;
cout << Solution().lengthOfLongestSubstring( "pwwkew" )<<endl;
cout << Solution().lengthOfLongestSubstring( "" )<<endl;
return 0;
}
похожие темы
-
438 Find All Anagrams in a String
- Диапазон набора символов? английские строчные буквы
- Порядок возвращаемых решений? Любые.
-
76 Minimum Window Substring
- диапазон набора символов
- Если нет решения? вернуть""
* Если есть несколько решений? Гарантированно иметь только одно решение - Что значит содержать все символы? С = "а", Т = "аа"
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.
личный блогСтек томатной технологииа такжеДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт WeChat: Tomato Technology Stack.