leetcode题解（数组类问题）

面试中的算法问题，有很多并不需要复杂的数据结构支撑。就是用数组，就能考察出很多东西了。其实，经典的排序问题，二分搜索等等问题，就是在数组这种最基础的结构中处理问题的，今天主要学习常见的数组中处理问题的方法。

数组中的问题其实最常见。

排序：选择排序；插入排序；归并排序；快速排序
查找：二分查找法
数据结构：栈；队列；堆

从二分查找法看如何写出正确的程序

建立一个基础的框架
什么是正确的程序

二分查找法

二分查找法的思想在1946年提出。
第一个没有bug的二分查找法在1962年才出现。
对于有序数列，才能使用二分查找法（排序的作用）

需要注意的问题

声明变量的时候，明确变量的意义，并且在书写整个逻辑的时候，要不听的维护住这个变量的意义。
初始值问题
边界问题

    template
    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
    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;
    }

注意

求mid值是采用(l+r)/2容易整形溢出
采用mid = l + (r-l)/2;

如何写出正确的程序？

明确变量的含义
循环不变量
小数据量调试（4到6个数据）空集，边界（小数据集上代码如何运作的）
耐心找到bug，定位错误发生的位置。
大数据量测试（性能）

LeetCode题解： Move Zeros

直观的解题思路

拿出非0元素
将非0元素拿出来，然后空位补0

    class Solution {
    public:
 // 时间复杂度 O(n)
 // 空间复杂度 O(n) 新创建数组
 void moveZeroes(vector& nums) {

     vector 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 vec(arr, arr + sizeof(arr)/sizeof(int));

 Solution().moveZeroes(vec);

 for( int i = 0 ; i < vec.size() ; i ++ )
     cout<
即使简单的算法也能进一步优化。
不开辟额外空间
k - [0…k)中保存所有当前遍历过的非0元素
    class Solution {
    public:
 // 时间复杂度 O(n)
 // 空间复杂度 O(1)
 void moveZeroes(vector& 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 vec(arr, arr + sizeof(arr)/sizeof(int));

 Solution().moveZeroes(vec);

 for( int i = 0 ; i < vec.size() ; i ++ )
     cout<
进一步优化

非0的赋值不用操作了。

非0的与0直接互换。
    class Solution {
    public:
 // 时间复杂度 O(n)
 // 空间复杂度 O(1)
 void moveZeroes(vector& 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& 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
注意的问题
如何定义删除？从数组中去除？还是放在数组末尾？
剩余元素的排列是否要保证原有的相对顺序？
是否有空间复杂度的要求？ O(1)
基础算法思路的应用
75 Sort Colors

基数排序法
    // 时间复杂度: O(n)
    // 空间复杂度: O(k), k为元素的取值范围
    // 对整个数组遍历了两遍
    class Solution {
    public:
 void sortColors(vector &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 vec = vector( nums , nums + sizeof(nums)/sizeof(int));

 Solution().sortColors( vec );
 for( int i = 0 ; i < vec.size() ; i ++ )
     cout<
可以只扫描一遍么？

一次三路快排

设置三个索引：zero two i


三路快排
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    // 对整个数组只遍历了一遍
    class Solution {
    public:
 void sortColors(vector &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 vec = vector( nums , nums + sizeof(nums)/sizeof(int));

 Solution().sortColors( vec );
 for( int i = 0 ; i < vec.size() ; i ++ )
     cout<
相似题目
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 twoSum(vector& 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(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)
计算其和sum，验证sum >= s  
时间复杂度O(n^3)
代码实现
int minSubArrayLen(int s, vector& 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& nums) {

 assert(s > 0);

 // sums[i]存放nums[0...i-1]的和
 vector 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& 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" )<
相似题目

438 Find All Anagrams in a String
字符集范围？英文小写字母  
返回的解的顺序？任意。

76 Minimum Window Substring
字符集范围  
若没有解？ 返回“”

*若有多个解？保证只有一个解  
什么叫包含所有字符？S = “a”，T = “aa”

原创始发于慕课网

leetcode题解（数组类问题）

C/C++/C#相关栏目本月热门文章