将题目分类,总结常用的解题思路

参考图书

  • 《算法(第 4 版)》
  • 《编程之美》
  • 《剑指 Offer(纪念版)》

题目表格

题目 位置 解题思路 要点
插入排序      
希尔排序      
快速排序      
并归排序      
二分查找      
数组中只出现一次的数字 《剑指 Offer》P211 异或 + 分组  
Missing Number LeetCode 268 异或  
数组中重复的数字 《剑指 Offer》P261 1. 排序
2. 遍历 + 哈希表
3. 推理 + 重排数组
 
Find All Numbers Disappeared in an Array LeetCode 448 1. 推理 + 重排数组 2. “染色”  
数字在排序数组中出现的次数 《剑指 Offer》P204 1. 遍历
2. 二分查找
 
数组中出现次数超过一半的数字 《剑指 Offer》P163 1. 排序
2. 基于 Partition 函数
3. 所求数字比其他所有数字出现次数之和还要多
是否修改输入的数组
数组中出现次数超过一半的数字 《编程之美》P129 1. 排序
2.所求数字比其他所有数字出现次数之和还要多
 
寻找数组中的最大值和最小值 《编程之美》P165 1. 遍历
2. 分组
3. 分治
 
快速寻找满足条件的两个数 《编程之美》P176 1. 穷举
2. 排序 + 二分查找
3. 排序 + 遍历
 
最小的 K 个数 《剑指 Offer》P167 1. 排序
2. 基于 Partition 函数
3. 数据容器 + 最大堆
 
最大的 K 个数 《编程之美》P139 1. 排序
2. 基于快速排序
3+ TODO
 
构建乘积数组 《剑指 Offer》P263 画图  
子数组的最大乘积 《编程之美》P180 1. 枚举
2. 逻辑推理
 
子数组的最大和 《编程之美》P183 1. 枚举
2. 动态规划
 
连续子数组之和的最大值 《剑指 Offer》P171 1. 枚举
2. 分析数组的规律
3. 动态规划
 
连续子数组之和的最大值(二维) 《编程之美》P189 TODO  
数组中最长递增子序列 《编程之美》P194 1. 枚举
2. 动态规划
 
数组循环移位 《编程之美》P199 分析题意  
数组分割 《编程之美》P202 1. 排序 + 分组
2. 动态规划
 
二维数组中的查找 《剑指 Offer》P38 1. 遍历
2. 分析简单例子,寻找普遍规律;分组、剔除;
 
旋转数组的最小数字 《剑指 Offer》P66 1. 二分查找
2. 双指针找分界点
 
调整数组顺序使得奇数位于偶数前面 《剑指 Offer》P102 1. 遍历
2. 双指针交换奇偶数
3. 抽象 “分组逻辑判断”
 
把数组排成最小的数 《剑指 Offer》P177 抽象 sort 函数的 compare 函数  
数组中的逆序对 《剑指 Offer》P189 1. 遍历
2. 分组 + 并归排序
 

以上。