字数
2180 字
阅读时间
11 分钟
数组
查找：运用 HashMap 的键的唯一性
二分查找
前提条件：数组为有序数组，且无重复元素
难点：边界条件的确定
- 循环条件
- while(left < right)
- while(left <= right)
- 右边界的更新
- right == mid
- rifht == mid - 1
将区间定义为 不变量，再不断循环的过程中，while 条件判断的处理要遵循 不变量规则
第一种写法
区间定义为 [left, right]
分别对应
- while(left <= right)，因为 left == right 是有意义的
- if(nums[mid] > target) right 赋值为 mid - 1，因为当前的 nums[mid] 一定不是 target
java
class Solution {
public int search(int[] nums, int target) {
// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
}title:位运算符
<< ：左移运算符， num << 1,相当于 num乘以2
>> ：右移运算符， num >> 1,相当于 num除以2
正数左边第一位补0，负数补1
>>> ：无符号右移运算符，无符号右移运算符和右移运算符的主要区别在于负数的计算，因为无符号右移是高位补0，移多少位补多少个0。
15的二进制位是0000 1111 ， 右移2位0000 0011，结果为3第二种写法
区间定义为 [left, right)
分别对应
- while(left < right) 因为 left == right 是区间是没有意义的
- if(nums[mid] > target) right 更新为 right，因为 nums[mid] 的值取不到，不能确定该下标是否对应 target
java
class Solution {
public int search(int[] nums, int target) {
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid;
}
return -1;
}
}双指针法
快慢指针
java
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};左右指针
java
// 时间复杂度为 O(n)
class Solution {
public int[] sortedSquares(int[] nums) {
int right = nums.length - 1;
int left = 0;
int[] result = new int[nums.length];
int index = result.length - 1;
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
result[index--] = nums[left] * nums[left];
++left;
} else {
result[index--] = nums[right] * nums[right];
--right;
}
}
return result;
}
}滑动窗口
主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以时间复杂度是 2 × n 也就是 O(n)
——可以理解为 start 和 end 交替前进，当 start+1 时 end 不变，反之亦然，总的时间应该是 2n，也就是 n
java
// 时间复杂度为 O(n)
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= s) {
result = Math.min(result, right - left + 1);
sum -= nums[left++]; // 精髓之处
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}三数之和
Loading Question... - 力扣（LeetCode）
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。
把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。
去重的过程不好处理，有很多小细节，如果在面试中很难想到位。
时间复杂度可以做到$O(n^2)$，但还是比较费时的，因为不好做剪枝操作解题思路：
- 排序 + 双指针
java
public List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length <= 2) return ans;
Arrays.sort(nums); // O(nlogn)
for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
int target = -nums[i];
int left = i + 1, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
// 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
left++; right--; // 首先无论如何先要进行加减操作
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (nums[left] + nums[right] < target) {
left++;
} else { // nums[left] + nums[right] > target
right--;
}
}
}
return ans;
}四数之和
思路同三数之和：排序 + 双指针 + 两层 for 循环
不同之处：
- 对比三数之和，不需要开始 for 循环时的剪枝操作
if (nums[i] > target) break，因为四数之和的 target 可以是负数，四个数的首位值大于 0 只是针对 target 为非负数的情况（负数是需要末尾值小于 target）
2.剪枝操作：
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
java
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 4) {
return result;
}
Arrays.sort(nums);
int length = nums.length;
// -2 -1 0 0 1 2 / 0
for (int i = 0; i < length - 3; ++i) {
// 对比三数之和，不用判断 nums[i] > target
// if (nums[i] > target) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
for (int j = i + 1; j < length - 2; ++j) {
if ( j > i + 1 && nums[j] == nums[j - 1]) continue;
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
int temp = nums[i] + nums[j];
int tempTarget = target - temp;
int left = j + 1, right = length - 1;
while (left < right) {
if (nums[left] + nums[right] == tempTarget) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (nums[left] + nums[right] < tempTarget) {
left++;
} else {
right--;
}
}
}
}
return result;
}删除
排序好的数组
快慢双指针
未排序
快慢双指针（分别从起始和末尾考虑， head 和 tail）
动态规划
带备忘录的递归结构
核心：拆分子问题，记住过往，减少重复计算
- 穷举分析
- 确定边界
- 找规律，确定最优子结构
- 写出状态方程
- 代码实现
- 最优子结构
- 状态转移方程
- 边界
- 重叠子问题
- 背包问题
- 最小编辑距离
二叉树
生成二叉树
数组生成二叉树——遍历
java
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
/**
* 二叉树的生成
*
* @author DangerShi
*/
public class TreeBuilder {
class TreeNode {
Object data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(Object data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
public TreeNode arrayToBTree(Object[] arrs) {
if (arrs == null || arrs.length == 0) {
return new TreeNode();
}
List<TreeNode> nodes = new ArrayList<>(arrs.length);
for (Object obj : arrs) {
TreeNode treeNode = new TreeNode();
treeNode.data = obj;
nodes.add(treeNode);
}
for (int i = 0; i < arrs.length/2 - 1; i++) {
TreeNode node = nodes.get(i);
node.left = nodes.get(i*2 + 1);
node.right = nodes.get(i*2 + 2);
}
// 只有当总节点数是奇数时，最后一个父节点才有右子节点
int lastPNodeIndex = arrs.length/2 - 1;
TreeNode lastPNode = nodes.get(lastPNodeIndex);
lastPNode.left = nodes.get(lastPNodeIndex*2 + 1);
if (arrs.length%2 != 0) {
lastPNode.right = nodes.get(lastPNodeIndex*2 + 2);
}
return nodes.get(0);
}
@Test
public void test() {
/**
* 1
* 2 3
* 4 5 6 7
*/
TreeNode treeNode = arrayToBTree(new Object[]{1,2,3,4,5,6,7});
}
}数组生成二叉树——递归（数组是升序的，生成方式为中序遍历）
java
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right){
if(left > right){
return null;
}
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}boyer-moore 算法
#boyer-moore
背景
java
public int majorityElement(int[] nums) {
int count = 0;
int temp = 0;
for(int i = 0; i < nums.length; i++) {
if(count == 0){
temp = nums[i];
}
count += (temp == nums[i]) ? 1 : -1;
}
return temp;
}贡献者
jiechen