704.二分查找

https://leetcode.cn/problems/binary-search/description/

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right)
        {
            int mid = left + (right - left)/2;  //除二相当于左移1 ， 也可以left + right / 2
            if(nums[mid] > target)
            right = mid -1;
            else if(nums[mid] < target)
            left = mid + 1;
            else return mid;
        }
        return -1;
    }
};

35.搜索插入位置

https://leetcode.cn/problems/search-insert-position/description/

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right)
        {
            int mid = (left + right)/2;
            if(nums[mid] > target)
                right = mid - 1;
            else if(nums[mid] < target)
                left = mid + 1;
            else return mid;
        }
        return right + 1;
    }
};

34.在排序数组中寻找目标值的第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = searchBoder(nums, target, "start");
        int end = searchBoder(nums, target, "end");
        vector<int> ans = {start,end};
        return ans;
    }
private: 
    int searchBoder(vector<int>& nums, int target, string s) {
        //要找的不是target，而是target(可能不止一个)的两侧位置！！！！
        int left = 0;
        int right = nums.size() - 1;
        int start = -1; int end = -1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] > target) //说明target的最后一个元素(比如133345678的第三个3)必定在中值(4)左侧
            right = mid - 1;       //所有的3在【left,mid-1】内，注意是所有的3！！！
            else if(nums[mid] < target)
            left = mid + 1;         //同理
            else                    //中值刚好是target.此时要找左右边界，先找左边界start
            {
                //找到了某个3，第一个3就至少是这个位置，接着把搜索范围的右侧(right)更新到这个3左边的位置，再次二分
                //注意：已经找到了某个3，现在要找第一个3，left肯定在这个3左边了，是把right也放到它左边来找第一个3！！！！
                if(s == "start")
                {
                    start = mid;
                    right = mid - 1;  
                }
                if(s == "end")
                {
                    //找最后一个3，同理
                    end = mid;
                    left = mid + 1;
                }
            }
        }
        if(s == "start") return start;
        else return end;
    }
};

69.x的平方根

https://leetcode.cn/problems/sqrtx/description/

class Solution {
public:
    int mySqrt(int x) {
        //二分查找，根号x <= x/2 + 1，一般小于x/2即可，x = 1的时候取等号，可以特殊讨论
        if(x == 1 || x == 0)  return x;
        int left = 0;
        int right = x/2;
        while(left <= right)
        {
            int mid = (left + right)/2;
            if((long)mid*mid < x)
            {
                if((mid+1)*(mid+1) > x)      //比如说找8的平方根，当前mid = 2,mid + 1 = 3,就可以直接返回2了
                return mid;

                else 
                left = mid + 1;
            }
            else if((long)mid*mid > x)
            {
                if((long)(mid-1)*(mid-1) < x)     //同理
                return mid-1;

                else 
                right = mid - 1;
            }
            else                            //mid刚好就是平方根
            return mid;
        }
        return -1;
    }
};

367.有效的完全平方数

https://leetcode.cn/problems/valid-perfect-square/description/

class Solution {
public:
    bool isPerfectSquare(int x) {
        if(x == 1 || x == 0)  return true;
        int left = 0;
        int right = x/2;
        
        while(left <= right)
        {
            int mid = (left + right)/2;
            if((long)mid*mid < x)
            {
                left = mid + 1;
            }
            else if((long)mid*mid > x)
            {
                right = mid - 1;
            }
            else                            //mid刚好就是平方根
            return true;
        }
        return false;
    }
};

27.移除元素

https://leetcode.cn/problems/remove-element/description/

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast++)
        {
            if(val != nums[fast])
            nums[slow++] = nums[fast];
        }
        return slow;
    }
};

26.删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 1)  return 1;

        int slow = 0;
        for(int fast = 1; fast < nums.size(); fast++)
        {
            if(nums[slow] != nums[fast])
            {
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
};

283.移动零

https://leetcode.cn/problems/move-zeroes/description/

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast++)
        {
            if(nums[fast] != 0)
            nums[slow++] = nums[fast];
        }
        cout<<slow;
        while(slow < nums.size())
        {
            nums[slow++] = 0;
        }
    }
};

844.比较含退格的字符串

https://leetcode.cn/problems/backspace-string-compare/description/

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        fun(s);
        fun(t);
        return s==t;
    }
    void fun(string &s){
        int slow = 0;
        for(int fast = 0; fast < s.size(); fast++)
        {
            if(s[fast] != '#')
            s[slow++] = s[fast];
            else if(slow > 0)
            slow--;
        }
        s.resize(slow);
    }
};

977.有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/description/

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int size = nums.size();
        int k = size - 1;
        int forward = 0;
        int back = size-1;
        vector<int> result(size,0);
        while(forward <= back)
        {
            int a = nums[forward]*nums[forward];
            int b = nums[back]*nums[back];
            if(a < b)
            {
                result[k--] = b;
                back--;
            }
            else 
            {
                result[k--] = a;
                forward++;
            }
        }
        return result;
    }
};

209.长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int start = 0;
        int sum = 0;
        int len = 0;
        int res = INT32_MAX;
        for(int end = 0; end < nums.size(); end++)
        {
            sum += nums[end];
            while(sum >= target)
            {
                len = end - start + 1;
                res = res > len ? len : res;
                sum -= nums[start];
                start++;
            }
        }
        return res == INT32_MAX ? 0 : res;
    }
};

904.水果成栏

https://leetcode.cn/problems/fruit-into-baskets/description/

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int num = fruits.size();
        if(num <= 2)
        return num;

        unordered_map<int,int> type_count;
        int types = 0;
        int res = 0;
        for(int start = 0, end = 0; end < num; end++)
        {
            if(type_count[fruits[end]] == 0)         //如果当前的水果种类之前没有，就加一个种类
            types++;

            type_count[fruits[end]]++;               //不管以前有没有这种水果，他的数量++

            while(types > 2)                         //如果种类数超过2了，考虑后移start,
            {
                type_count[fruits[start]]--;

                if(type_count[fruits[start]] == 0)   //直到消失这个种类
                types--;

                start++;                             //每次都要后移一个
            }
            res = max(res, end - start + 1);
        }
        return res;
    }
};

76.最小覆盖字符串

https://leetcode.cn/problems/minimum-window-substring/description/

class Solution {
public:
    string minWindow(string s, string t) {
        if(s.size() < t.size())
        return "";
        unordered_map<char,int> hs,ht;      //用于记录s t的每个字符有几个
        int cnt = 0;
        string ans = "";

        for(auto& ch :t)
        ht[ch]++;

    //不管怎么样, end都要向后扩，但只有多余了 start 才会收缩（向后）以找到最短
    //比如abcde第四次循环完成，就找到abcd最接近的答案，可能刚好就是abcd，也可能是bcd 还可能不够，但start一定是最靠后的位置

        for(int start = 0, end = 0; end < s.size(); end++)
        {
            hs[s[end]]++;                        //不管怎么样end都要后扩，让s[end]的个数加一

            if(hs[s[end]] <= ht[s[end]])         //是否是有效添加？无效添加就是比如目前已经有3个a，但是t只有两个a，多了一个
            {
                cnt++;
            }

            while(hs[s[start]] > ht[s[start]])   //移完后面移前面，尽可能保证start靠后，啥时候保证不了？缩的该有的都没了的时候
            {
                hs[s[start++]]--;                //start可以后移，s[start]个数减少一个
                //cout<<s[start]<<endl;
            }

            int curLen = end - start + 1;
            if(cnt == t.size())
            {
                if (ans.empty() || ans.size() > curLen)
                //这里很重要，ans.empty()保证第一次ans可以填入，ans比当前len长保证把ans更新为更短答案
                ans = s.substr(start, curLen);
            }  
        }
        return ans;
    }
};

59.螺旋矩阵Ⅱ

https://leetcode.cn/problems/spiral-matrix-ii/description/

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        //分为奇数偶数，奇数比如5就一共有两圈加中心一个25，偶数比如4就正好两圈
        //上 -- 右 -- 下 -- 左 最外圈每次填n-1次，左闭右开。每往里一圈，起点右下移一个，右边往前移一个
        vector<vector<int>> matrix(n,vector<int>(n,0));
        int startx = 0, starty = 0;
        int end = n - 1;
        int loop = n/2;
        int count = 1;
        while(loop--)
        {
            //上
            for(int i = starty; i < end; i++)
            {
                matrix[startx][i] = count++;
            }
            //右
            for(int i = startx; i < end; i++)
            {
                matrix[i][end] = count++;
            }
            // //下
            for(int i = end; i > startx; i--)
            {
                matrix[end][i] = count++;
            }
            //  //左
            for(int i = end; i > starty; i--)
            {
                matrix[i][startx] = count++;
            }

            startx++;
            starty++;
            end--;

        }
        if(n%2 != 0)
        matrix[n/2][n/2] = n*n;
        return matrix;
    }
};

54.螺旋矩阵

https://leetcode.cn/problems/spiral-matrix/
https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        vector<int> res;
        //分别表示left right bottom top, 左上角为(0,0)
        if(array.size() == 0) return res;
        int l = 0, r = array[0].size() - 1, t = 0, b = array.size() - 1;
        while(1)
        {
            for(int i = l; i <= r; i++)  
            res.push_back(array[t][i]);

            if(++t > b)             //跑完顶行，下移一行
            break;

            for(int i = t; i <= b; i++)
            res.push_back(array[i][r]); 

            if(--r < l)             //跑完右行，左移一行
            break;

            for(int i = r; i >= l; i--)
            res.push_back(array[b][i]);

            if(--b < t)             //跑完底行，上移一行
            break;

            for(int i = b; i >= t; i--)
            res.push_back(array[i][l]);

            if(++l > r)             //跑完左行，右移一行
            break;
        }
        return res;
    }
};

本栏目推荐文章
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• 类模板实现简单的数组
• 用jacoco统计JAVA项目测试代码覆盖率
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• GDB调试之源代码查看与管理(六)
• 写代码时如何合理的画图表达逻辑结构
• 十行python代码实现文件去重，去除重复文件的脚本
• 数组内存图
• [代码随想录] 第四天
• idea 中java代码修改后运行代码不生效

随想录 数组 随想 代码随想录 数组 随想 代码 训练营 数组 随想 代码 随想录 之和 数组 交集 随想录 之和 训练营 数组 数组 随想录 训练营 矩阵 数组 随想录 矩阵 螺旋 随想录 训练营 数组 随想 随想录 数组 小结 随想 算法 随想录 训练营 数组 随想录 训练营 数组 交集