leetcode题解(数组问题)

栏目: 编程工具 · 发布时间: 6年前

内容简介:面试中的算法问题,有很多并不需要复杂的数据结构支撑。就是用数组,就能考察出很多东西了。其实,经典的排序问题,二分搜索等等问题,就是在数组这种最基础的结构中处理问题的,今天主要学习常见的数组中处理问题的方法。** 循环不变量。声明不变。控制边界。**** 极端情况:如果都为非0,则每个都自己和自己交换**

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

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

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

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

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

二分查找法

  • 二分查找法的思想在1946年提出。
  • 第一个没有bug的二分查找法在1962年才出现。
  • 对于有序数列,才能使用二分查找法 (排序的作用)
leetcode题解(数组问题)

需要注意的问题

  • 声明变量的时候,明确变量的意义,并且在书写整个逻辑的时候,要不听的维护住这个变量的意义。
  • 初始值问题
  • 边界问题
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;
    }
    
复制代码

注意

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

如何写出正确的程序?

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

LeetCode题解: Move Zeros

leetcode题解(数组问题)

直观的解题思路

leetcode题解(数组问题)
  • 拿出非0元素
  • 将非0元素拿出来,然后空位补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)中保存所有当前遍历过的非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)中
            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的与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

注意的问题

  • 如何定义删除?从数组中去除?还是放在数组末尾?
  • 剩余元素的排列是否要保证原有的相对顺序?
  • 是否有空间复杂度的要求? O(1)

基础算法思路的应用

75 Sort Colors

leetcode题解(数组问题)

基数排序法

// 时间复杂度: 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;
    }
   
复制代码

可以只扫描一遍么?

leetcode题解(数组问题)

一次三路快排

设置三个索引:zero two i

leetcode题解(数组问题)

三路快排

// 时间复杂度: 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 - 输入有序数组

leetcode题解(数组问题)

需要考虑的问题

  • 如果没有解怎样?保证有解
  • 如果有多个解怎样?返回任意解

解法

  • 最直接的思考:暴力解法。双层遍历,O(n^2)

    • 暴力解法没有充分利用原数组的性质 —— 有序:有序?二分搜索?
  • 二分搜索法

    • 对于每个i, 在剩余数组中查找target-nums[i]的值
    • 时间复杂度为O(NlogN)
      leetcode题解(数组问题)
  • 对撞指针

leetcode题解(数组问题)
  • 一般会是大于或者小于。
  • 如果大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长度最小的子数组

leetcode题解(数组问题)

什么是子数组

leetcode题解(数组问题)
  • 一般不要求连续
  • 而这个题目中规定了子数组要连续这样的特性。
    • 如果没有解怎么办?返回0

暴力解O(N^3)

  • 计算其和sum,验证sum >= 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;
    }
    
复制代码

滑动窗口解

leetcode题解(数组问题)
  • 如果当前子数组不到就往后再看一个

  • 窗口不停向前滑动。

// 滑动窗口的思路
// 时间复杂度: 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;
    }
};

复制代码

在滑动窗口中做记录

无重复字符的最长子串

leetcode题解(数组问题)

注意

字符集?只有字母?数字+字母?ASCII?

大小写是否敏感?

思路

leetcode题解(数组问题)
  • j++如果没有重复元素,窗口j继续往后
  • 如果有重复元素,i++去除重复
  • freq[256]记录窗口中的元素
leetcode题解(数组问题)

实现代码

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

    • 字符集范围
    • 若没有解? 返回“”
      *若有多个解?保证只有一个解
    • 什么叫包含所有字符?S = “a”,T = “aa”

-------------------------华丽的分割线--------------------

看完的朋友可以点个喜欢/关注,您的支持是对我最大的鼓励。

个人博客番茄技术小栈和 掘金主页

想了解更多,欢迎关注我的微信公众号:番茄技术小栈

leetcode题解(数组问题)

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员的英语

程序员的英语

[韩]朴栽浒、[韩]李海永 / 颜廷连 / 人民邮电出版社 / 2018-2 / 49.00元

高考以后就把英语都还给老师了? 写代码特顺溜,一到英语就卡壳? 常见的语法书太枯燥,单词书又太宽泛? 不用急,快来加入针对开发人员的英语读解能力训练项目! - 安全与黑客攻击、无人机与机器人、大数据、物联网、云计算,顺应新技术潮流! - 语法、单词、完形填空、阅读理解、翻译,多角度提升读解能力! - 英语母语技术人员审校,提供“语言和技术”双保险!一起来看看 《程序员的英语》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

html转js在线工具
html转js在线工具

html转js在线工具