50. Pow(x, n) https://leetcode-cn.com/problems/powx-n/

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

说明:

-100.0 < x < 100.0

n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解：

直接调库函数，不过面试中肯定不可以。

暴力，写个循环直接乘，O(N)。

分治，y = x**(n/2)。 n是偶数，两部分一样只计算一边即可，res = y*y。n为奇数，res = y*x*y。一直这样算到x**1 或 x**0。时间复杂度为O(logN)。

递归实现

class Solution:
def myPow(self, x: float, n: int) -> float:
if not n:
return 1
if n < 0:
return 1 / self.myPow(x, -n)
if n % 2:
return x * self.myPow(x, n-1) # n为奇数，通过n-1次方去做
return self.myPow(x*x, n/2) # n为偶数

迭代实现，分治的最小计算乘子为x。 例如，x**(7) = x * x**(6) = x * (x**2)**(3) =  x * (x**2) * ((x**2)**2)**1

class Solution:
def myPow(self, x: float, n: int) -> float:
if not n:
return 1
if n < 0: # n小于0的话就转化成n大于0的形式，把x变为1/x即可
x = 1/x
n = -n

    res = 1  
    while n:   # 分治的最小单位是1次方  
        if n & 1:   # n 为奇数，先乘多出来的一个x  
            res \*= x  
        x \*= x  # 基本乘子从x变为x\*\*2  
        n >>= 1  # n = floor(n/2)  
    return res

169. 求众数  https://leetcode-cn.com/problems/majority-element/

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

解：

暴力，两层嵌套循环，枚举所有x，针对某一个x去数组里面计数。O(N2)

直接排序后取中间元素，肯定是众数。O(NlogN)

class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
return nums[int((n-1)/2)]

遍历一次，用hashmap存元素计数，最后再去map里面看一下计数最大的元素是哪个。O(N)

class Solution:
def majorityElement(self, nums: List[int]) -> int:
count = dict()
for x in nums:
count[x] = count.get(x, 0) + 1

    max\_count = 0  
    for key, value in count.items():  
        if value > max\_count:  
            max\_count = value  
            res = key  
    return res   # 或者直接利用字典的get函数，一行就可以 return max(count, key=count.get)

分治递归求解，直到所有的子问题都是长度为 1 的数组。由于传输子数组需要额外的时间和空间，所以我们实际上只传输子区间的左右指针 low 和 high 表示相应区间的左右下标。

　　长度为 1 的子数组中唯一的数显然是众数，直接返回即可。

　　如果回溯后某区间的长度大于 1 ，必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

　　原问题的答案就是下标为 0 和 n 之间的众数这一子问题。

时间复杂度为O(NlogN)

class Solution:
def majorityElement(self, nums: List[int]) -> int:
return self.helper(nums, 0, len(nums)-1)

def helper(self, nums, low, high):  
    if low == high:  # 长度为1的子数组，众数就是那唯一的元素  
        return nums\[low\]

    # 子数组长度大于1，递归的去找左右数组的众数  
    mid = low + (high - low) // 2  
    left = self.helper(nums, low, mid)  
    right = self.helper(nums, mid+1, high)

    if left == right:  # 判断左右两个众数的关系，如果左右众数相同，那一定是左右总体的众数  
        return left  

    # 如果不相同，总体上count大的那个是整体的众数  
    left\_count, right\_count = 0, 0  
    for i in range(low, high+1):  
        if nums\[i\] == left:  
            left\_count += 1  
        elif nums\[i\] == right:  
            right\_count += 1

    return left if left\_count > right\_count else right

53. 最大子序和 https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解：

动态规划，对数组进行遍历，当前最大连续子序列和为sum，结果为ans。如果sum>0，说明前面的子序列对整体有增益，保留；否则前面的子序列不要，只保留当前的遍历数。每次比较sum和ans大小，ans取最大值。O(N)

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0

    res = nums\[0\]  
    sum\_ = 0  
    for i in range(len(nums)):  
        if sum\_ > 0:  
            sum\_ += nums\[i\]  
        else:  
            sum\_ = nums\[i\]  
        if sum\_ > res:  
            res = sum\_  
    return res

分治，和最大的子序列要么在左半边，要么在右半边，要么跨过左右。在左右两边的情况直接递归求解，在中间的情况，子序列连续且跨越mid点，说明在左右两边都是连续的，分别自右向左、自右向左找最大连续子序列。O(N*logN)

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]

    n = len(nums)

    # 分别计算左右两边的最大子序列和  
    mid = (n-1) // 2  
    left = self.maxSubArray(nums\[: mid+1\])  
    right = self.maxSubArray(nums\[mid+1:\])

    # 计算跨越左右两边的情况，即从右向左计算左边的最大子序列和，再从左向右计算右边的最大子序列和，相加即可  
    medium\_l = nums\[mid\]  
    tmp = 0  
    for i in range(mid, -1, -1):  
        tmp += nums\[i\]  
        medium\_l = max(medium\_l, tmp)

    medium\_r = nums\[mid+1\]  
    tmp = 0  
    for i in range(mid+1, n):  
        tmp += nums\[i\]  
        medium\_r = max(medium\_r, tmp)

    medium = medium\_l + medium\_r

    return max(left, right, medium)  # 返回三种情况中的最大值，就是当前数组中的最大子序列和

438. 找到字符串中所有字母的异位词  https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

解：

暴力，枚举每个可能的子串起始索引，再直接判断是否为异位词，O(N*K)

滑动窗口+哈希表，还是哈希表来存p的字符，枚举每个可能的子串起始索引，用哈希表判断，O(N)

class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
if not s:
return []

    def build\_map(p):  
        aph\_map = dict()  
        for c in p:  
            aph\_map\[c\] = aph\_map.get(c, 0) + 1  
        return aph\_map

    p\_map = build\_map(p)

    s = list(s)  
    n, k = len(s), len(p)

    base\_map = build\_map(s\[:k\])  # 遍历的过程中每次走一个元素又来一个元素，始终维护这个hashmap  
    res = \[\]

    for i in range(n-k+1):  
        if base\_map == p\_map:  
            res.append(i)  
        if i != n-k:  
            # s\[i\] 退出去  
            tmp = base\_map.get(s\[i\])-1  
            if tmp:  
                base\_map\[s\[i\]\] = tmp  
            else:  
                base\_map.pop(s\[i\])  
            base\_map\[s\[i+k\]\] = base\_map.get(s\[i+k\], 0) + 1  # s\[i+k\] 进来

    return res

437. 路径总和iii https://leetcode-cn.com/problems/path-sum-iii/

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

解：

注意这道题路径的起点和终点都可以是任意的，所以在dfs的时候不好直接计数，还是要在遍历到某个节点node的时候把之前所有可能的路径和作为一个list传进来，新的路径和就包括原先的路径和加上node.val，以及从node开始的新路径、和为node.val。然后左右节点dfs即可。

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if root is None:
return 0

    # sums为node的父节点已能构成的和，返回最长可延伸到node结束的所有路径所能构成的和列表  
    def dfs(node, sums):  
        left = right = 0  # 左右的值默认为0

        # 算上node以后，可能的路径和包括，之前的和加当前结点值能构成的新和，以及从当前结点开始算的新和  
        tmp = \[num + node.val for num in sums\] + \[node.val\]

        if node.left:  
            left = dfs(node.left, tmp)  # 左右子树dfs搜索

        if node.right:  
            right = dfs(node.right, tmp) 

        return tmp.count(sum) + left + right  

    return dfs(root, \[\])

设计一个比较好的递归函数。双递归。

pathSum函数，给定一个节点和目标值，返回以这个节点为根的树中，和为目标值的路径总数。

count函数，给定一个节点和目标值，返回这个节点为根的树中，以这个节点为路径开头，和为目标值的路径总数。

# Definition for a binary tree node.

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if root is None:
return 0
return self.count(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum) # root中路径数=以root开头的路径数+不以root开头的路径数

def count(self, node, sum):  
    if node is None:  
        return 0  
    tmp = 0  
    if node.val == sum:  
        tmp += 1  
    tmp += self.count(node.left, sum - node.val) + self.count(node.right, sum - node.val)  
    return tmp

4. 寻找两个有序数组的中位数 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解：

先不考虑时间复杂度要求，双指针遍历的做法。维护一个数组res存放到中位数mid和后一个数mid+1，如果中位数是一个数，返回res[-2]；如果需要除以2，返回(res[-1]+res[-2])/2。比较烦人的是要注意一个nums为空的情况，以及判断好是否需要向res中添加元素的条件。

class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if not nums1 and not nums2:
return 0.
elif not nums1:
n = len(nums2)
return float(nums2[n//2]) if n%2 != 0 else (nums2[(n//2)-1]+nums2[(n//2)])/2
elif not nums2:
n = len(nums1)
return float(nums1[n//2]) if n%2 != 0 else (nums1[(n//2)-1]+nums1[(n//2)])/2

    m, n = len(nums1), len(nums2)  
    target\_len = (m+n)//2 + 1 if (m+n) % 2 == 0 else (m+n)//2 + 2  
    i, j = 0, 0  
    res = \[\]  
    while i < m and j < n:  
        if nums1\[i\] < nums2\[j\]:  
            res.append(nums1\[i\])  
            i += 1  
        else:  
            res.append(nums2\[j\])  
            j += 1  
        if len(res) == target\_len:  
            break

    if i < m:  
        while i < m:  
            if len(res) == target\_len:  
                break  
            res.append(nums1\[i\])  
            i += 1

    if j < n:  
        while j < n:  
            if len(res) == target\_len:  
                break  
            res.append(nums2\[j\])  
            j += 1

    if (m+n) % 2 == 0:  
        return (res\[-1\]+res\[-2\])/2  
    return float(res\[-2\])

要找到中位数的话就是要把A和B在某个位置i和j切分成两部分，left_A和left_B共同构成left，right_A和right_B共同构成right，只要left和right长度相等且max(left) <= min(right)，那么中位数就等于( max(left) + min(right) )/2。如何找边界值，可以用二分法，先确定 num1 取 m1 个数的左半边，那么 num2 取 m2 = (m+n+1)/2 - m1 的左半边，找到合适的 m1，就用二分法找。

当 [ [a1],[b1,b2,b3] | [a2,..an],[b4,…bn] ]

只需要比较 b3 和 a2 的关系的大小，就可以知道这种分法是不是准确的

例如：nums1 = [-1,1,3,5,7,9]，nums2 =[2,4,6,8,10,12,14,16]

当 m1 = 4, m2 = 3，它的中位数就是median = (num1[m1] + num2[m2])/2

class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1, n2 = len(nums1), len(nums2)
if n1 > n2:
nums1, nums2, n1, n2 = nums2, nums1, n2, n1 # 保证 n2 >= n1，便于判断边界

    k = (n1 + n2 + 1) // 2  # 令left和right两部分长度相同的全局切分位置  
    left = 0  
    right = n1-1  
    while left <= right:  # 二分的在nums1中找到一个位置m1，使得 nums1\[m1\] == nums2\[k-m1-1\]  
        m1 = left + (right - left) // 2  
        m2 = k - m1  
        if nums1\[m1\] < nums2\[m2-1\]:  
            left = m1 + 1  
        else:  
            right = m1 - 1 

    m1 = left   # 如果不存在相等的数，nums1\[left\]也是第一个大于nums\[k-left\]的数或者left=n1  
    m2 = k - m1 

    c1 = max(nums1\[m1-1\] if m1 > 0 else float("-inf"), nums2\[m2-1\] if m2 > 0 else float("-inf") )

    if (n1 + n2) % 2 == 1:  
        return c1

    c2 = min(nums1\[m1\] if m1 < n1 else float("inf"), nums2\[m2\] if m2 <n2 else float("inf"))  
    return (c1 + c2) / 2