40道算法题大全（在力扣你遇到过哪些醒脑的题解）
40道算法题大全（在力扣你遇到过哪些醒脑的题解）常规思路是使用动规解决（大家的讨论也都是围绕 DP 进行的），但是如果你了解一个定理，四平方和定理：任一个正整数都能拆成四个整数的平方和，这个问题就可以很快解决，速度快得超乎你的想象。279.完全平方数这道题的解法对于一些同学来说应该非常深刻，其中一个想法是放 hash Table，每个出现的数字就放在桶里面，每次出现就统计，代码如下：class Solution(object): def singleNumber(self nums): """ :type nums: List[int] :rtype: int """ hash_table = {} for i in nums: try:
众所周知，力扣的题库在众多程序员中一直拥有良好口碑，题库内的编程练习题也是从实际业务中提炼出的精华，同时许多大厂面试官也会通过力扣题库选择面试题给到面试者作为能力的鉴定。
所以在力扣上无论是求职找工作还是刷提神醒脑算法题、又或者 ACM 的同学希望得到一些专项的练习、对算法书籍的一些实际操作，相信都能在平台上得到收获。
所谓算法对应的题解，有的题解运行速度快，构思巧妙，有的题解循环次数太多，运行速度慢，这次力扣君列举了一些让人 "提神醒脑" 的题解，以飨读者，帮助大家发现算法和题解中意想不到的美。
136.只出现一次的数字
这道题的解法对于一些同学来说应该非常深刻，其中一个想法是放 hash Table，每个出现的数字就放在桶里面，每次出现就统计，代码如下：
class Solution(object):
def singleNumber(self nums):
"""
:type nums: List[int]
:rtype: int
"""
hash_table = {}
for i in nums:
try:
hash_table.pop(i)
except:
hash_table[i] = 1
return hash_table.popitem()[0]
但这样子做的话想法可能就太常规了，神奇的做法如下（使用 XOR）：
class Solution(object):
def singleNumber(self nums):
"""
:type nums: List[int]
:rtype: int
"""
a = 0
for i in nums:
a ^= i
return a
当然解法有很多，感兴趣的同学可以直接点击进入官网，力扣君也提供了相应的解法视频。
279.完全平方数
常规思路是使用动规解决（大家的讨论也都是围绕 DP 进行的），但是如果你了解一个定理，四平方和定理：任一个正整数都能拆成四个整数的平方和，这个问题就可以很快解决，速度快得超乎你的想象。
240. 搜索二维矩阵 II
常规思路是进行二分查找，此时就能看到一个奇妙的解法，代码如下：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix int target) {
if(matrix.size() == 0 || matrix[0].size() == 0) return false;
int i = 0 j = matrix[0].size()-1; // start at the end of first row
while(i < matrix.size() && j >= 0){ // initially matrix[i][j] represents the max of each row
if(matrix[i][j] == target) return true;
if(matrix[i][j] < target) i ; // if max of row < target move down a row
else j--; // you're in the right row so traverse backwards through the row
}
return false;
}
};
基本思路就是从矩阵第一行最右侧开始查找，当前值比 target 大往左走，比 target 小的话往下走。
214.最短回文串
当然如果你想挑战高难度，可以尝试挑战下这道题
常规做法：
class Solution:
def shortestPalindrome(self s):
"""
:type s: str
:rtype: str
"""
ss=s[::-1]
n=len(ss)
for i in range(len(s) -1 -1):
if ss[n-i:]==s[:i]:
break
return (ss[:n-i] s)
可使用 Manacher 和 KMP， Manacher 算法是求最长回文子串非常漂亮的算法了。
本题目可以转换为求给定字符串从首字母开始的最长回文子串（然后将余下的 reverse，insert 到头部就可以），而求从首字母开始的最长回文子串，可以用 Manacher 算法，也可以将 str 反转以后拼接到 str 尾部，使用 KMP 的求 next 数组，这样 next 数组最后一个值就是从首字母出发的最长回文子串长度。
如果你可以举一反三，想到更好的方法，也可以写在评论区或者去官网试试身手哦～
写在最后
解题方法千变万化，重在思考的过程，并非答案。许多实战过的小伙伴相信也在面试大厂的岗位时，了解面试官其实并不关心最终结果，而是需要你提供自己的理解和思路。
BY /
本文作者：力扣
声明：本文归“力扣”版权所有，如需转载请联系。
