Data Structure and Algorithm
贪心算法
- 思想：选择每一阶段的局部最优，从而达到全局最优。
- 难点：如何通过局部最优，推出整体最优。
- 验证：手动模拟或举反例判断是否可以用贪心。
解题步骤
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
题目
-
思路：优先以较小尺寸的饼干满足较小胃口值的孩子
-
实现：将孩子胃口值
g[i]和饼干尺寸s[j]升序排列，遍历每个饼干，优先满足胃口小的孩子，若当前孩子得到满足，则考察下一个孩子，直至用尽所有饼干 或 满足所有孩子。
-
思路：保留沿途上的极值点作为摆动序列元素
-
实现：使用变量
prediff表示上一状态两个元素之间的差值，curdiff表示当前两个元素之间的差值，当prediff和curdiff异号时，表示遇到了一个极值点，元素数量加一，并更新prediff的状态。
-
思路：使用非负子序和去更新最大子序和
-
实现：遍历数组中的元素，将其加到
cursub中，并以此更新maxsub。如若cursub < 0，就将其置零，使得新的子序和从0开始累加，而非原本的负值。
-
思路：累加相邻两天的正利润
-
实现：将股票的交易利润进行分解。遍历股票价格，计算前后两天的交易利润，累加大于0的利润。
-
思路：最大跳跃距离是否能覆盖数组最后一个位置
-
实现：维护一个最远跳跃距离
maxjump，遍历数组[0, maxjump]，不断更新maxjump。若maxjump覆盖最后一个位置，则返回true。
-
思路：每一步尽可能跳远一些
-
实现：维护最远跳跃距离
maxjump和 当前跳跃距离curjump，遍历数组[0,n-2]，不断更新maxjump，若访问到curjump的位置，则增加跳跃次数，并使用maxjump更新curjump。
-
思路：优先取反绝对值较大的负数
-
实现：对数组以绝对值大小升序排列，逆序遍历整个数组，遇到负数且
K > 0时就将负数取反并--K。退出循环后若K为奇数，就将数组的首元素取反一次。
-
思路：当前剩余油量小于零时更新起始加油站编号
-
实现：使用变量
totalrest和currest表示总/当前剩油量，剩油量由gas[i] - cost[i]表示。遍历所有加油站，不断更新totalrest和currest，若currest < 0，则将currest置零 并 将下一个加油站作为起始加油站。退出循环后，若totalrest < 0，说明不能走完整个路程。
-
思路：分别正序及逆序根据评分及糖果数分发糖果
-
实现：使用长度为
n且初值为1的数组记录每个孩子的糖果数，先正序遍历数组，使相邻孩子中评分高的糖果数再多出一个；再逆序遍历数组，使相邻孩子中评分高且糖果少的，糖果数再多出一个。
-
思路：尽可能使用10美元的零钱而保留5美元的零钱
-
实现：使用变量
five、ten及twenty分别表示三种零钱的数量。遍历整个数组，更新5美元和10美元零钱数，当收到20美元的账单时，尽可能使用10美元零钱去找零。
-
思路：优先将身高较高且编号较小的人插入队列
-
实现：对数组根据身高较高且编号较小的顺序进行排序，构造
list<vetor<int>>队列，遍历整个数组，根据编号将队员插入队列中。
-
思路：根据气球右边界判定重叠范围
-
实现：根据气球的右边界对数组升序排列，使用变量
cover表示气球覆盖范围的右边界，遍历数组[1,n-1]，若当前气球的左边界大于cover，则更新cover并 增加弓箭数。
-
思路：根据区间右边界判定重叠范围
-
实现：根据区间的右边界对数组升序排列，使用变量
prev表示上一区间的右边界，遍历数组[1,n-1]，若当前区间的左边界小于prev，则增加区间移除数；否则更新prev。
-
思路：根据字母最后出现的位置划分区间
-
实现：保存字符串
S中每个字母最后出现的位置，使用变量begin和end表示区间的左/右边界，遍历S，不断更新end。若当前索引抵达end，则记录此区间，并更新begin。
-
思路：根据区间左边界排序后动态更新重叠区间
-
实现：根据区间的左边界对数组升序排列，使用二维数组
ret表示所有重叠区间，遍历数组[1,n-1]，若当前区间的左边界大于ret末区间的右边界，则将此区间添加到ret中；否则更新ret末区间的右边界为两个右区间的较大者。
-
思路：逆序地保证数组前后位数数字递增
-
实现：使用
flag记录起始修改位置，逆序遍历数字中的每一位，若当前数字大于下一位数字，则将当前数字减一，并更新flag为下一位数字的索引。退出循环后，将从flag（包含）位置以后的数字修改为9。
-
思路：累加当前股价与当前最低股价+手续费之间的正利润
-
实现：使用变量
minprice表示当前最低股价，遍历数组[1,n-1]，不断更新minprice，若当前股价大于minprice + fee，则累加当前利润，并更新minprice（免去手续费）。
双指针
若两个指针指向同一数组
- 遍历方向相同且不会相交，则称为滑动窗口，经常用于区间搜索
- 遍历方向相反，则称为对撞指针，用于在有序数组中进行搜索
题目
-
思路：根据
target的大小动态调整对撞指针的位置 -
实现：使用变量
lo和hi表示数组中的对撞指针，当指针指向的元素之和小于target时，向右移动lo；当指针指向的元素之和大于target时，向左移动hi，直到和等于target。
-
思路：使用对比指针比较两个数组中的元素并逆序填充较大者
-
实现：使用两个指针分别逆序遍历两个数组中的元素，在第一个数组空白处逆序填入两指针指向元素的较大者。当出现遍历完一个数组的情况时，直接填入另一个数组中的元素即可。
-
思路：使用快慢指针从头节点开始向后移动直到相遇后的再次相遇
-
实现：初始时快慢指针同时指向链表的头节点，随后快指针每次向后移动两部，慢指针每次向后移动一步，直到两指针相遇。此时将快指针移至头节点，快慢指针各每次向后移动一步，直到两指针相遇，即为入环的第一个节点。
-
思路：使用滑动窗口寻找有效的子串并比较出最短的
-
实现：首先将
t中的所有字符存储到哈希映射中，然后在s中移动滑动窗口并将当前字符存储到另一哈希映射中，根据当前字符在两个哈希映射中的出现次数进行滑动窗口的移动，当s中有效字符数量和t字符串长度一致时，更新最短子串。
-
思路：不断移动对撞指针直至找到合适的整数
-
实现：初始时指针
lo指向 0，指针hi指向sqrt(c)。通过将平方和与c进行比较，判断左移lo或右移hi或返回结果。
-
思路：利用对撞指针判断字符是否相等
-
实现：使用指针
lo和hi分别指向字符串的首位，依次判断字符是否相等。如相等则移动双指针；如不相等，则分别判断移动左右指针后的子字符串是否是回文串。
-
思路：对字典自定义排序后利用双指针判断字符是否相等
-
实现：首先根据字符串长度和字母序对字典进行排序，随后将指针
i、j分别指向字符串s和 排序后的字符串，判断两个串中的字符是否相等。如相等则同时移动i和j，否则只移动i，此时如果j移动到了字符串末尾，则返回当前字典中的字符串。
-
思路：使用双指针分别指向新数组和原数组
-
实现：使用变量
idx表示新数组的索引，遍历整个数组，如果当前元素不等于val，则将其放入新数组中，并后移idx。
-
思路：使用对撞指针依次交换字符串中的字符
-
实现：使用指针
lo和hi分别指向字符串的首尾，每次交换指针所指向的字符，同时移动双指针。
-
思路：移动双指针填充扩容后的字符串
-
实现：首先根据空格的个数对原字符串进行扩容，然后使用指针
i和j分别指向扩容后的字符串和原字符串的最后一个字符。当i > j时，遍历原字符串，如遇空格就向新字符串中逆序填充%20，否则就填充当前字符。
-
思路：利用双指针找到待删节点的前驱节点
-
实现：使用指针
first指向head，指针second指向dummy。首先将first后移n次，然后同时后移first和second直至first为空，此时second便指向待删节点的前驱节点。
-
思路：移动双指针寻找链表交点
-
实现：使用指针
pA和pB分别指向两个链表，如果pA或pB为空，则将其指向另一链表，否则后移该指针，直到两指针相遇。
-
思路：排序后固定第一个数的情况下使用对撞指针寻找另外两个数
-
实现：首先对数组进行升序排序，将数组的前n-2个元素之一作为三元组的第一个数，在余下子数组中利用对撞指针寻找另外两个数。
-
思路：排序后固定前两个数的情况下使用对撞指针寻找后两个数
-
实现：首先对数组进行升序排序，在数组的前n-3个元素中选两个作为四元组的前两个数，在余下子数组中利用对撞指针寻找后两个数。此题有多处剪枝操作，可大幅降低时间复杂度，同时需注意整数溢出问题。
二分查找
题目
-
思路：在
0 ~ x中使用二分查找搜索k^2 <= x的最大k -
实现：令
lo和hi分别指向0和x，当lo <= hi时，若中位数的平方小于等于x，则更新ret，并向右半区间继续查找；否则，向左半区间继续查找。
-
思路：使用二分查找分别搜索数组中该元素的第一个位置及该元素值+1的第一个位置
-
实现：使用
fPos表示target的第一个出现位置，lPos表示target + 1的出现位置-1。若fPos处的值合理则返回结果。
-
思路：在有序子数组中继续使用二分查找搜索目标值
-
实现：将中位数
nums[mid]与首元素nums[lo]进行比较，若前半部分有序且目标值在其中，则深入前半部分继续查找；否则深入后半部分继续查找。
-
思路：在有序子数组中继续使用二分查找搜索目标值
-
实现：将中位数
nums[mid]与首元素nums[lo]进行比较，若nums[mid]与数组首位元素均相等，则前后各压缩一次数组；若前半部分有序且目标值在其中，则深入前半部分继续查找；否则深入后半部分继续查找。
-
思路：根据中位数的奇偶性进行相邻元素判断从而实现二分查找
-
实现：若
mid为奇数，则将mid索引处的元素与上一元素相比；若mid为偶数，则将mid索引处的元素与下一元素相比；若比较的结果相等，则深入后半部分查找，否则深入前半部分继续查找。
-
思路：根据不大于
mid的元素数量进行二分查找 -
实现：使用
cnt表示不大于mid的元素数量，若cnt <= mid则深入后半部分查找，否则深入前半部分继续查找。
-
思路：总和减去元素和
-
实现：使用变量
total表示[0, n]的总和，sum表示数组nums中的元素和，则total - sum即为丢失的数字。
-
思路：递归求取左子树和右子树上的节点数
-
实现：首先求取左子树和右子树上的层数，若二者相等，则左子树为满二叉树，返回左子树节点数并递归求取右子树；若二者不相等，则右子树为满二叉树，返回右子树节点数并递归求取左子树。
-
思路：根据两数组总长度的奇偶性寻找数组第
k个元素 -
实现：使用
idx1和idx2表示两数组的起始索引，newIdx1和newIdx2表示两数组第k/2个元素的索引。若newIdx1处的元素值不大于newIdx2处的元素值，则k减去newIdx1前的元素数，将idx1更新为newIdx1 + 1；否则k减去newIdx2前的元素数，将idx2更新为newIdx2 + 1。
dfs/bfs
dfs
深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历； 因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。
bfs
广度优先搜索（breadth-first search，BFS）不同与深度优先搜索，它是一层层进行遍历的，因此需要用先入先出的队列而非先入后出的栈进行遍历。
由于是按层次进行遍历，广度优先搜索时 按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。
回溯
回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状态的深度优先搜索。 通常来说，排列、组合、选择类问题使用回溯法比较方便。
顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点(及 其子节点)并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态 还原。
动态规划
动态规划（Dynamic Programming，DP）在查找有很多 重叠子问题情况的最优解时有效。它将问题重新组合成子问题。
解决动态规划问题的关键是找到 状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。
Others
- 思路：将原始数字进行翻转后与原数字进行对比