2019 算法面试相关(leetcode)--递归与分治

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

一、 Pow(x, n)

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2^-2 = 1/2² = 1/4 = 0.25

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1] 。

---

1、比较容易想的就是循环累乘

var myPow = function(x, n) {
    
    let res = 1
    
    if(n < 0){
        
        x = 1/x
        
        n = -n
    }
    
    if(x == 1) return 1
    
    if(x == -1) return n%2 ? -1 : 1

    for(let i = 0; i < n; i++){
        
        res *= x
    }

    return res
};

效率并不理想，甚至会超时。
2、我们可以尝试用分治+递归算法
xⁿ = x^(n/2) * x^(n/2)

var myPow = function(x, n) {
    
    if(n == 0 || x == 1) return 1
    
    if(n < 0) return 1/myPow(x,-n)
    
    if(n % 2) return x*myPow(x,n - 1)
    
    return myPow(x*x,Math.floor(n/2))
};

3、那么能不能不用递归呢？只用分治算法

var myPow = function(x, n) {

    if(n < 0){

        x = 1.0/x

        n = -n
    }

    let res = 1

    while(n){

        if(n%2) res *= x

        x *= x

        n = Math.floor(n/2)
    }

    return res
};

二、 求众数

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

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

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

---

同样是有多种解法
1、首先是暴力法，就是两层嵌套，效率是O(n²),效率很低，这里不再赘述。
2、我们注意到，题目中有假设数组总是存在众数
那么可以用排序法,那么数组中间那个数就一定是众数

var majorityElement = function(nums) {
    
    nums.sort((a,b) => a - b)

    return nums[Math.floor(nums.length/2)]
};

排序时间复杂度是O(nlogn),而且还会改变数组，这方法并不推荐
3、既然是计数，那么很容易想到哈希表去计数。

var majorityElement = function(nums) {
    
    let dic = {}

    for (const num of nums) {
     
        dic[num] = (dic[num] || 0) + 1

        if(dic[num] > nums.length/2) return num
    }
};

这种算法时间复杂度是O(n),但因为引入了哈希表，空间复杂度也是O(n)

4、摩尔投票法。既然数组一定存在众数，假设数组存在m个数字，众数存在n个，n > m/2。那么如果数组去掉一个众数，再去掉一个其他数字，众数数目为n - 1,数组数目为m - 2，n - 1 > (m - 2)/2，还是会存在众数。同样，如果我们去掉k个众数，同时去掉k个其余数字，剩下的数组还是会存在同样的众数。

var majorityElement = function(nums) {
    
    let count = 1,res = nums[0]

    for(let i = 1; i < nums.length; i++){
        
        if(nums[i] == res) count++

        else {

            count -- 

            if(count == 0){

                res = nums[i]
    
                count++
            } 
        }
    }
    
    return res
};

该算法同样用到了分治思想，时间复杂度O(n),空间复杂度O(1)