[数据结构与算法]001 leetcode数组总结

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

• 题目：有序数组中每个元素保留一个
• 双指针

二、80 删除有序数组中的重复项II

• 题目：有序数组中每个元素保留两个
• 双指针
  • 方法一：保留重复数字中的第一个和最后一个
  • 方法二：保留重复数字的前两个

三、704 二分查找

• 题目：无重复元素的有序数组中找目标值
• 二分查找

四、33 搜索旋转排序数组

• 题目：无重复元素的有序数组按某个点旋转后查找目标值
• 二分查找
  • 方法一：找到旋转点，判断属于那部分区间，再二分查找
  • 方法二：直接二分查找,注意二分法中if的判断条件为，target在有序区间中

五、81 搜索旋转排序数组II

• 题目：有重复元素的有序数组中按某个点旋转后查找目标值
• 二分查找
  • 始终是寻找有序区间，在有序区间内开始正常的二分查找

六、4 寻找两个正序数组中的中位数

• 题目：给定两个有序数组，寻找合并后有序数组的中位数
• 二分查找，每次抛弃一半的范围

七、1 两数之和

• 题目：给定目标值，找到数组中不同的两个数使他们的和为目标值，返回这两个数的下标
• 哈希

八、15 三数之和

• 题目：一个有重复值乱序排列的数组，求其中所有和为0的三个数，返回所有没有重复三元组的结果
• 排序+双指针，注意去重

九、16 最接近的三数之和

• 题目：一个数组和一个目标值，求数组中三数之和离目标值最近的一个组合，返回这三个数的和
• 排序+双指针

十、18 四数之和

• 题目：一个数组一个目标值，求出所有四数之和为目标值的组合，返回所有没有重复四元组的结果
• 排序+双指针
  • 终极去重
  • 数据范围过大，强制类型转换

十一、27 移除元素

• 给定一个数组和一个关键字，删除数组中所有和关键字相等的元素，返回新数组的长度，在O(1)空间复杂度内完成
• 双指针

十二、31 下一个排列

• 给一个数组，求它的下一个排列，即比这些数字组成的整数大的最小组合
• 数学问题

十三、60 排列序列

• 题目：给数字1到n，它的所有排列自小到大排列，求第k个排列，返回存储该排列的字符串
• 逆康托展开，依次求解所找排列的每一位

十四、36 有效的数独

• 给一个矩阵，判断每行每列每个九宫格是否有数字重复
• 遍历一次同时判断三个条件

十五、42 接雨水

• 题目：给定一个数组表示宽为1的高度图，计算按照该方式排列的柱子能接到多少水
• 双指针
• 单调栈
• 将单个条件分解为两个条件，再组合起来

十六、48 旋转图像

• 给一个矩阵，求它绕中心顺时针旋转90度后的矩阵
• 两次翻转矩阵

十七、66 加一

• 题目：给定一个数组表示一个大数，给该数字加一

十八、70 爬楼梯

• 题目：n阶才可以到达楼顶，一次可以爬2阶或2阶，有几种方法可以到达楼顶
• 斐波那契数列

十九、89 格雷码

• 题目：n位编码总位数，打印其所有数字格雷码的十进制表示
• 位运算

二十、73 矩阵置零

• 题目：将矩阵中0所在的行和列全部置为0
• 将矩阵的0行0列作为标志位

二十一、134 加油站

• 题目：一条环路上有n个加油站，给两个数组，分别存储加油站油的数量和到达下一个加油站所需花费的油，求从哪开始可以走完环路回到起点
• 模拟+剪枝

二十二、135 分糖果

• 题目：n个孩子分糖果，每个孩子至少一颗糖果，评分更高的孩子要比评分低的孩子获得更多的糖果。
• 贪心

二十三、136 只出现一次的数字

• 题目：给一个数组，其中一个数字出现一次，其余数字出现两次，求只出现一次的数字
• 位运算

二十四、137 只出现一次的数字II

• 题目：给一个数组，其中一个数字出现一次，其余数字出现一次，求只出现一次的数
• 位运算

二十五、260 只出现一次的数字III

• 题目：给一个数组，其中两个数字出现一次，其余数字出现两次，求两个出现一次的数字
• 位运算

二十六、128 最长连续序列

• 题目：给一个乱序数组，找到最长连续序列的长度
• 哈希
• 并查集