精华内容
下载资源
问答
  • 四月准备实习过程遇见一些原题,一部分是面试被问到,一部分是看面经整理,还有一些类似题目,从本地复制过来,备份一下(#.#) 一些同类题目之后会单独整理一下,重新做一遍,贴上代码。 04.05: NO 3. ...

    三四月准备实习过程中遇见的一些原题,一部分是面试被问到的,一部分是看面经整理的,还有一些类似题目,从本地复制过来,备份一下(#.#)
    一些同类的题目之后会单独整理一下,重新做一遍,贴上代码。

    04.05:

    NO 3. 无重复字符的最长子串。 字符串的子串默认是连续的,子序列默认是不连续的。 双指针,枚举起点(外层for循环控制),移动终点(内层while循环控制)。map记录起点到终点间,每个字符出现次数。

    NO 5. 最长回文子串。 从中间位置向两侧扩散,若子串长度为奇数,则中间位置为单个字符,若子串长度为偶数,则中间位置为两个相邻字符,遍历所有中间位置(2n - 1个),不断更新最长子串(可以只记录当前子串的起始位和结束位,最后进行substr()操作)。

    NO 72. 编辑距离。 三种操作包括插入、删除和替换。二维动态规划,dp[i] [j]表示从word1前i位变化到word2前j位的最短编辑距离。讨论时,分为word1和Word2的最后一位相等或不相等两种情况,注意初始化和字符串长度问题。

    NO 647. 回文子串。 1. 暴力搜索,时间复杂度O(n^3),超时。2. 区间动态规划,dp[i] [j]表示从i位置到j位置的子串是否为回文串,在dp[i+1] [j-1]的基础上根据s[i]和s[j]是否相等来对dp[i] [j]判断。两层for循环分别遍历子串长度和子串起始位置。3. 从中间位置向两侧扩散,若子串长度为奇数,则中间位置为单个字符,若子串长度为偶数,则中间位置为两个相邻字符,遍历所有中间位置(2n - 1个),计算所有回文子串个数。

    04.06:

    NO 322. 零钱兑换。 计算可以凑成总金额所需的最少的硬币个数,完全背包。dp初始值设置为amount+1就可以了。

    NO 124. 二叉树中的最大路径和。 dfs 自下而上递归,每个节点返回以该节点作为路径一端的最长路径,并计算更新当前的最大路径和(当前节点值+max(0, 左节点返回值)+max(0, 右节点返回值)),注意存在值为负数的节点,最大路径和不能初始化为0。

    NO 49. 字母异位词分组。 unordered_map<string, vector<string> > mp; 排序后key值相同的分为一组;也可以统计每个字符串中每个字母出现次数。

    NO 55. 跳跃游戏。 贪心。遍历所有位置,并在每一个位置处更新当前所能到达的最远距离,当最远距离小于当前位置,即不能到达当前位置时,返回false。

    NO 114. 二叉树展开为链表。 题目中要求原地展开,即可以将原二叉树展开为只存在右子树的树结构,dfs自下而上,将每个节点的处理好的左子树移动到右子树的位置,再在末尾连接处理好的右子树。

    04.10:

    NO 1246. 回文串移除。 给定一个整数数组,每一次操作你都可以选择并删除它的一个回文子数组,求删除所有数字的最小删除次数。动态规划,dp[i] [j]表示删除i到j位置的子数组需要的最小删除次数。单独考虑arr[i]的删除与否时,有状态转移方程为dp[i][j] = min(dp[i][j], dp[i+1][j] + 1);考虑arr[i]和arr[i+1]相等时,有状态转移方程dp[i][j] = min(dp[i][j], dp[i+2][j] + 1);考虑arr[i]和arr[k]相等时(arr[k]是arr[i+2]到arr[j]中的任意一个),有状态转移方程dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k+1][j])。共三种情况,最后返回dp[0] [i -1]。

    NO 654. 最大二叉树。 维护每棵子树根节点的index取值范围,记录start/end位置,从start到end遍历获取最大值,确定子树根节点,dfs遍历获取左右子树。

    NO 814. 二叉树剪枝。 题目要求移除所有不包含 1 的子树的原二叉树。自底向上dfs,每个节点保存flag状态,flag为true表示以该节点为根节点的子树不会被移除, 为false表示要被移除,每层dfs中flag初始值为bool flag = (root -> val == 1 ? true : false);,之后和左右子树返回的状态做或运算,确定该节点的最终状态。

    NO 669. 修剪二叉搜索树。 自上而下dfs。分为三种情况:1.当前节点的值在所给范围内时,当前节点不变,左右子树通过下层dfs获得;2. 当前节点的值小于下边界时,其左子树一定也小于下边界,则当前根节点如果存在,一定由其右子树中某节点替换;3. 当前节点的值大于上边界时,同2,当前根节点如果存在,一定由其左子树中某节点替换。

    NO 701. 二叉搜索树插入节点。 根据二叉搜索树的性质,默认把新节点插入到原二叉搜索树中作为叶子结点。根据大小判断dfs自上而下的走向。

    NO 450. 二叉搜索树删除节点。 首先自上而下递归找到待删除节点,找到后,分三种情况讨论:1. 待删除节点是叶子结点,直接删除即可;2. 待删除节点左子树为空,直接将右节点变为当前节点;3. 待删除节点的左子树不为空, 将左节点a变为当前节点,其中a的左子树保持不变,a的右子树用变量保存,a的右节点变为待删除节点的右节点,再将用变量保存的a的原右子树连接到现右子树的最左端。

    04.11:

    NO 931. 下降路径最小和。 题目要求在下一行选择的元素和当前行所选元素最多相隔一列(前一列,本列,后一列)。矩阵动态规划,dp[row][col]表示到(row, col)位置的最小和,状态转移方程:dp[row][col] += min(A[row - 1][col], A[row - 1][col - 1], A[row - 1][col + 1]);。如果考虑空间复杂度,可以直接在原数组上修改:A[row][col] += min(A[row - 1][col], A[row - 1][col - 1], A[row - 1][col + 1]);。注意数组越界。

    NO 1289. 下降路径最小和2。 题目要求相邻两行所选择的数字不在同一列。矩阵动态规划,dp[row][col]表示到(row, col)位置的最小和,记录dp[row - 1]的第一小和第二小的位置,状态转移方程:dp[row][col] = dp[row - 1][minv] or dp[row - 1][second_minv] + arr[row][col];

    快手笔试题。 删除字符串中的3个或3个以上的连续数字,删除后,后面位置的字符向前补位,输出最后剩下的字符串。双指针。注意每次删除连续数字后,i向后后退两位。

    NO 416. 分割等和子集。 01背包,true/false问题。相当于每个数字的体积和价值相等,判断最终(sum/2)大小的背包所能装的最大价值是否恰好是(sum/2)。dp[i] = dp[i] or dp[i-num[j]];。存在两种数据情况:第一个: n <= 10000,最大值-最小值小于等于1000; 第二个:n <= 30,每个数都是int整数。在第一种情况中,可能存在负数值,背包问题不能解决负数值,可以将数组中的每个数减去最小值,保证全部为正数,sum最大可能为10^7,可以使用背包解法。第二种情况中,sum值可能非常大,不能用背包解法,用dfs(加速 折半搜索)。

    NO 377. 组合总和4。 完全背包,组合问题,如果组合问题需考虑元素之间的顺序,需将target放在外循环,将nums数组放在内循环。dp[i] += dp[i - nums[j]];

    04.12:

    NO 518. 零钱兑换2。 组合完全背包, 无顺序。初始化dp[0] = 1;

    NO 494. 目标和。 为整数数组中的每个数添加正号或负号,求使这些数字相加和为target的所有添加符号的方法数。类似01背包问题,从考虑每个数字取或者不取转换为每个数字取正号还是负号,所以不能省略dp数组的第一维。背包问题不能解决负数值,将sum减去可能取到的最小值(-1000)。类似思路同NO. 416中所述。

    NO 139. 单词拆分。 类似于完全背包问题,并且单词的组合是有顺序的。用map将字典中的单词做标记,两层for循环,外层遍历结束位置,内层遍历起始位置,动态规划dp[end]表示截止到end位置的字符串子串能否由字典中的单词拼接而成,更新dp[end]时,分两种情况讨论,分别为start == 0,以及start != 0

    NO 474. 一和零。 注意题目要求:“每个 0 和 1 至多被使用一次。”,即0和1可以不被全部使用。转换成01背包问题,不同的是此时相当于有两个背包,分别装0和1,容量对应给定的0和1的个数,数组中的字符串相当于装进去的物品。三重for循环,三维dp改进成二维dp,dp[i][j]表示用i0j1可以拼成的最多的字符串个数。

    04.13:

    NO 470. 用 Rand7() 实现 Rand10()。 Rand7()等概率产生1-7中的每个数,则tmp=7*(rand7()-1)+rand7(); 等概率产生1-49中的每个数,如果产生的数在1-40之间,则将产生的数模10再加1,即可等概率产生1-10中的每个整数;如果产生的数在41-49之间,则tmp=(tmp-40-1)*7+rand7(); 再次映射,等概率产生1-63中的每个数,如果产生的数在1-60之间,同上将产生的数模10再加1,等概率产生1-10中的每个整数;如果产生的数在61-63之间,则tmp=(tmp-60-1)*7+rand7(); 再次映射,等概率产生1-21中的每个数,再取模映射,如果产生的数恰好为21,则丢弃重新进入循环。

    NO 76. 最小覆盖子串。 双指针,滑动窗口 + unordered_map。注意对cnt做计数的时候,只对--mp[s[j]] >= 0以及++mp[s[i]] > 0的情况做加减计数,这样cnt就不用考虑不在t字符串中的字符,以及出现次数大于在t字符串中出现次数的字符了。避免频繁的调用substr()函数,只需要记录子串的起始位置以及长度(通过ji的位置确定)。char类型有256种,可以用256空间大小的数组代替map。

    NO 300. 最长上升子序列。 时间复杂度O(nlogn)。定义最长子序列数组subList,扫描原数组中的每一个数,是否大于当前subList中的最后一位数,如果大于,直接添到subList中,否则通过二分查找到subList中第一个大于nums[i]的数,替换。注意最后得到的subList并不一定是所求的最长上升子序列。int id = upper_bound(dp.begin(), dp.end(), nums[i]) - dp.begin();

    04.25:

    NO 289. 生命游戏。 要求原地算法解题。可以直接复制数组或用二维数组前缀和求解,需要新开辟空间;用位运算记录,原数组中每一位为0或1,在int中只占1bit,可以用剩下的其他位来记录变化情况(如第二低位,与2做或运算),最后将次低位移动到最低位(>>)。

    NO 5393. 可获得的最大点数。 给定一个一维数组,每次从开头或末尾选择一个数字,一共选择k次,求选择数字的最大和。保存数组的前缀和和后缀和,枚举前面取i个数字,后面取k - i个数字。前缀和后缀和数组可在index = 0处补0位,避免计算最大点数时越界。

    NO 498. 对角线遍历。 m*n矩阵中,按照左上对角线遍历数据,遍历顺序头尾相接。同样可以用NO5394的方法解决。但是本题目中,每一行数字数目都是满的,可以根据同一条对角线上(一共有m+n-1条对角线)相邻数字的位置变化规律,通过一次遍历完成题目。避免使用map结构造成的时间和空间的额外开销。

    NO 5394. 对角线遍历2。 按照左上方向对角线遍历二维数组。观察到同一条对角线方向上,横纵index之和相等,可以用map<int, vector<int>> mp 记录,mp.first记录横纵坐标之和,mp.second记录该条对角线上的所有数据。注意遍历时,第一维从大到小遍历。也可以用vector<pair<int, int>> store 来记录横纵坐标,自定义排序函数。

    04.27:

    NO 53. 最大子序和。 Kadane算法。给定一维整数数组,求最大子序和,其中原数组中包括负数。维护整数数组前缀和,当前缀和小于零时,前缀和置零,每次更新前缀和同时,更新答案ans = max(ans, pre_sum); 注意将ans初始化为nums[0], 防止该整数数组中全部为负数。

    NO 363. 矩形区域不超过K的最大数值和。 由NO53.引申而来,联想到维护前缀和。暴力方法:维护二维数组前缀和,随后枚举矩形区域的左上点坐标,以及右下点坐标,根据前缀和计算矩形区域的值,然后选择不大于K的值,更新答案。时间复杂度O(n^ 4); 枚举两列和下边 + 二分的方法(时间复杂度O(n^3 logn)):用set 以及lower_bound(pre_sum - k)实现二分,为什么是pre_sum - k?设从第0行到矩形区域上边围成的数值为a,则我们需要求的是pre_sum - a <= k,且越接近k越好,则整理有a >= pre_sum - k,且越接近pre_sum-k越好。

    NO 918. 环形子数组的最大和。 NO53.延伸。分为两种情况:1.组成最大和的所有数字都出现在原数组中;2.或者组成最大和的所有数字出现在环形数组中,即一定包括A[0]和A[n-1]。第一种情况可以用NO.53方法正常求解,第二种情况,设定包含A[0]的区间为[0, j],包含A[n-1]的区间为[i, n-1],根据题意可知j < i,即转化为在原数组中求子数组的最小值,且该最小值必须小于0,再用原数组总和减去该最小值。最终答案即为两种情况的最大值。

    面试题17.24. 最大子矩阵。 由NO53.引申而来,由一维数组引申为二维数组,并且返回左上角和右下角坐标。维护行前缀和的思路同NO363.,更新最大子矩阵时,维护前row行的最小值,同时维护左上角的横轴坐标。或者按照Kadane算法均可。

    04.28:

    NO 392. 判断子序列。 原问题—双指针一次遍历较长的字符串。后续挑战:预处理较长字符串t,用二维数组保存每个小写字母的位置vector<vector<int>> pos(26);,每个字母的位置由大到小, 判断字符串Si中某个字符是否存在于t中时,二分。

    NO 516. 最长回文子序列。 子序列 + 最大值 -> 动态规划。dp[i][j]表示从i位置到j位置的回文子序列最大长度,分为两种情况,当s[i] == s[j]时,dp[i][j] = dp[i+1][j-1] + 2;;当s[i] != s[j]时,dp[i][j] = max(dp[i+1][j], dp[i][j-1]);。遍历顺序可以外层for循环遍历长度,内层for循环遍历起点;也可以外层for循环反向遍历起点,内层for循环顺序遍历终点(终点位置要大于起点)。

    NO 225. 用队列实现栈。 可以用一个队列实现,也可以用两个队列实现。总体思想遵循队列先进先出,栈先进后出的原则。用一个队列时,push()操作需要将新加入的数交换到队头,交换方法为在压入新数后,将队列中的数重新压入一遍。每次操作时间复杂度为O(n),pop()操作直接从队头取出数即可,top()同理。用两个队列时,保证其中一个队列为空队列,做为缓存队列,push()操作直接将新加入的数压入非空队列中,每次时间复杂度为O(1),pop()操作时,将非空队列中的数依次压入空队列中,直到只剩下最后一个数,将这个数弹出,时间复杂度为O(n),top()操作同理。

    NO 232. 用栈实现队列。 总体思想遵循队列先进先出,栈先进后出的原则。根据负负得正->用两个栈实现队列,一个栈负责push,另一个栈负责pop。每次执行pop操作时,只有当负责pop的栈为空时,才将数据转入到该栈中。

    04.29:

    NO 54. 螺旋矩阵。 求n*m二维矩阵的顺时针(或逆时针)螺旋顺序。记录up/down/left/right四个边界位置,通过控制边界位置,不断压入元素。可以用while循环控制每条边的压入,每个while循环包括四个方向的遍历,每条边遍历完毕后,要及时判断是否退出循环。

    NO 6. Z字形变换。 找规律,按照给定的行数,第一行和最后一行具有相同的规律,与上一个位置在原字符串中的index差值为step = 2 * numRows - 2,其他行在step间,会插入Z字形的斜边上的数字,与上一个位置的index差值规律为2 * (numRows - row)

    NO 48. 旋转图像。 将n*n的二维矩阵顺时针(或逆时针)旋转90度。由于矩阵位置上的对称性,可以只考虑其中一个象限,要注意当n为奇数时,所选象限长宽一个为n/2,一个为n/2 + 1,因为所选象限中每一个位置只应该变换一次。变换映射规律为matrix[i][j] = matrix[n - 1 - j][i];

    展开全文
  • 删除排序数组中的重复项双指针:283。移动零 20210202排序:面试题17.15。最长单词等级:524。通过删除字母匹配到字典里最长单词 20210129排序:75。颜色分类(十大排序) 20210126数据结构:146.LRU缓存机制数据...
  • 数组总结

    2020-07-02 00:08:28
    数组类总结 找规律 螺旋矩阵 (medium) 螺旋矩阵II (medium) 旋转图像 (medium) 矩阵置零 (medium) 除自身以外数组乘积 (medium) 搜索二维矩阵II (medium 二分查找) ...删除排序数组中的重复项 (easy 双指针).

    哈希

    两数之和:easy

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

    示例:

    给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
    

    维护一个hash表,边遍历数组边存储值到hash表中,当遍历到nums[i]时,如果hash[target - nums[i]] > 0,那么就找到了符合条件的两个值

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    C++代码

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> res(2,-1);
            unordered_map<int, int> hash;
            for(int i = 0; i < nums.size(); i++) {
                if(hash.count(target - nums[i]) != 0) {
                    res[0] = hash[target - nums[i]];
                    res[1] = i;
                    break;
                }
                hash[nums[i]] = i;
            }
            return res;
        }
    };
    

    两个数组的交集:easy

    给定两个数组,编写一个函数来计算它们的交集。

    示例 1:

    输入: nums1 = [1,2,2,1], nums2 = [2,2]
    输出: [2]
    

    示例 2:

    输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出: [9,4]
    

    说明:

    • 输出结果中的每个元素一定是唯一的。

    • 我们可以不考虑输出结果的顺序。

    • 方法1

    将数组nums1的元素放入一个set中,然后遍历nums2的元素nums2[i],判断它是否在set中,如果在set中,则说明这个元素是交集的部分,将它加入结果中。

    nums1的大小为m,数组nums2的大小为n

    • 时间复杂度:O(m + n)
    • 空间复杂度:O(m)

    C++代码

    class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            if(nums1.empty() || nums2.empty())
                return vector<int>();
            
            unordered_set<int> st;
            for(auto a : nums1)
                st.insert(a);
            
            vector<int> res;
            for(int a : nums2)
            {
                if(st.count(a) > 0)
                {
                    res.push_back(a);
                    st.erase(a);
                }
            }
            
            return res;
        }
    };
    
    • 方法2:排序 +双指针

    先将nums1nums2排序(从小到大排序),维护一个set存放交集元素,定义两个指针p1p2分别从nums1nums2出发,处理情况如下:

    1. 如果nums1[p1] == nums2[p2],则将numns[p1]放入set,同时++p1,++p2
    2. 否则,nums1[p1] < nums2[p2] ? ++p1 : ++p2

    直到p1p2到达数组尾部。

    最后将set中的元素放入结果数组中即可。

    nums1的大小为m,数组nums2的大小为n

    • 时间复杂度:O(m log m + n log n)
    • 空间复杂度:O(max(m,n))

    C++代码

    class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            sort(nums1.begin(),nums1.end());
            sort(nums2.begin(),nums2.end());
            
            vector<int> res;
            set<int> st;
            int p1 = 0,p2 = 0;
            while(p1 < nums1.size() && p2 < nums2.size())
            {
                if(nums1[p1] == nums2[p2])
                {
                    st.insert(nums1[p1]);
                    ++p1;
                    ++p2;
                }
                else{
                    nums1[p1] < nums2[p2] ? ++p1 : ++p2;
                }
            }
            
            for(auto a : st) res.push_back(a);
            
            return res;
        }
    };
    
    • 方法3

    现将nums1从小到大排序,遍历数组nums2的每一个元素nums2[i],同时在nums1中二分查找nums2[i],如果能找到nums2[i],则将它加入set中;否则,跳过。最后,将set中的元素放入结果数组即可。

    nums1的大小为m,数组nums2的大小为n

    • 时间复杂度:O((m + n) log m)
    • 空间复杂度:O(min(m,n))

    C++代码

    class Solution {
    public:
        bool binarySearch(const vector<int>& vec,int target)
        {
            int l = 0,r = vec.size() - 1;
            while(l <= r)
            {
                int m = (l + r) / 2;
                if(vec[m] < target) l = m+1;
                else if(vec[m] > target) r = m-1;
                else return true;
            }
            
            return false;
        }
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            sort(nums1.begin(),nums1.end());
            
            set<int> st;
            vector<int> res;
            for(auto a : nums2)
            {
                if(binarySearch(nums1,a))
                    st.insert(a);
            }
            
            for(auto a : st) res.push_back(a);
            
            return res;
        }
    };
    

    两个数组的交集II:easy

    给定两个数组,编写一个函数来计算它们的交集。

    示例 1:

    输入: nums1 = [1,2,2,1], nums2 = [2,2]
    输出: [2,2]
    

    示例 2:

    输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出: [4,9]
    

    说明

    • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
    • 我们可以不考虑输出结果的顺序。

    进阶:

    • 如果给定的数组已经排好序呢?你将如何优化你的算法?

    • 如果 nums1 的大小比 nums2 小很多,哪种方法更优?

    • 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

    • 方法1

    unordered_map无序哈希表)来建立nums1中字符和其出现个数之间的映射, 然后遍历nums2数组,如果当前字符在哈希表中的个数大于0,则将此字符加入结果中,然后哈希表的对应值自减1。

    nums1的大小为m,数组nums2的大小为n

    • 时间复杂度:O(m + n)
    • 空间复杂度:O(max(m,n))

    C++代码

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            vector<int> res;
            unordered_map<int,int> mp;
            
            for(auto a : nums1) ++mp[a];
            for(auto b : nums2)
            {
                if(mp[b] > 0)
                {
                    res.push_back(b);
                    --mp[b];
                }
            }
            
            return res;
        }
    };
    

    优化空间:哈希表统计两数组中长度较小的那个数组的元素个数。

    • 时间复杂度:O(m + n)
    • 空间复杂度:O(min(m,n))

    C++代码

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            vector<int> res;
            
            unordered_map<int,int> mp;
            
            if(nums1.size() > nums2.size())
            {
                //长度较小的数组拷贝到临时数组
                vector<int> tmp(nums2);
                nums2 = nums1;
                nums1 = tmp;
            }
            
            for(auto a : nums1) ++mp[a];
            for(auto b : nums2)
            {
                if(mp[b] > 0)
                {
                    res.push_back(b);
                    --mp[b];
                }
            }
            
            return res;
        }
    };
    
    • 方法2

    先将nums1nums2排序(从小到大排序),定义两个指针p1p2分别从nums1nums2出发,处理情况如下:

    1. 如果nums1[p1] == nums2[p2],则将numns[p1]放入结果,同时++p1,++p2
    2. 否则,nums1[p1] < nums2[p2] ? ++p1 : ++p2

    直到p1p2到达数组尾部。

    nums1的大小为m,数组nums2的大小为n

    • 时间复杂度:O(m log m + n log n)
    • 空间复杂度:O(max(m,n))

    C++代码

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            sort(nums1.begin(),nums1.end());
            sort(nums2.begin(),nums2.end());
            
            vector<int> res;
            int p1 = 0,p2 = 0;
            while(p1 < nums1.size() && p2 < nums2.size())
            {
                if(nums1[p1] == nums2[p2])
                {
                    res.push_back(nums1[p1]);
                    ++p1;
                    ++p2;
                }
                else{
                    nums1[p1] < nums2[p2] ? ++p1 : ++p2;
                }
            }
            
            return res;
        }
    };
    

    存在重复元素:easy

    给定一个整数数组,判断是否存在重复元素。

    如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

    示例 1:

    输入: [1,2,3,1]
    输出: true
    

    示例 2:

    输入: [1,2,3,4]
    输出: false
    

    利用unordered_set无序集合,遍历数组的时候将元素放入集合中,找出已经在集合中出现的元素就是重复的元素

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    C++代码

    class Solution {
    public:
        bool containsDuplicate(vector<int>& nums) {
            if(nums.empty())
                return false;
            
            int len=nums.size();
            unordered_set<int> st;
            for(auto a:nums)
            {
                if(st.find(a) != st.end())
                    return true;
                else
                    st.insert(a);
            }
            
            return false;
        }
    };
    

    求众数:easy

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于n/2 ⌋ 的元素。

    你可以假设数组是非空的,并且给定的数组总是存在众数。

    示例 1

    输入:[3,2,3]
    输出:3
    

    示例 2

    输入:[2,2,1,1,1,2,2]
    输出:2
    

    方法1:哈希表

    基于原数组建立哈希表,key为元素,value为元素个数,找出value > len/2的元素就是众数

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    C++代码

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            unordered_map<int,int> mp;
            int len = nums.size();
            int res = INT_MIN;
            for(auto a : nums)
            {
                mp[a]++;
                if(mp[a] > len/2) 
                {
                    res = a;
                    break;
                }
            }
            
            return res;
        }
    };
    

    方法2:摩尔投票法

    参见博客

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int cnt = 0;
            int res = 0;
            for(int i=0;i<nums.size();i++)
            {
                if(cnt == 0)
                {
                    cnt++;
                    res = nums[i];
                }
                else if(nums[i] == res)
                    cnt++;
                else
                    cnt--;
            }
            
            return res;
            
        }
    };
    

    有效的数独:medium

    判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

    1. 数字 1-9 在每一行只能出现一次。
    2. 数字 1-9 在每一列只能出现一次。
    3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫格内只能出现一次。

    img

    上图是一个部分填充的有效的数独。

    数独部分空格内已填入了数字,空白格用 '.' 表示。

    示例 1:

    输入:
    [
      ["5","3",".",".","7",".",".",".","."],
      ["6",".",".","1","9","5",".",".","."],
      [".","9","8",".",".",".",".","6","."],
      ["8",".",".",".","6",".",".",".","3"],
      ["4",".",".","8",".","3",".",".","1"],
      ["7",".",".",".","2",".",".",".","6"],
      [".","6",".",".",".",".","2","8","."],
      [".",".",".","4","1","9",".",".","5"],
      [".",".",".",".","8",".",".","7","9"]
    ]
    输出: true
    

    示例 2:

    输入:
    [
      ["8","3",".",".","7",".",".",".","."],
      ["6",".",".","1","9","5",".",".","."],
      [".","9","8",".",".",".",".","6","."],
      ["8",".",".",".","6",".",".",".","3"],
      ["4",".",".","8",".","3",".",".","1"],
      ["7",".",".",".","2",".",".",".","6"],
      [".","6",".",".",".",".","2","8","."],
      [".",".",".","4","1","9",".",".","5"],
      [".",".",".",".","8",".",".","7","9"]
    ]
    输出: false
    解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。
         但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
    

    说明:

    • 一个有效的数独(部分已被填充)不一定是可解的。
    • 只需要根据以上规则,验证已经填入的数字是否有效即可。
    • 给定数独序列只包含数字 1-9 和字符 '.'
    • 给定数独永远是 9x9 形式的。

    解答

    要判断是否出现重复元素,只需要遍历的时候用哈希表记录每一个字符ch(介于'1'~'9'之间)出现的次数,当字符再次出现的时候判断ch在哈希表中的次数是否大于0,就可以判断是否出现重复的字符。由于在每一行、每一列和每一个3x3宫格内都不能出现重复的字符,那么需要以逐行、逐列和逐个3x3宫格的方式分别遍历,同时利用哈希表记录并判断,便能得出结果。

    • 时间复杂度:O(9x9) = O(1)
    • 空间复杂度:O(9) = O(1)

    C++代码

    class Solution {
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
            unordered_map<char,int> mp;
            int row = board.size();
            int col = board[0].size();
            
            for(int i=0;i<row;i++)
            {
                for(int j=0;j<col;j++)
                {
                    int ch = board[i][j];
                    if(ch != '.')
                    {
                        mp[ch]++;
                        if(mp[ch] > 1)
                            return false;
                    }
                }
                
                mp.clear();
            }
            
            for(int i=0;i<col;i++)
            {
                for(int j=0;j<row;j++)
                {
                    char ch = board[j][i];
                    if(ch != '.')
                    {
                        mp[ch]++;
                        if(mp[ch] > 1)
                            return false;
                    }
                }
                
                mp.clear();
            }
            
            for(int i=0;i<row;i+=3)
            {
                for(int j=0;j<col;j+=3)
                {
                    for(int x=i;x<i+3;x++)
                        for(int y=j;y<j+3;y++)
                        {
                            char ch=board[x][y];
                            if(ch != '.')
                            {
                                mp[ch]++;
                                if(mp[ch] > 1)
                                    return false;
                            }
                        }
                    
                    mp.clear();
                }
            }
            
            return true;
        }
    };
    

    双指针

    三数之和:medium

    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 abc ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

    注意:答案中不可以包含重复的三元组。

    例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
    
    满足要求的三元组集合为:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]
    

    对整个数组排序,先遍历数组取三数中的第一个数nums[i],注意num[i]只到数组的倒数第三个元素,然后剩下两个数需要满足条件target = 0 - nums[i],这两个数在数组中num[i]后面部分,维持两个双指针lr,令tmp = nums[l] + nums[r],处理情况如下:

    1. 如果tmp < target,则l右移一步;
    2. 如果tmp > target,则r左移一步;
    3. 否则,满足条件,添加两个数到结果数组中,同时将lr分别右移和左移到下一个不重复的元素处。

    注意:遍历数组的时候取第一个数的时候过滤重复元素,可以提高查找效率

    • 时间复杂度:O(n2)
    • 空间复杂度:O(1)
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            int len = nums.size();
            if(len < 3)
                return vector<vector<int>>();
            
            sort(nums.begin(),nums.end());
            vector<vector<int>> res;
            for(int i=0;i<len-2;i++)
            {
                if(i == 0 || (i > 0 && nums[i] != nums[i-1]))
                {
                    int l = i+1;
                    int r = len-1;
                    int target = 0 - nums[i];
                    while(l < r)
                    {
                        int tmp = nums[l] + nums[r];
                        if(target > tmp)
                        {
                            l++;
                        }
                        else if(target < tmp)
                        {
                            r--;
                        }
                        else{
                            res.push_back({nums[i],nums[l],nums[r]});
                            l++;
                            r--;
                            while(l < r && nums[l] == nums[l-1])
                                l++;
                            while(l < r && nums[r] == nums[r+1])
                                r--;
                        }
                    }
                    
                }
            }
            
            return res;
        }
    };
    

    最接近的三数之和:medium

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

    例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
    
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
    

    思路和三数之和类似:先排序数组,遍历数组取第一个数(只到数组倒数第三个元素),剩下两个数在第一个数的右边部分,定义双指针l和r分别指向i+1len-1,当前三数和tmp = nums[l] + nums[r] + nums[i],然后向中间移动,移动规则如下:

    1. 如果tmp < target,则++l,同时比较abs(tmp - target)abs(res - target),取较小值对应的那个三数和给结果res
    2. 如果tmp > target,则–r,同时比较abs(tmp - target)abs(res - target),取较小值对应的那个三数和给结果res
    3. 如果tmp == target,则tmp即为所求
    • 时间复杂度:O(n2)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            sort(nums.begin(),nums.end());
            int len = nums.size();
            if(len < 3) return INT_MAX;
            
            int res = nums[0] + nums[1] + nums[2];
            
            for(int i=0;i<len-2;i++)
            {
                if(i == 0 || nums[i] != nums[i-1])
                {
                    int l = i+1,r = len-1;
                    while(l < r)
                    {
                        int tmp = nums[l] + nums[r] + nums[i];
                        if(tmp < target)
                        {
                            res = abs(res - target) < abs(target - tmp) ? res : tmp;
                            ++l;
                        }
                        else if(tmp > target)
                        {
                            res = abs(res - target) < abs(target - tmp) ? res : tmp;
                            --r;
                        }
                        else{
                            return tmp;
                        }
                        
                        if(i > 0)
                        {
                            while(l < r && nums[l] == nums[l-1]) ++l;
                            while(l < r && nums[r] == nums[r+1]) --r;
                        }
                    }
                }
                
            }
            
            return res;
        }
    };
    

    四数之和:medium

    双指针

    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>>res;
            if(nums.size()<4)
                return res;
            sort(nums.begin(),nums.end());
            for(int i=0;i<nums.size()-3;i++)
            {
                if(i>0 && nums[i]==nums[i-1])//去除重复
                    continue;
                for(int j=i+1;j<(int)nums.size()-2 ;j++)
                {
                    if(j>i+1 && nums[j]==nums[j-1])//去除重复
                        continue;
                    int left=j+1;
                    int right=nums.size()-1;
                    while(left<right)
                    {
                        int temp=nums[i]+nums[j]+nums[left]+nums[right];
                        if(temp==target)
                        {
                            res.push_back({nums[i],nums[j],nums[left],nums[right]});
                            while(left<right && nums[left]==nums[left+1])//去除重复
                                left++;
                            while(left<right && nums[right]==nums[right-1])//去除重复
                                right--;
                            left++;
                            right--;
                        }
                        else if(temp<target)
                            left++;
                        else
                            right--;
                    }
                }
            }
    
            return res;
            
        }
    };
    

    删除排序数组中的重复项:easy

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

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    示例 1:

    给定数组 nums = [1,1,2], 
    
    函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
    
    你不需要考虑数组中超出新长度后面的元素。
    

    示例 2:

    给定 nums = [0,0,1,1,1,2,2,3,3,4],
    
    函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
    
    你不需要考虑数组中超出新长度后面的元素。
    
    class Solution {
    public:
        int removeDuplicates(vector<int>& nums) {
            if(nums.empty())
                return 0;
            int j=0;
            for(int i=1;i<nums.size();i++)
            {
               if(nums[i]!=nums[i-1])
                   j++;
                nums[j]=nums[i];
            }
    
            return j+1;
        }
    };
    

    移动零:easy

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    示例:

    输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]
    

    说明:

    1. 必须在原数组上操作,不能拷贝额外的数组。
    2. 尽量减少操作次数。

    双指针法,快指针i遍历一遍数组,当快指针的元素非零时,令慢指针idx的元素等于快指针元素,同时慢指针前进一步。最后,所有的非零元素都移到了数组前半部分(相对顺序不变),然后将之后的元素全部置0。

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        void moveZeroes(vector<int>& nums) {
            if(nums.empty())
                return;
            
            int idx = 0;
            for(int i=0;i<nums.size();i++)
            {
                if(nums[i] != 0)
                {
                    nums[idx++] = nums[i];
                }
            }
            
            for(;idx<nums.size();idx++)
                nums[idx] = 0;
            
            return;
        }
    };
    

    判断子序列:medium

    给定字符串 st ,判断 s 是否为 t 的子序列。

    你可以认为 st 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

    字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace“是”abcde“的一个子序列,而”aec"不是)。

    示例 1:

    s = “abc”, t = “ahbgdc

    返回 true.

    示例 2:

    s = “axc”, t = “ahbgdc

    返回 false.

    后续挑战 :

    如果有大量输入的 S,称作S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

    双指针法,设置指针ij分别指向字符串st

    1. 如果s[i] == t[j],则i前进一步,j前进一步
    2. 否则,j前进一步

    最后,判断指针i是否走完s,就能判断s是否为t的子序列。

    • 时间复杂度:O(m+n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        bool isSubsequence(string s, string t) {
            int len = s.size();
            int len1 = t.size();
            
            if(len > len1) return false;
            int i = 0,j = 0;
            while(i < len && j < len1)
            {
                if(s[i] == t[j])
                {
                    i++;
                   
                }
                
                j++;
            }
            
            if(i == len) return true;
            return false;
        }
    };
    

    盛最多水的容器:medium

    给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai)(i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

    说明:你不能倾斜容器,且 n 的值至少为 2。

    1

    图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

    示例:

    输入: [1,8,6,2,5,4,8,3,7]
    输出: 49
    

    双指针法,定义两个指针lr分别指向数组两端,两个指针向中间移动,移动规则如下:

    1. 如果height[l] < height[r],则++l
    2. 否则,–r

    每走一步,计算容器装水量为左右边缘较小的那个高度乘边缘的的距离min(height[l],height[r]) * (r - l),然后和结果比较去较大值。

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        int maxArea(vector<int>& height) {
            int len = height.size();
            if(len == 0) return 0;
            
            int res = 0;
            int l = 0;
            int r = len - 1;
            while(l < r)
            {
                int tmp = min(height[l],height[r]);
                int sum = (r - l)*tmp;
                if(height[l] < height[r])
                    ++l;
                else
                    --r;
                
                res = max(res,sum);
                
                while(l < r && tmp == height[l]) ++l;
                while(l < r && tmp == height[r]) --r;
            }
            
            return res;
        }
    };
    

    合并两个有序数组:easy

    合并两个有序数组

    给定两个有序整数数组 nums1nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

    说明:

    • 初始化 nums1nums2 的元素数量分别为 mn
    • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

    示例:

    输入:
    nums1 = [1,2,3,0,0,0], m = 3
    nums2 = [2,5,6],       n = 3
    
    输出: [1,2,2,3,5,6]
    

    双指针法,思路同合并两个有序链表

    • 时间复杂度:O(m + n)
    • 空间复杂度:O(m + n)

    C++代码

    class Solution {
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
           for(int i=m,j=0;i<m+n ;i++)
               nums1[i] = nums2[j++];
            
            vector<int> vec(m + n,0);
            
            int l = 0;
            int r = m;
            int cnt = 0;
            while(l < m && r < m + n)
            {
                vec[cnt++] = nums1[l] < nums1[r] ? nums1[l++] : nums1[r++];
            }
            
            while(l < m)
                vec[cnt++] = nums1[l++];
            while(r < m + n)
                vec[cnt++] = nums1[r++];
            
            copy(vec.begin(),vec.end(),nums1.begin());
        }
    };
    

    找规律

    螺旋矩阵:medium

    54. 螺旋矩阵
    给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

    示例 1:

    输入:
    [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
    ]
    输出: [1,2,3,6,9,8,7,4,5]

    示例 2:

    输入:
    [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9,10,11,12]
    ]
    输出: [1,2,3,4,8,12,11,10,9,5,6,7]

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int>res;
            if(matrix.empty())
                return res;
            int top=0,bottom=matrix.size()-1,left=0,right=matrix[0].size()-1;
            while(top<=bottom && left<=right)
            {
                for(int i=left;i<=right;i++)
                {
                    res.push_back(matrix[top][i]);
                }
                for(int i=top+1;i<=bottom;i++)
                    res.push_back(matrix[i][right]);
                for(int i=right-1;i>=left && bottom>top;i--)
                    res.push_back(matrix[bottom][i]);
                for(int i=bottom-1;i>top && right>left;i--)
                    res.push_back(matrix[i][left]);
                top++;
                bottom--;
                left++;
                right--;
            }
    
            return res;
    
    
        }
    };
    

    螺旋矩阵II:medium

    LeetCode中文

    LeetCode英文

    给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

    示例:

    输入: 3
    输出:
    [
     [ 1, 2, 3 ],
     [ 8, 9, 4 ],
     [ 7, 6, 5 ]
    ]
    

    思路和 螺旋矩阵 相同,还是分层处理,不过螺旋矩阵是从矩阵读取值,这一题是写入值到矩阵。可以定义一个变量cnt用于全局计数,直到cnt等于n2的时候终止写入。

    • 时间复杂度:O(n2)
    • 空间复杂度:O(n2)

    C++代码

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>>res(n,vector<int>(n));
    
            int top=0,bottom=n-1,left=0,right=n-1;
            int j=1;
            while(top<=bottom  && left<=right)
            {
                for(int i=left;i<=right;i++)
                {
                    res[top][i]=j;
                    j++;
                }
                for(int i=top+1;i<=bottom;i++)
                {
                    res[i][right]=j;
                    j++;
                }
                for(int i=right-1;i>=top && top<bottom;i--)
                {
                    res[bottom][i]=j;
                    j++;
                }
                for(int i=bottom-1;i>top && left<right;i--)
                {
                    res[i][left]=j;
                    j++;
                }
                top++;
                bottom--;
                left++;
                right--;
            } 
    
            return res;
    
        }
    };
    

    旋转图像:medium

    48. 旋转图像
    给定一个 n × n 的二维矩阵表示一个图像。

    将图像顺时针旋转 90 度。

    说明:

    你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

    示例 1:

    给定 matrix =
    [
    [1,2,3],
    [4,5,6],
    [7,8,9]
    ],

    原地旋转输入矩阵,使其变为:
    [
    [7,4,1],
    [8,5,2],
    [9,6,3]
    ]

    示例 2:

    给定 matrix =
    [
    [ 5, 1, 9,11],
    [ 2, 4, 8,10],
    [13, 3, 6, 7],
    [15,14,12,16]
    ],

    原地旋转输入矩阵,使其变为:
    [
    [15,13, 2, 5],
    [14, 3, 4, 1],
    [12, 6, 8, 9],
    [16, 7,10,11]
    ]

    class Solution {
    public:
        void rotate(vector<vector<int>>& matrix) {
            int n=matrix.size();
    
            // transpose matrix
            for (int i = 0; i < n; i++)
            {
                for (int j = i; j < n; j++)
                {
                    int tmp = matrix[j][i];
                    matrix[j][i] = matrix[i][j];
                    matrix[i][j] = tmp;
                }
            }
        // reverse each row
            for (int i = 0; i < n; i++) 
            {
               for (int j = 0; j < n / 2; j++) 
                {
                   int tmp = matrix[i][j];
                   matrix[i][j] = matrix[i][n - j - 1];
                   matrix[i][n - j - 1] = tmp;
                }
    
            }
        }
    };
    

    矩阵置零:medium

    73. 矩阵置零
    给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。

    示例 1:

    输入:
    [
    [1,1,1],
    [1,0,1],
    [1,1,1]
    ]
    输出:
    [
    [1,0,1],
    [0,0,0],
    [1,0,1]
    ]

    示例 2:

    输入:
    [
    [0,1,2,0],
    [3,4,5,2],
    [1,3,1,5]
    ]
    输出:
    [
    [0,0,0,0],
    [0,4,5,0],
    [0,3,1,0]
    ]
    进阶:

    一个直接的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
    一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
    你能想出一个常数空间的解决方案吗?

    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) {
            if(matrix.empty())
                return;
            int m=matrix.size();
            int n=matrix[0].size();
            set<int>row,cols;
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(matrix[i][j]==0)
                    {
                        row.insert(i);
                        cols.insert(j);
                    }
                }
            }
    
            // for(int i=0;i<m;i++)
            // {
            //     for(int j=0;j<n;j++)
            //     {
            //         if(row.find(i)!=row.end() || cols.find(j)!=cols.end())
            //             matrix[i][j]=0;
            //     }
            // }
    
            set<int>::iterator it;
            for(int i=0;i<m;i++)
            {
                for(it=cols.begin();it!=cols.end();it++)
                    matrix[i][*it]=0;
            }
            for(int i=0;i<n;i++)
            {
                for(it=row.begin();it!=row.end();it++)
                    matrix[*it][i]=0;
            }
        }
    };
    

    除自身以外数组的乘积:medium

    238.除自身以外数组的乘积

    给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

    示例:

    输入: [1,2,3,4]
    输出: [24,12,8,6]
    

    说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

    进阶

    你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

    方法1

    由于output[i] = nums[0]*nums[1]*...*nums[i-1]*nums[i+1]*...*nums[len-1],可以将output[i]分为两部分,前半部分为C[i] = nums[0]*nums[1]*...*nums[i-1],后半部分为D[i] = nums[i+1]*...*nums[len-1]。可以发现规律,数组C和D相邻元素之间存在递推关系:

    C[i] = C[i-1]*nums[i-1] (i = 1~len-1)
    D[i] = D[i+1]*nums[i+1] (i = 0~len-2)
    

    因此求出数组output的每一项output[i] = C[i]*D[i]

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    C++代码

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int len = nums.size();
            if(len == 0) return nums;
            
            vector<int> res(len,1);
            vector<int> C(len,1);
            vector<int> D(len,1);
            for(int i=1;i<len;i++)
            {
                C[i] = nums[i-1]*C[i-1];
            }
            
            for(int i=len-2;i>=0;i--)
            {
                D[i] = D[i+1]*nums[i+1];
            }
            
            for(int i=0;i<len;i++)
            {
                res[i] = C[i]*D[i];
            }
            
            return res;
        }
    };
    

    方法2:优化空间复杂度

    先将数组C的数值计算到输出数组res中,然后定义一个变量tmp代替数组D的递推关系计算,对数组res从后向前进行递推计算得出最终结果。可以优化空间复杂度到常数时间。

    • 时间复杂度:O(n) (输出数组不被视为额外空间)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int len = nums.size();
            if(len == 0) return nums;
            
            vector<int> res(len,1);
            for(int i=1;i<len;i++)
            {
                res[i] = res[i-1] * nums[i-1];
            }
            
            int tmp = 1;
            for(int i=len-2;i>=0;i--)
            {
                tmp *= nums[i+1];
                res[i] *= tmp; 
            }
            
            return res;
        }
    };
    

    搜索二维矩阵:medium,二分查找

    74. 搜索二维矩阵

    编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

    每行中的整数从左到右按升序排列。
    每行的第一个整数大于前一行的最后一个整数。
    示例 1:

    输入:
    matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
    ]
    target = 3
    输出: true

    示例 2:

    输入:
    matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
    ]
    target = 13
    输出: false

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m=matrix.size();
            if(m==0)
                return false;
            int n=matrix[0].size();
            int left=0,right=m*n-1;
            int mid,mid_matrix;
            while(left<=right)
            {
                mid=(left+right)/2;
                mid_matrix=matrix[mid/n][mid%n];
                if(target==mid_matrix)
                    return true;
                else if(target<mid_matrix)
                    right=mid-1;
                else
                    left=mid+1;
    
            }
            return false;    
        }
    };
    
            if(matrix.empty())
                return false;
            int row=0;
            int column=matrix[0].size()-1;
            while(row<matrix.size()&& column>=0)
            {
                if(target==matrix[row][column])
                    return true;
                else if(target<matrix[row][column])
                    column--;
                else
                    row++;
            }
            return false;
    

    其它

    杨辉三角:easy

    给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

    1

    在杨辉三角中,每个数是它左上方和右上方的数的和。

    示例:

    输入: 5
    输出:
    [
         [1],
        [1,1],
       [1,2,1],
      [1,3,3,1],
     [1,4,6,4,1]
    ]
    
    • 解答

    利用杨辉三角的性质,利用上一行的数值推导出下一行,推导关系式为:

    • 时间复杂度:O(n2)
    • 空间复杂度:O(n2)

    C++代码

    class Solution {
    public:
        vector<int> transform(vector<int> vec)
        {
            vector<int> res;
            res.push_back(1);
            int len = vec.size();
            for(int i=1;i<len;i++)
            {
                res.push_back(vec[i-1] + vec[i]);
            }
            
            res.push_back(1);
            return res;
            
        }
        
        vector<vector<int>> generate(int numRows) {
            vector<vector<int>> res;
            if(numRows == 0)
                return res;
            if(numRows == 1)
            {
                res.push_back({1});
                return res;
            }
            
            res.push_back({1});
            for(int i=1;i<numRows;i++)
            {
                res.push_back(transform(res[i-1]));
            }
            
            return res;
        }
    };
    

    Python代码

    
    

    缺失数字:easy

    给定一个包含 0, 1, 2, ..., nn 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

    示例 1:

    输入: [3,0,1]
    输出: 2
    

    示例 2:

    输入: [9,6,4,2,3,5,7,0,1]
    输出: 8
    

    说明:

    你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

    方法1:位运算

    将原数组的所有元素和0~n的所有数字做异或运算,得到结果就是缺失的数字

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int res = 0;
            for(int i=0;i<nums.size();i++)
            {
                res ^= (i + 1) ^ nums[i];
            }
            
            return res;
        }
    };
    

    方法2:等差数列

    等差数列求0~n的和减去数组所有元素相加得到的和即为缺失的数字

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int sum = 0;
            int n = nums.size();
            for(auto num : nums) sum += num;
            return (int)((1 + n) * n / 2) - sum;
        }
    };
    

    旋转数组:easy

    189.旋转数组

    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    示例 1:

    输入: [1,2,3,4,5,6,7] 和 k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1 步: [7,1,2,3,4,5,6]
    向右旋转 2 步: [6,7,1,2,3,4,5]
    向右旋转 3 步: [5,6,7,1,2,3,4]
    

    示例 2:

    输入: [-1,-100,3,99] 和 k = 2
    输出: [3,99,-1,-100]
    解释: 
    向右旋转 1 步: [99,-1,-100,3]
    向右旋转 2 步: [3,99,-1,-100]
    

    说明:

    • 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    • 要求使用空间复杂度为 O(1) 的原地算法。
    • 方法1

    设数组的长度为lenklen取模得到k1 = k % len,开辟一个新数组cp拷贝numsnums的值清空,然后进行如下步骤:

    1. cp数组的最后k1个元素添加到数组nums尾部
    2. cp数组的开始len-k1个元素添加到数组nums尾部
    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    C++代码

    class Solution {
    public:
        void rotate(vector<int>& nums, int k) {
            int len = nums.size();
            int k1 = k%len;
            
            vector<int> cp(nums);
            nums.clear();
            
            copy(cp.end() - k1,cp.end(),back_inserter(nums));
            copy(cp.begin(),cp.end() - k1,back_inserter(nums));
        }
    };
    
    • 方法2

    设数组的长度为lenklen取模得到k1 = k % len,然后进行如下步骤:

    1. 反转数组的最后k1个元素
    2. 反转数组的前面len - k1个元素
    3. 反转整个数组

    最后得到的数组的就是旋转之后的数组

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        void rotate(vector<int>& nums, int k) {
            if(k == nums.size())
                return;
            
            int len = nums.size();
            int k1 = k % len;
            
            reverse(nums.begin(),nums.end() - k1);
            reverse(nums.end() - k1,nums.end());
            reverse(nums.begin(),nums.end());
        }
    };
    

    寻找重复数:medium

    278.寻找重复数

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

    示例 1:

    输入: [1,3,4,2,2]
    输出: 2
    

    示例 2:

    输入: [3,1,3,4,2]
    输出: 3
    

    说明

    • 不能更改原数组(假设数组是只读的)。
    • 只能使用额外的 O(1) 的空间。
    • 时间复杂度小于 O(n2) 。
    • 数组中只有一个重复的数字,但它可能不止重复出现一次。

    遍历数组,判断当前元素nums[i]是否和位置i+1相等:

    1. 如果nums[i] == i+1,则nums[i]位于它自己的位置,++i遍历下一个元素;
    2. 否则,找到位置是nums[i]-1位置的元素nums[nums[i] - 1]
      • 如果nums[nums[i] - 1] == nums[i],则找到重复元素nums[i]
      • 否则,交换nums[nums[i] - 1]nums[i]
        重复情况2的过程,直到nums[i] == i+1时,执行情况1
    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            if(nums.empty())
                return 0;
            
            for(int i=0;i<nums.size();i++)
            {
                while(nums[i] != i+1)
                {
                    int tmp = nums[i];
                    if(nums[tmp-1] == tmp)
                        return tmp;
                    swap(nums[i],nums[tmp-1]);
                }
            }
            
            return -1;
        }
    };
    

    合并区间:medium

    56. 合并区间

    给出一个区间的集合,请合并所有重叠的区间。

    示例 1:

    输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

    示例 2:

    输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

    class Solution {
    public:
    
        vector<vector<int>> merge(vector<vector<int>>& intervals) {
            vector<vector<int>>res;
            if(intervals.size()==0 || intervals.size()==1)
                return intervals;
            sort(intervals.begin(),intervals.end(),[&,this](vector<int>&v1,vector<int>&v2)
            {return v1[0]<v2[0];});
            for(int i=0;i<intervals.size();i++)
            {
                vector<int>temp=intervals[i];
                while(i+1<intervals.size() && temp[1]>=intervals[i+1][0])//循环
                {
                    ++i;
                    temp[1]=max(temp[1],intervals[i][1]);
                }
                res.push_back(temp);
            }
    
            return res;
        }
    };
    

    下一个排列:medium

    LeetCode中文

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

    如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

    必须原地修改,只允许使用额外常数空间。

    以下是一些例子,输入位于左侧列,其相应输出位于右侧列。

    1,2,31,3,2
    3,2,11,2,3
    1,1,51,5,1

    此题需要找出规律,举一个例子来说明,有如下的一个数组

    1  2  7  4  3  1
    

    下一个排列为:

    1  3  1  2  4  7
    

    那么是如何得到的呢,我们通过观察原数组可以发现,如果从末尾往前看,数字逐渐变大,到了2时才减小的,然后我们再以这个2的位置的后一个位置开始,从前往后找第一个比2大的数字,是3,那么我们交换2和3,再把此时3后面的所有数字(不包括3的位置)反转一下即可,步骤如下:

    1  2  7  4  3  1
    
    1  2  7  4  3  1
    
    1  3  7  4  2  1
    
    1  3  1  2  4  7
    

    再举几个例子验证仍然符合这个规律。因此,处理过程可总结以下几个步骤:

    1. 从后往前遍历数组,找到数值开始减小的那个位置idx,即nums[idx-1] < nums[idx]
    2. idx_l = idx-1,从idx位置从前往后移动直到找到最后一个数值大于nums[idx_l]的元素;
    3. 交换nums[idx_l]nums[idx]的值;
    4. 反转数组在idx位置之后的所有元素。

    最后,就可以得到下一个排列。

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int len = nums.size();
            if(len <= 0)
                return;
            
            int idx = len - 1;
            for(;idx >= 1 && nums[idx-1] >= nums[idx];idx--);
            
            if(idx == 0)
            {
                reverse(nums.begin(),nums.end());
                return;
            }
            
            int idx_l = idx - 1;
            for(int i=idx;idx<len;idx++)
            {
                if(nums[idx] <= nums[idx_l])
                    break;
            }
            
            swap(nums[idx-1],nums[idx_l]);
            
            reverse(nums.begin() + idx_l + 1,nums.end());
            
            return;
        }
    };
    

    缺失的第一个正数:hard

    41.缺失的第一个正数

    给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

    示例 1:

    输入: [1,2,0]
    输出: 3
    

    示例 2:

    输入: [3,4,-1,1]
    输出: 2
    

    示例 3:

    输入: [7,8,9,11,12]
    输出: 1
    

    说明:

    你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。

    • 方法1

    使用unordered_set结构的集合st装入nums中的元素,同时找到nums元素的最大值Max,然后遍历1~Max范围内的数,找到第一个不在集合st中数就是缺失的第一个正数,如果都在集合st中,那么缺失的第一个正数就在1和Max+1的较小值中取得。

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    C++代码

    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            unordered_set<int> st;
            int Max = INT_MIN;
            for(auto a : nums)
            {
                st.insert(a);
                Max = max(Max,a);
            }
            
            for(int i=1;i<=Max;i++)
            {
                if(st.count(i) == 0)
                    return i;
            }
            
            return max(Max + 1,1);
        }
    };
    
    • 方法2:优化空间复杂度

    对于大小为n(n>0)的数组,这n个数可以分为以下几种情况:

    1. 这n个数都小于等于0
    2. 这n个数都大于n
    3. 存在一个或多个位于[1,n]的数

    对于情况1情况2,要查找的第一个缺失的正数就是1;

    问题是对于情况3应该怎么考虑呢?

    假设这些位于[1,n]的数i,在数组中的位置应该为i-1,而小于等于0的数,以及大于n的数,在数组剩余位置:

    • 如果数组所有的数都在[1,n],那么每个元素都在其值减1的位置,此时要找的第一个缺失的整数就是n+1
    • 否则,数组中,必然存在一个位置idx,其元素值不等于idx+1,而范围[1,n]就是正数序列最开始的n个数,因此,从左往右查找第一个下标加1不等于值的位置,那么要找的第一个缺失的正数就是该位置的下标加1。

    注意交换元素的方法可以将范围在[1,n]的元素放置到正确的位置,详见 寻找重复数

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    C++代码

    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int len = nums.size();
            if(len == 0) return 1;
            
            for(int i=0;i<len;i++)
            {
                while(nums[i] > 0 && nums[i] <= len && nums[i] != i+1 && nums[nums[i] - 1] != nums[i])
                {
                    swap(nums[nums[i] - 1],nums[i]);
                }
            }
            
            for(int i=0;i<len;i++)
            {
                if(nums[i] != i + 1)
                    return i + 1;
            }
            
            return len + 1;
        }
    };
    
    展开全文
  • leetcode刷题

    2020-01-10 10:40:25
    目录分治算法寻找两个有序数组的位数合并k个链表最大子序和多数元素数组的第K个最大元素搜索二维矩阵 II为运算表达式设计优先级最接近原点的K个点矩形内船只的数目双指针无重复的最长子串数之和接雨水盛最多水...

    菜鸡刷题,是记录自己的写题过程,不具备什么参考价值,有空的话会找优秀的解法,暂时以先做出来为准

    分治算法

    寻找两个有序数组的中位数

    4
    我觉得似乎没有用分治法

    难点在于题目要求时间复杂度为O(log(m+n))
    这类题可以转化为求有序数组第k大/小的问题



    通过比较两个数组k//2处的数字,可以一下排除一半的查询范围
    感谢这位的解法三 参考解法

    class Solution:
        def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
            def findKnum(nums1,begin1,m,nums2,begin2,n,k):
                if begin1>=m: return nums2[begin2+k-1]
                if begin2>=n: return nums1[begin1+k-1]
                if k==1:
                    return min(nums1[begin1],nums2[begin2])
                p1 = min(begin1 + k//2 -1,m-1)
                p2 = min(begin2 + k//2 -1,n-1)
                if nums1[p1]<nums2[p2]:
                    return findKnum(nums1,p1+1,m,nums2,begin2,n,k-(p1-begin1+1))
                else:
                    return findKnum(nums1,begin1,m,nums2,p2+1,n,k-(p2-begin2+1))
    
            m = len(nums1)
            n = len(nums2)
            if (m+n)%2==1: return findKnum(nums1,0,m,nums2,0,n,(m+n)//2+1)
            else: return (findKnum(nums1,0,m,nums2,0,n,(m+n)//2+1)+findKnum(nums1,0,m,nums2,0,n,(m+n-1)//2+1))/2
    

    合并k个链表

    23

    这里分治解法的思想是两两链表合并,时间复杂度为O(Nlogk)

    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    
            def merge2List(l1,l2):
                l = ListNode(-1)
                p = l
                while l1 and l2:
                    if l1.val<=l2.val:
                        p.next = l1
                        l1 = l1.next
                    else:
                        p.next = l2
                        l2 = l2.next
                    p = p.next
                if l1: p.next = l1
                if l2: p.next = l2
                return l.next
            if len(lists)==0:return None
            while len(lists)!=1:
                lists.append(merge2List(lists.pop(0),lists.pop(0)))
            return lists[0]
    

    最大子序和

    53
    这里分别使用了两种方法:动态规划法和分治法(感谢大神)

    分治法的主要思想是最大子序和分为以下三种情况:在左半段里,在右半段里,或者是跨过左右半端,并依次这么分下去,取最大值即可

    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            # 这里用的动态规划,在返回值的时候请动脑子应该返回啥
            n = len(nums)
            dp = [0 for i in range(n)]
            dp[0] = nums[0]
            for i in range(1,n):
                dp[i] = max(dp[i-1]+nums[i],nums[i])
            return max(dp)
    
    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            size = len(nums)
            if size == 0:
                return 0
            return self.__max_sub_array(nums, 0, size - 1)
    
        def __max_sub_array(self, nums, left, right):
            if left == right:
                return nums[left]
            mid = (left + right) >> 1
            return max(self.__max_sub_array(nums, left, mid),
                       self.__max_sub_array(nums, mid + 1, right),
                       self.__max_cross_array(nums, left, mid, right))
    
        def __max_cross_array(self, nums, left, mid, right):
            # 一定包含 nums[mid] 元素的最大连续子数组的和,
            # 思路是看看左边"扩散到底",得到一个最大数,右边"扩散到底"得到一个最大数
            # 然后再加上中间数
            left_sum_max = 0
            start_left = mid - 1
            s1 = 0
            while start_left >= left:
                s1 += nums[start_left]
                left_sum_max = max(left_sum_max, s1)
                start_left -= 1
    
            right_sum_max = 0
            start_right = mid + 1
            s2 = 0
            while start_right <= right:
                s2 += nums[start_right]
                right_sum_max = max(right_sum_max, s2)
                start_right += 1
            return left_sum_max + nums[mid] + right_sum_max
    
    作者:liweiwei1419
    链接:https://leetcode-cn.com/problems/maximum-subarray/solution/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    

    多数元素

    169

    这里的思想是把数组看成左右两部分,如果左右两部分众数一样则整个数组的众数就是该数字,如果不一样,分别计算左右众数在整个数组中的个数,选出最大的

    class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            def findmost(left,right):
                if left==right:
                    return nums[left]
                mid = (left+right)>>1
                lmost = findmost(left,mid)
                rmost = findmost(mid+1,right)
                if lmost==rmost: return lmost
                else:
                    ln,rn = 0,0
                    for i in range(left,right+1):
                        if nums[i]==lmost: ln += 1
                        elif nums[i]==rmost: rn += 1
                    return lmost if ln>rn else rmost
            n = len(nums)
            return findmost(0,n-1)
    

    数组中的第K个最大元素

    215
    这里分别使用了两种方法,分治法和

    分治法用了快排中的思想,先找一个数排到适当的位置,根据它是第几个数判断我们要找的数会在它的左右范围内查找

    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            def quick_sort(l,r):
                pivot = nums[l]
                i = l
                while l!=r:
                    while nums[r]<=pivot and l<r:
                        r -= 1
                    while nums[l]>=pivot and l<r:
                        l += 1
                    if l<r:
                        nums[l],nums[r] = nums[r],nums[l]
                nums[l],nums[i] = pivot,nums[l]
                return l
            n = len(nums)
            l = 0
            r = n-1
            m = quick_sort(l, r)
            while m!=k-1:
                if m>k-1:
                    r = m-1
                    m = quick_sort(l,r)
                else:
                    l = m+1
                    m = quick_sort(l,r)
            return nums[m]
    
    class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            def build_heap(i):
                smallest = i
                l = 2*i + 1
                r = 2*i + 2
                if l<k and nums[i]>nums[l]:
                    smallest = l
                if r<k and nums[smallest]>nums[r]:
                    smallest = r
                if i!=smallest:
                    nums[i],nums[smallest] = nums[smallest],nums[i]
                    build_heap(smallest)
            n = len(nums)
            for i in range(k-1,n):
                for j in range(k-1,-1,-1):
                    if nums[i]>nums[0]:
                        nums[0],nums[i] = nums[i],nums[0]
                    build_heap(j)
            return nums[0]
    

    搜索二维矩阵 II

    240

    这里的思想是把矩阵分为四个部分,然后如果target小于某个矩阵左上角的值,就排除该矩阵,这里要注意边界条件

    class Solution:
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            def search_target(left,right,up,down):
                if left>right or up>down or matrix[up][left]>target: return False
                if left==right and up==down: return matrix[up][left]==target
                if matrix[up][left]==target:return True
                cmid = (left+right)>>1
                rmid = (up+down)>>1
                return search_target(left,cmid,up,rmid) or search_target(cmid+1,right,up,rmid) or search_target(left,cmid,rmid+1,down) or search_target(cmid+1,right,rmid+1,down)
                
            m = len(matrix)
            if m==0: return False
            n = len(matrix[0])
            return search_target(0,n-1,0,m-1)
    

    为运算表达式设计优先级

    241

    这里的思想是看到一个运算符,就分别计算它的左右两个部分

    class Solution:
        def diffWaysToCompute(self, input: str) -> List[int]:
            def cal(x,y,op):
                if op=='+':
                    return x+y
                elif op=='-':
                    return x-y
                elif op=='*':
                    return x*y
    
            def multi_calculate(s):
                if s.isdigit(): return [int(s)]
                res = []
                for c in range(len(s)):
                    if s[c] in ['+','-','*']:
                        for l in multi_calculate(s[:c]):
                            for r in multi_calculate(s[c+1:]):
                                res.append(cal(l,r,s[c]))
                return res
            return multi_calculate(input)
    

    最接近原点的K个点

    973

    分治的思想用于类似快速排序那样,和数组中的第K个最大元素那题类似

    class Solution:
        def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
            def distance(p):
                return p[0]**2+p[1]**2
    
            def quick_sort(left,right):
                i = left
                pivot = points[left]
                while left<right:
                    while distance(pivot)<=distance(points[right]) and left<right:
                        right -= 1
                    while distance(pivot)>=distance(points[left]) and left<right:
                        left += 1
                    if left!=right:
                        points[left],points[right] = points[right],points[left]
                points[left],points[i] = pivot,points[left]
                return left
            
            n = len(points)
            if K>=n: return points
            if K<=0: return []
            l,r = 0,n-1
            k = quick_sort(l,r)
            while k!=K:
                if k>K:
                    r = k-1
                    k = quick_sort(l,r)
                elif k<K:
                    l = k+1
                    k = quick_sort(l, r)
            return points[:k]
    

    矩形内船只的数目

    1274
    在这里插入图片描述
    在这里插入图片描述

    这里分治法的思想是把完整的海域分成四个部分,分别判断,如果有船则细分,没有则忽略

    # """
    # This is Sea's API interface.
    # You should not implement it, or speculate about its implementation
    # """
    # class Sea(object):
    #    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
    
    # class Point(object):
    # 	def __init__(self, x: int, y: int):
    # 		self.x = x
    # 		self.y = y
    
    class Solution(object):
        def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
            def find_ship(topRight,bottomLeft):
                left,right,up,down = bottomLeft.x,topRight.x,topRight.y,bottomLeft.y
                if left>right or up<down or not sea.hasShips(topRight,bottomLeft): return 0
                if left==right and up==down: return 1
                cmid = (left+right)>>1
                rmid = (up+down)>>1
                return find_ship(Point(cmid,up),Point(left,rmid+1))+find_ship(topRight,Point(cmid+1,rmid+1))+find_ship(Point(cmid,rmid),bottomLeft)+find_ship(Point(right,rmid),Point(cmid+1,down))
            return find_ship(topRight,bottomLeft)
    

    双指针

    子序列!=子串 (子序列可以是由里面的字母按顺序但可以不连续的组成的部分)

    无重复的最长子串

    3

    主要的思想就是用两个指针,分别表示子串的起始和结束位置

    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            w = {}
            l,r = 0,0
            n = len(s)
            count = 0
            while r<n:
                if s[r] not in w.keys() or w[s[r]]<l:
                    w[s[r]] = r
                else:
                    l = w[s[r]]+1    
                    w[s[r]] = r
                count = max(count,r-l+1)
                r += 1
            return count
    

    三数之和

    15

    用排序,用两个指针分别指向数组的头和尾,然后根据结果的大小进行移动

    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            # 先排序,O(NlogN),再用两个指针分别指向左右,根据和的大小进行移动,这里需要注意优化,比如输入的列表长度小于3且最大的一项都小于0则无需向下排,另外如果选的最小项>0也无需排,相等的值可以跳过
            nums.sort()
            n = len(nums)
            res = []
            if n<3 or nums[-1]<0: return res
            for i in range(n-2):
                l,r = i+1,n-1
                if nums[i]>0:
                    return res
                if i>0 and nums[i]==nums[i-1]:
                    continue
                while l<r:
                    s = nums[i]+nums[l]+nums[r]
                    if s>0:
                        r -= 1
    
                    elif s<0:
                        l += 1
                    else:
                        res.append([nums[i],nums[l],nums[r]])
                        while l<r and nums[l]==nums[l+1]:
                            l += 1
                        while l<r and nums[r]==nums[r-1]:
                            r -= 1
                        l += 1
                        r -= 1
            return res
    

    接雨水

    42

    分别用了动态规划法和双指针法
    其中双指针法主要思路就是在首尾各有一个指针,然后按照条件进行移动

    class Solution:
        def trap(self, height: List[int]) -> int:
            # 这里用了动态规划的思想,如果按常规的方法,应该是循环找每一列的左边最高列和右边最高列,这样会有很多重复的数据,所以只需把它们保存起来即可
            # n = len(height)
            # if n<3: return 0
            # max_left = [0 for _ in range(n)]
            # max_right = [0 for _ in range(n)]
            # for i in range(n):
            #     if i==0: 
            #         max_left[i] = height[i]
            #     else:
            #         max_left[i] = max(max_left[i-1],height[i])
            # # print(max_left)
            # for i in range(n-1,-1,-1):
            #     if i==n-1: 
            #         max_right[i] = height[i]
            #     else:
            #         max_right[i] = max(max_right[i+1],height[i])
            # # print(max_right)
            # ans = 0
            # for i in range(n):
            #     if height[i]<max_left[i] and height[i]<max_right[i]:
            #         ans += min(max_left[i],max_right[i])-height[i]
            # return ans
    
            # 这个节约了一点空间,可以不用数组表示左边最大值
            # n = len(height)
            # if n<3: return 0
            # max_left = 0
            # max_right = [0 for _ in range(n)]
            # for i in range(n-1,-1,-1):
            #     if i==n-1: 
            #         max_right[i] = height[i]
            #     else:
            #         max_right[i] = max(max_right[i+1],height[i])
            # # print(max_right)
            # ans = 0
            # for i in range(n):
            #     max_left = max(max_left,height[i])
            #     if height[i]<max_left and height[i]<max_right[i]:
            #         ans += min(max_left,max_right[i])-height[i]
            # return ans
    
    class Solution:
        def trap(self, height: List[int]) -> int:
            # 这是用了双指针,但是对于它的逻辑我还不是那么熟悉,还需要反复看,但是空间复杂度下降为常数了
            n = len(height)
            if n<3:return 0
            left,right = 1,n-2
            max_left,max_right = 0,0
            ans = 0
            for i in range(1,n-1):
                if height[left-1]<height[right+1]:
                    max_left = max(max_left,height[left-1])
                    if height[left]<max_left:
                        ans += max_left-height[left]
                    left += 1
                else:
                    max_right = max(max_right,height[right+1])
                    if height[right]<max_right:
                        ans += max_right-height[right]
                    right -= 1
            return ans
    

    盛最多水的容器

    11

    有指向首尾的两个指针,移动较短的那根才有可能盛水量变多

    class Solution:
        def maxArea(self, height: List[int]) -> int:
            # 这个就是使用两个指针,分别指向头和尾,由于大小取决于两者中最短的线,移动较短的线才有可能得到更大的面积
            n = len(height)
            l,r = 0,n-1
            maxarea = 0
            while l<r:
                maxarea = max(maxarea,min(height[l],height[r])*(r-l))
                if height[l]<height[r]:
                    l += 1
                else:
                    r -= 1
            return maxarea
    

    最接近的三数之和

    16

    和三数之和那题类似,先排序,再用两个指针找

    class Solution:
        def threeSumClosest(self, nums: List[int], target: int) -> int:
            # 主要还是和三数之和类似的方法,先排序,再设置两个指针找
            n = len(nums)
            nums.sort()
            if n<3: return
            minsum = nums[0]+nums[1]+nums[2]
            for i in range(n-2):
                l,r = i+1,n-1
                while l<r:
                    s = nums[i]+nums[l]+nums[r]
                    minsum = s if abs(target-s)<abs(target-minsum) else minsum
                    if s<target:
                        l += 1
                    elif s>target:
                        r -= 1
                    else:
                        return target
            return minsum
    

    删除排序数组中的重复项

    26

    设置快慢两个指针,不相等时就覆盖

    class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
            # 还是双指针的思想,一个快一个慢然后比较并赋值,应该是O(N)
            n = len(nums)
            if n<2:return n
            p,q=0,1
            while q<n:
                if nums[p]!=nums[q]:
                    p += 1
                    nums[p] = nums[q]
                q += 1
            return p+1
    

    四数之和

    18

    和三数之和类似

    class Solution:
        def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
            # O(N^3) 基本思路同两数和三数相加一样
            nums.sort()
            n = len(nums)
            res = []
            if n < 4: return res
            for i in range(n-3):
                if i>0 and nums[i]==nums[i-1]: continue
                for j in range(i+1,n-2):
                    if j>i+1 and nums[j]==nums[j-1]: continue
                    l,r = j+1,n-1
                    while l<r:
                        s = nums[i]+nums[j]+nums[l]+nums[r]
                        if s==target:
                            res.append([nums[i],nums[j],nums[l],nums[r]])
                            while l<r and nums[l]==nums[l+1]:
                                l += 1
                            while l<r and nums[r]==nums[r-1]:
                                r -=1
                            l += 1
                            r -= 1
                        elif s>target:
                            r -= 1
                        else:
                            l += 1
            return res
    

    合并两个有序数组

    88

    两个数组分别从后往前比较,然后从后向前放置合并元素

    class Solution:
        def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            cur = m+n-1
            i,j = m-1,n-1
            while i>=0 and j>=0 and cur>=0:
                if nums1[i]>nums2[j]:
                    nums1[cur] = nums1[i]
                    i -= 1
                else:
                    nums1[cur] = nums2[j]
                    j -= 1
                cur -= 1
            while j>=0:
                nums1[cur] = nums2[j]
                j -= 1
                cur -= 1
    

    分隔链表

    86

    似乎可以省掉一个变量,不用cur直接用head,但是基本思想就是找到要插入的位置和要插入的元素

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def partition(self, head: ListNode, x: int) -> ListNode:
            pre = ListNode(-1)
            pre.next = head
            cur = head
            h = pre # 插入到它后面
            prehead = pre 
            while cur:
                while h and h.next and (h.next).val<x:
                    h = h.next
                pre = h
                cur = h.next
                while cur and cur.val>=x:
                    cur = cur.next
                    pre = pre.next
                if h and cur:
                    pre.next = cur.next
                    cur.next = h.next
                    h.next = cur
            return prehead.next
    

    删除链表的倒数第N个节点

    19

    是用一个指针先走N步,然后另一个指针从头一起走,这样就可以指向倒数第N个节点

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
            prehead = ListNode(-1)
            prehead.next = head
            pre = prehead
            f = head
            while n>0 and f:
                f = f.next
                n -= 1
            while f and pre and head:
                f = f.next
                pre = pre.next
                head = head.next
            pre.next = head.next
            return prehead.next
    

    两个数组的交集

    349

    按双指针写,用了排序,所以时间复杂度比较搞

    class Solution:
        def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
            res = []
            nums1.sort()
            nums2.sort()
            i,j = 0,0
            m,n = len(nums1),len(nums2)
            while i<m and j<n:
                if nums1[i]>nums2[j]:
                    j += 1
                elif nums1[i]<nums2[j]:
                    i += 1
                else:
                    res.append(nums1[i])
                    i += 1
                    while i<m and nums1[i]==nums1[i-1]:
                        i += 1
                    j += 1
                    while j<n and nums2[j]==nums2[j-1]:
                        j += 1
            return res
    

    两数之和 II - 输入有序数组

    167

    非常简单的一题,和两数之和一样,对于排序数组是首尾两个指针,根据和大小分别移动两个指针

    class Solution:
        def twoSum(self, numbers: List[int], target: int) -> List[int]:
            n = len(numbers)
            l,r = 0,n-1
            while l<r:
                numsum = numbers[l]+numbers[r]
                if numsum==target:
                    return [l+1,r+1]
                elif numsum>target:
                    r -= 1
                else:
                    l += 1
            return []
    

    串联所有单词的字串

    30

    有点滑动窗口的样子

    class Solution:
        def findSubstring(self, s: str, words: List[str]) -> List[int]:
            res = []
            m = len(words) # 单词个数
            if m==0: return []
            n = len(words[0]) # 每个单词的长度
            ns = len(s)
            l,r = 0,m*n
            words.sort()
            while r<=ns:
                m_words = []
                for i in range(m):
                    m_words.append(s[l+i*n:l+(i+1)*n])
                if sorted(m_words)==words: res.append(l)
                l += 1
                r += 1
            return res
    

    寻找重复数

    287

    思想是类似二分法那样,计算小于等于中间数的个数,如果大于一定的数目,就说明重复数在那个范围里

    class Solution:
        def findDuplicate(self, nums: List[int]) -> int:
            n =len(nums)
            left,right = 1,n-1
            while left<right:
                mid = (left+right)>>1
                cnt = 0
                for num in nums:
                    if num<=mid:
                        cnt += 1
                if cnt>mid:
                    right = mid
                else:
                    left = mid+1
            return left
    

    实现Strstr()

    28

    很简单的一题,就是类似滑动窗口的思想

    class Solution:
        def strStr(self, haystack: str, needle: str) -> int:
            m = len(haystack)
            n = len(needle)
            l,r = 0,n
            while r <= m:
                if haystack[l:r]==needle:
                    return l
                l += 1
                r += 1
            return -1
    

    颜色分类

    75

    我觉得这题能这么写是因为只有三类,它的普适写法应该是先扫一边计算每个元素个数再重新产生该列表,如果用双指针的话就分别指向0和2的位置,然后扫描的元素符合条件,就和相应位置的元素交换

    class Solution:
        def sortColors(self, nums: List[int]) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            n = len(nums)
            zero,two = 0,n-1
            cur = 0
            while cur<=two:
                if nums[cur]==0:
                    nums[cur],nums[zero] = nums[zero],nums[cur]
                    zero += 1
                    cur += 1
                elif nums[cur]==2:
                    nums[cur],nums[two] = nums[two],nums[cur]
                    two -= 1
                else:
                    cur += 1
    

    移除元素

    27

    首尾两个指针,然后用尾部的非target替换首部target

    class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            # 首尾两个指针,找到想要的值就替换
            n = len(nums)
            if n<1: return n
            p,q = 0,n-1
            while p<q:
                while p<q and nums[p]!=val:
                    p += 1
                while p<q and nums[q]==val:
                    q -=1
                if p<q:
                    nums[p] = nums[q]
                    p += 1
                    q -= 1
            return p+1 if p==q and nums[p]!=val else p
    

    反转字符串

    344

    首尾指针交换

    class Solution:
        def reverseString(self, s: List[str]) -> None:
            """
            Do not return anything, modify s in-place instead.
            """
            n = len(s)
            l,r = 0,n-1
            while l<r:
                s[l],s[r] = s[r],s[l]
                l += 1
                r -= 1
    

    环形链表

    141

    快慢两个指针,相遇即有环

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            slow = head
            if head and head.next and (head.next).next:
                fast = (head.next).next
            else:
                return False
            while slow and slow.next and fast and fast.next:
                if slow==fast:
                    return True
                slow = slow.next
                fast = (fast.next).next
            return False
    

    回文链表

    234

    先找中间位置,然后将后半段逆序,然后分别比较前后半段

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def isPalindrome(self, head: ListNode) -> bool:
            cnt = 0
            p = head
            while p:
                cnt += 1
                p = p.next
            if cnt<=1: return True
            p = head
            half_cnt = (cnt-1)//2
            while half_cnt>0:
                half_cnt -= 1
                p = p.next
            pre = p.next
            cur = pre.next
            while cur:
                pre.next = cur.next
                cur.next = p.next
                p.next = cur
                cur = pre.next
            half_cnt = cnt//2-1
            p1 = head
            p2 = p.next
            while half_cnt>=0:
                if p1.val!=p2.val:
                    return False
                half_cnt -= 1
                p1 = p1.next
                p2 = p2.next
            return True
    

    移动零

    283

    也是很简单的一题,两个指针,把非零的元素按位置顺序放入数组中

    class Solution:
        def moveZeroes(self, nums: List[int]) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            n = len(nums)
            i,j = 0,0
            while j<n:
                if nums[j]!=0:
                    nums[i] = nums[j]
                    i += 1
                j += 1
            while i<n:
                nums[i] = 0
                i += 1
    

    长度最小的子数组

    209

    类似滑动窗口的思想

    class Solution:
        def minSubArrayLen(self, s: int, nums: List[int]) -> int:
            n = len(nums)
            if sum(nums)<s: return 0
            l,r = 0,0
            minlen = n
            valsum = nums[0]
            if valsum>s:
                return 1
            while r<n:
                if valsum<s:
                    r += 1
                    if r<n:
                        valsum += nums[r]
                else:
                    minlen = min(minlen,r-l+1)
                    valsum -= nums[l]
                    l += 1
            return minlen
    

    旋转链表

    61

    主要是找到旋转位置,然后放到头部,有点像找到链表倒数第k个元素

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def rotateRight(self, head: ListNode, k: int) -> ListNode:
            cnt = 0
            p = head
            while p:
                cnt += 1
                p = p.next
            if cnt<=1: return head
            prehead = ListNode(-1)
            prehead.next = head
            k = k%cnt
            if k==0: return head
            q = head
            tail = prehead
            while k>=0:
                q = q.next
                tail = tail.next
                k -= 1
            while q:
                head = head.next
                q = q.next
                tail = tail.next
            tail.next = prehead.next
            prehead.next = head.next
            head.next = None
            return prehead.next
    

    反转字符串中的元音字母

    345

    分别从前后查找需要交换的元素

    class Solution:
        def reverseVowels(self, s: str) -> str:
            n = len(s)
            l,r = 0,n-1
            vowel = ['a','e','i','o','u']
            s_list = list(s)
            while l<r:
                while l<r and s_list[l].lower() not in vowel:
                    l += 1
                while l<r and s_list[r].lower() not in vowel:
                    r -= 1
                if l<r:
                    s_list[l],s_list[r] = s_list[r],s_list[l]
                    l += 1
                    r -= 1
            return ''.join(s_list)
    

    环形链表 II

    142

    先像之前的一样判断有无环,然后一个从head开始,一个从相遇点开始,再一次相遇时就为环的起点

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def detectCycle(self, head: ListNode) -> ListNode:
            slow,fast = head,head
            flag = False
            while slow and slow.next and fast and fast.next and (fast.next).next:
                slow = slow.next
                fast = (fast.next).next
                if slow== fast:
                    flag = True
                    break
            if not flag:
                return None
            p = head
            while p!=slow:
                p = p.next
                slow = slow.next
            return p
    

    验证回文串

    125

    首尾指针比较

    class Solution:
        def isPalindrome(self, s: str) -> bool:
            n = len(s)
            l,r = 0,n-1
            while l<r:
                while l<r and not s[l].isalnum():
                    l += 1
                while l<r and not s[r].isalnum():
                    r -= 1
                if l<r:
                    if s[l].lower()!=s[r].lower():
                        return False
                    l += 1
                    r -= 1
            return True
    

    两个数组的交集 II

    350

    很简单第一题,排序后比较

    class Solution:
        def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
            nums1.sort()
            nums2.sort()
            m = len(nums1)
            n = len(nums2)
            p1,p2 = 0,0
            res = []
            while p1<m and p2<n:
                if nums1[p1]==nums2[p2]:
                    res.append(nums1[p1])
                    p1 += 1
                    p2 += 1
                elif nums1[p1]>nums2[p2]:
                    p2 += 1
                else:
                    p1 += 1
            return res
    

    乘积小于K的子数组

    713

    这个有参考别人的方式,我自己写的不知道为什么超时了,注意这里res的算法,有点巧妙

    class Solution:
        def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
            n = len(nums)
            if n==0: return 0
            res = 0
            l,r = 0,0
            multi = 1
            while l<n:
                while r<n and multi*nums[r]<k:
                    multi *= nums[r]
                    r += 1
                if l<r:
                    res += r-l
                    multi //= nums[l]
                    l += 1
                else:
                    l += 1
                    r = l
                    multi = 1
            return res
    

    通过删除字母匹配到字典里最长单词

    524

    这里我先给字典按长度和字典序排列,然后分别在字符串中查找字典中的对应字符串

    class Solution:
        def findLongestWord(self, s: str, d: List[str]) -> str:
            d.sort(key=lambda x: [-len(x), x])
            # print(d)
            for ds in d:
                i,j = 0,0
                while i<len(s) and j<len(ds):
                    if s[i]==ds[j]:
                        j += 1
                    i += 1
                if j==len(ds): return ds
            return ''
    

    有序转化数组

    360
    在这里插入图片描述

    先找出曲线最低或最高点,然后用两个指针从此点分别向左向右移动

    class Solution:
        def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
            n = len(nums)
            if n==0: return []
            res = []
            mindex = 0
            if a!=0:
                mid = -b/(2*a)
                d = abs(nums[0]-mid)
                for i in range(1,n):
                    if abs(nums[i]-mid)<d:
                        d = abs(nums[i]-mid)
                        mindex = i
            l,r = mindex-1,mindex
            while l>=0 and r<n:
                if abs(nums[l]-mid)<abs(nums[r]-mid):
                    res.append(a*(nums[l])**2+b*nums[l]+c)
                    l -= 1
                else:
                    res.append(a*(nums[r])**2+b*nums[r]+c)
                    r += 1
            while l>=0:
                res.append(a*(nums[l])**2+b*nums[l]+c)
                l -= 1
            while r<n:
                res.append(a*(nums[r])**2+b*nums[r]+c)
                r += 1
            return res if a>0 or (a==0 and b>0) else reversed(res)
    

    数组中的K-diff数对

    532

    先排序再用双指针找符合条件的元素

    class Solution:
        def findPairs(self, nums: List[int], k: int) -> int:
            nums.sort()
            n = len(nums)
            if n<2: return 0
            l,r = 0,1
            res = 0
            while r<n:
                m = nums[r]-nums[l]
                if m==k:
                    res += 1
                    l += 1
                    while l<n and nums[l]==nums[l-1]:
                        l += 1
                    while r<n and nums[r]==nums[r-1]:
                        r += 1
                    if l==r:
                        r = l+1
                elif m<k:
                    r += 1
                else:
                    l += 1
                    if l==r:
                        r = l+1
            return res
    

    字符串的排列

    567

    滑动窗和字典计数的方式

    class Solution:
        def checkInclusion(self, s1: str, s2: str) -> bool:
            m = len(s1)
            n = len(s2)
            if m>n: return False
            s1_dict = {}
            for c in s1:
                s1_dict[c] = s1_dict.get(c,0)+1
            l,r = 0,m-1
            s2_dict = {}
            for i in range(m):
                s2_dict[s2[i]] = s2_dict.get(s2[i],0)+1
            while r<n:
                if s1_dict==s2_dict:
                    return True
                s2_dict[s2[l]] -= 1
                if s2_dict[s2[l]]==0: s2_dict.pop(s2[l])
                l += 1
                r += 1
                if r<n:
                    s2_dict[s2[r]] = s2_dict.get(s2[r],0)+1
            return False
    

    至多包含两个不同字符的最长子串

    159
    在这里插入图片描述

    滑动窗口的思想

    class Solution:
        def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
            pos = {}
            n = len(s)
            l,r = 0,0
            maxlen = 0
            while r<n:
                # print('l:',l)
                # print('r:',r)
                if s[r] not in pos.keys() and len(pos)==2:
                        p1,p2 = pos.items()
                        maxlen = max(maxlen,r-l)
                        l = min(p1[1],p2[1])+1
                        pos.pop(p1[0]) if p1[1]<p2[1] else pos.pop(p2[0])
                pos[s[r]] = r
                r += 1
            maxlen = max(maxlen,r-l)
            return maxlen
    

    较小的三数之和

    259
    在这里插入图片描述

    先排序,然后首尾指针,按照条件进行移动,注意这里符合条件的处理方式

    class Solution:
        def threeSumSmaller(self, nums: List[int], target: int) -> int:
            nums.sort()
            n = len(nums)
            if n<3: return 0
            res = 0
            for i in range(n-2):
                t = target-nums[i]
                l,r = i+1,n-1
                while l<r:
                    m = nums[l]+nums[r]
                    if m<t:
                        res += r-l
                        l += 1
                    else:
                        r -= 1
            return res
    

    最大连续1的个数 II

    487
    在这里插入图片描述

    从头开始的两个指针

    class Solution:
        def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
            n = len(nums)
            l,r = 0,0
            is_change = False # 判断是否已经转化过一次
            c_index = 0
            res = 0
            while r<n:
                if nums[r]==0:
                    if not is_change:
                        is_change = True
                        c_index = r
                    else:
                        res = max(res,r-l)
                        is_change = False
                        l = c_index+1
                        r -= 1
                r += 1
            res = max(res,r-l)
            return res
    

    划分字母区间

    763

    应该算是合并子区间的问题,好像没有用到双指针

    class Solution:
        def partitionLabels(self, S: str) -> List[int]:
            def merge_intervals(a):
                n = len(a)
                i,j = 0,1
                while i<len(a) and j<len(a):
                    if a[i][0]<a[j][0]<a[i][1]:
                        a[i][1] = max(a[i][1],a[j][1])
                        a.pop(j)
                    else:
                        i += 1
                        j = i+1
    
            pos = {}
            res = []
            n = len(S)
            for i in range(n):
                if S[i] not in pos:
                    pos[S[i]] = [i,i]
                else:
                    pos[S[i]][1] = i
            # print(pos)
            pos_list = list(pos.values())
            # print(pos_list)
            merge_intervals(pos_list)
            for i in range(len(pos_list)):
                res.append(pos_list[i][1]-pos_list[i][0]+1)
            # print(pos_list)
            return res
    

    安排工作以达到最大收益

    826

    这里是参考别人的,写得比我原先的简洁很多,这里有几个坑,一个是可能难度小的收益大,所以可以把最好收益存下来

    class Solution:
        def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
            jobs = list(zip(difficulty, profit))
            jobs.sort()
            ans = i = best = 0
            for skill in sorted(worker):
                while i < len(jobs) and skill >= jobs[i][0]:
                    best = max(best, jobs[i][1])
                    i += 1
                ans += best
            return ans
    

    独特字符串

    828

    这也是参考别人的,写的很精妙,思想就是每个字母分别看在哪些子串中可以作为独特字符
    在这里插入图片描述

    class Solution:
        def uniqueLetterString(self, S: str) -> int:
            index = collections.defaultdict(list)
            for i, c in enumerate(S):
                index[c].append(i)
            print(index)
            n = len(S)
            res = 0
            for A in index.values():
                A = [-1] + A + [n]
                for i in range(1,len(A)-1):
                    res += (A[i] - A[i-1]) * (A[i+1] - A[i])
            return res%(10**9+7)
    

    比较含退格的字符串

    844

    这里用写的,没有用双指针

    class Solution:
        def backspaceCompare(self, S: str, T: str) -> bool:
            def get_str(s):
                stack = []
                n = len(s)
                for c in s:
                    if c=='#':
                        if stack:
                            stack.pop()
                    else:
                        stack.append(c)
                return ''.join(stack)
            return get_str(S)==get_str(T)
    

    数组中的最长山脉

    845

    左右指针,顺着规律找山脉

    class Solution:
        def longestMountain(self, A: List[int]) -> int:
            n = len(A)
            l,r=0,0
            res = 0
            while r<n:
                for i in range(l,n-1):
                    if A[i+1]>A[i]:
                        l = i
                        break
                    elif i==n-2:
                        l = n-1
                r = l+1
                is_down = False
                while r<n and A[r]>A[r-1]:
                    r += 1
                if r<n and A[r]==A[r-1]:
                    l = r
                    continue
                while r<n and A[r]<A[r-1]:
                    is_down = True
                    r += 1
                if is_down:
                    res = max(res,r-l)
                    l = r-1
            return res
    

    救生艇

    881

    这个也是参考别人的答案,一个重的搭配目前最轻的,不行的话就一个人搭船,我在这题走了很多弯路,我希望找到一个体重和符合要求且是最大的,完全没必要

    class Solution:
        def numRescueBoats(self, people: List[int], limit: int) -> int:
            people.sort()
            n = len(people)
            res = 0
            l,r = 0,n-1
            while l<=r:
                res += 1
                if people[l]+people[r]<=limit:
                    l += 1
                r -= 1
            return res
    

    水果成篮

    904

    这个和159题-至多包含两个不同字符的最长子串 非常相似

    class Solution:
        def totalFruit(self, tree: List[int]) -> int:
            fruit = {}
            n = len(tree)
            l,r = 0,0
            maxlen = 0
            while r<n:
                if len(fruit)==2 and tree[r] not in fruit.keys():
                    p1,p2 = fruit.items()
                    maxlen = max(maxlen,r-l)
                    l = min(p1[1],p2[1])+1
                    fruit.pop(p1[0]) if p1[1]<p2[1] else fruit.pop(p2[0])
                fruit[tree[r]] = r
                r += 1
            maxlen = max(maxlen,r-l)
            return maxlen
    

    三数之和的多种可能

    923

    这里除了和之前三数之和那题类似,还多了一个计数步骤

    class Solution:
        def threeSumMulti(self, A: List[int], target: int) -> int:
            def get_choice(n,x):  # 这里是计算从n个数取x个数有多少种方式
                if n<x: return 0
                if n==x: return 1
                if x==1: return n
                a,b = 1,1
                for i in range(x):
                    a *= (n-i)
                    b *= (i+1)
                return a//b
            cnt = {}
            A_list = []
            for num in A:
                if num not in cnt.keys():
                    A_list.append(num)
                cnt[num] = cnt.get(num,0)+1
            A_list.sort()
            n = len(A_list)
            ans = 0
            for i in range(n):
                l,r = i,n-1
                while l<=r:
                    # print('i,l,r:',i,l,r)
                    m = A_list[i]+A_list[l]+A_list[r]
                    if m==target:
                        c = {}
                        c[A_list[i]] = c.get(A_list[i],0)+1
                        c[A_list[l]] = c.get(A_list[l],0)+1
                        c[A_list[r]] = c.get(A_list[r],0)+1
                        res = 1
                        for j in c.keys():
                            res *= get_choice(cnt[j],c[j])
                        ans += res
                        l += 1
                        r -= 1
                    elif m<target:
                        l += 1
                    else:
                        r -= 1
            return ans%(10**9+7)
    

    长按键入

    925

    很简单的一题,主要是在typed中找有无name匹配即可

    class Solution:
        def isLongPressedName(self, name: str, typed: str) -> bool:
            m = len(name)
            n = len(typed)
            i,j = 0,0
            while i<m and j<n:
                if name[i]==typed[j]:
                    i += 1
                j += 1
            return False if i<m else True
    

    有序数组的平方

    977

    很简单的一题

    class Solution:
        def sortedSquares(self, A: List[int]) -> List[int]:
            ans = [x*x for x in A]
            ans.sort()
            # 或者将A直接平方,然后通过首尾两个指针放到新列表的相应位置
            return ans
    

    三个有序数组的交集

    1213
    在这里插入图片描述

    这题也比较简单,主要是移动指针

    class Solution:
        def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
            n1,n2,n3 = len(arr1),len(arr2),len(arr3)
            i,j,k = 0,0,0
            ans = []
            while i<n1 and j<n2 and k<n3:
                if arr1[i]==arr2[j]==arr3[k]:
                    ans.append(arr1[i])
                    i += 1
                    j += 1
                    k += 1
                elif arr1[i]<arr2[j] or arr1[i]<arr3[k]:
                    i += 1
                elif arr2[j]<arr1[i] or arr2[j]<arr3[k]:
                    j += 1
                elif arr3[k]<arr1[i] or arr3[k]<arr2[j]:
                    k += 1
            return ans
    
    

    最大连续1的个数 III

    1004

    和之前最大连续1的个数类似,别忘了考虑K为0的情况

    class Solution:
        def longestOnes(self, A: List[int], K: int) -> int:
            n = len(A)
            l,r = 0,0
            res = 0
            zero_list = []
            while r<n:
                if A[r]==0:
                    if len(zero_list)==K:
                        res = max(res,r-l)
                        if zero_list:
                            l = zero_list.pop(0)+1
                        else:
                            l = r+1
                    if K!=0:
                        zero_list.append(r)
                r += 1
            res = max(res,r-l)
            return res
    

    大样本统计

    1093

    没用到双指针思想

    class Solution:
        def sampleStats(self, count: List[int]) -> List[float]:
            n = len(count)
            minval,maxval = n-1,0
            cnt = 0
            numsum = 0
            mostcnt,mostval = 0,0
            for i in range(n):
                if count[i]>0:
                    minval = min(minval,i)
                    maxval = max(maxval,i)
                    cnt += count[i]
                    numsum += i*count[i]
                    if count[i]>mostcnt:
                        mostcnt = count[i]
                        mostval = i
            mid = cnt/2
            midval1,midval2 = n,n
            m = 0
            for i in range(n):
                m += count[i]
                if m>=mid:
                    midval1 = min(midval1,i)
                if m>=mid+1:
                    midval2 = min(midval2,i)
                    break
            midval = midval1 if cnt%2==1 else (midval1+midval2)/2
            return [minval,maxval,numsum/cnt,midval,mostval]
    

    区间列表的交集

    986

    按照条件进行移动指针

    class Solution:
        def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
            m = len(A)
            n = len(B)
            i,j = 0,0
            ans = []
            while i<m and j<n:
                if B[j][0]>A[i][1]:
                    i += 1
                elif A[i][0]>B[j][1]:
                    j += 1
                else:
                    if A[i][0]<=B[j][0]<=A[i][1]:
                        ans.append([B[j][0],min(A[i][1],B[j][1])])
                    elif B[j][0]<=A[i][0]<=B[j][1]:
                        ans.append([A[i][0],min(A[i][1],B[j][1])])
                    if A[i][1]<B[j][1]:
                        i += 1
                    else:
                        j += 1
            return ans
    

    统计「优美子数组」

    1248

    把奇数的位置存起来,需要奇数外的偶数不会影响结果,所以只需要乘积计算包含偶数的各个情况

    class Solution:
        def numberOfSubarrays(self, nums: List[int], k: int) -> int:
            n = len(nums)
            odd = []
            for i in range(n):
                if nums[i]%2==1:
                    odd.append(i)
            odd = [-1] + odd + [n]
            # print(odd)
            m = len(odd)
            ans = 0
            for i in range(k,m-1):
                ans += (odd[i-k+1]-odd[i-k])*(odd[i+1]-odd[i])
            return ans
    

    和相同的二元子数组

    930

    这是把需要的数记录下来,计算包含需要数的范围数目,只要前后无影响的数目个数相乘即可,和前面的思想很像,这里就是把1都记录下来

    class Solution:
        def numSubarraysWithSum(self, A: List[int], S: int) -> int:
            def get_num(x):
                ans = 0
                for i in range(x):
                    ans += x-i
                return ans
            n = len(A)
            ans = 0
            if sum(A)<S or n<1: return 0
            pos = []
            for i in range(n):
                if A[i]==1:
                    pos.append(i)
            pos = [-1] + pos + [n]
            m = len(pos)
            if S!=0:
                for i in range(S,m-1):
                    ans += (pos[i-S+1]-pos[i-S])*(pos[i+1]-pos[i])
            else:
                for i in range(1,m):
                    ans += get_num(pos[i]-pos[i-1]-1)
            return ans
    
    

    未完成的part

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 数组相关题目

    2020-03-07 12:53:03
    文章目录一、数组实现栈二、数组实现队列、稀疏数组四、数组中的最大... 搜索二维矩阵88. 合并两个有序数组121. 买卖股票最佳时机1122. 买卖股票最佳时机2169. 多数元素189. 旋转数组_和恢复229. 求众数 II(...

    一、数组实现栈

    public static class ArrayStack {
    	private Integer[] arr;
    	private Integer size;
    
    	public ArrayStack(int initSize) {
    		if (initSize < 0) {
    			throw new IllegalArgumentException("The init size is less than 0");
    		}
    		arr = new Integer[initSize];
    		size = 0;
    	}
    
        /**
         * 返回栈顶元素
         * @return
         */
    	public Integer peek() {
    		if (size == 0) {
    			return null;
    		}
    		return arr[size - 1];
    	}
    
        /**
         * 入栈
         * @param num
         */
    	public void push(int num) {
    		if (size == arr.length) {
    			throw new ArrayIndexOutOfBoundsException("The queue is full");
    		}
    		arr[size++] = num;
    	}
    
    
        /**
         * 出栈
         * @return
         */
    	public Integer pop() {
    		if (size == 0) {
    			throw new ArrayIndexOutOfBoundsException("The queue is empty");
    		}
    		return arr[--size];
    	}
    }
    
    // 自动扩容版本
    public class MyStack {
        public static void main(String[] args) {
            MyStack stack = new MyStack(3);
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            System.out.println(stack.size());
        }
        private int[] storage;  //存放栈中元素的数组
        private int capacity;   //栈的容量
        private int count;      //栈中元素数量
        private static final int GROW_FACTOR = 2; //扩容因子
    
        //TODO:不带初始容量的构造方法,默认容量为8
        public MyStack() {
            this.capacity = 8;
            this.storage=new int[8];
            this.count = 0;
        }
    
        //TODO:带初始容量的构造方法
        public MyStack(int initialCapacity) {
            if (initialCapacity < 1)
                throw new IllegalArgumentException("Capacity too small.");
            this.capacity = initialCapacity;
            this.storage = new int[initialCapacity];
            this.count = 0;
        }
    
        //TODO:入栈
        public void push(int value) {
            if (count == capacity) {
                ensureCapacity();
            }
            storage[count++] = value;
        }
    
        //TODO:扩容
        private void ensureCapacity() {
            // 扩容的容量
            int newCapacity = capacity * GROW_FACTOR;
            // 扩容后的数组,大小是原来的两倍,保留原数组中元素
            storage = Arrays.copyOf(storage, newCapacity);
            // 更新容量
            capacity = newCapacity;
        }
    
        //TODO:返回栈顶元素并出栈
        private int pop() {
            count--;
            if (count == -1)
                throw new IllegalArgumentException("Stack is empty.");
    
            return storage[count];
        }
    
        //TODO:返回栈顶元素不出栈
        private int peek() {
            if (count == 0){
                throw new IllegalArgumentException("Stack is empty.");
            }else {
                return storage[count-1];
            }
        }
    
        //TODO:判断栈是否为空
        private boolean isEmpty() {
            return count == 0;
        }
    
        //TODO:返回栈中元素的个数
        private int size() {
            return count;
        }
    }
    

    二、数组实现队列

    public static class ArrayQueue {
        // 存放队列元素的数组
    	private Integer[] arr;
    	// 队列中数据的个数
    	private Integer size;
    	// 指向队列头
    	private Integer start;
    	// 指向队列尾
    	private Integer end;
    
    	public ArrayQueue(int initSize) {
    		if (initSize < 0) {
    			throw new IllegalArgumentException("The init size is less than 0");
    		}
    		arr = new Integer[initSize];
    		size = 0;
    		start = 0;
    		end = 0;
    	}
    
        /**
         * 返回队列头
         * @return
         */
    	public Integer peek() {
    		if (size == 0) {
    			return null;
    		}
    		return arr[start];
    	}
    
    
       /**
        * 添加元素
        * @param num
        */
    	public void push(int num) {
    	    // 判断队列是否已经满了
    		if (size == arr.length) {
    			throw new ArrayIndexOutOfBoundsException("The queue is full");
    		}
    		// 没有满,大小加一
    		size++;
    		// 队列尾赋值
    		arr[end] = num;
    		// 跟新队列尾的位置
    		end = end == arr.length - 1 ? 0 : end + 1;
    	}
    
       /**
        * 出队列
        * @return
        */
    	public Integer poll() {
    	    // 队列为空
    		if (size == 0) {
    			throw new ArrayIndexOutOfBoundsException("The queue is empty");
    		}
    		// 不为空的时候大小减一
    		size--;
    		// 记录当前队列头元素
    		int tmp = start;
    		// 更新队列头位置
    		start = start == arr.length - 1 ? 0 : start + 1;
    		// 返回队列头元素
    		return arr[tmp];
    	}
    }
    

    三、稀疏数组

    public class SparseArray {
        public static void main(String[] args) {
            //原始二维数组:10*10
            int chessArray1[][] = new int[10][10];
            chessArray1[1][2] = 1;
            chessArray1[2][3] = 2;
            chessArray1[4][5] = 2;
            System.out.println("原始数组:");
            //1.遍历每一行
            for (int[] row : chessArray1) {
                //2.遍历每一行的数据
                for (int data : row) {
                    System.out.printf("%d\t",data);
                }
                System.out.println();
            }
    
            /**
             * 将二维数组转化为稀疏数组
             */
            //1.获取原始数组中不为0的元素的个数
            int sum = 0;
            for (int[] row : chessArray1) {
                for (int data : row) {
                    if (data != 0) {
                        sum++;
                    }
                }
            }
            //2.根据sum创建稀疏数组
            int sparseArray[][] = new int [sum+1][3];
            sparseArray[0][0] = 10;
            sparseArray[0][1] = 10;
            sparseArray[0][2] = sum;
            //3.将二维数组中的有效数字存到稀疏数组
            int count = 0;//记录非0数据的个数
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 10; j++) {
                    if (chessArray1[i][j] != 0){
                        count++;
                        //有效元素在原二维数组中的位置
                        sparseArray[count][0] = i;
                        sparseArray[count][1] = j;
                        //有效元素的值
                        sparseArray[count][2] = chessArray1[i][j];
                    }
                }
            }
            System.out.println("稀疏数组:");
            //1.遍历每一行
            for (int[] row : sparseArray) {
                //2.遍历每一行的数据
                for (int data : row) {
                    System.out.printf("%d\t",data);
                }
                System.out.println();
            }
    
            /**
             * 将稀疏数组转化为原二维数组
             */
            //1.先获取原数组的大小,创建二维数组
            int chessArray2[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
            //2.从第二行开始遍历稀疏数组,取出值赋值给二维数组
            for (int i = 1; i < sparseArray.length; i++) {
                chessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
            }
            System.out.println("恢复后的二维数组:");
            //3.输出新的二维数组
            for (int[] row : chessArray2) {
                //2.遍历每一行的数据
                for (int data : row) {
                    System.out.printf("%d\t",data);
                }
                System.out.println();
            }
    
        }
    }
    原始数组:
    0	0	0	0	0	0	0	0	0	0	
    0	0	1	0	0	0	0	0	0	0	
    0	0	0	2	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	2	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    稀疏数组:
    10	10	3	
    1	2	1	
    2	3	2	
    4	5	2	
    恢复后的二维数组:
    0	0	0	0	0	0	0	0	0	0	
    0	0	1	0	0	0	0	0	0	0	
    0	0	0	2	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	2	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    0	0	0	0	0	0	0	0	0	0	
    

    四、数组中的最大差值

    public  static int maxGap(int[] arr){
        if (arr == null || arr.length < 2){
            return 0;
        }
        int length = arr.length;
        // 初始化max为最小值
        int max = Integer.MIN_VALUE;
        // 初始化min为最大值
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < length; i++) {
            //求出数组中的最大值
            max = Math.max(max,arr[i]);
            //求出数组中的最小值
            min = Math.min(min,arr[i]);
        }
        // 如果数组中只有一个数
        if (max == min){
            return 0;
        }
        // 用来标识每个桶中是否有数据(length + 1 个桶)
        boolean[] hasNum = new boolean[length + 1];
        // 用来存放每个桶中的最大值(length + 1 个桶)
        int[] maxs = new int[length + 1];
        // 用来存放每个桶中的最小值(length + 1 个桶)
        int[] mins = new int[length + 1];
        // 数组中的当前元素应该进入哪个桶
        int bid;
        // 更新当前桶中的最大值和最小值,标记是否是存入数据
        for (int i = 0; i < length; i++) {
            //确定当前数放入到哪个桶中
            bid = bucket(arr[i], length, min, max);
            // 如果当前桶中没有数,则当前数为最小,如果有则和原来最小数比较更新最小数
            mins[bid] = hasNum[bid] ? Math.min(arr[i], mins[bid]) : arr[i];
            // 如果当前桶中没有数,则当前数为最大,如果有则和原来最大数比较更新最大数
            maxs[bid] = hasNum[bid] ? Math.min(arr[i], maxs[bid]) : arr[i];
            hasNum[bid] = true;
        }
        // 全局最大差值
        int result = 0;
        // 第一个桶的最大值
        int lastMax = maxs[0];
        // 从第2个桶开始遍历,比较当前非空桶的最小值和上一个非空桶的最大值之间的差值和全局差值的大小关系
        for (int i = 1; i < maxs.length; i++) {
            if (hasNum[i]) {
                result = Math.max(result, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return result;
    }
    
    /**
     * 确定数组中某个数该去几号桶
     * @param num
     * @param length
     * @param min
     * @param max
     * @return
     */
    private static int bucket(int num, int length, int min, int max) {
        return((num - min) * length / (max - min));
    }
    

    在这里插入图片描述

    01. 两数之和

    /**
     * @auther Mr.Liao
     * @date 2019/11/5 14:26
     * 给定一个整数数组 nums 和一个目标值 target
     * 请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
     */
    public class Solution {
        public static void main(String[] args) {
            int[] arr = {2, 3, 7, 11};
            System.out.println(Arrays.toString(twoSum3(arr,9)));
        }
        
        /**
         * 一遍哈希表
         * @param nums
         * @param target
         * @return
         * 假设 a + b  = target
         */
        public static int[] twoSum2(int[] nums, int target) {
            Map<Integer, Integer> map = new HashMap<>();
            // 遍历数组,假设当前元素的为a,看是否存在b
            for (int i = 0; i < nums.length; i++) {
                // 当前元素a,对应的b
                int complement = target - nums[i];
                // b是否在数组中(是否存在map中),存在返回下标
                if (map.containsKey(complement)) {
                    return new int[]{map.get(complement), i};
                }
                // 元素为k,下标为v,存入map中
                map.put(nums[i], i);
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    
        /**
         * 不使用hash表 空间复杂度O(1)
         * @param nums
         * @param target
         * @return
         */
        public static int[] twoSum3(int[] nums, int target) {
            // 先排序
            Arrays.sort(nums);
            int l = 0, r = nums.length - 1;
            while (l < r) {
                // 左右两个数相加大于target,右边界左移
                if (nums[l] + nums[r] > target) {
                    r--;
                } else if (nums[l] + nums[r] < target) {
                    // 小于,则左边界右移
                    l++;
                } else {
                    // 找到相加等于的返回
                    return new int[]{l, r};
                }
            }
            return new int[]{};
        }
    }
    

    04. 有序数组的中位数

    在这里插入图片描述
    我们只需要直接找出在数组1切这一刀的正确位置就可以了。 为了减少查找次数,我们对短的数组进行二分查找。将在数组1切割的位置记为cut1,在数组2切割的位置记为cut2,cut2=(size/2)-cut1。
    cut1,cut2分别表示的是数组1,数组2左边的元素的个数。

    切这一刀的结果有三种

    • 1)L1 > R2 则cut1应该向左移,才能保证合并后的数组前后部分顺序正确
    1 2 3 5 8 | 7 9 10 11 12  (此时结果是一样的,但是顺序不对,举了很多例子都会出现这种情况)
    
    • 2)L2 > R1 则cut1应该向右移,才能保证合并后的数组前后部分顺序正确
    1 2 3 5 7 10 | 5 8 9 11 12   (此时顺序结果都不对)
    
    • 3)其他情况(L1 <= R2 L2 <= R1),cut1的位置是正确的,可以停止查找,输出结果。

    其他说明
    1)考虑到边界条件,就是 cut 的位置可能在边缘,就是cut1=0或者cut1=N1,cut2=0或者cut2=N2的这些情况,我们将min和max两个特殊值分别加在数组1和数组2的两端,就可以统一考虑了。还有N1个数为0的时候,直接输出结果即可。
    在这里插入图片描述
    在这里插入图片描述

    2)为了减少查找时间,使用的是二分查找,就是cut1的位置是一半一半的查找的,实现时间只要log(N),不然就会超时。所以,我们不能只是简单地将cut1--或者cut1++,而是要记下每次cut1的区域范围,我们将cut1的范围记录下来,用[cutL, cutR]表示。一开始cut1的范围是[cutL,cutR]=[0,N1], 如果L1 > R2 则cut1应该向左移,cut1的范围就变成了[cutL, cut1-1],下次的cut1的位置就是cut1 = (cutR - cutL) / 2 + cutL;如果L2 > R1 则cut1应该向右移,cut1的范围就变成了[cut1+1, cutR],下次的cut1的位置就是cut1 = (cutR - cutL) / 2 + cutL;

    3)数组的元素个数和是奇数的情况下,中间的元素应该就是min(R1, R2),只需另外处理输出就可以了。

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int N1 = nums1.length;
        int N2 = nums2.length;
        if (N1 > N2) {// 确保 nums1是短的部分。
            return findMedianSortedArrays(nums2, nums1);
        }
        if (N1 == 0)
            return ((double) nums2[(N2 - 1) / 2] + (double) nums2[N2 / 2]) / 2;
        int N = N1 + N2;
        int cutL = 0, cutR = N1;
        int cut1 = 0, cut2;
        while (cut1 <= N1) {
        	// cutL和 curR的中间位置
            cut1 = (cutR - cutL) / 2 + cutL;
            // cut2的位置
            cut2 = N / 2 - cut1;
            // cut1前面一个数
            double L1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1 - 1];
            // cut2前面一个数
            double L2 = (cut2 == 0) ? Integer.MIN_VALUE : nums2[cut2 - 1];
            // R1位置就是cut1位置
            double R1 = (cut1 == N1) ? Integer.MAX_VALUE : nums1[cut1];
            // R2位置就是cut2位置
            double R2 = (cut2 == N2) ? Integer.MAX_VALUE : nums2[cut2];
            if (L1 > R2)
                cutR = cut1 - 1; //下一次 cut1二分的范围,右边界往左
            else if (L2 > R1)
                cutL = cut1 + 1; // 下一次cut1二分的范围,左边界往右
            else { // 找到正确的位置
                if (N % 2 == 0) { // 偶数个数的时候,取四个数中间两个数
                    L1 = (L1 > L2 ? L1 : L2);
                    R1 = (R1 < R2 ? R1 : R2);
                    return (L1 + R1) / 2;
                }
                else { // 奇数个数的时候
                    R1 = (R1 < R2 ? R1 : R2);
                    return R1;
                }
            }
        }
        return -1;
    }
    

    在这里插入图片描述
    拓展:找两个有序数组中,从小到大的第K个数

    public class Solution {
        public double findMedianSortedArrays(int nums1[], int nums2[]) {
            int n = nums1.length + nums2.length;
            // 两个数组长度加起来是偶数,找到中间两个数
            if (n % 2 == 0) {
                // 第(n / 2)个数
                int a = findKth(nums1, 0, nums2, 0, n / 2);
                // 第(n / 2 + 1)个数
                int b = findKth(nums1, 0, nums2, 0, n / 2 + 1);
                return (a + b) / 2.0;
            }
            // 两个数组长度加起来是奇数,找到第(n / 2 + 1)个数,就是中位数
            return findKth(nums1, 0, nums2, 0, n / 2 + 1);
        }
    
        /**
         * 两个数组中从小到大的第k个数
         * @param A
         * @param startOfA A数组开始下标,用来表示删掉以后哪些数还是有效的
         * @param B
         * @param startOfB B数组开始下标,用来表示删掉以后哪些数还是有效的
         * @param k        AB数组合起来C数组中的第几个数,注意不是下标
         * @return
         */
        public static int findKth(int[] A, int startOfA, int[] B, int startOfB, int k) {
            // A数组空了
            if (startOfA >= A.length) {
                // 返回 B的第k个数
                return B[startOfB + k - 1];
            }
            if (startOfB >= B.length) {
                return A[startOfA + k - 1];
            }
            if (k == 1) {
                return Math.min(A[startOfA], B[startOfB]);
            }
            // 找到A、B数组中从有效部分开始的第 k/2个数,对应数组中下标:有效位置+ k / 2 - 1
            // 当某一个数组没有 k/2 个之后,用最大值替代
            int halfKthOfA = startOfA + k / 2 - 1 < A.length ? A[startOfA + k / 2 - 1] : Integer.MAX_VALUE;
            int halfKthOfB = startOfB + k / 2 - 1 < B.length ? B[startOfB + k / 2 - 1] : Integer.MAX_VALUE;
            // 比较这两个数的大小
            if (halfKthOfA < halfKthOfB) {
                // 如果A的第 k/2个位置比B小,则丢掉A前 k/2个,要找的数变为第 k - k / 2 个,更新A起始位置
                return findKth(A, startOfA + k / 2, B, startOfB, k - k / 2);
            } else {
                return findKth(A, startOfA, B, startOfB + k / 2, k - k / 2);
            }
        }
    }
    

    11. 盛最多水的容器

    在这里插入图片描述

    class Solution {
        public static void main(String[] args) {
            int[] arr = new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7};
            System.out.println(maxArea(arr));
        }
    
        public static int maxArea(int[] height) {
            int area = 0, l = 0, r = height.length - 1;
            while (l < r) {
                area = height[l] < height[j] ?
                	Math.max(area, (r - l) * height[l++] :
                	Math.max(area, (r - l) * height[j--];
            }
            return area;
        }
    }
    

    15. 三数之和

    /**
     * 标签:数组遍历,双指针
     * 
     * 首先对数组进行排序,排序后固定一个数 nums[i],再使用左右指针指向 nums[i]后面的两端,
     * 数字分别为 nums[L] 和 nums[R]计算三个数的和 sum 判断是否满足为 0,满足则添加进结果集
     * 因为已经排好序了,当 nums[i]大于 0(后面的数都比它大),则三数之和必然无法等于 0,结束循环
     * 如果 nums[i] == nums[i-1],则说明该数字重复,会导致结果重复,所以应该跳过
     * 当 sum == 0 时,nums[L] == nums[L+1] 则会导致结果重复,应该跳过,L++
     * 当 sum == 0 时,nums[R] == nums[R-1] 则会导致结果重复,应该跳过,R--
     * 
     * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4] 相加等于0
     * 排序:[-4, -1, -1, 0, 1, 2]
     * nums[i]=-4 nums[L]=-1 nums[R]=2 
     * [[-1, 0, 1],[-1, -1, 2]]
     */
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> arr = new ArrayList<>();
            if (nums == null || nums.length < 3) {
                return arr;
            }
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                // l从1开始,r为数组结束下标
                int l = i + 1, r = nums.length - 1;
                // 如果两个数重复,跳过当次循环
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                // 当前数大于0,不存在了
                if (nums[i] > 0) {
                    break;
                }
                while (l < r) {
                    int sum = nums[i] + nums[l] + nums[r];
                    if (sum < 0) {
                        l++;
                    } else if (sum > 0) {
                        r--;
                    } else {
                        arr.add(Arrays.asList(nums[i], nums[l], nums[r]));
                        // 去重:l多移动一位
                        while (l < r && nums[l] == nums[l + 1]) {
                            l++;
                        }
                        // 去重:r多移动一位
                        while (l < r && nums[r] == nums[r - 1]) {
                            r--;
                        }
                        l++;
                        r--;
                    }
                }
            }
            return arr;
        }
    }
    

    26. 删除排序数组中多余重复元素

    /**
     * 删除重复项只保留一个
     * 双指针
     * 如果 l r指针指向的元素相同则 r继续右移
     * 如果 l r指向的元素不同,则把 r位置的数换到 l的下一个位置,l r都右移一位
     * 直到 r 指向数组结尾的下一个位置,此时l指向不重复新数组的最后一个位置
     */
    class Solution {
        public int removeDuplicates(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            int l = 0;
            int r = 1;
            while(r < nums.length){
                // 把 r位置的数换到 l的下一个位置,l r都右移一位
                if(nums[l] != nums[r]){
                    nums[l + 1] = nums[r];
                    l++;
                }
                r++;
            }
            return l + 1;
        }
    }
    

    27. 删除数组中指定的元素

    /**
     * 全部移除某个元素
     * 给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。
     * 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     */
    class Solution {
        public static void main(String[] args) {
            int[] nums = {3, 2, 2, 3};
            System.out.println(removeElement(nums, 3));
        }
    
        public static int removeElement(int[] nums, int val) {
            int l = 0, r = 0;
            while (r < nums.length) {
                // 如果r位置的数不是给定的数,则把r位置的数赋值给l位置, l r都右移
                if (nums[r] != val) {
                    nums[l] = nums[r];
                    l++;
                }
                // 如果是要删除的数,只是r右移
                r++;
            }
            return l;
        }
    }
    

    ① 删除字符串中的空格

    // 如果给的字符串数组,删除后返回不含空格的字符长度
    public int deleteSpace(char[] str) {
        int l = 0, r = 0;
        while (r < str.length) {
            if (str[r] != ' ') {
                str[l] = str[r];
                l++;
            }
            r++;
        }
        return l;
    }
    // 如果给的是字符串,则要使用额外空间
    public String deleteSpace(String str) {
    	// 或者直接转成字符串数组,使用上面的方法
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == ' ') {
                continue;
            }
            res.append(c);
        }
        return res.toString();
    }
    

    31. 下一个全排列

    在这里插入图片描述

    class Solution {
        public void nextPermutation(int[] nums) {
            if (nums == null || nums.length == 0) return;
            int n = nums.length;
            int small = -1;
            int big = 1;
            // 从右到左,找到第一个左边比右边小的数
            for (int i = n - 2; i >= 0; i--) {
                if (nums[i] < nums[i + 1]) {
                    small = i;
                    break;
                }
            }
            // 如果本来就是最大的(3,2,1),此时循环完后 small依然是 -1
            if (small == -1) {
                reverse(nums, 0, nums.length - 1);
                return;
            }
            // 如果找到了一个比右边小的数,再从右到small位置找第一个比small大的数
            for (int i = n - 1; i > small ; i--) {
                if (nums[i] > nums[small]) {
                    big = i;
                    break;
                }
            }
            swap(nums, small, big);
            reverse(nums, small + 1, n - 1);
            return;
        }
    
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    
        private void reverse(int[] nums, int i, int j) {
            while (i < j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
    }
    

    42. 接雨水

    class Solution {
        public int trap(int[] height) {
            if (height == null || height.length < 3) return 0;
            int maxRain = 0, leftMax = 0, rightMax = 0, left = 0, right = height.length - 1;
            while (left < right) {
                // 更新左边最大值
                leftMax = Math.max(leftMax, height[left]);
                // 更新右边最大值
                rightMax = Math.max(rightMax, height[right]);
                if (leftMax < rightMax) {
                    maxRain += leftMax - height[left];
                    left++;
                } else {
                    maxRain += rightMax - height[right];
                    right--;
                }
            }
            return maxRain;
        }
    }
    

    当左边最大值小于右边最大值的时候,左边当前墙能接的雨水是确定的
    在这里插入图片描述
    当左边最大值大于右边最大值的时候,右边当前墙能接的雨水是确定的
    在这里插入图片描述

    46. 全排列

    在这里插入图片描述

    class Solution {
    
        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] nums = {1, 2, 3};
            System.out.println(solution.permute(nums));
        }
    
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if (nums == null || nums.length == 0) return res;
            dfs(nums, res, new ArrayList<>(), new boolean[nums.length]);
            return res;
        }
    
        /**
         * @param nums
         * @param res
         * @param subset    以某一个数开头的结果 ([1,...]...[2,...]...[3,...])
         * @param visited   用于记录当前递归中哪些数被访问了,在下一层递归中可以知道,从而跳过这个数
         */
        private void dfs(int[] nums, List<List<Integer>> res, List<Integer> subset, boolean[] visited) {
            // 退出条件:已经找完了数组中的所有数,即形成了一种可能,将该可能加入到结果中,返回
            if (subset.size() == nums.length) {
                res.add(new ArrayList<>(subset));
                return;
            }
            // 拆解
            for (int i = 0; i < nums.length; i++) {
                // 当前元素已经被访问过,跳过当前元素
                if (visited[i]) continue;
                // 当前元素添加到当前层中
                subset.add(nums[i]);
                // 当前元素的状态设置为被访问过
                visited[i] = true;
                dfs(nums, res, subset, visited);
                // 递归每一层返回的时候,将已经加入到subset中的数移除
                subset.remove(subset.size() - 1);
                // 并且清除访问状态
                visited[i] = false;
            }
    
        }
    }
    

    47. 全排列 II

    class Solution {
    
        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] nums = {1, 1, 3};
            System.out.println(solution.permute(nums));
        }
    
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if (nums == null || nums.length == 0) return res;
            Arrays.sort(nums);
            dfs(nums, res, new ArrayList<>(), new boolean[nums.length]);
            return res;
        }
    
        /**
         * @param nums
         * @param res
         * @param subset    以某一个数开头的结果 ([1,...]...[2,...]...[3,...])
         * @param visited   用于记录当前递归中哪些数被访问了,在下一层递归中可以知道,从而跳过这个数
         */
        private void dfs(int[] nums, List<List<Integer>> res, List<Integer> subset, boolean[] visited) {
            // 退出条件:已经找完了数组中的所有数,即形成了一种可能,将该可能加入到结果中,返回
            if (subset.size() == nums.length) {
                res.add(new ArrayList<>(subset));
                return;
            }
            // 拆解
            int preNum = nums[0] - 1;
            for (int i = 0; i < nums.length; i++) {
                // 当前数被访问过,或者当前数等于前一个数
                if (visited[i] || nums[i] == preNum) continue;
                preNum = nums[i];
                // 当前元素添加到当前层中
                subset.add(nums[i]);
                // 当前元素的状态设置为被访问过
                visited[i] = true;
                dfs(nums, res, subset, visited);
                // 递归每一层返回的时候,将已经加入到subset中的数移除
                subset.remove(subset.size() - 1);
                // 并且清除访问状态
                visited[i] = false;
            }
        }
    }
    

    53. 最大子序和

    在这里插入图片描述
    方法一

    public class Solution {
        public static void main(String[] args) {
            int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
            System.out.println(maxSubArray2(arr));
        }
    
        public static int maxSubArray1(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            // max记录全局最大值,sum记录区间和,如果当前sum>0,那么可以继续和后面的数求和,否则就从0开始
            int max = Integer.MIN_VALUE, sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                max = Math.max(max, sum);
                sum = Math.max(sum, 0);
            }
            return max;
        }
    }
    

    方法二:分治

    public static int maxSubArray3(int[] nums) {
        return findMaxSubSum(nums, 0, nums.length - 1);
    }
    
    public static int findMaxSubSum(int[] nums, int start, int end) {
        if (start == end) return nums[start];
        if (start > end) return Integer.MIN_VALUE;
        // 左边区间的最大子序和
        int leftMax;
        // 右边区间的最大子序和
        int rightMax;
        // 中间向左最大子序和
        int middleToLeftMax = 0;
        // 中间向右最大子序和
        int middleToRightMax = 0;
        int middle = start + (end - start) / 2;
        leftMax = findMaxSubSum(nums, start, middle - 1);
        rightMax = findMaxSubSum(nums, middle + 1, end);
        // 从中间向左
        for (int i = middle - 1, sum = 0; i >= start; i--) {
            sum += nums[i];
            if (middleToLeftMax < sum) middleToLeftMax = sum;
        }
        // 从中间向向右
        for (int i = middle + 1, sum = 0; i <= end; i++) {
            sum += nums[i];
            if (middleToRightMax < sum) middleToRightMax = sum;
        }
        // 左右两个区间中较大的子序和,和跨过中点的最大子序和比较,取较大值
        return Math.max(Math.max(leftMax, rightMax), middleToLeftMax + middleToRightMax + nums[middle]);
    }
    

    54. 螺旋矩阵

    class Solution {
        public static void main(String[] args) {
            int[][] ints = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}};
            spiralOrder(ints);
        }
    
        public static List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> res = new ArrayList<>();
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return res;
            }
            int left = 0, right = matrix[0].length - 1;
            int top = 0, bottom = matrix.length - 1;
            while (left < right && top < bottom) {
                for (int i = left; i < right; i++) res.add(matrix[top][i]);
                for (int i = top; i < bottom; i++) res.add(matrix[i][right]);
                for (int i = right; i > left; i--) res.add(matrix[bottom][i]);
                for (int i = bottom; i > top; i--) res.add(matrix[i][left]);
                left++;
                right--;
                top++;
                bottom--;
            }
            if (left == right) {
                for (int i = top; i <=bottom ; i++) res.add(matrix[i][left]);
            } else if (top == bottom) {
                for (int i = left; i <=right ; i++) res.add(matrix[top][i]);
            }
            return res;
        }
    }
    

    在这里插入图片描述

    69. 螺旋矩阵2

    参考54

    class Solution {
        public int[][] generateMatrix(int n) {
            int left = 0, right = n - 1, top = 0, bottom = n - 1;
            int[][] mat = new int[n][n];
            int num = 1, tar = n * n;
            while(top < bottom && left < right){
                for(int i = left; i < right; i++) mat[top][i] = num++; // left to right.
                for(int i = top; i < bottom; i++) mat[i][right] = num++; // top to bottom.
                for(int i = right; i > left; i--) mat[bottom][i] = num++; // right to left.
                for(int i = bottom; i > top; i--) mat[i][left] = num++; // bottom to top.
                // 更新边界指针
                top++;
                bottom--;
                left++;
                right--;
            }
            // 当 n是奇数的时候,填上正中间这个数
            if (n%2!=0) mat[n/2][n/2] = n;
            return mat;
        }
    }
    

    74. 搜索二维矩阵

    /**
     * 每行中的整数从左到右按升序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     * 1 2 3
     * 4 5 6
     * 7 8 9
     */
    class Solution {
        /**
         * 一次二分
         * @param matrix
         * @param target
         * @return
         */
        public boolean searchMatrix1(int[][] matrix, int target) {
            int m = matrix.length; // 行
            if (m == 0) return false;
            int n = matrix[0].length; // 列
            // 二分查找,整体看成一个有序数组
            int l = 0, r = m * n - 1;
            int mid, x;
            while (l <= r) {
                mid = l + (r - l) / 2;
                // mid位置的数在矩阵中的位置[mid / n][mid % n]
                x = matrix[mid / n][mid % n];
                if (target == x) return true;
                else {
                    if (target < x) r = mid - 1;
                    else l = mid + 1;
                }
            }
            return false;
        }
    
        /**
         * 两次二分
         * @param matrix
         * @param target
         * @return
         */
        public boolean searchMatrix2(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0) {
                return false;
            }
            if (matrix[0] == null || matrix[0].length == 0) {
                return false;
            }
            // 二分列,找到第一列中最后一个<=target的行,这个数可能就在这一行中
            int row = matrix.length;
            int column = matrix[0].length;
            int start = 0, end = row - 1;
            while (start + 1 < row) {
                int mid = start + (end - start) / 2;
                int x = matrix[mid][0];
                if (x == target) {
                    return true;
                } else if (x < target) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
            if (matrix[end][0] <= target) {
                row = end;
            } else if (matrix[start][0] <= target) {
                row = start;
            } else {
                return false;
            }
            // 二分行,找到列
            start = 0;
            end = column - 1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                int x = matrix[row][mid];
                if (x == target) {
                    return true;
                } else if (x < target) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
            if (matrix[row][start] == target) {
                return true;
            } else if (matrix[row][end] == target) {
                return true;
            } else {
                return false;
            }
        }
    }
    

    88. 合并两个有序数组

    /**
     * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
     * 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
     *
     * 因为 nums1 的空间都集中在后面,所以从后向前处理排序的数据会更好,节省空间,一边遍历一边将值填充进去
     * 设置指针 len1 和 len2 分别指向 nums1 和 nums2 的有数字尾部,从尾部值开始比较遍历
     * 同时设置指针 len 指向 nums1 的最末尾,每次遍历比较值大小之后,则进行填充
     * 当 len1<0 时遍历结束,此时 nums2 中还有数据未拷贝完全,将其直接拷贝到 nums1 的前面,最后得到结果数组
     * 时间复杂度:O(m+n)
     *
     */
    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            // nums1有效数组的长度
            int len1 = m - 1;
            // nums2有效数组的长度
            int len2 = n - 1;
            // 合并后nums1从尾到头的位置
            int len = m + n - 1;
            while(len1 >= 0 && len2 >= 0) {
                // 谁大谁往后填
                nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
            }
            // 如果nums2中还有剩余的数,将剩余的数拷贝到nums1中,如果没有 len2=-1
            System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
        }
    }
    

    121. 买卖股票的最佳时机1

    在这里插入图片描述

    /**
     * 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
     * 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
     * 注意你不能在买入股票前卖出股票。
     * 等价于:
     *      在数组中找到两个数,使得后面的数减前面的数,差值最大,返回最大差值
     */
    class Solution {
        public static void main(String[] args) {
            int[] arr = {7, 1, 5, 3, 6, 4};
            System.out.println(maxProfit(arr));
        }
    
        public static int maxProfit(int[] prices) {
            if (prices.length < 2) {
                return 0;
            }
            int maxProfit = 0;
            int minPrice = prices[0];
            for (int i = 1; i < prices.length; i++) {
                //找到价格最低的一天
                minPrice = Math.min(minPrice, prices[i]);
                //每一天都减去价格最低的一天,取最大值
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            }
            return maxProfit;
        }
    }
    

    122. 买卖股票的最佳时机2

    在这里插入图片描述

    class Solution {
        public int maxProfit(int[] prices) {
            int maxProfit = 0;
            // 从第二天开始计算
            for (int i = 1; i < prices.length; i++) {
                // 今天的价格减去昨天的价格,如果大于0,则获得利润
                int temp = prices[i] - prices[i -1];
                if (temp > 0) {
                    maxProfit += temp;
                }
            }
            return maxProfit;
        }
    }
    

    169. 多数元素(超过n/2)

    class Solution {
        public int majorityElement(int[] nums) {
            int count = 0, candidate = -1;
            for (int i = 0; i < nums.length; i++) {
                // 当count为零时,当前数作为候选众数candidate
                if (count == 0) {
                    candidate = nums[i];
                    count = 1;
                } else if (candidate == nums[i]) {
                    // 后面的值和candidate相等,则count++
                    count++;
                } else {
                    // 如果值不相等,则则count--,直到count为0,抵消掉之前的数
                    count--;
                }
            }
            return candidate;
        }
    }
    

    189. 旋转数组_和恢复

    输入: [1,2,3,4,5,6,7] 和 k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1 步: [7,1,2,3,4,5,6]
    向右旋转 2 步: [6,7,1,2,3,4,5]
    向右旋转 3 步: [5,6,7,1,2,3,4]

    class Solution {
        public void rotate(int[] nums, int k) {
            k %= nums.length;
            // 1,2,3,4,5,6,7 -> 7,6,5,4,3,2,1
            reverse(nums, 0, nums.length - 1);
            // 7,6,5,4,3,2,1 -> 5,6,7,4,3,2,1
            reverse(nums, 0, k - 1);
            // 5,6,7,4,3,2,1 -> 5,6,7,1,2,3,4
            reverse(nums, k, nums.length - 1);
        }
        /**
         * 翻转数组
         * @param nums
         * @param start 起始下标
         * @param end   结束下标
         */
        public static void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start++;
                end--;
            }
        }
    }
    时间复杂度:O(n),n个元素被反转了总共 3 次。
    空间复杂度:O(1),没有使用额外的空间。
    

    200. 岛屿数量

    在这里插入图片描述

    class Solution {
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
    
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            int cnt = 0;
            int m = grid.length, n = grid[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 如果是water就跳过,如果是land就recursion
                    if (grid[i][j] == '1') {
                        // 将成片的 land更新成 water
                        dfs(grid, i, j);
                        // 递归完之后,land的数量加一
                        cnt++;
                    }
                }
            }
            return cnt;
        }
    
        private void dfs(char[][] grid, int i, int j) {
            // 不越界,或者碰到了 water
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
            // 把检查过的陆地更新成水,连成一片的 land算作一个岛屿
            // 之所以要变成 water,表示已经计算过了,不影响后面的过程
            grid[i][j] = '0';
            // 然后再看当前元素的四个方向
            for (int k = 0; k < 4; k++) {
                dfs(grid, i + dx[k], j + dy[k]);
            }
        }
    }
    

    215. 数组中第k大元素

    /**
     * [3,2,3,1,2,4,5,5,6] 和 k = 4
     * [6,5,5,4,3,3,2,2,1] 第4大,从左往右第4个就是4 两个5相等但是算两个
     * 不是说 6第一个 5第二大 4第三大
     */
    class Solution {
        public static void main(String[] args) {
            int[] nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
            System.out.println(findKthLargest(nums, 4));
        }
        public static int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for (int num : nums) {
                queue.offer(num);
                System.out.println("添加元素:"+queue);
                // 如果队列中的数量大于 k则弹出最小的,然后继续往里面放
                if (queue.size() > k) queue.poll();
                System.out.println("添加以后:"+queue);
            }
            // 循环完之后,队列中保留了 k个元素,最小的就是第 k大的元素
            return queue.poll();
        }
    }
    
    添加元素:[3]
    添加以后:[3]
    添加元素:[2, 3]
    添加以后:[2, 3]
    添加元素:[2, 3, 3]
    添加以后:[2, 3, 3]
    添加元素:[1, 2, 3, 3]
    添加以后:[1, 2, 3, 3]
    添加元素:[1, 2, 3, 3, 2]
    添加以后:[2, 2, 3, 3]
    添加元素:[2, 2, 3, 3, 4]
    添加以后:[2, 3, 3, 4]
    添加元素:[2, 3, 3, 4, 5]
    添加以后:[3, 4, 3, 5]
    添加元素:[3, 4, 3, 5, 5]
    添加以后:[3, 4, 5, 5]
    添加元素:[3, 4, 5, 5, 6]
    添加以后:[4, 5, 5, 6]
    4
    

    229. 求众数 II(超过n/3次的元素)

    class Solution {
        public List<Integer> majorityElement(int[] nums) {
            List<Integer> res = new ArrayList<>();
            if (nums == null || nums.length == 0)
                return res;
            //初始化:定义两个候选人及其对应的票数
            int candidateA = nums[0];
            int candidateB = nums[0];
            int countA = 0;
            int countB = 0;
            //遍历数组,找到出现次数最多的两个数,只有这两个数出现的次数可能大于n/3
            for (int num : nums) {
                if (num == candidateA) {
                    countA++;//投A
                    continue;
                }
                if (num == candidateB) {
                    countB++;//投B
                    continue;
                }
                //此时当前值和AB都不等,检查是否有票数减为0的情况,如果为0,则更新候选人
                if (countA == 0) {
                    candidateA = num;
                    countA++;
                    continue;
                }
                if (countB == 0) {
                    candidateB = num;
                    countB++;
                    continue;
                }
                //若此时两个候选人的票数都不为0,且当前元素不投AB,那么A,B对应的票数都要--;
                countA--;
                countB--;
            }
    
            //上一轮遍历找出了两个候选人,但是这两个候选人是否均满足票数大于N/3仍然没法确定,需要重新遍历,确定票数
            countA = 0;
            countB = 0;
            for (int num : nums) {
                if (num == candidateA)
                    countA++;
                else if (num == candidateB)
                    countB++;
            }
            if (countA > nums.length / 3)
                res.add(candidateA);
            if (countB > nums.length / 3)
                res.add(candidateB);
            return res;
        }
    }
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    

    
    
    展开全文
  • excel使用

    2012-11-25 17:06:01
    (9) 快速清除单元格内容如果要删除内容单元格中的内容和它格式和批注,就不能简单地应用选定该单元格,然后按Delete键方法了。要彻底清除单元格,可用以下方法:选定想要清除单元格或单元格范围;单击...
  • LeetCode解题总结

    2018-10-09 16:02:19
    2.4 删除链表中重复元素 2.5 指定位置旋转链表 2.6 删除倒数第N个节点 2.7 成对交换链表元素 2.8 复制复杂链表 2.9 链表环相关问题 2.9.1 链表是否有环 2.9.2 链表环入口 2.10 改变链表中元素位置2.11 LRU Cache...
  • <div><h3>数据结构概论 数据结构是计算机存储、组织数据方式。...经 位童鞋指正,发现此处有误,正确插入方法可查看评论,为保留错误原文不做改动!不懂具体插入过程可移步:...
  • 删除链表中重复的节点 测试57 第五十八题 二叉树的下一个节点 测试58 第五十九题 对称的二叉树 测试59 第六十题 按之字形顺序打印二叉树 测试60 第六十一题 把二叉树打印成多行 测试61 第六十二题 序列化...
  • 6.22 如何在一个文件判断声明为extern数组大小(例如,数组定义和大小在另一个文件)?sizeof操作符似乎不行。 6.23 sizeof返回大小是以字节计算,怎样才能判断数组有多少个元素呢? 第7章 内存分配 ...
  • 面试题3:二数组中的查找:对于在一个每一行从左到右依次递增,每一列从上到下依次递增数组查找一个元素,可以选择从数组左上角开始查找array[i][j],如果目标元素大于array[i][j],i+=1,如果元素小于array...
  • 剑指offer典型面试题

    2019-01-08 16:33:41
     面试题57:删除链表中重复的结点  8.4 树  面试题58:二叉树的下一个结点  面试题59:对称的二叉树  面试题60:把二叉树打印成多行  面试题61:按之字形顺序打印二叉树  面试题62:序列化二叉树  面试题63...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    《你必须知道495个C语言问题》以问答形式组织内容,讨论了学习或使用C语言过程经常遇到一些问题。书列出了C用户经常问400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预...
  • 杨 帆 -《准确性、全面性、美观性——测试数据设计中的三要素》 周咏基 -《论随机化算法原理与设计》 ## 2000 陈 彧 《信息学竞赛中的思维方法》 方 奇 《动态规划》 高寒蕊 -《递推关系建立及在信息学...
  • 实例139 删除数组中重复的连续元素 实例140 删除有序数组中的重复元素 实例141 数组合并 实例142 利用数组计算平均成绩 实例143 数组中整数的判断 实例144 判断二数组中是否有相同的元素 实例145 计算两个...
  • 0378. 有序矩阵中第 K 小元素 0380. 常数时间插入、删除和获取随机元素 0394. 字符串解码 91 0416. 分割等和子集 0445. 两数相加 II 0454. 四数相加 II 0464. 我能赢么 0494. 目标和 0516. 最长回...
  • 5.7 我编译器提供头文件定义NULL为0L。为什么? 57 5.8 NULL可以合法地用作函数指针吗? 57 5.9 如果NULL和0作为空指针常量是等价,那我到底该用哪一个呢? 58 5.10 但是如果NULL值改变了,比如在...
  • 实例139 删除数组中重复的连续元素 实例140 删除有序数组中的重复元素 实例141 数组合并 实例142 利用数组计算平均成绩 实例143 数组中整数的判断 实例144 判断二数组中是否有相同的元素 实例145 计算两个...
  • 张恒捷 -《关于三维最小乘积生成树一些研究》 徐 毅 -《浅谈回文子串问题》 梁泽宇 - 《浅谈维护多维数组方法在数据结构题中的应用》 **王悦同 -《根号算法——不只是分块》** **黄志翱 -《浅谈动态树相关...
  • 1.6.3 创建对多个工作表相同单元格区域的三维引用 30 1.6.4 更新跨工作簿引用公式 31 1.7 审核公式 31 1.7.1 使用公式错误检查器 32 1.7.2 定位特定类型数据 33 1.7.3 追踪单元格之间关系 33 1.7.4 ...
  • 实例084 使用正则表达式检查字符串中重复出现词 实例085 使用正则表达式替换字符串 实例086 使用正则表达式拆分字符串 实例087 使用正则表达式验证输入字母 实例088 使用正则表达式验证中文汉字输入 实例089...
  • 实例084 使用正则表达式检查字符串中重复出现词 实例085 使用正则表达式替换字符串 实例086 使用正则表达式拆分字符串 实例087 使用正则表达式验证输入字母 实例088 使用正则表达式验证中文汉字输入 实例089...
  • 实例084 使用正则表达式检查字符串中重复出现词 实例085 使用正则表达式替换字符串 实例086 使用正则表达式拆分字符串 实例087 使用正则表达式验证输入字母 实例088 使用正则表达式验证中文汉字输入 实例089...
  •  实例084 使用正则表达式检查字符串中重复出现词 99  实例085 使用正则表达式替换字符串 101  实例086 使用正则表达式拆分字符串 102  实例087 使用正则表达式验证输入字母 102  实例088 使用正则表达式...
  • 实例085 自动删除textbox控件中的非法字符 139 实例086 在richtextbox控件替换文本文字 141 实例087 利用richtextbox控件实现文字定位与标示 142 实例088 将数据表中的字段添加到combobox控件 143 实例089 对...
  • 数据结构与算法.xmind

    2020-06-19 17:04:23
    分配一个[array.length][10列]数组来装我们元素 最外层for循环控制要分配和回收次数(根据最大值) 将元素个、十、百位依次放到桶子上(第一次就是放个位,第二次放十位) 依据每列...
  • 实例130 使用泛型去掉数组中的重复数字 161 第6章 数据结构与算法 163 6.1 数据结构实现 164 实例131 单向链表实现 164 实例132 双向链表实现 168 实例133 堆栈实现 173 实例134 队列实现 175 实例135 树...
  • 32.搜索二维矩阵(74) 33.子集(78) 34.面试中的智力题 35.旋转图像(48) PART III:算法视野扩展 Bresenham直线算法与画圆算法 C语言经典算法100例 决策树和随机森林 常用推荐算法 微软面试100...
  • PowerPoint.2007宝典 8/10

    2012-04-01 18:39:23
    10.12.6 三维旋转和三维格式 218 10.13 小结 221 第11章 创建SmartArt图形 222 11.1 了解SmartArt类型及其用途 222 11.1.1 列表 222 11.1.2 流程 223 11.1.3 循环 224 11.1.4 层次结构 224 11.1.5 ...

空空如也

空空如也

1 2 3
收藏数 43
精华内容 17
关键字:

删除三维矩阵中重复的矩阵