中文leetcode网址：link
目录
- 简单篇：
- twoSum（题目编号1：[link](https://leetcode-cn.com/problems/two-sum/)）
- 整数翻转（题目编号7：[link](https://leetcode-cn.com/problems/reverse-integer/)）
- 回文数（题目编号9：[link](https://leetcode-cn.com/problems/palindrome-number/)）
- 罗马数字转整数（题目编号13：[link](https://leetcode-cn.com/problems/roman-to-integer/)）
- 最长公共前缀（题目编号14：[link](https://leetcode-cn.com/problems/longest-common-prefix/)）
- 有效的括号（题目编号20：[link](https://leetcode-cn.com/problems/valid-parentheses/)）
- 合并两个有序链表（题目编号21：[link](https://leetcode-cn.com/problems/merge-two-sorted-lists/)）
- 删除排序数组中的重复项（题目编号26：[link](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/)）
- 移除元素（题目编号27：[link](https://leetcode-cn.com/problems/remove-element/)）
- 实现strStr()（题目编号28：[link](https://leetcode-cn.com/problems/implement-strstr/)）
- 搜索插入位置（题目编号35：[link](https://leetcode-cn.com/problems/search-insert-position/)）
- 外观数列（题目编号38：[link](https://leetcode-cn.com/problems/count-and-say/)）
- 最大子序和（题目编号53：[link](https://leetcode-cn.com/problems/maximum-subarray/submissions/)）
- 最后一个单词的长度（题目编号58：[link](https://leetcode-cn.com/problems/length-of-last-word/submissions/)）
- 二进制求和（题目编号67：[link](https://leetcode-cn.com/problems/add-binary/submissions/)）
- x的平方根（题目编号69：[link](https://leetcode-cn.com/problems/sqrtx/submissions/)）
- 爬楼梯（题目编号70：[link](https://leetcode-cn.com/problems/climbing-stairs/submissions/)）
- 删除排序链表中的重复元素（题目编号83：[link](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/submissions/)）
- 合并两个有序数组（题目编号88：[link](https://leetcode-cn.com/problems/merge-sorted-array/submissions/)）
- 相同的树（题目编号100：[link](https://leetcode-cn.com/problems/same-tree/submissions/)）
- 对称二叉树（题目编号101：[link](https://leetcode-cn.com/problems/symmetric-tree/solution/)）
- 只出现一次的数字（题目编号136：[link](https://leetcode-cn.com/problems/single-number/submissions/)）
- 验证回文串（题目编号125：[link](https://leetcode-cn.com/problems/valid-palindrome/submissions/)）
- 相交链表（题目编号160： [link](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/submissions/)）
- 两数之和II（题目编号167：[link](https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/submissions/)）
- 多数元素（题目编号169：[link](https://leetcode-cn.com/problems/majority-element/submissions/)）
- 二叉树的最大深度（题目编号104：[link](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/submissions/)）
- 二叉树的层次遍历II（题目编号107：[link](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/solution/)）
- 二叉树的最小深度（题目编号111：[link](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/)）
- 路径总和（题目编号112：[link](https://leetcode-cn.com/problems/path-sum/)）
- 杨辉三角（题目编号118：[link](https://leetcode-cn.com/problems/pascals-triangle/)）
- 杨辉三角II（题目编号119：[link](https://leetcode-cn.com/problems/pascals-triangle-ii/submissions/)）
- 买卖股票的最佳时机（题目编号121：[link](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)）
- 旋转数组（题目编号189：[link](https://leetcode-cn.com/problems/rotate-array/submissions/)）
- 打家劫舍（题目编号198：[link](https://leetcode-cn.com/problems/house-robber/submissions/)）
- 位1的个数（题目编号191：[link](https://leetcode-cn.com/problems/number-of-1-bits/)）
- 快乐数（题目编号202：[link](https://leetcode-cn.com/problems/happy-number/submissions/)）
- 移除链表元素（题目编号203：[link](https://leetcode-cn.com/problems/remove-linked-list-elements/submissions/)）
- 计数质数（题目编号204：[link](https://leetcode-cn.com/problems/count-primes/submissions/)）
- 同构字符串（题目编号205：[link](https://leetcode-cn.com/problems/isomorphic-strings/)）
- 反转链表（题目编号206：[link](https://leetcode-cn.com/problems/reverse-linked-list/)）
- 存在重复元素（题目编号217：[link](https://leetcode-cn.com/problems/contains-duplicate/)）
- 存在重复元素II（题目编号219：[link](https://leetcode-cn.com/problems/contains-duplicate-ii/)）
- 用队列实现栈（题目编号225：[link](https://leetcode-cn.com/problems/implement-stack-using-queues/)）
- 翻转二叉树（题目编号226：[link](https://leetcode-cn.com/problems/invert-binary-tree/)）
- 2的幂（题目编号231：[link](https://leetcode-cn.com/problems/power-of-two/)）
- 用栈实现队列（题目编号232：[link](https://leetcode-cn.com/problems/implement-queue-using-stacks/submissions/)）
- 回文链表（题目编号234：[link](https://leetcode-cn.com/problems/palindrome-linked-list/submissions/)）
- 二叉搜索树的最近公共祖先（题目编号235：[link](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)）
- 删除链表中的节点（题目编号237：[link](https://leetcode-cn.com/problems/delete-node-in-a-linked-list/)）
- 有效的字母异位词（题目编号242：[link](https://leetcode-cn.com/problems/valid-anagram/)）
- 二叉树的所有路径（题目编号257：[link](https://leetcode-cn.com/problems/binary-tree-paths/)）
- 各位相加（题目编号258：[link](https://leetcode-cn.com/problems/add-digits/)）
- 缺失数字（题目编号268：[link](https://leetcode-cn.com/problems/missing-number/)）
- 买卖股票的最佳时机II（题目编号122：[link](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/submissions/)）
- 第一个错误的版本（题目编号278：[link](https://leetcode-cn.com/problems/first-bad-version/)）
- 移动零（题目编号283：[link](https://leetcode-cn.com/problems/move-zeroes/)）
- 单词规律（题目编号290：[link](https://leetcode-cn.com/problems/word-pattern/)）
- Nim游戏（题目编号292：[link](https://leetcode-cn.com/problems/nim-game/)）
- 猜数字（题目编号299：[link](https://leetcode-cn.com/problems/bulls-and-cows/)）
- 区域和检索（题目编号303：[link](https://leetcode-cn.com/problems/range-sum-query-immutable/)）
- 3的幂（题目编号326：[link](https://leetcode-cn.com/problems/power-of-three/)）
- 4的幂（题目编号342：[link](https://leetcode-cn.com/problems/power-of-four)）
- 反转字符串（题目编号344：[link](https://leetcode-cn.com/problems/reverse-string/)）
- 反转字符串中的元音字母（题目编号345：[link](https://leetcode-cn.com/problems/reverse-vowels-of-a-string/)）
- 有效的完全平方数（题目编号367：[link](https://leetcode-cn.com/problems/valid-perfect-square/)）
- 两个数组的交集（题目编号349：[link](https://leetcode-cn.com/problems/intersection-of-two-arrays/)）
- 两个数组的交集II（题目编号350：[link](https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/)）
- 两整数之和（题目编号371：[link]()）
- 猜数字大小（题目编号374：[link](https://leetcode-cn.com/problems/guess-number-higher-or-lower/)）
- 赎金信（题目编号383：[link](https://leetcode-cn.com/problems/ransom-note/)）
- 字符串中的第一个唯一字符（题目编号387：[link](https://leetcode-cn.com/problems/first-unique-character-in-a-string/)）
- 找不同（题目编号389：[link](https://leetcode-cn.com/problems/find-the-difference/)）
- 判断子序列 （题目编号392：[link](https://leetcode-cn.com/problems/is-subsequence/)）
- 左叶子之和（题目编号404：[link](https://leetcode-cn.com/problems/sum-of-left-leaves/)）
- 数字转换为十六进制数（题目编号405：[link](https://leetcode-cn.com/problems/convert-a-number-to-hexadecimal/)）
- 最长回文串（题目编号409：[link](https://leetcode-cn.com/problems/longest-palindrome/)）
- Fizz Buzz（题目编号412：[link](https://leetcode-cn.com/problems/fizz-buzz/)）
- 第三大的数（题目编号414：[link](https://leetcode-cn.com/problems/third-maximum-number/submissions/)）
- 字符串相加（题目编号415：[link](https://leetcode-cn.com/problems/add-strings/)）
- 字符串中的单词数（题目编号434：[link](https://leetcode-cn.com/problems/number-of-segments-in-a-string/)）
- 排列硬币（题目编号441：[link](https://leetcode-cn.com/problems/arranging-coins/)）
- 压缩字符串（题目编号443：[link](https://leetcode-cn.com/problems/string-compression/)）
- 回旋镖的数量（题目编号447：[link](https://leetcode-cn.com/problems/number-of-boomerangs/)）
- 找到所有数组中消失的数字（题目编号448：[link](https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/)）
- 最小移动次数使数组元素相等（题目编号453：[link](https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements/)）
- 颠倒二进制位（题目编号190：[link](https://leetcode-cn.com/problems/reverse-bits/)）
- 分发饼干（题目编号455：[link]()）
- 重复的子字符串（题目编号459：[link](https://leetcode-cn.com/problems/repeated-substring-pattern/)）
- 汉明距离（题目编号431：[link](https://leetcode-cn.com/problems/hamming-distance/)）
- 岛屿的周长（题目编号463：[link](https://leetcode-cn.com/problems/island-perimeter/)）
- 供暖器（题目编号475：[link](https://leetcode-cn.com/problems/heaters/)）
- 数字的补数（题目编号476：[link](https://leetcode-cn.com/problems/number-complement/)）
- 密钥格式化（题目编号482：[link](https://leetcode-cn.com/problems/license-key-formatting/)）
- 最大连续1的个数（题目编号485：[link](https://leetcode-cn.com/problems/max-consecutive-ones/)）
- 构造矩形（题目编号492：[link](https://leetcode-cn.com/problems/construct-the-rectangle/)）
- 下一个更大元素（题目编号496：[link](https://leetcode-cn.com/problems/next-greater-element-i/)）
- 键盘行（题目编号500：[link](https://leetcode-cn.com/problems/keyboard-row/)）
- 七进制数（题目编号504：[link](https://leetcode-cn.com/problems/base-7/)）
- 相对名次（题目编号506：[link](https://leetcode-cn.com/problems/relative-ranks/)）
- 完美数（题目编号507：[link](https://leetcode-cn.com/problems/perfect-number/)）
- 斐波那契数列（题目编号509：[link](https://leetcode-cn.com/problems/fibonacci-number/)）
- 检测大写字母（题目编号520：[link](https://leetcode-cn.com/problems/detect-capital/)）
- 最长特殊序列（题目编号521：[link](https://leetcode-cn.com/problems/longest-uncommon-subsequence-i/)）
- 数组中的K-diff数对（题目编号532：[link](https://leetcode-cn.com/problems/k-diff-pairs-in-an-array/)）
- 反转字符串II（题目编号541：[link](https://leetcode-cn.com/problems/reverse-string-ii/)）
- 学生出勤记录I（题目编号551：[link](https://leetcode-cn.com/problems/student-attendance-record-i/)）
- 反转字符串中的单词III（题目编号557：[link](https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/)）
- N叉树的最大深度（题目编号559：[link](https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/)）
- 数组拆分I（题目编号561：[link](https://leetcode-cn.com/problems/array-partition-i/)）
- 二叉树的坡度（题目编号563：[link](https://leetcode-cn.com/problems/binary-tree-tilt/)）
- 重塑矩阵（题目编号566：[link](https://leetcode-cn.com/problems/reshape-the-matrix/)）
- 另一棵树的子树（题目编号572：[link](https://leetcode-cn.com/problems/subtree-of-another-tree/)）
- 分糖果（题目编号575：[link](https://leetcode-cn.com/problems/distribute-candies/)）
- N叉树的前序遍历（题目编号589：[link](https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/)）
- N叉树的后序遍历（题目编号590：[link](https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/)）
- 最长和谐子序列（题目编号594：[link](https://leetcode-cn.com/problems/longest-harmonious-subsequence/)）
- 范围求和（字母编号598：[link](https://leetcode-cn.com/problems/range-addition-ii/)）
- 两个列表的最小索引总和（题目编号599：[link](https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/)）
- 根据二叉树创建字符串（题目编号606：[link](https://leetcode-cn.com/problems/construct-string-from-binary-tree/)）
- 合并二叉树（题目编号617：[link](https://leetcode-cn.com/problems/merge-two-binary-trees/)）
- 三个数的最大乘积（题目编号628：[link](https://leetcode-cn.com/problems/maximum-product-of-three-numbers/)）
- 平方数之和（题目编号633：[link](https://leetcode-cn.com/problems/sum-of-square-numbers/)）
- 二叉树的层平均值（题目编号637：[link](https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/)）
- 子数组的最大平均数I（题目编号643：[link](https://leetcode-cn.com/problems/maximum-average-subarray-i/)）
- 错误的集合（题目编号645：[link](https://leetcode-cn.com/problems/set-mismatch/)）
- 修剪二叉搜索树（题目编号669：[link](https://leetcode-cn.com/problems/trim-a-binary-search-tree/)）
- 二叉树中第二小的节点（题目编号671：[link](https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/)）
- 最长连续递增序列（题目编号674：[link](https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/)）
- 验证回文字符串II（题目编号680：[link](https://leetcode-cn.com/problems/valid-palindrome-ii/)）
- 棒球比赛（题目编号682：[link](https://leetcode-cn.com/problems/baseball-game/)）
- 最长同值路径（题目编号687：[link](https://leetcode-cn.com/problems/longest-univalue-path/)）
- 员工的重要性（题目编号690：[link](https://leetcode-cn.com/problems/employee-importance/)）
- 交替位二进制数（题目编号693：[link](https://leetcode-cn.com/problems/binary-number-with-alternating-bits/)）
- 计数二进制子串（题目编号696：[link](https://leetcode-cn.com/problems/count-binary-substrings/)）
简单篇：
twoSum（题目编号1：link）
- 暴力循环
- 先排序后双指针，一个从前往后，一个从后往前
- Hash表（python用字典）
整数翻转（题目编号7：link）
resut = result * 10 + x % 10
x = x / 10
- 数值溢出问题，数值范围− 2 31 -2^{31}−231 ~ 2 31 − 1 2^{31}-1231−1，result超过范围时需返回0。
回文数（题目编号9：link）
- python2的整数分为int和long，long不会溢出，python3将二者整合为int型，在内存允许的情况下不会溢出。
- C语言下要考虑溢出问题
- 回文数判断可以只使用后半部分翻转与前半部分比较，可以避免出现溢出。
if x == 0:
return True
elif x < 0 or x % 10 == 0:
return False
else:
inverse_num = 0
while x > inverse_num:
inverse_num = inverse_num * 10 + x % 10
x = x // 10
if x == inverse_num or x == inverse_num // 10:
return True
else:
return False
- 注意尾数为0的情况，仅靠最后一种case来处理是不够的。比如10，最后会出现inverse_num = 1， x = 0， 那么满足 x == inverse_num // 10，输出True，实际为False。如果是完全翻转数字的话不会出现这个问题，翻转后的inverse_num=1，跟原来的数字10比较，不一致。
罗马数字转整数（题目编号13：link）
class Solution:
def romanToInt(self, s: str) -> int:
processed = 0
result = 0
while processed < len(s):
if s[processed] == 'I':
if processed + 1 < len(s):
if s[processed+1] == 'V':
result += 4
processed += 1
elif s[processed+1] == 'X':
result += 9
processed += 1
else:
result += 1
else:
result += 1
elif s[processed] == 'X':
if processed + 1 < len(s):
if s[processed+1] == 'L':
result += 40
processed += 1
elif s[processed+1] == 'C':
result += 90
processed += 1
else:
result += 10
else:
result += 10
elif s[processed] == 'C':
if processed + 1 < len(s):
if s[processed+1] == 'D':
result += 400
processed += 1
elif s[processed+1] == 'M':
result += 900
processed += 1
else:
result += 100
else:
result += 100
elif s[processed] == 'V':
result += 5
elif s[processed] == 'L':
result += 50
elif s[processed] == 'D':
result += 500
elif s[processed] == 'M':
result += 1000
processed += 1
return result
最长公共前缀（题目编号14：link）
- 本人解法：如果是空list，直接返回""，如果是只有1个字符串的list，直接返回strs[0]。其他均为一般情况，使用while循环。
if len(strs) == 0:
return ""
if len(strs) == 1:
return strs[0]
common_len = 0
while True:
if common_len > len(strs[0]) - 1:
return strs[0][:common_len]
tmp_char = strs[0][common_len]
for str_index in range(1, len(strs)):
if common_len > len(strs[str_index]) -1:
return strs[0][:common_len]
if strs[str_index][common_len] == tmp_char:
continue
else:
return strs[0][:common_len]
common_len += 1
- 需要注意是要检查数组越界问题
- 别人的解法：先对字符串数组排序，然后比较第一个字符串和最后一个字符串的公共前缀即可，但复杂度一样是O(MN)，没有优化。
有效的括号（题目编号20：link）
class Solution:
def isValid(self, s: str) -> bool:
if len(s) == 0:
return True
if len(s) % 2 == 1:
return False
buffer = []
left = ['{', '(', '[']
right = ['}', ')', ']']
pairs = {}
for i, j in zip(left, right):
pairs[i] = j
for i in range(len(s)):
if len(buffer) == 0:
if s[i] in left:
buffer.append(s[i])
else:
return False
elif s[i] in left:
buffer.append(s[i])
elif pairs[buffer[-1]] == s[i]:
buffer.pop()
continue
else:
return False
if len(buffer) == 0:
return True
else:
return False
- 自己的解法：使用缓存list，记录尚未配对的左括号。
- 对空str和奇数位str先返回结果。
- 注意：访问完全部数据没有return False的时候并不是一定是True，要判断buffer是否为空，有可能最后留下了几个左括号。
合并两个有序链表（题目编号21：link）
- 自己的解法：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
result_list = ListNode()
p = result_list
p1 = l1
p2 = l2
while p1 is not None and p2 is not None:
if p1.val <= p2.val:
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
p = p.next
while p1 is not None:
p.next = p1
p1 = p1.next
p = p.next
while p2 is not None:
p.next = p2
p2 = p2.next
p = p.next
return result_list.next
- 还有递归的方式，比较耗内存。
- 后两个while可以直接将剩下的链表节点直接挂在p后面
if p1 is not None:
p.next = p1
else:
p.next = p2
删除排序数组中的重复项（题目编号26：link）
- 自己的解答：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
return_len = 1
for i in range(1, len(nums)):
if nums[i] != nums[return_len - 1]:
nums[return_len] = nums[i]
return_len += 1
return return_len
- 注意题目是原地删除，那么需要采用赋值的方式，只需要保持nums前几位是正确的唯一数字即可，逐个判断当前数字和数组的唯一序列中最后一个元素是否相等，若不相等，就把当前元素赋值给唯一序列后的那个元素。因为是排序序列，所以只需要判断和唯一序列的最后一个值是否相同就可以，不是排序序列的话会麻烦一些，需要和前边的进行逐个比较或者使用字典比较。
- 注意这里使用了引用，因此无需将nums返回就可以让调用者看到更改后的nums。
移除元素（题目编号27：link）
- 这道题和上一道很像，这个是排除指定的数字。自己的解法：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
return_len = 0
for i in range(len(nums)):
if nums[i] != val:
if return_len != i:
nums[return_len] = nums[i]
return_len += 1
return return_len
- 遍历列表，当前数字和目标数字不一样的时候，判断要放置元素的位置和当前位置是否是同一个，如果是一样的就不用赋值了，如果不一样就赋值，给return_len加1。
实现strStr()（题目编号28：link）
- 我的实现：
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) == 0:
return 0
for i in range(len(haystack) - len(needle) + 1):
is_same = True
for j in range(len(needle)):
if haystack[i + j] != needle[j]:
is_same = False
break
if is_same:
return i
return -1
- 需要注意特殊情况，needle为空字符串时，直接返回0。还有注意i的下标区间。简单的思考，如果haystack和needle的长度一样时，range里面不能是0。
搜索插入位置（题目编号35：link）
- 二分法，我的实现：
class Solution:
def searchInsert(self, nums, target) -> int:
# 二分法
if nums[0] > nums[-1]:
order = 1
else:
order = 0
left = 0
right = len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] < target:
if order == 0:
left = middle + 1
else:
right = middle - 1
elif nums[middle] > target:
if order == 1:
left = middle + 1
else:
right = middle - 1
else:
return middle
return left
- 我觉得题目并没有说明数组是升序还是降序，要考虑两种情况。
外观数列（题目编号38：link）
- 我的解法：
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return '1'
last_level = self.countAndSay(n - 1)
result = ''
continue_char = last_level[0]
continue_num = 1
for char in last_level[1:]:
if char == continue_char:
continue_num += 1
else:
result += str(continue_num) + continue_char
continue_char = char
continue_num = 1
result += str(continue_num) + continue_char
return result
- 要用递归的方式求解
- 递归要注意递归的终止条件
最大子序和（题目编号53：link）
- 求解方案包括两种，动态规划和分治法
- 动态规划，以f(i)表示以i结尾的序列的最大和，那么想要获得以i+1结尾的序列的最大和，即出现新的数字nums[i+1]时，只有两种选择，f(i)+nums[i+1]，或者nums[i+1]，从f(i)递推f(i+1)时，只需求两种选择的最大值就是f(i+1)。问题的解就是f(i)序列的最大值。只需单次遍历数据，维护f(i)和max(f(i))两个变量即可。时间复杂度为O(n)，空间复杂度为O(1)。
pre = 0
maxAns = 0
for num in nums:
pre = max(pre + num, num)
maxAns = max(maxAns, pre)
return maxAns
- 分治法较为复杂，是本题较复杂的解法，需要递归求解。耗费的内存和时间都比较多。
- 分治法将问题拆分为数组左右两部分的子序列最大和的融合结果。
- 对单个序列，维护4个变量，以序列左端点为起始点的最大序列和lsum，以序列右端点为终点的最大序列和rsum，整个序列的和isum，序列内的最大子序和msum。
- 定义求nums内从l到r的序列内的最大序列和的函数get。
- get函数，先求l到r序列的中点，m=(l+r) // 2，求出nums序列l到m的左半部分的4个变量状态lSub，求出nums序列m+1到r的右半部分的4个变量状态rSub。
- 定义融合lSub和rSub的函数pushUp，融合方法为：最简单的是整个序列的和isum，等于左右两部分的isum之和，lsum有两种选择，一是左半部分的lsum，二是左半部分的isum+右半部分的lsum，类似地，rsum也是两种选择，右半部分的rsum，或左半部分的rsum+右半部分的isum，复杂一些的是msum，msum可能跨越分割点，也可能没有跨越分割点，因此有三种选择，左半部分的msum，右半部分的msum，或左半部分的rum+右半部分的lsum，求最大值。
st = self.Status()
st.isum = lSub.isum + rSub.isum
st.lsum = max(lSub.lsum, lSub.isum + rSub.lsum)
st.rsum = max(rSub.rsum, lSub.rsum + rSub.isum)
st.msum = max(max(lSub.msum, rSub.msum), lSub.rsum + rSub.lsum)
- 分治法的完整代码
class Solution:
class Status:
def __init__(self, l=0, r=0, i=0, m=0):
self.lsum = l
self.rsum = r
self.isum = i
self.msum = m
def pushUp(self, l: Status, r: Status) -> Status:
st = self.Status()
st.isum = l.isum + r.isum
st.lsum = max(l.lsum, l.isum + r.lsum)
st.rsum = max(r.rsum, l.rsum + r.isum)
st.msum = max(max(l.msum, r.msum), l.rsum + r.lsum)
return st
def get(self, nums: List[int], l: int, r: int) -> Status:
if l == r:
return self.Status(nums[l], nums[l], nums[l], nums[l])
m = (l + r) // 2
lSub = self.get(nums, l, m) # type: Status
rSub = self.get(nums, m+1, r) # type: Status
return self.pushUp(lSub, rSub)
def maxSubArray(self, nums: List[int]) -> int:
return self.get(nums, 0, len(nums) - 1).msum
- 自己的分治法还是很不熟练，分左右两部分的时候是[l, m]和[m+1, r]，注意右半部分的起点是m+1。
- 注意python的类中类调用的时候，也是需要self.Status，否则也会报错找不到。
- 还有类内的递归方法，开始写的时候定义成staticmethod提示在递归时找不到，不知道为什么，改成类普通函数（带有self参数的），调用时变成self.get，就可以了。
最后一个单词的长度（题目编号58：link）
- 这个题就比较简单了，维护当前单词的长度和最后一个单词的长度即可，当出现空格的时候，把当前单词的长度赋值给记录最后一个单词长度的变量，特别需要注意的是，不能直接赋值，需要判断当前单词的长度是否为0，因为可能出现连续空格的情况。当访问完字符串的时候，还需要再判断一次当前单词长度是否为0，不为0则赋值给记录最后一个单词长度的变量。
- 加一（题目编号66：link）
- 先给数组最后一位+1，然后从最后一位开始倒序往前遍历，如果当前位<10，那么退出遍历，否则先把当前位赋值为0，接着要进位了，要先判断当前位是不是第1位了，是否前边已经没有数字了，如果是第一位则给数组前加一个元素1，退出循环，如果前面还有数字，那么就给前一位加1（进位），继续循环，判断下一位是否是10，是否需要进位。
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
addToPre = 0
digits[-1] += 1
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 10:
break
else:
digits[i] = 0
if i > 0:
digits[i - 1] += 1
else:
digits = [1] + digits
break
return digits
二进制求和（题目编号67：link）
- 实现：
class Solution:
def addBinary(self, a: str, b: str) -> str:
res = ''
addToPre = 0
i, j = len(a) - 1, len(b) - 1
while i >= 0 or j >= 0:
cur = 0
if i >= 0:
cur += int(a[i])
if j >= 0:
cur += int(b[j])
cur += addToPre
if cur >= 2:
addToPre = 1
cur -= 2
else:
addToPre = 0
res = str(cur) + res
i -= 1
j -= 1
if addToPre == 1:
res = '1' + res
return res
- 注意进位
- 注意判断访问完字符串a和b之后是否还有进位
x的平方根（题目编号69：link）
- 二分法，但这时候要注意x可能无法刚好开根号，那么什么时候返回呢，我选择的条件的是:
mid ** 2 == x or (mid ** 2 < x and (mid + 1) ** 2 > x)
- 第二个条件针对的就是无法刚好开根号，直接对结果取整了。
爬楼梯（题目编号70：link）
- 简单写法是递归调用f(n-1)+f(n-2)，需要写明递归终止条件，f(1)=1，f(2)=2。该方案超时了。
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
- 另一种方法是递推，利用循环，减少空间占用和时间复杂度。
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
f1 = 1
f2 = 2
tmp_n = 3
while tmp_n <= n:
cur = f1 + f2
f1 = f2
f2 = cur
tmp_n += 1
return cur
删除排序链表中的重复元素（题目编号83：link）
- 链表为已排序链表，那么只需后面的数字跟前一个保留下来的数字不一致即可。原始链表第一个元素肯定是唯一的，可以作为返回链表的头结点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
p = head
cur = p
while p:
while p and cur.val == p.val:
p = p.next
cur.next = p
cur = p
return head
合并两个有序数组（题目编号88：link）
- 可以倒序看两个数组，比较两个数组最后一个数字，把大的放到m+n-1的位置，注意是m+n-1，不要搞成m+n-2。然后改变下标，继续处理num1或nums2下一个数字。
- while循环退出时，如果nums1还未处理完，那么不需任何操作，即可返回，如果nums2还未处理完，那么逐个元素拷贝即可。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
while m > 0 and n > 0:
if nums1[m - 1] > nums2[n - 1]:
nums1[m + n - 1] = nums1[m - 1]
m -= 1
else:
nums1[m + n - 1] = nums2[n - 1]
n -= 1
while n > 0:
nums1[n - 1] = nums2[n - 1]
n -= 1
相同的树（题目编号100：link）
- 递归的方法评估p和q的左右子树是否完全一致。递归的终止条件包括几项，若p和q都是None，那么返回True，若p和q只有一个是None，那么肯定是不相等，返回False，不满足以上条件表示p和q都是非空节点，那么判断p和q两个节点的值是否相等，若不相等，返回False，若相等，则递归判断p和q的左右子树是否完全一致，注意左右子树之间是and连接，需要同时满足条件。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p is None and q is None:
return True
if p is None or q is None:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
对称二叉树（题目编号101：link）
- 这道题跟上一道很像，上一道是判断两棵树是不是一样的，这道题变成一颗树是不是对称二叉树，其实就是左右两颗子树是否是对称的，这一部分可以借鉴上一题的解答。此外，要注意root可能是None，没有左右子树。
- 我的解答：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
return self.isSame(root.left, root.right)
def isSame(self, left: TreeNode, right: TreeNode) -> bool:
if left is None and right is None:
return True
if left is None or right is None:
return False
if left.val != right.val:
return False
return self.isSame(left.left, right.right) and self.isSame(left.right, right.left)
- 不使用递归的方法，改用循环。那么就使用队列的思想。这一点还不太熟悉，要注意，如何把递归改写成循环。改写代码如下：
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
queue = [root, root]
while len(queue) > 0:
p, q = queue[:2]
queue = queue[2:]
if p is None and q is None:
pass
elif p is None or q is None:
return False
elif p.val != q.val:
return False
else:
queue.append(p.left)
queue.append(q.right)
queue.append(p.right)
queue.append(q.left)
return True
只出现一次的数字（题目编号136：link）
- 不考虑时间和空间复杂度，可以有多重解法。
- 最简单的是异或运算，异或运算满足交换律，a异或a=0，a异或b异或a=a异或a异或b=b。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
for num in nums[1:]:
nums[0] ^= num
return nums[0]
验证回文串（题目编号125：link）
- 注意要判断字符是否是大小写字母和数字，还有不区分大小写。
class Solution:
def isPalindrome(self, s: str) -> bool:
p1 = 0
p2 = len(s) - 1
while p1 < p2:
if not self.check_available(s[p1]):
p1 += 1
continue
if not self.check_available(s[p2]):
p2 -= 1
continue
if s[p1].lower() != s[p2].lower():
return False
p1 += 1
p2 -= 1
return True
def check_available(self, char):
if 'A' <= char <= 'Z' or 'a' <= char <= 'z' or '0' <= char <= '9':
return True
return False
相交链表（题目编号160： link）
- 两个链表如果相交，那么肯定共享后面的一部分，可以先求两个链表的长度，然后长的链表先往前移动差值dif步，然后两个链表同步前进，判断节点是否相同。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
p = headA
len_A = 0
while p:
len_A += 1
p = p.next
p = headB
len_B =0
while p:
len_B += 1
p = p.next
dif = len_A - len_B
if dif >= 0:
p1 = headA
p2 = headB
else:
p1 = headB
p2 = headA
dif *= -1
while dif > 0:
p1 = p1.next
dif -= 1
while p1 and p2:
if p1 == p2:
return p1
p1 = p1.next
p2 = p2.next
return None
两数之和II（题目编号167：link）
- 数组是升序的，从数组前后两个方向移动，如果两个数字和等于目标值，就直接返回；若和小于目标值，前边的下标后移；若大于，后面的下标前移。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
p1 = 0
p2 = len(numbers) - 1
while p1 < p2:
res = numbers[p1] + numbers[p2]
if res == target:
return [p1 + 1, p2 + 1]
elif res < target:
p1 += 1
else:
p2 -= 1
多数元素（题目编号169：link）
- 本题有一种比较巧妙的方法，Boyer-Moore 投票算法link
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = 0
count = 0
for num in nums:
if count == 0:
candidate = num
count = 1
elif candidate == num:
count += 1
else:
count -= 1
return candidate
- leetcode还给出一种随机算法，随机选择一个下标，测试对应的数字是否是数组的众数，期望的随机采样次数小于等于2。期望的时间复杂度为O(n)，空间复杂度为O(1)。
- 其他方法还包括：哈希法、分治法、排序法。
二叉树的最大深度（题目编号104：link）
- 本题最简单的思路是递归，知道左右两个子树的深度后，求最大值，再加1，就是当前节点的深度。还可以使用广度优先搜索遍历树的所有节点，时间复杂度都是O(n)。递归法的空间复杂度是O(depth），广度优先搜索法的最大时间复杂度是O(n)（队列里存放了接近全部的节点）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
nodelist = [root]
ans = 0
while len(nodelist) > 0:
sz = len(nodelist)
while sz > 0:
node = nodelist[0]
nodelist.pop(0)
if node.left:
nodelist.append(node.left)
if node.right:
nodelist.append(node.right)
sz -= 1
ans += 1
return ans
def maxDepthV1(self, root: TreeNode) -> int:
if root is None:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
二叉树的层次遍历II（题目编号107：link）
- 这道题就是对二叉树进行层次遍历，用队列的形式，遍历每一层的节点，把当前节点从前面弹出，然后把每个节点不是空的左右子节点放到队列的后面，逐层遍历，直到没有新的非空左右子节点。
- 题目要求是从叶子层到根，所以要对层次遍历的结果按层次倒序，然后返回。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
queue = [root]
while len(queue):
len_last_level = len(queue)
tmp_res = []
while len_last_level > 0:
node = queue[0]
queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
tmp_res.append(node.val)
len_last_level -= 1
res.append(tmp_res)
return res[::-1]
二叉树的最小深度（题目编号111：link）
- 这道题关键是要理解题意，否则[1,2]这个测试用例无法通过。
- 递归终止条件：当root为空时，返回0；当root左右子节点均为空时，返回1；如果左右子节点中有有一个非空，那么就返回该子节点的深度+1（最重要的部分）；如果左右子节点都非空，那么返回左右子节的深度的最小值+1。
- 这个题解讲的好link，可参考。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
left_depth = self.minDepth(root.left)
right_depth = self.minDepth(root.right)
if not root.left or not root.right:
return left_depth + right_depth + 1
else:
return min(left_depth, right_depth) + 1
路径总和（题目编号112：link）
- 递归法比较简单，但需要注意递归终止条件，当root为空的时候怎么处理，我之前的解答是当root为空，判断目标值sum是否为0，若为0，则返回True，否则返回False，评估系统认为此时应该为False，比较奇怪。
- 当root为空，直接返回False，这样才满足答案的要求。当root非空，但左右子节点均为空时。判断root.val是否和目标值sum相等，若相等则返回True，不想等则返回False。若左右子节点有非空节点，那么对左右子树分别判断是否存在新目标值得序列（新目标值=原目标值sum-root.val，因为root节点算在从根节点到叶节点的序列里，要减去该值，得到新的目标值）。注意两个子树的递归结果用或(or)来结合。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return sum == root.val
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
杨辉三角（题目编号118：link）
- 简单的递推法，根据上一层的结果递归下一层，注意每一层的第一个值和最后一个值都是1，其他位置i的值是上一层的前一位置i-1和同一位置i处元素之和。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0:
return []
res = [[1]]
for level in range(1, numRows):
tmp_res = [1] * (len(res[-1]) + 1)
for num_index in range(1, len(res[-1])):
tmp_res[num_index] = res[-1][num_index - 1] + res[-1][num_index]
res.append(tmp_res)
return res
杨辉三角II（题目编号119：link）
- 这道跟上一道一样，就是返回最后一行就可以了。
- 注意k是从0开始，0就是表示第一行（[1]）
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = [[1]]
for level in range(1, rowIndex+1):
tmp_res = [1] * (len(res[-1]) + 1)
for num_index in range(1, len(res[-1])):
tmp_res[num_index] = res[-1][num_index - 1] + res[-1][num_index]
res.append(tmp_res)
return res[-1]
- 因为只需要返回最后一层，
买卖股票的最佳时机（题目编号121：link）
- 该系列有好几道，一次买卖，两次买卖，多次买卖。
- 方法为动态规划。需要仔细研究一下。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
minPrice = float('inf')
maxProfit = 0
for price in prices:
maxProfit = max(maxProfit, price - minPrice)
minPrice = min(minPrice, price)
return maxProfit
旋转数组（题目编号189：link）
- 这道题比较复杂的方法包括：暴力循环（一次将数组移动一格，多次移动数组元素），新建数组。
- 计算量最小的方法是将数组下标a的元素移动到(a+k)%N位置后，继续移动(a+k)%N的元素到其目标位置上（N表示数组长度），以此类推，但是==直接这样实现，在某些特殊情况下会遇到问题，即N刚好可以整除k的情况，这样会导致处理几个数字之后又回到了原始位置a，这时如果不加以特殊处理，会循环移动数组某几个数组，导致结果错误。此时，应该从a+1位置继续开始移动，开启下一个周期循环。==最终每个数字只移动一次。时间复杂度是O(N)，空间复杂度是O(1)。
public:
void rotate(vector<int>& nums, int k) {
if(nums.size() == 0 || k % nums.size() == 0)
return;
int move = k % nums.size();
if(move == 0)
return;
int current, start, prev, next, count = 0, tmp;
for(start = 0; count < nums.size(); start++)
{
current = start;
prev = nums[start];
do{
next = (current + move) % nums.size();
tmp = nums[next];
nums[next] = prev;
prev = tmp;
current = next;
count++;
}while(start != current);
}
return;
}
};
打家劫舍（题目编号198：link）
- 这道是典型的动态规划题目，为了在第k个点获取最大利益，有两种可能，偷或者不偷第k个点，因此当前点的最大利益是max(前k-2个点的最大利益+第k个点的收益，前k-1个点的最大利益）。
- 可以记录所有点的最大收益，为了优化内存，可以只保留最近两个点的最大收益。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
if(nums.size() == 2) return max(nums[0], nums[1]);
// vector<int> dp;
// dp.push_back(nums[0]);
// dp.push_back(max(nums[0], nums[1]));
// for(int i = 2; i < nums.size(); i++)
// {
// dp.push_back(max(dp[i - 2] + nums[i], dp[i - 1]));
// }
// return dp.back();
int p1 = nums[0];
int p2 = max(nums[0], nums[1]);
int tmp;
for(int i = 2; i < nums.size(); i++)
{
tmp = p2;
p2 = max(p1 + nums[i], p2);
p1 = tmp;
}
return p2;
}
};
位1的个数（题目编号191：link）
- 用n & (n-1)，位运算就可以把n二进制中的最后一个1变为0。
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n)
{
n = n & (n - 1);
count += 1;
}
return count;
}
};
快乐数（题目编号202：link）
- 这道题目的关键是如何判断循环，解法是用一个哈希表记录出现过的数字。
- 需要分析一下为什么数字不会越来越大。比如999，下一个数字是243，三位以内的数字的下一个值都只能比243小，两位的99会到三位数·162，四位及以上的数字都会每次减少一位，直到3位数。因此不需要考虑数字越来越大的问题。因此一个数字如果不是快乐数，那么一定是进入了循环。
- unordered_map，头文件是<unordered_map>，获取元素个数是map.size()函数，判断某个键值是否在map中出现过，方法是map.find(x) != map.end()，如果出现过，则为真。
#include <unordered_map>
class Solution {
public:
bool isHappy(int n) {
unordered_map<int, int> map;
while(true){
int next = get_next(n);
if(next == 1){
return true;
}
if(map.size() > 0 && map.find(next) != map.end()){
return false;
}
map.insert({{next, 0}});
n = next;
}
}
int get_next(int n){
int tmp_sum = 0;
while(n){
int last_digit = n % 10;
tmp_sum += last_digit * last_digit;
n = n / 10;
}
return tmp_sum;
}
};
移除链表元素（题目编号203：link）
- 先创建一个dummy node，用指针p指向该node，并用指针q也指向该node。p一直移动，修改链表，最后返回q->next，即新链表的起始节点。
- 判断p指向的下一个节点的值是不是目标值，如果是则p指向下一个节点的下一个节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* p = new ListNode(0);
ListNode* q = p;
p->next = head;
while(p && p->next){
if(p->next->val == val){
p->next = p->next->next;
}
else{
p = p->next;
}
}
return q->next;
}
};
计数质数（题目编号204：link）
- 这道题目不能用暴力搜索，逐个判断每个数是不是质数，太慢了。要采用一些技巧，比如2是质数，那么2的所有倍数都不是质数，以后就不用再判断这些数字了。
- 遍历的时候也要注意减少重复遍历。
#include<vector>
class Solution {
public:
int countPrimes(int n) {
if(n <= 2){
return 0;
}
vector<bool> isPrime(n, true);
isPrime[0] = false;
isPrime[1] = false;
for(int i = 0; i < sqrt(n); i++)
{
if(isPrime[i] == true){
for(int j = i; i * j < n; j++){
isPrime[i * j] = false;
}
}
}
int count = 0;
for(vector<bool>::iterator it = isPrime.begin(); it != isPrime.end(); it++){
if(*it == true){
count += 1;
}
}
return count;
}
};
同构字符串（题目编号205：link）
- 这道题自己想错了，自己原来的思路：统计每个字符出现的次数，排序，如果两个字符串中各个元素出现次数序列完全一致，说明可以符合要求。但实际题目还有另一个要求，是对应位置替换，而不是全部打乱重组，因此该思路是不对的。
- 第一种正确的解法，利用map，s中第一次出现某个字母，就建立s[i]到t[i]的映射，下一次出现该字母时，判断t中对应位置的字符是不是和map里存储的映射对象一致，不一致则不符合要求。注意要双向遍历，还要建立t到s的映射，否则测试样例"ab"-"aa"无法通过：
#include<unordered_map>
class Solution {
public:
bool isIsomorphic(string s, string t) {
if(s.length() == 0 && t.length() == 0){
return true;
}
if(s.length() != t.length()){
return false;
}
unordered_map<char, char> map_s_t, map_t_s;
for(int i = 0; i < s.length(); i++){
if(map_s_t.find(s[i]) == map_s_t.end()){
// not found
map_s_t[s[i]] = t[i];
}
else if(map_s_t[s[i]] != t[i]){
return false;
}
if(map_t_s.find(t[i]) == map_t_s.end()){
// not found
map_t_s[t[i]] = s[i];
}
else if(map_t_s[t[i]] != s[i]){
return false;
}
}
return true;
}
};
- 还有另外一种简单做法，上面这种解法时间复杂度比较高，要学习另一种。
- 字符转换为ASCII码，只有256种，因此可以用256数组来存储字符的映射关系。遍历s，第一次遇到某个字符时，建立s[i]到t[i]的映射，存储在数组中，再遇到该字符时，发现配对关系已经确定，就检查当前的t[i]与上次建立的映射字符是否一致，不一致则返回false。同理，要建立s到t和t到s的双向映射关系。该方法比上一种方法的效率大大提高，运行耗时从20ms降低到4ms。也减少了内存的占用。
- C++里，char型字符转换为ASCII码的函数是 int ascii = (int)char
class Solution {
public:
bool isIsomorphic(string s, string t) {
int count_s[256], count_t[256];
for(int i = 0; i < 256; i++){
count_s[i] = count_t[i] = -1;
}
for(int i = 0; i < s.length(); i++){
int int_chr_s = (int)s[i];
int int_chr_t = (int)t[i];
if(count_s[int_chr_s] == -1){
// not init
count_s[int_chr_s] = int_chr_t;
}
else if(count_s[int_chr_s] != int_chr_t){
return false;
}
if(count_t[int_chr_t] == -1){
// not init
count_t[int_chr_t] = int_chr_s;
}
else if(count_t[int_chr_t] != int_chr_s){
return false;
}
}
return true;
}
};
反转链表（题目编号206：link）
- 循环法：用3个指针记录上一个节点prev，当前节点cur，下一个节点next，然后改变当前节点的next，指向prev，然后移动三个指针。循环终止条件是cur指向NULL，注意返回的是前一个节点的指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* cur = head;
ListNode* next;
while(cur){
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
- 递归法稍难一些。该函数是返回反转后链表的头结点，假设当前节点为k，已经得到了k+1以及后面节点反转后的头结点p，那么把节点k也反转的操作是：k->next->next = k，把k指向k+1的箭头反过来，变为节点k+1的next指向k，注意还要设置节点k的next指向空，否则会导致节点k和k+1相互连接，成一个环。
// 递归法
if(head == NULL || head->next == NULL)
return head;
ListNode* p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
存在重复元素（题目编号217：link）
- 给定一个整数数组，判断是否存在重复元素。
- 思路1：最简单的思路是双层遍历，逐个判断两个元素是否相等。会超时。
- 思路2：将数组排序，时间复杂度O(NlogN)，再遍历一遍，判断相邻两个数字是否相等。
- 思路3：哈希表，存储曾经出现过的数字。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if(nums.size() == 0) return false;
sort(nums.begin(), nums.end());
// for(int i = 0; i < nums.size()-1; i++)
// {
// if(nums[i] == nums[i+1]){
// return true;
// }
// }
for(vector<int>::iterator it = nums.begin(); it < nums.end() - 1; it++){
if(*it == *(it+1)) return true;
}
return false;
}
};
- 哈希法，占用内存比排序法稍大，时间更快一些：
//哈希
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++){
if(map.find(nums[i]) != map.end()){
return true;
}
map[nums[i]] = 1;
}
return false;
存在重复元素II（题目编号219：link）
- 沿用上一题的哈希法，记录每个元素出现的位置，第二次出现的时候，比较记录的位置和当前位置的距离是否小于等于k，如果不满足条件，则更新记录的位置为当前位置，因为前一次出现的位置和未来可能出现的相等的值都不会满足条件了，当前位置还有可能后后面再次出现的位置满足条件。
#include<unordered_map>
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
//哈希法
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++){
if(map.find(nums[i]) != map.end()){
if(map[nums[i]] + k >= i){
return true;
}
}
map[nums[i]] = i;
}
return false;
}
};
- 还有其他方法，第二遍刷的时候学一下，都是些稍微复杂的方法。
用队列实现栈（题目编号225：link）
- 思路1：双队列，一直保持其中一个为空，另一个push元素，当需要pop时，把非空队列除最后一个元素外的元素全部push到另一个队列中。top操作就先pop，记录值，再push，返回记录的值即可。注意这里在类内初始化两个队列时要放在类方法外面，不要放到MyStack(){}构造函数里面。
#include<queue>
class MyStack {
public:
/** Initialize your data structure here. */
MyStack() {
}
queue<int> s1, s2;
/** Push element x onto stack. */
void push(int x) {
if(s1.empty()){
s2.push(x);
}
else{
s1.push(x);
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
if(s1.empty()){
if(s2.size() == 0){
return 0; // 异常情况
}
else{
while(s2.size() > 1){
int top = s2.front();
s1.push(top);
s2.pop();
}
int res = s2.front();
s2.pop();
return res;
}
}
else{
while(s1.size() > 1){
int top = s1.front();
s2.push(top);
s1.pop();
}
int res = s1.front();
s1.pop();
return res;
}
}
/** Get the top element. */
int top() {
int res = this->pop();
this->push(res);
return res;
}
/** Returns whether the stack is empty. */
bool empty() {
return s1.empty() && s2.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
- 思路2：单队列，pop的时候把除最后一个元素外的元素逐个从队列中弹出，从队尾进入。返回最后一个元素。
#include<queue>
class MyStack {
public:
/** Initialize your data structure here. */
MyStack() {
}
queue<int> q;
/** Push element x onto stack. */
void push(int x) {
q.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = q.size();
if(size == 0) return 0; //异常情况
while(size > 1){
int val = q.front();
q.pop();
q.push(val);
size--;
}
int res = q.front();
q.pop();
return res;
}
/** Get the top element. */
int top() {
int res = this->pop();
this->push(res);
return res;
}
/** Returns whether the stack is empty. */
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
- 两种方法的耗时和内存消耗都一样。
翻转二叉树（题目编号226：link）
- 递归法：递归终止条件是当root为空节点或者左右子节点都是空节点，直接返回root。其他情况，假设已经将当前节点的左子树和右子树翻转，得到inversed_left和inversed_right，那么将翻转后的左子树变为右子节点，将翻转后的右子树变为左子节点即可。方法耗时只击败了7%。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL || (root->left == NULL && root->right == NULL)){
return root;
}
TreeNode* inversed_left = invertTree(root->left);
TreeNode* inversed_right = invertTree(root->right);
root->left = inversed_right;
root->right = inversed_left;
return root;
}
};
- 另一种方法，广度优先遍历，逐层遍历树的各个节点，把每个节点的左右子节点交换。耗时0ms。
TreeNode* invertTree(TreeNode* root){
if(!root) return root;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
TreeNode* tmp = cur->left;
cur->left = cur->right;
cur->right = tmp;
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
return root;
}
2的幂（题目编号231：link）
- 对2取余，余数一直是0的话，说明是2的幂次方。
class Solution {
public:
bool isPowerOfTwo(int n) {
//对2取余，余数一直是0的话，说明是2的幂次方。
if(n <= 0) return false;
while(n > 1){
int tmp = n % 2;
if(tmp == 1) return false;
n = n / 2;
}
return true;
}
};
- 一种奇特的思路，运用之前统计1出现次数的方法，在n>=1时，计算n & (n - 1)，结果就是令n的二进制最右边一个1变成0，如果这时候返回的结果是0，就说明n只有最高位是1。
bool isPowerOfTwo(int n) {
if(n <= 0) return 0;
return (n & (n - 1)) == 0;
}
用栈实现队列（题目编号232：link）
- 用双栈实现队列，第一个栈用于存放元素，第二个栈为辅助，当需要pop队列第一个元素时，把栈1所有元素弹出并压到s2中，再把s2栈顶元素记录为res并弹出，再将其他元素弹出并压到s1中。获取队列front的代码，相比pop的代码，少了一步弹出s2栈顶元素，其他都一样。判断队列是否为空，只需返回栈1是否为空即可。
#include<stack>
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
stack<int> s1, s2;
/** Push element x to the back of queue. */
void push(int x) {
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(s1.empty()){
return 0; //异常
}
else{
while(!s1.empty()){
int tmp = s1.top();
s2.push(tmp);
s1.pop();
}
int res = s2.top();
s2.pop();
while(!s2.empty())
{
int tmp = s2.top();
s1.push(tmp);
s2.pop();
}
return res;
}
}
/** Get the front element. */
int peek() {
if(s1.empty()){
return 0; //异常
}
else{
while(!s1.empty()){
int tmp = s1.top();
s2.push(tmp);
s1.pop();
}
int res = s2.top();
while(!s2.empty())
{
int tmp = s2.top();
s1.push(tmp);
s2.pop();
}
return res;
}
}
/** Returns whether the queue is empty. */
bool empty() {
return s1.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
- 代码在peek方法部分，可以优化一下，维护一个变量front，记录队列最前边一个元素，push时，如果栈s1为空，更新front变量为当前push的值，其他情况不需要更新front，而在pop时，必须更新front，弹出栈s2的栈顶元素后，如果s2不为空，插入一个操作，更新front为s2栈顶元素。代码会简洁一些，用一个int元素的空间换取peek方法加速。
#include<stack>
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
stack<int> s1, s2;
int front = 0;
/** Push element x to the back of queue. */
void push(int x) {
if(s1.empty()) front = x;
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(s1.empty()){
return 0; //异常
}
else{
while(!s1.empty()){
int tmp = s1.top();
s2.push(tmp);
s1.pop();
}
int res = s2.top();
s2.pop();
if(s2.empty()){
front = 0;
}
else{
front = s2.top();
}
while(!s2.empty())
{
int tmp = s2.top();
s1.push(tmp);
s2.pop();
}
return res;
}
}
/** Get the front element. */
int peek() {
return front;
}
/** Returns whether the queue is empty. */
bool empty() {
return s1.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
回文链表（题目编号234：link）
- 在时间复杂度O(N)，空间复杂度O(N)的情况下，方法是：1.用快慢指针法，找到链表的中间节点（链表长度奇偶不影响），然后将后半部分链表翻转，逐元素比较两个一半长度的链表即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head == NULL || head->next == NULL) return true;
//1.快慢指针找到链表中点
ListNode *p1, *p2;
p1 = p2 = head;
while(p2 && p2->next){
p1 = p1->next;
p2 = p2->next->next;
}
//p1是链表的中点
//2.翻转后半部分链表
ListNode* p = inverseLinkList(p1);
while(head && p){
if(head->val != p->val){
return false;
}
head = head->next;
p = p->next;
}
return true;
}
ListNode* inverseLinkList(ListNode* head){
if(!head || !head->next) return head;
ListNode* p = inverseLinkList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
};
- 链表翻转的循环法
//循环法
ListNode* pre = NULL;
while(p1){
ListNode* tmp = p1->next;
p1->next = pre;
pre = p1;
p1 = tmp;
}
- 题目要求空间复杂度O(1)的话，链表翻转部分应该只能用循环法了。做题的时候循环法又出错了，复习的时候要注意。
二叉搜索树的最近公共祖先（题目编号235：link）
- 二叉搜索树（BST）的性质：
a. 节点 NN 左子树上的所有节点的值都小于等于节点 NN 的值
b. 节点 NN 右子树上的所有节点的值都大于等于节点 NN 的值
c. 左子树和右子树也都是 BST - 递归法：如果p和q的值都在root的一侧，那么root一定不是要求的最近公共祖先，要继续在对应的子树里找，如果向下递归的时候，某一层，p和q的值在不同子树，那么当前root就是要求的最近公共祖先。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return root;
if(p->val < root->val && q->val < root->val){
return lowestCommonAncestor(root->left, p, q);
}
else if(p->val > root->val && q->val > root->val){
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
};
- 本题循环法也比较简单，把向下递归改为移动root节点即可。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return root;
while(true)
{
if(p->val < root->val && q->val < root->val){
root = root->left;
}
else if(p->val > root->val && q->val > root->val){
root = root->right;
}
else{
return root;
}
}
}
};
删除链表中的节点（题目编号237：link）
- 看了半天输入参数，一直感觉奇怪，为什么只有一个输入参数，不是应该输入链表头结点和要删除节点的指针或者值吗？原来是题目很奇妙，解法是把要删除的节点的下一个节点的值复制到当前节点，然后删除下一个节点。我把下一个节点用delete删除了，这样比较好吧。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
ListNode* p = node->next;
node->next = node->next->next;
delete p;
}
};
有效的字母异位词（题目编号242：link）
- 这道题目说了两个字符串都是小写字母，那么就可以用26维的数组count存放s中每种字符出现的次数，然后遍历t，将count对应字符出现的次数减一，如果出现负值，那么说明两个字符串的字符构成不一致，返回false。
- s和t的长度不一致时可以直接返回。
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.length() != t.length())
return false;
int count[26];
for(int i = 0; i < 26; i++) count[i] = 0;
char base = 'a';
int int_base = (int)base;
for(int i = 0; i < s.length(); i++){
count[(int)s[i] - int_base]++;
}
for(int i = 0; i < t.length(); i++){
int pos = (int)t[i] - int_base;
if(count[pos] == 0){
return false;
}
count[pos]--;
}
return true;
}
};
二叉树的所有路径（题目编号257：link）
- 递归法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(root == NULL){
res.push_back("");
return res;
}
if(root->left == NULL && root->right == NULL){
res.push_back(to_string(root->val));
}
if(root->left){
vector<string> left_res = binaryTreePaths(root->left);
for(int i = 0; i < left_res.size(); i++){
res.push_back(to_string(root->val) + "->" + left_res[i]);
}
}
if(root->right){
vector<string> right_res = binaryTreePaths(root->right);
for(int i = 0; i < right_res.size(); i++){
res.push_back(to_string(root->val) + "->" + right_res[i]);
}
}
return res;
}
};
- 记住int转string的函数是to_string(int)，是一个普通函数，不是int类型的方法，不能对一个数字.to_string()。
各位相加（题目编号258：link）
- 这道题可以通过循环来解，但是有一种很奇妙的做法，解法
class Solution {
public:
int addDigits(int num) {
return (num - 1) % 9 + 1;
}
};
- 丑数（题目编号263：link）
- 如果能被2、3、5中任何一个整除，那么就除这个数，继续判断结果是不是丑数。如果一个数是丑数，经过多次这样的运算就会变成1。
- 题目关键是1到底算不算丑数。
class Solution {
public:
bool isUgly(int num) {
if(num <= 0) return false;
if(num == 1) return true;
if(num % 2 == 0) return isUgly(num / 2);
if(num % 3 == 0) return isUgly(num / 3);
if(num % 5 == 0) return isUgly(num / 5);
return false;
}
};
缺失数字（题目编号268：link）
- 这道比较简单，0~n的和可以通过数组求和公式快速计算，减去nums内各个元素之和，就是缺失的数字。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int target = (0 + n) * (n + 1) / 2;
int sum = 0;
for(int i = 0; i < n; i++){
sum += nums[i];
}
return target - sum;
}
};
买卖股票的最佳时机II（题目编号122：link）
- 这道题目比较难，之前刷剑指offer的时候就没搞明白，这次再试试。
- 动态规划法，定义状态dp[i][0]表示第i天状态为持有现金时的最大收益，dp[i][1]表示第i天状态为持有股票时的最大收益。那么，第i+1天，若持有现金，那么想要获得最大收益有两种可能，一是顺着第i天的持有现金状态，不进行交易，或者第i-1天为持有股票状态，第i+1天卖出套现；同样，第i+1天，持有股票状态时的最大收益也有两种可能，一是不卖，
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() == 0) return 0;
int n = prices.size();
vector<vector<int>> dp;
vector<int> tmp_dp;
tmp_dp.push_back(0);
tmp_dp.push_back(-prices[0]);
dp.push_back(tmp_dp);
for(int i = 1; i < prices.size(); i++){
tmp_dp[0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
tmp_dp[1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp.push_back(tmp_dp);
}
return dp[n - 1][0];
}
// int maxProfit(vector<int>& prices) {
// int max_profit = 0;
// for(int i = 1; i < prices.size(); i++){
// if(prices[i] > prices[i - 1]){
// max_profit += prices[i] - prices[i - 1];
// }
// }
// return max_profit;
// }
};
第一个错误的版本（题目编号278：link）
- 二分法
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int left = 1, right = n;
while(left < right){
int mid = left + (right - left) / 2;
if(isBadVersion(mid) == false){
left = mid + 1;
}
else{
right = mid;
}
}
return left;
}
};
移动零（题目编号283：link）
- 这题就是从前往后遍历，非0数字从0号位置开始放，记录目前遇到多少个非0数字即可。注意最后还要把放置非0元素之和，vector剩余的空间置0。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cnt = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] != 0){
nums[cnt] = nums[i];
cnt++;
}
}
for(int i = cnt; i < nums.size(); i++)
{
nums[i] = 0;
}
}
};
单词规律（题目编号290：link）
- 这个跟之前的有道题很像，那个是匹配两个字符串。这个需要先划分第二个string为多个string。然后再建立字典，双向匹配。
class Solution {
public:
bool wordPattern(string pattern, string str) {
vector<string> arr;
int start = 0;
for(int i = 0; i < str.size(); i++){
if(i == str.size() - 1){
arr.push_back(str.substr(start, i - start + 1));
}
else if(str[i] == ' ' ){
arr.push_back(str.substr(start, i - start));
start = i + 1;
}
}
map<char, string> map_c2s;
map<string, char> map_s2c;
if(pattern.size() != arr.size()) return false;
for(int i = 0; i < pattern.size(); i++){
if(map_c2s.find(pattern[i]) == map_c2s.end())
{
map_c2s[pattern[i]] = arr[i];
}
else{
if(map_c2s[pattern[i]] != arr[i]){
return false;
}
}
if(map_s2c.find(arr[i]) == map_s2c.end())
{
map_s2c[arr[i]] = pattern[i];
}
else{
if(map_s2c[arr[i]] != pattern[i]){
return false;
}
}
}
return true;
}
};
- 这里用的是map，之前用unordered_map，二者的区别是什么呢？
Nim游戏（题目编号292：link）
- 这个比较简单，自己先拿，拿完之后剩下4的倍数，就可以赢，否则都赢不了。所以拿之前如果是4的倍数，那么一定是对手赢。
- C++三元运算符，a > b? c: d。
class Solution {
public:
bool canWinNim(int n) {
return n % 4 == 0? false: true;
}
};
猜数字（题目编号299：link）
- 首先补齐两个数字字符串，然后遍历每一位，如果数字字符相同，则cntA++，否则用两个map分别统计两个字符串中不匹配位置处每个数字出现的次数。最后遍历secret字符串的统计结果，判断guess中是否有这个数字，有的话，给cntB加上两个map中对应数字出现次数的最小值。
- 返回合成的1A3B形式的字符串。
- 注意map的遍历：for(map<char, int>::iterator it = map_obj.begin(); it != map_obj.end(); it++)，这里的it是指针，it->first可以得到key，it->second可以得到value。
- C++，数字转字符串可以用to_string(num)实现，但char怎么转string?
- C++的min函数需要#include<algorithm>
#include<algorithm>
class Solution {
public:
string getHint(string secret, string guess) {
int size_s = secret.size(), size_g = guess.size();
if(size_s > size_g){
for(int i = 0; i < size_s - size_g; i++){
secret = '0' + secret;
}
}
else if(size_s < size_g){
for(int i = 0; i < size_g - size_s; i++){
guess = '0' + guess;
}
}
int cntA = 0, cntB = 0;
map<char, int> map_s, map_g;
for(int i = 0; i < secret.size(); i++){
if(secret[i] == guess[i]){
cntA++;
}
else{
if(map_s.find(secret[i]) == map_s.end()){
map_s[secret[i]] = 1;
}
else{
map_s[secret[i]]++;
}
if(map_g.find(guess[i]) == map_g.end()){
map_g[guess[i]] = 1;
}
else{
map_g[guess[i]]++;
}
}
}
for(map<char, int>::iterator it = map_s.begin(); it != map_s.end(); it++){
if(map_g.find(it->first) != map_g.end()){
cntB += min(map_g[it->first], map_s[it->first]);
}
}
string res = to_string(cntA) + "A" + to_string(cntB) + "B";
return res;
}
};
区域和检索（题目编号303：link）
- 用一个新的vector记录，从位置0到位置k的元素之和，新的vector最前边放0，长度为nums.size()+1，似乎在求解区间之和的时候方便一些。
- 计算区间长度时用0到j的元素之和-0到i-1的元素之和，注意要包含i和j，因此左右两边不一样。
- C++的vector清空是vector_obj.clear()方法，但似乎实际上不会回收空间。还有erase方法，复杂一些。
class NumArray {
public:
vector<int> arr_sum;
NumArray(vector<int>& nums) {
arr_sum.clear();
arr_sum.push_back(0);
for(int num: nums){
arr_sum.push_back(arr_sum[arr_sum.size() - 1] + num);
}
}
int sumRange(int i, int j) {
if(arr_sum.empty() || i > arr_sum.size() || j > arr_sum.size()) return 0;
return arr_sum[j + 1] - arr_sum[i];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(i,j);
*/
3的幂（题目编号326：link）
- 我使用的方法是指数从0开始增加，直到pow(3, 指数) >= n时退出循环，判断此时是等还是不等。
- 还可以用换底公式，用以10为底的对数log10进行换底，计算log3(n)，判断结果是不是整数。
class Solution {
public:
bool isPowerOfThree(int n) {
int tmp = 0;
while(pow(3, tmp) < n){
tmp++;
}
return pow(3, tmp) == n? true: false;
}
};
4的幂（题目编号342：link）
- 跟上题一模一样，这次尝试换底公式法。
class Solution {
public:
bool isPowerOfFour(int num) {
if(num <= 0) return false;
double log_res = log10(num) / log10(4);
return abs(log_res - (int) log_res) == 0? true: false;
}
};
反转字符串（题目编号344：link）
- 前后对着调换字符即可。
class Solution {
public:
void reverseString(vector<char>& s) {
char tmp;
for(int i = 0; i < s.size() / 2; i++){
tmp = s[i];
s[i] = s[s.size() - 1 - i];
s[s.size() - 1 - i] = tmp;
}
}
};
反转字符串中的元音字母（题目编号345：link）
- 双指针法，这里我是把元音字母放到一个vector里，用std::find从vector中搜索某个字母，判断该字母是否是元音字母。
- 注意元音字母包含大小写。
- while循环移动指针时，注意不要越界。
- 有些时候可以优化，快速退出循环，避免不必要的计算。
class Solution {
public:
string reverseVowels(string s) {
vector<char> arr;
arr.push_back('a');
arr.push_back('e');
arr.push_back('i');
arr.push_back('o');
arr.push_back('u');
arr.push_back('A');
arr.push_back('E');
arr.push_back('I');
arr.push_back('O');
arr.push_back('U');
char tmp;
int p = 0, q = s.size() - 1;
while(p < q){
while(p < q && std::find(arr.begin(), arr.end(), s[p]) == arr.end()) p++;
while(q > p && std::find(arr.begin(), arr.end(), s[q]) == arr.end()) q--;
if(p < q){
tmp = s[p];
s[p] = s[q];
s[q] = tmp;
p++;
q--;
}
else{
break;
}
}
return s;
}
};
- 还可以把几个大小写元音字母放到string里，调用string_obj.find(target_string)方法，如果没找到目标字符串就返回string_obj.npos，这里的target_string有重载，可以是char型字符，还可以是char*指针（这里是不是C风格字符串？）。用字符串的查找比前面的vector查找，速度上快了一倍。
class Solution {
public:
string reverseVowels(string s) {
string dict_char = "aeiouAEIOU";
char tmp;
int p = 0, q = s.size() - 1;
while(p < q){
while(p < q && dict_char.find(s[p]) == dict_char.npos) p++;
while(q > p && dict_char.find(s[q]) == dict_char.npos) q--;
if(p < q){
tmp = s[p];
s[p] = s[q];
s[q] = tmp;
p++;
q--;
}
else{
break;
}
}
return s;
}
};
有效的完全平方数（题目编号367：link）
- 这道题会有平方后的结果溢出的问题。把临时变量用long表示就通过了。
- 其他方法还有二分法，牛顿迭代法等。时间复杂度都是log(N)。
class Solution {
public:
bool isPerfectSquare(int num) {
long tmp = 1;
while(true){
if(tmp * tmp >= num) break;
tmp++;
}
return tmp * tmp == num? true: false;
}
};
两个数组的交集（题目编号349：link）
- 主要思想是先用第一个unordered_map记录数组nums1中的出现过的元素，然后遍历nums2，判断元素有没有在map中，在的话添加到另一个记录结果中数字的map中。第二个map可以不使用，当某个数字已经在结果中出现后，可以修改第一个map该键对应的value。
#include<unordered_map>
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> map_1, map_2;
for(int i = 0; i < nums1.size(); i++){
if(map_1.find(nums1[i]) == map_1.end()){
map_1[nums1[i]] = 1;
}
}
vector<int> res;
for(int i = 0; i < nums2.size(); i++){
if(map_1.find(nums2[i]) != map_1.end() && map_2.find(nums2[i]) == map_2.end()){
res.push_back(nums2[i]);
map_2[nums2[i]] = 1;
}
}
return res;
}
};
#include<unordered_map>
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> map_1;
for(int i = 0; i < nums1.size(); i++){
if(map_1.find(nums1[i]) == map_1.end()){
map_1[nums1[i]] = 1;
}
}
vector<int> res;
for(int i = 0; i < nums2.size(); i++){
if(map_1.find(nums2[i]) != map_1.end() && map_1[nums2[i]] == 1){
res.push_back(nums2[i]);
map_1[nums2[i]] = 2;
}
}
return res;
}
};
两个数组的交集II（题目编号350：link）
- 延续上边一道题的思想，用map记录nums1中每个元素出现的次数，遍历nums2，遇到nums1中出现的数字的时候，就把map中对应的计数器减一，当计数器大于0时才往res里放。
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> map_1;
for(int i = 0; i < nums1.size(); i++){
if(map_1.find(nums1[i]) == map_1.end()){
map_1[nums1[i]] = 1;
}
else{
map_1[nums1[i]]++;
}
}
vector<int> res;
for(int i = 0; i < nums2.size(); i++){
if(map_1.find(nums2[i]) != map_1.end() && map_1[nums2[i]] > 0){
res.push_back(nums2[i]);
map_1[nums2[i]]--;
}
}
return res;
}
};
- 可优化的点：对长度短的数组建立map，可以减少耗时。
- 如果数组都排好序了，该怎么做？
- 进阶部分未来再研究一下。
两整数之和（题目编号371：link）
- 不使用±运算计算两整数之和，分析可以发现可以用异或运算计算得到不带进位的加法结果，使用与运算再向左移动一个二进制位可以得到进位结果，当进位结果不为0时就需要重复进行异或和与运算。注意左移运算需要前边的数字是unsigned int。溢出问题。
class Solution {
public:
int getSum(int a, int b) {
int res_sum = a, carry = b;
while(carry != 0){
int tmp = res_sum ^ carry;
carry = (unsigned int)(res_sum & carry) << 1;
res_sum = tmp;
}
return res_sum;
}
};
猜数字大小（题目编号374：link）
- 二分法，循环条件
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* int guess(int num);
*/
class Solution {
public:
int guessNumber(int n) {
int left = 1, right = n;
while(left < right){
int mid = left + (right - left) / 2;
int guess_res = guess(mid);
if(guess_res == 0){
return mid;
}
else if(guess_res == 1){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return left;
}
};
- 循环里面可以是left<=right，这样的话，事实上是不会退出while循环的，但是C++似乎还是要求必须在循环外加return语句。写return 0也可以运行通过。这点需要注意，n可能不符合规定，所以外面还是需要return语句。
赎金信（题目编号383：link）
- 遍历第一个字符串，用unordered_map统计每个字符出现的次数，遍历第二个字符串，如果是第一个字符串中需要的字符，而且计数器大于0，就给计数器减一。最后再遍历map，看是否是所有位置都已经是0，都是0的话说明第一个字符串中每个字符都可以从第二个字符串中取出。
- 这里我采用的是unordered_map，观察题目，所有字符都是小写字母，其实可以用hash的思想，用26个元素的数组记录每个字母出现的次数。
#include<unordered_map>
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char, int> ransom_map;
for(int i = 0; i < ransomNote.size(); i++){
if(ransom_map.find(ransomNote[i]) == ransom_map.end()){
ransom_map[ransomNote[i]] = 1;
}
else{
ransom_map[ransomNote[i]]++;
}
}
for(int i = 0; i < magazine.size(); i++){
char cur = magazine[i];
if(ransom_map.find(cur) != ransom_map.end() and ransom_map[cur] > 0){
ransom_map[cur]--;
}
}
for(unordered_map<char, int>::iterator it = ransom_map.begin(); it != ransom_map.end(); it++){
if(it->second > 0) return false;
}
return true;
}
};
- 用数组替换unordered_map，效率提高。
#include<unordered_map>
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int cnt[26];
for(int i = 0; i < 26; i++) cnt[i] = 0;
for(int i = 0; i < ransomNote.size(); i++){
cnt[ransomNote[i] - 'a']++;
}
for(int i = 0; i < magazine.size(); i++){
char cur = magazine[i];
if(cnt[cur - 'a'] > 0){
cnt[cur - 'a']--;
}
}
for(int i = 0; i < 26; i++){
if(cnt[i] > 0) return false;
}
return true;
}
};
字符串中的第一个唯一字符（题目编号387：link）
- 还是用26维数组统计每个字符出现的次数，再遍历一次字符串，如果某个字符只出现了一次，那么就返回。注意题目中说如果找不到符合要求的字符，就返回-1。
class Solution {
public:
int firstUniqChar(string s) {
int cnt[26];
for(int i = 0; i < 26; i++){
cnt[i] = 0;
}
for(char c: s){
cnt[c - 'a']++;
}
for(int i = 0; i < s.size(); i++){
if(cnt[s[i] - 'a'] == 1) return i;
}
return -1;
}
};
找不同（题目编号389：link）
- 跟前边几道题目的方法一样，只包含小写字母，就用26维数组记录每个字母出现的次数。
class Solution {
public:
char findTheDifference(string s, string t) {
int cnt[26];
for(int i = 0; i < 26; i++){
cnt[i] = 0;
}
for(char c: s){
cnt[c - 'a']++;
}
for(char c: t){
cnt[c - 'a']--;
}
for(int i = 0; i < 26; i++){
if(cnt[i] == -1) return (char)('a' + i);
}
return '0';
}
};
判断子序列 （题目编号392：link）
- 双指针法，使用贪心算法，匹配到s某个字符，就把指针往后移动
class Solution {
public:
bool isSubsequence(string s, string t) {
if(s.size() > t.size()) return false;
int p = 0, q = 0;
while(p < s.size() && q < t.size()){
if(s[p] == t[q]){
p++;
}
q++;
}
return p == s.size();
}
};
- 此题，如果是对同一个t，测试多个s是否在t中，那么可以使用动态规划法，dp[i][j]表示从位置i开始往后的字符串中26个小写字母中序号为j的字母第一次出现的位置，倒序递推，令m = t.size()，初始化dp[m][…] = m，递推如下：
d p [ i ] [ j ] = { i t[i]=j d p [ i + 1 ] [ j ] t[i]!=j dp[i][j]= \begin{cases} i& \text{t[i]=j}\\ dp[i+1][j]& \text{t[i]!=j} \end{cases}dp[i][j]={idp[i+1][j]t[i]=jt[i]!=j
class Solution {
public:
bool isSubsequence(string s, string t) {
//动态规划法
int m = t.size();
vector<vector<int>> f(m + 1, vector<int>(26, 0));
for(int i = m; i >= 0; i--){
for(int j = 0; j < 26; j++){
if(i == m){
f[i][j] = m;
}
else if(t[i] == j + 'a'){
f[i][j] = i;
}
else{
f[i][j] = f[i+1][j];
}
}
}
int add = 0;
for(int i = 0; i < s.size(); i++){
if(f[add][s[i] - 'a'] == m) return false;
add = f[add][s[i] - 'a'] + 1;
}
return true;
}
};
- 动态规划法，如果是单次运行，内存消耗较大，但是如果是多次从一个字符串t判断字符串t是否存在，则单次检测的时间复杂度会从双指针法的O(m)降低到O(n)，m表示t的长度，n表示n的长度，建立动态规划矩阵的时间复杂度是O(m)。
左叶子之和（题目编号404：link）
- 经典的层次遍历法，注意题目要求的是左叶子节点，而非左子节点。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include<queue>
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root == NULL) return 0;
queue<TreeNode*> q;
q.push(root);
int res = 0;
while(q.size() > 0){
TreeNode* node = q.front();
q.pop();
if(node->left){
if(node->left->left == NULL && node->left->right == NULL)
res += node->left->val;
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
return res;
}
};
- 递归法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include<queue>
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root == NULL) return 0;
int res = 0;
if(root->left){
if(root->left->left == NULL && root->left->right == NULL)
res += root->left->val;
res += sumOfLeftLeaves(root->left);
}
if(root->right){
res += sumOfLeftLeaves(root->right);
}
return res;
}
};
数字转换为十六进制数（题目编号405：link）
- 不管是正数还是负数，直接转换为unsigned int处理。
class Solution {
public:
string toHex(int num) {
if(num == 0) return string(1, '0');
string res = "";
int tmp;
unsigned int num1 = num;
while(num1){
tmp = num1 % 16;
if(tmp < 10){
res = string(1, '0' + tmp) + res;
}
else{
res = string(1, 'a' + tmp - 10) + res;
}
num1 /= 16;
}
return res;
}
};
- 对补码的理解还不够，还需要思考学习。
最长回文串（题目编号409：link）
- 最开始没注意看清题目，以为是从中找到连续的回文字符串，结果不是，顺序任意。回文字符串中至多有一个字符出现奇数次，那么就统计字符串中有多少个字符出现的次数为奇数，中间那个奇数的字符只能是这些中的一个，因此其他字符就要丢弃多余的一个，把偶数的数量留下来分别放在中间字符的两边。
class Solution {
public:
int longestPalindrome(string s) {
int cnt[128];
for(int i = 0; i < 128; i++){
cnt[i] = 0;
}
for(char c: s){
cnt[c]++;
}
int odd_cnt = 0;
for(int i = 0; i < 128; i++){
odd_cnt += cnt[i] % 2;
}
return odd_cnt == 0? s.length(): s.length() - odd_cnt + 1;
}
};
Fizz Buzz（题目编号412：link）
- 这题很简单，如果除数多，可以依次判断，可以被对应的数整除，就在临时字符串后面加上该除数对应的字符串即可，不需判断是否能被15整除。
class Solution {
public:
vector<string> fizzBuzz(int n) {
vector<string> res;
string tmp;
for(int i = 1; i <= n; i++){
tmp = "";
if(i % 3 != 0 && i % 5 != 0)
{
tmp = to_string(i);
res.push_back(tmp);
continue;
}
if(i % 3 == 0){
tmp += "Fizz";
}
if(i % 5 == 0){
tmp += "Buzz";
}
res.push_back(tmp);
}
return res;
}
};
第三大的数（题目编号414：link）
- 注意要找的数字是唯一出现的数，因此当判断某个数字在前三大数组成的vector中时就需要跳过。
- 做题的时候当输入为[1,1,2]或[1,2,2]时报错heap_over_flow错误，是因为越界，访问非法内容，是最后返回时之前写的是three_max_num[nums.size() > 2? 2:0]，当数组只有3个元素且有重复元素时，three_max_num的长度会小于3，因此报错。
- 排序部分可以优化。
class Solution {
public:
int thirdMax(vector<int>& nums) {
if(nums.size() == 0) return 0;
vector<int> three_max_num;
for(int num: nums){
if(find(three_max_num.begin(), three_max_num.end(), num) != three_max_num.end()){
continue;
}
if(three_max_num.size() < 3){
three_max_num.push_back(num);
}
else if(num > three_max_num.back()){
three_max_num[2] = num;
}
my_sort(three_max_num);
}
return three_max_num[three_max_num.size() == 3 && nums.size() > 2? 2:0];
}
void my_sort(vector<int>& arr){
// 对三个数字组成的数组进行降序排序
for(int i = 0; i < arr.size(); i++){
for(int j = i + 1; j < arr.size(); j++){
if(arr[i] < arr[j]){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
};
字符串相加（题目编号415：link）
- 之前好像有类似的题目，可能是vector吧。
class Solution {
public:
string addStrings(string num1, string num2) {
string res = "";
int add2next = 0, res_add;
int p1 = num1.size() - 1, p2 = num2.size() - 1;
while(p1 >= 0 && p2 >= 0){
res_add = (num1[p1] - '0') + (num2[p2] - '0') + add2next;
add2next = res_add / 10;
res_add = res_add % 10;
res = to_string(res_add) + res;
p1--;
p2--;
}
while(p1 >= 0){
res_add = (num1[p1] - '0') + add2next;
add2next = res_add / 10;
res_add = res_add % 10;
res = to_string(res_add) + res;
p1--;
}
while(p2 >= 0){
res_add = (num2[p2] - '0') + add2next;
add2next = res_add / 10;
res_add = res_add % 10;
res = to_string(res_add) + res;
p2--;
}
if(add2next == 1){
res = "1" + res;
}
return res;
}
};
字符串中的单词数（题目编号434：link）
- 这道之前好像也有。
class Solution {
public:
int countSegments(string s) {
int res_cnt = 0;
bool new_str = false;
for(char c: s){
if(c == ' '){
if(new_str){
res_cnt++;
new_str = false;
}
}
else{
new_str = true;
}
}
return new_str? res_cnt + 1: res_cnt;
}
};
排列硬币（题目编号441：link）
- 这道之前也出现过类似的，解法一样，就是题目变了一下，前面那道应该是找开方后向下取整的结果。
- 注意溢出问题。mid要用long int。
class Solution {
public:
int arrangeCoins(int n) {
int left = 0, right = n;
while(left <= right){
long int mid = left + (right - left) / 2;
long int res_mid = (mid + 1) * mid / 2;
long int res_mid_next = (mid + 1) * (mid + 2) / 2;
if(res_mid == n){
return mid;
}
else if(res_mid > n){
right = mid - 1;
}
else if(res_mid_next > n){
return mid;
}
else{
left = mid + 1;
}
}
return left;
}
};
压缩字符串（题目编号443：link）
- 又是重复题目。
class Solution {
public:
int compress(vector<char>& chars) {
char tmp_char;
int cnt = 0, pos = 0;
for(int i = 0; i < chars.size(); i++){
if(cnt == 0){
tmp_char = chars[i];
cnt++;
}
else if(tmp_char == chars[i]){
cnt++;
}
else{
chars[pos++] = tmp_char;
if(cnt > 1){
pos = add_num(chars, cnt, pos);
}
tmp_char = chars[i];
cnt = 1;
}
}
if(cnt > 0){
chars[pos++] = tmp_char;
if(cnt > 1)
{
pos = add_num(chars, cnt, pos);
}
}
return pos;
}
int add_num(vector<char>& chars, int cnt, int pos){
int start_pos = pos;
while(cnt){
int res_mod = cnt % 10;
chars[pos++] = res_mod + '0';
cnt /= 10;
}
int end_pos = pos - 1;
while(start_pos < end_pos){
char tmp_exchange = chars[start_pos];
chars[start_pos] = chars[end_pos];
chars[end_pos] = tmp_exchange;
start_pos++;
end_pos--;
}
return pos;
}
};
回旋镖的数量（题目编号447：link）
- 对于每个点，计算与其他点的距离，并记录每个距离值出现的次数，如果距离为5的点出现4次，那么就可以组成P 4 2 P_4^2P42种回旋镖。
- 注意，对每个点要重新初始化map。
- 但是会存在重复计算的问题，比如点i和j的距离和j和i的距离。
#include<unordered_map>
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int res = 0;
for(int i = 0; i < points.size(); i++){
unordered_map<int, int> map;
for(int j = 0; j < points.size(); j++){
if(j == i) continue;
int dist = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2);
if(map.find(dist) == map.end()){
map[dist] = 1;
}
else{
map[dist]++;
}
}
for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
res += it->second * (it->second - 1);
}
}
return res;
}
};
找到所有数组中消失的数字（题目编号448：link）
- 数字的范围是1~n，数组长度也是n，因此可以利用下标信息来记录哪些数字出现过，比如4出现过，那么就把nums[4-1]变为负数，最后再次遍历数组，找出哪些位置是正数，表示pos+1这个数字没出现过。
- C++求绝对值的函数是abs和fabs，分别针对整数和浮点数。需要#include<cmath>
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> res;
for(int i = 0; i < nums.size(); i++){
if(nums[abs(nums[i]) - 1] > 0){
nums[abs(nums[i]) - 1] *= -1;
}
}
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0){
res.push_back(i + 1);
}
}
return res;
}
};
最小移动次数使数组元素相等（题目编号453：link）
- 有多种解法，下面是比较简单的一种，除一个数字外其他数字加1，各个数字的大小关系上其实相当于该数字减1。题中要求的移动次数，等同于将所有数字减到数组中的最小数字。还需要再研究一下。
#include<algorithm>
class Solution {
public:
int minMoves(vector<int>& nums) {
if(nums.size() == 0) return 0;
int moves = 0, min_num = nums[0];
for(auto num: nums){
min_num = min(min_num, num);
}
for(auto num: nums){
moves += num - min_num;
}
return moves;
}
};
颠倒二进制位（题目编号190：link）
- 本题，uint32_t左移<<1的结果似乎与*2不一致。
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
int count = 0;
int last;
while(count < 32)
{
last = n % 2;
res = res * 2 + last;
n = n / 2;
count += 1;
}
return res;
}
};
分发饼干（题目编号455：link）
- 先把两个vector排序，调用algorithm库的sort函数，是从小到大排序，sort(vec.begin(), vec.end())。然后双指针法，如果饼干大于小孩的需求，就把cnt++，指针后移，否则饼干指针后移。
#include<algorithm>
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int cnt = 0, p = 0, q = 0;
while(p < g.size() && q < s.size()){
if(s[q] >= g[p]){
cnt++;
p++;
q++;
}
else{
q++;
}
}
return cnt;
}
};
重复的子字符串（题目编号459：link）
- 暴力循环，可能的子字符串长度为1~n/2，测试s[j] == s[j - len_sub_str]。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.length();
for(int i = 1; i <= n / 2 ; i++){
if(n % i == 0){
bool match = true;
for(int j = i; j < n; j++){
if(s[j] != s[j - i]) {
match = false;
break;
}
}
if(match) return true;
}
}
return false;
}
};
汉明距离（题目编号431：link）
- 两个整数二进制位不一样的位数，就是先异或，再统计异或结果二进制中1的个数。
class Solution {
public:
int hammingDistance(int x, int y) {
int res = x ^ y, cnt = 0;
while(res){
cnt++;
res = res & (res - 1);
}
return cnt;
}
};
岛屿的周长（题目编号463：link）
- 暴力循环，每个小方格的周长为4，某个放个上下左右有n个相连的格子，该方格对整个岛屿周长的贡献就会减掉几n，如果上下左右都有方格，那么它对岛屿周长没有贡献。该方法耗时较长，但也能通过。
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int perimeter = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[i].size(); j++){
if(grid[i][j] == 0) continue;
int tmp = 4;
if(j >= 1 && grid[i][j - 1] == 1) tmp--;
if(i >= 1 && grid[i - 1][j] == 1) tmp--;
if(j < grid[i].size() - 1 && grid[i][j + 1] == 1) tmp--;
if(i < grid.size() - 1 && grid[i+1][j] == 1) tmp--;
perimeter += tmp;
}
}
return perimeter;
}
};
- 另一种思路，如果一个格子上面的格子不是岛屿，那么就把边长+2，如果一个格子左边一格不是岛屿，那么就把边长+2，利用的是对称性，可以稍微减少一些判断次数。
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int perimeter = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[i].size(); j++){
if(grid[i][j] == 0) continue;
if(i == 0 || grid[i - 1][j] == 0) perimeter += 2;
if(j == 0 || grid[i][j - 1] == 0) perimeter += 2;
}
}
return perimeter;
}
};
供暖器（题目编号475：link）
- 为每间房屋找到一个距离最近的供暖器，记录这个最小距离，求所有房屋到供暖期最小距离的最大值，设置供暖期的供暖半径为该值，就可以满足所有房屋的需求。
- 最简单的方法是双重遍历，但是会超时。用二分查找法来为单个房屋寻找距离最近的供暖器。注意有可能供暖期没有刚好安放在房屋的坐标上，可能出现二分查找找不到的情况。要考虑left是到0，heater.size()还是中间某个位置（此时房屋是在heaters[left]和heaters[left-1]中间），分别计算最小距离。
- 注意题目没说heaters的坐标是排序好的，要先排序。sort(heaters.begin(), heaters.end())。
#include<algorithm>
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
int radius = 0;
sort(heaters.begin(), heaters.end());
for(int i = 0; i < houses.size(); i++){
int left = 0, right = heaters.size() - 1, min_dist;
bool found = false;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(heaters[mid] == houses[i]){
found = true;
break;
}
else if(heaters[mid] < houses[i]){
left = mid + 1;
}
else{
right = mid - 1;
}
}
if(found){
min_dist = 0;
}
else{
if(left == 0){
min_dist = abs(heaters[0] - houses[i]);
}
else if(left == heaters.size()){
min_dist = abs(heaters[heaters.size() - 1] - houses[i]);
}
else{
min_dist = min(abs(heaters[left] - houses[i]), abs(heaters[left - 1] - houses[i]));
}
}
radius = max(radius, min_dist);
}
return radius;
}
};
数字的补数（题目编号476：link）
- 先求num的二进制位，然后取反，转换为10进制数。mul = mul << 1，这部分如果是mul *= 2会报溢出错误。
class Solution {
public:
int findComplement(int num) {
int res = 0, mul = 1;
while(num){
int tmp = num % 2;
res += (1 - tmp) * mul;
num = num / 2;
mul = mul << 1;
}
return res;
}
};
密钥格式化（题目编号482：link）
- 倒序访问S，如果不是‘-’，就添加到res后面，每K个字符加一个’-’，最后反向res，调用reverse函数，buxu
class Solution {
public:
string licenseKeyFormatting(string S, int K) {
string res = "";
int cnt = 0;
for(int i = S.length() - 1; i >= 0; i--){
if(S[i] != '-'){
if(cnt == K){
res += "-";
cnt = 0;
}
res += string(1, (char)toupper(S[i]));
cnt++;
}
}
reverse(res.begin(), res.end());
return res;
}
};
最大连续1的个数（题目编号485：link）
- 注意最后一段连续的1，不要忘记判断。
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int max_len = 0, cnt = 0;
for(int num: nums){
if(num == 1){
cnt++;
}
else{
max_len = max(max_len, cnt);
cnt = 0;
}
}
max_len = max(max_len, cnt);
return max_len;
}
};
构造矩形（题目编号492：link）
- 从1到sqrt(area)遍历，如果可以被area整除，说明可以构造除长和宽为正整数的矩形，记录W和L，遍历结束返回结果即可。
class Solution {
public:
vector<int> constructRectangle(int area) {
int L, W;
for(int i = 1; i <= sqrt(area); i++){
if(area % i == 0){
W = i;
L = area / i;
}
}
vector<int> res;
res.push_back(L);
res.push_back(W);
return res;
}
};
下一个更大元素（题目编号496：link）
- 要看清题意，nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。而不是把nums2升序排序后，x的下一个元素。
- 将官方题解放在这里，思路比较巧。
- 我们可以忽略数组 nums1，先对将 nums2 中的每一个元素，求出其下一个更大的元素。随后对于将这些答案放入哈希映射（HashMap）中，再遍历数组 nums1，并直接找出答案。对于 nums2，我们可以使用单调栈来解决这个问题。
- 我们首先把第一个元素 nums2[1] 放入栈，随后对于第二个元素 nums2[2]，如果 nums2[2] > nums2[1]，那么我们就找到了 nums2[1] 的下一个更大元素 nums2[2]，此时就可以把 nums2[1] 出栈并把 nums2[2] 入栈；如果 nums2[2] <= nums2[1]，我们就仅把 nums2[2] 入栈。对于第三个元素 nums2[3]，此时栈中有若干个元素，那么所有比 nums2[3] 小的元素都找到了下一个更大元素（即 nums2[3]），因此可以出栈，在这之后，我们将 nums2[3] 入栈，以此类推。
- 可以发现，我们维护了一个单调栈，栈中的元素从栈顶到栈底是单调不降的。当我们遇到一个新的元素 nums2[i] 时，我们判断栈顶元素是否小于 nums2[i]，如果是，那么栈顶元素的下一个更大元素即为 nums2[i]，我们将栈顶元素出栈。重复这一操作，直到栈为空或者栈顶元素大于 nums2[i]。此时我们将 nums2[i] 入栈，保持栈的单调性，并对接下来的 nums2[i + 1], nums2[i + 2] … 执行同样的操作。
作者：LeetCode
链接：https://leetcode-cn.com/problems/next-greater-element-i/solution/xia-yi-ge-geng-da-yuan-su-i-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#include<unordered_map>
#include<stack>
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> next_big;
stack<int> my_stack;
for(int i = 0; i < nums2.size(); i++){
if(my_stack.empty() || nums2[i] <= my_stack.top()){
my_stack.push(nums2[i]);
}
else{
while(!(my_stack.empty()) && nums2[i] > my_stack.top()){
next_big[my_stack.top()] = nums2[i];
my_stack.pop();
}
my_stack.push(nums2[i]);
}
}
while(!(my_stack.empty())){
next_big[my_stack.top()] = -1;
my_stack.pop();
}
vector<int> res;
for(int i = 0; i < nums1.size(); i++){
res.push_back(next_big[nums1[i]]);
}
return res;
}
};
键盘行（题目编号500：link）
- 用一个map记录每个字母在第几行就可以了。判断的时候判断string里第二个字符起每个字符和前一个字符的行数是否一致。
#include<unordered_map>
class Solution {
public:
vector<string> findWords(vector<string>& words) {
unordered_map<char, int> keyboard_map;
string tmp = "QWERTYUIOP";
for(char c: tmp){
keyboard_map[c] = 0;
}
tmp = "ASDFGHJKL";
for(char c: tmp){
keyboard_map[c] = 1;
}
tmp = "ZXCVBNM";
for(char c: tmp){
keyboard_map[c] = 2;
}
vector<string> res;
for(int i = 0; i < words.size(); i++){
bool match = true;
for(int j = 1; j < words[i].size(); j++){
if(keyboard_map[(char)toupper(words[i][j])] != keyboard_map[(char)toupper(words[i][j - 1])]){
match = false;
break;
}
}
if(match){
res.push_back(words[i]);
}
}
return res;
}
};
七进制数（题目编号504：link）
- 负数只需在其绝对值的7进制编码前加负号即可。
- 题目规定了数字的范围，所以负数*-1不会有越界。（这点对不对？）
class Solution {
public:
string convertToBase7(int num) {
if(num < 0){
return "-" + convertToBase7(num * -1);
}
if(num == 0) return "0";
string res = "";
while(num){
res += to_string(num % 7);
num /= 7;
}
reverse(res.begin(), res.end());
return res;
}
};
相对名次（题目编号506：link）
- sort函数的另一种用法，第三个参数，自定义排序方法。
- pair的使用。
class Solution {
public:
static bool my_cmp(const pair<int, int> a, const pair<int, int> b){
return a.first > b.first;
}
vector<string> findRelativeRanks(vector<int>& nums) {
vector<pair<int, int>> nums_pair;
for(int i = 0; i < nums.size(); i++){
nums_pair.push_back({nums[i], i});
}
sort(nums_pair.begin(), nums_pair.end(), my_cmp);
vector<string> res(nums.size());
for(int i = 0; i < nums_pair.size(); i++){
if(i > 2){
res[nums_pair[i].second] = to_string(i + 1);
}
else if(i == 0){
res[nums_pair[i].second] = "Gold Medal";
}
else if(i == 1){
res[nums_pair[i].second] = "Silver Medal";
}
else{
res[nums_pair[i].second] = "Bronze Medal";
}
}
return res;
}
};
完美数（题目编号507：link）
- 遍历解法，也能通过。注意小于等于0的数字没有正因子，所以直接返回false。
- 还有另外一种方法，可以直接计算出所有的完美数。
class Solution {
public:
bool checkPerfectNumber(int num) {
if(num <= 0) return false;
int sum_res = 0;
for(int i = 1; i < sqrt(num); i++){
if(num % i == 0){
sum_res += i + num / i;
}
}
return sum_res == num * 2;
}
};
斐波那契数列（题目编号509：link）
class Solution {
public:
// int fib(int N) {
// if(N <= 0) return 0;
// if(N == 1) return 1;
// return fib(N - 1) + fib(N - 2);
// }
int fib(int N){
if(N <= 0) return 0;
if(N == 1) return 1;
int n1 = 0, n2 = 1, tmp;
for(int i = 2; i <= N; i++){
tmp = n1 + n2;
n1 = n2;
n2 = tmp;
}
return n2;
}
};
检测大写字母（题目编号520：link）
class Solution {
public:
bool detectCapitalUse(string word) {
if(word.length() <= 1) return true;
if(word[0] != (char)toupper(word[0])){
int i = 1;
while(i < word.size()){
if(word[i] == (char)toupper(word[i])) return false;
i++;
}
}
else{
if((word[1] != (char)toupper(word[1]))){
int i = 2;
while(i < word.size()){
if(word[i] == (char)toupper(word[i])) return false;
i++;
}
}
else{
int i = 2;
while(i < word.size()){
if(word[i] != (char)toupper(word[i])) return false;
i++;
}
}
}
return true;
}
};
最长特殊序列（题目编号521：link）
- 一定要理解题意。
- 两个字符串如果长度相等，那么判断两个字符串是否相等，如果相等，则返回-1，若不等，则返回字符串的长度。
- 如果两个字符串的长度不等，那么长的那个一定不是短的字符串的子序列，因此就可以直接认为是最长特殊序列，返回其长度即可。
class Solution {
public:
int findLUSlength(string a, string b) {
if(a.length() == b.length()){
if(a == b){
return -1;
}
else{
return a.length();
}
}
return max(a.length(), b.length());
}
};
数组中的K-diff数对（题目编号532：link）
- 先排序再快慢指针，判断两个指针指向的数字之差，如果等于k，计数器加1，left和right都往后移动，直到找到一个和当前值不同的位置，需要时刻保持right一定在left的右侧，不能重合。
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int left = 0, right = 1, cnt = 0;
while(right < nums.size()){
int diff = abs(nums[left] - nums[right]);
if(diff == k){
cnt++;
while(right < nums.size() - 1 && nums[right + 1] == nums[right]){
right++;
}
while(left < right && nums[left + 1] == nums[left]){
left++;
}
left++;
while(right <= left){
right++;
}
}
else if(diff < k){
right++;
}
else{
left++;
if(right <= left){
right++;
}
}
}
return cnt;
}
};
反转字符串II（题目编号541：link）
- 看清题意即可。
class Solution {
public:
static void my_reverse(string& s, int start, int end){
while(start < end){
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
string reverseStr(string s, int k) {
int i;
for(i = 0; i < s.length() / (2 * k); i++){
my_reverse(s, 2 * k * i, 2 * k * i + k - 1);
}
if(s.length() - 2 * k * i < k){
my_reverse(s, 2 * k * i, s.length() - 1);
}
else{
my_reverse(s, 2 * k * i, 2 * k * i + k - 1);
}
return s;
}
};
学生出勤记录I（题目编号551：link）
class Solution {
public:
bool checkRecord(string s) {
int cnt_A = 0;
for(int i = 0; i < s.length(); i++){
if(s[i] == 'A'){
cnt_A++;
if(cnt_A == 2) return false;
}
else if(i < s.length() - 2 && s[i] == 'L' && s[i + 1] == 'L' && s[i + 2] == 'L'){
return false;
}
}
return true;
}
};
反转字符串中的单词III（题目编号557：link）
- 当未发现字符串开始时，设置start = -1作为标志。
class Solution {
public:
static void my_reverse(string& s, int start, int end){
while(start < end){
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
string reverseWords(string s) {
int start = -1, end;
for(int i = 0; i < s.length(); i++){
if(s[i] == ' '){
if(start == -1){
continue;
}
end = i - 1;
my_reverse(s, start, end);
start = -1;
}
else if(start == -1){
start = i;
}
}
if(start != -1){
my_reverse(s, start, s.length() - 1);
}
return s;
}
};
N叉树的最大深度（题目编号559：link）
- 和二叉树的最大深度类似，层次遍历即可。注意queue的使用，push，front，pop，注意pop是没有返回值的，获取队列最前边元素的函数是front()。
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
#include<queue>
class Solution {
public:
int maxDepth(Node* root) {
if(root == NULL) return 0;
queue<Node*> q;
q.push(root);
int level = 0;
while(!(q.empty())){
level++;
int len = q.size();
while(len--){
Node* node = q.front();
q.pop();
for(Node* tmp: node->children){
if(tmp != NULL){
q.push(tmp);
}
}
}
}
return level;
}
};
数组拆分I（题目编号561：link）
- 排序即可，2i和2i+1组成一对。
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int res;
for(int i = 0; i < nums.size(); i++){
if(i % 2 == 0){
res += nums[i];
}
}
return res;
}
};
二叉树的坡度（题目编号563：link）
- 写一个递归求子树节点之和的函数，用一个全局变量累加所有节点的坡度。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int res = 0;
int findTilt(TreeNode* root) {
res = 0;
sumOfNodes(root);
return res;
}
int sumOfNodes(TreeNode* root){
if(root == NULL) return 0;
int left = sumOfNodes(root->left);
int right = sumOfNodes(root->right);
res += abs(left - right);
return left + right + root->val;
}
};
重塑矩阵（题目编号566：link）
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
if(nums.size() == 0) return nums;
if(nums.size() * nums[0].size() != r * c) return nums;
vector<vector<int>> res(r, vector<int>(c));
int row = 0, col = 0;
for(int i = 0; i < nums.size(); i++){
for(int j = 0; j < nums[i].size(); j++){
res[row][col] = nums[i][j];
col++;
if(col == c){
row++;
col = 0;
}
}
}
return res;
}
};
另一棵树的子树（题目编号572：link）
- 写一个函数，判断两棵树是不是一样的，递归判断s，s->left，s->right是否和t完全一样。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if(t == NULL) return true;
if(s == NULL) return false;
bool root = isSameTree(s, t);
bool left = false, right = false;
if(!root){
left = isSubtree(s->left, t);
if(!left){
right = isSubtree(s->right, t);
if(!right){
return false;
}
}
}
return true;
}
bool isSameTree(TreeNode* s, TreeNode* t){
if(s == NULL && t == NULL) return true;
if(s == NULL || t == NULL) return false;
if(s->val == t->val){
return isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
}
return false;
}
};
分糖果（题目编号575：link）
- 统计糖果的种类数和总糖果数，如果糖果数的一半大于种类数，那么所能获得的最大种类数就是全部的种类数，否则说明种类很多，只能一样拿一个，最大类别数为糖果数的一半。
#include<unordered_map>
class Solution {
public:
int distributeCandies(vector<int>& candies) {
unordered_map<int, int> candy_count;
int total_count = 0, num_type = 0;
for(int i = 0; i < candies.size(); i++){
total_count++;
if(candy_count.find(candies[i]) == candy_count.end()){
candy_count[candies[i]] = 1;
num_type++;
}
}
return min(total_count / 2, num_type);
}
};
N叉树的前序遍历（题目编号589：link）
- 注意root->children是vector，判断是否为空，应该用.empty()。
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> res;
if(root == NULL) return res;
res.push_back(root->val);
if(!(root->children.empty())){
for(Node* tmp: root->children){
for(int val: preorder(tmp)){
res.push_back(val);
}
}
}
return res;
}
};
N叉树的后序遍历（题目编号590：link）
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> res;
if(root == NULL) return res;
if(!(root->children.empty())){
for(Node* tmp: root->children){
for(int val: postorder(tmp)){
res.push_back(val);
}
}
}
res.push_back(root->val);
return res;
}
};
最长和谐子序列（题目编号594：link）
- 要看懂题意。其实就是统计每个数字出现的次数，n和n+1组成一个符合要求的序列。
#include<unordered_map>
class Solution {
public:
int findLHS(vector<int>& nums){
unordered_map<int, int> my_map;
for(int i = 0; i < nums.size(); i++){
if(my_map.find(nums[i]) != my_map.end()){
my_map[nums[i]]++;
}
else{
my_map[nums[i]] = 1;
}
}
int res = 0;
for(unordered_map<int, int>::iterator it = my_map.begin(); it != my_map.end(); it++){
int key = it->first;
if(my_map.find(key + 1) != my_map.end()){
res = max(res, my_map[key] + my_map[key + 1]);
}
}
return res;
}
// int findLHS(vector<int>& nums) {
// int res = 0;
// for(int i = 0; i < nums.size(); i++){
// int count = 0;
// bool flag = false;
// for(int j = 0; j < nums.size(); j++){
// if(nums[j] == nums[i]){
// count++;
// }
// else if(nums[j] + 1 == nums[i]){
// count++;
// flag = true;
// }
// }
// if(flag){
// res = max(res, count);
// }
// }
// return res;
// }
};
范围求和（字母编号598：link）
- 左上角的区域每次都会加1，因此答案就是找每次的正方形区域的重叠面积。
class Solution {
public:
int maxCount(int m, int n, vector<vector<int>>& ops) {
int min_row = m, min_col = n;
for(int i = 0; i < ops.size(); i++){
min_row = min(min_row, ops[i][0]);
min_col = min(min_col, ops[i][1]);
}
return min_row * min_col;
}
};
两个列表的最小索引总和（题目编号599：link）
- 用map记录每个字符串出现的最小下标，遍历两个列表共有的字符串，统计最小索引和，同时记录索引和为该最小值的字符串。注意“同时记录”，可以减少一次对map的遍历。
#include<unordered_map>
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> map1, map2;
for(int i = 0; i < list1.size(); i++){
if(map1.find(list1[i]) == map1.end()){
map1[list1[i]] = i;
}
}
for(int i = 0; i < list2.size(); i++){
if(map2.find(list2[i]) == map2.end()){
map2[list2[i]] = i;
}
}
int min_sum = list1.size() + list2.size();
vector<string> res;
for(unordered_map<string, int>::iterator it = map1.begin(); it != map1.end(); it++){
string str = it->first;
if(map2.find(str) != map2.end()){
int tmp_sum = map1[str] + map2[str];
if(tmp_sum < min_sum){
min_sum = tmp_sum;
res.clear();
res.push_back(str);
}
else if(tmp_sum == min_sum){
res.push_back(str);
}
}
}
return res;
}
};
根据二叉树创建字符串（题目编号606：link）
- 当左右子节点都为空时，不用在后面加括号了，如果左为空右不为空，要为左边加一个()。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* t, string& res){
if(t != NULL){
res += to_string(t->val);
if(t->left == NULL && t->right == NULL) return;
res += "(";
dfs(t->left, res);
res += ")";
if(t->right != NULL){
res += "(";
dfs(t->right, res);
res += ")";
}
}
}
string tree2str(TreeNode* t) {
string res;
dfs(t, res);
return res;
}
};
合并二叉树（题目编号617：link）
- 用t1作为返回值，如果两个根节点都为空，而返回空；如果都不为空，把两个节点的值叠加在第一个节点上，然后递归左右子节点，并把返回的根节点赋值给t1的left和right。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(t1 == NULL && t2 == NULL) return t1;
if(t1 != NULL && t2 != NULL){
t1->val += t2->val;
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
}
return t1 == NULL? t2: t1;
}
};
三个数的最大乘积（题目编号628：link）
- 首先要对数组排序，判断数据的范围，如果是三个正数或者三个负数，那么最大乘积就来自最大的三个数字，负数也是这样，乘积最大的是三个最接近0的负数。如果是有正有负，那么判断排序后的nums[1]是正的还是负的，如果是正数，那么这第一个负数无论绝对值多大，都不会参与乘积，如果nums[1]也是负数，那么最小的两个负数是有可能参与乘积的，最小的两个负数与最大的正数相乘，也有可能是最终的解。
class Solution {
public:
int maximumProduct(vector<int>& nums) {
if(nums.size() < 3) return 0;
sort(nums.begin(), nums.end());
int mul_last_three = 1;
for(int i = nums.size() - 3; i < nums.size(); i++){
mul_last_three *= nums[i];
}
if(nums[0] >= 0 || nums[nums.size() - 1] < 0){
return mul_last_three;
}
else if(nums[1] < 0){
int res = max(mul_last_three, nums[0] * nums[1] * nums[nums.size() - 1]);
return res;
}
return mul_last_three;
}
};
平方数之和（题目编号633：link）
- 注意c是非负整数，有可能是0，而a和b都是整数，而非正整数。需要注意c=0的特殊情况。
class Solution {
public:
bool judgeSquareSum(int c) {
for(int a = 0; a <= sqrt(c); a++){
int b = sqrt(c - a * a);
if(a * a + b * b == c) return true;
}
return false;
}
};
二叉树的层平均值（题目编号637：link）
- 注意求单个层次节点之和的sum的类型设置为double，int的话容易溢出，采用avg += (double)node->val / size_copy时又有精度的问题，也无法通过。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include<queue>
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> res;
if(root == NULL) return res;
queue<TreeNode*> q;
q.push(root);
while(q.size() > 0){
int size = q.size();
int size_copy = size;
double sum = 0;
while(size--){
TreeNode* node = q.front();
q.pop();
sum += node->val;
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(sum / size_copy);
}
return res;
}
};
子数组的最大平均数I（题目编号643：link）
- 递推连续k个元素之和，减去移出长度为k序列的那个元素，再加上新的元素即可。
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
if(k <= 0) return 0.0;
if(nums.size() < k) return 0.0;
int sum = 0, max_sum;
for(int i = 0; i < nums.size(); i++){
if(i < k){
sum += nums[i];
if(i == k - 1){
max_sum = sum;
}
}
else{
sum = sum - nums[i - k] + nums[i];
max_sum = max(max_sum, sum);
}
}
return (double) max_sum / k;
}
};
错误的集合（题目编号645：link）
- 先排序，再找连续的两个相同数字，通过数组元素之和来判断缺失的数字。
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> res;
if(nums.size() == 0) return res;
sort(nums.begin(), nums.end());
int sum = 0, repeat_num = 0;
bool found = false;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
if(!found && i > 0 && nums[i] == nums[i - 1]){
repeat_num = nums[i];
found = true;
}
}
res.push_back(repeat_num);
res.push_back((1 + nums.size()) * nums.size() / 2 - (sum - res[0]));
return res;
}
};
- 把数组中下标为pos = nums[i] - 1处的元素乘-1表示对应位置的元素pos + 1已经出现过
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> res;
if(nums.size() == 0) return res;
int repeat_num, missing_num;
for(int i = 0; i < nums.size(); i++){
int abs_pos = abs(nums[i]) - 1;
if(nums[abs_pos] < 0){
repeat_num = abs(nums[i]);
}
else{
nums[abs_pos] *= -1;
}
}
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0){
missing_num = i + 1;
}
}
res.push_back(repeat_num);
res.push_back(missing_num);
return res;
}
};
修剪二叉搜索树（题目编号669：link）
- 若当前节点的值root->val小于low，那么裁剪后的结果一定在root->right；若当前节点的值root->val大于high，那么裁剪后的结果一定在root->left；否则就是左右都要裁剪一部分，当前节点要保留，修改root->left和root->right。最后返回root。
- 二叉搜索树要再研究一下。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root == NULL) return root;
if(root->val < low){
return trimBST(root->right, low, high);
}
if(root->val > high){
return trimBST(root->left, low, high);
}
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
二叉树中第二小的节点（题目编号671：link）
- 根节点一定是整棵树的最小值。然后使用深度优先搜索遍历节点，寻找除根节点外的最小值，有些子树可以不需要继续处理。比如root->val比当前找到的除根节点外的最小值res大，那其左右子树的节点值都比res大，没必要继续搜索，可直接返回。
- 需要复习
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
if(root == NULL){
return -1;
}
int res = -1;
dfs(root, root->val, res);
return res;
}
void dfs(TreeNode* root, int min_val, int& res){
if(root == NULL || (res != -1 && root->val >= res)) return;
if(root->val != min_val){
res = root->val;
}
dfs(root->left, min_val, res);
dfs(root->right, min_val, res);
}
};
最长连续递增序列（题目编号674：link）
- 遍历数组，如果比前一个数字大，count++，否则更新最长的长度。注意数组访问完的时候，在循环外还有再更新一次。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int res = 0, count = 0;
for(int i = 0; i < nums.size(); i++){
if(i == 0){
count = 1;
}
else{
if(nums[i] > nums[i - 1]){
count++;
}
else{
res = max(res, count);
count = 1;
}
}
}
res = max(res, count);
return res;
}
};
验证回文字符串II（题目编号680：link）
- 前后双指针判断字符是否对称，当遇到不对称的时候，尝试跳过左边的字符，或跳过右边的字符，判断中间的序列是否是对称的。
class Solution {
public:
bool validPalindrome(string s) {
bool drop_letter = false;
int p = 0, q = s.size() - 1;
while(p <= q){
if(s[p] == s[q]){
p++;
q--;
}
else{
return isValid(s, p + 1, q) || isValid(s, p, q-1);
}
}
return true;
}
private:
bool isValid(string& s, int p, int q){
while(p <= q){
if(s[p] == s[q]){
p++;
q--;
}
else{
return false;
}
}
return true;
}
};
棒球比赛（题目编号682：link）
- 用一个vector记录每个有效得分，最后再相加得到总分。
- string转int，stoi函数，转long，stol，转long long，stoll。
- C++的string判断是否相等，直接用“=”。
class Solution {
public:
int calPoints(vector<string>& ops) {
vector<int> scores;
int res = 0;
for(string s: ops){
if(s == "+"){
if(scores.size() < 2) return -1;
scores.push_back(scores[scores.size() - 2] + scores[scores.size() - 1]);
}
else if(s == "D"){
if(scores.size() == 0) return -1;
scores.push_back(scores[scores.size() - 1] * 2);
}
else if(s == "C"){
if(scores.size() == 0) return -1;
scores.pop_back();
}
else{
scores.push_back(stoi(s));
}
}
for(int s: scores){
res += s;
}
return res;
}
};
最长同值路径（题目编号687：link）
- 还没搞明白
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int longestUnivaluePath(TreeNode* root) {
int res = 0;
longestPath(root, res);
return res;
}
private:
int longestPath(TreeNode* root, int& res){
if(root == NULL) return 0;
int left_length = longestPath(root->left, res);
int right_length = longestPath(root->right, res);
int left_row = 0, right_row = 0;
if(root->left && root->left->val == root->val){
left_row = left_length + 1;
}
if(root->right && root->right->val == root->val){
right_row = right_length + 1;
}
res = max(res, left_row + right_row);
return max(left_row, right_row);
}
};
员工的重要性（题目编号690：link）
- bfs遍历。
/*
// Definition for Employee.
class Employee {
public:
int id;
int importance;
vector<int> subordinates;
};
*/
#include<queue>
#include<unordered_map>
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
if(employees.size() == 0) return 0;
queue<int> q;
unordered_map<int, int> importance_map;
unordered_map<int, vector<int>> employee_map;
for(int i = 0; i < employees.size(); i++){
importance_map[employees[i]->id] = employees[i]->importance;
employee_map[employees[i]->id] = employees[i]->subordinates;
}
int sum = 0;
if(employee_map.find(id) != employee_map.end()){
q.push(id);
while(q.size() > 0){
int t_id = q.front();
q.pop();
sum += importance_map[t_id];
for(int i = 0; i < employee_map[t_id].size(); i++){
q.push(employee_map[t_id][i]);
}
}
}
return sum;
}
};
交替位二进制数（题目编号693：link）
class Solution {
public:
bool hasAlternatingBits(int n) {
int last_digit = n % 2;
n /= 2;
int tmp;
while(n != 0){
tmp = n % 2;
if(tmp + last_digit != 1) return 0;
n /= 2;
last_digit = tmp;
}
return true;
}
};
计数二进制子串（题目编号696：link）
- 思路很奇妙，将字符串划分为连续相同字符的片段，统计每段的长度，第i段和第i+1段长度的最小值是这两段组成的子串的数量。==
class Solution {
public:
int countBinarySubstrings(string s) {
vector<int> vec_count;
int count = 0;
char cur;
for(int i = 0; i < s.length(); i++){
if(count == 0){
count = 1;
cur = s[i];
}
else{
if(s[i] == cur){
count++;
}
else{
vec_count.push_back(count);
count = 1;
cur = s[i];
}
}
}
vec_count.push_back(count);
int res = 0;
for(int i = 0; i < vec_count.size() - 1; i++){
res += min(vec_count[i], vec_count[i+1]);
}
return res;
}
};
版权声明：本文为leogo17原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。