茉莉Python

voidqueens@hotmail.com

0%

一、股票买卖系列

for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 择优(选择1,选择2...)

每天都有三种「选择」:买入、卖出、无操作,我们用 buy, sell, rest 表示这三种选择。

问题是,并不是每天都可以任意选择这三种选择的,因为 sell 必须在 buy 之后,buy 必须在 sell 之后(第一次除外)。那么 rest 操作还应该分两种状态,一种是 buy 之后的 rest(持有了股票),一种是 sell 之后的 rest(没有持有股票)。而且别忘了,我们还有交易次数 k 的限制,就是说你 buy 还只能在 k > 0 的前提下操作。

问题的「状态」有三个,第一个是天数,第二个是当天允许交易的最大次数,第三个是当前的持有状态(即之前说的 rest 的状态,我们不妨用 1 表示持有,0 表示没有持有)。

穷举:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp5.jpg

dp[3][2][1]:今天是第三天,我现在手上持有着股票,至今最多进行 2 次交易。

dp[2][3][0] 的含义:今天是第二天,我现在手上没有持有股票,至今最多进行 3 次交易。

最终所求:dp[n - 1][K][0],即最后一天,最多允许 K 次交易,所能获取的最大利润。

为什么不是 dp[n - 1][K][1]?因为 [1] 代表手上还持有股票,[0] 表示手上的股票已经卖出去了,很显然后者得到的利润一定大于前者。

状态转移:
https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp6.jpg

状态转移方程:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp7.jpg

bad case:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp8.jpg

总结:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp9.jpg

121. 买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题解一|暴力破解:

时间复杂度:O(n^2)
空间复杂度:O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit=0
        for i in range(len(prices)-1):
            for j in range(i+1,len(prices)):
                if prices[j]-prices[i] > profit:
                    profit=prices[j]-prices[i]           
        return profit

题解二:

时间复杂度:O(n)
空间复杂度:O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice=float('inf')
        profit=0
        for i in range(len(prices)):
            if prices[i] < minPrice:
                minPrice=prices[i]
            elif prices[i]-minPrice > profit :
                profit=prices[i]-minPrice
        return profit    

题解三:

时间复杂度:O(n)
空间复杂度:O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        profit=0
        tmp=prices[0]
        for i in range(1,len(prices)):
            tmp=min(tmp,prices[i])
            profit=max(profit,prices[i]-tmp)
        return profit

题解四|万能公式:

思路:
K=1

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp10.jpg

时间复杂度:O(n)
空间复杂度:O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp=[[0]*2 for i in range(n)]
        for i in range(n):
            if i-1==-1:
                dp[i][0]=0
                # dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
                          =max(dp[-1][0],dp[-1][1]+prices[i])
                          =max(0,-float('inf')+prices[i])
                          =0
                dp[i][1]=-prices[i]
                # dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
                          =max(dp[-1][1],dp[-1][0]-prices)
                          =max(-float('inf'),0-prices)
                          =-prices
                continue
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1], -prices[i])
        # print(dp)
        return dp[n-1][0] 

时间复杂度:O(n)
空间复杂度:O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp_i_0=0  # dp[-1][0]=0
        dp_i_1=-float('inf') # dp[-1][1]=-float('inf')
        for i in range(n):
            dp_i_0=max(dp_i_0,dp_i_1+prices[i])
            dp_i_1=max(dp_i_1,-prices[i])
        return dp_i_0
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        n = len(prices)
        dp = [[0,0] for _ in range(n)]
        dp[-1][0] = 0
        dp[-1][1] = - float('inf')
        dp[0][0] = 0
        dp[0][1] = - float('inf')
        for i in range(n):
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]+ prices[i]) 
            dp[i][1] = max(dp[i-1][1],- prices[i])
        return dp[-1][0]

122. 买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

思路:
K=+infinity

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp11.jpg

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp=[[0]*2 for i in range(n)]
        dp[-1][0]=0
        dp[-1][1]=-float('inf')
        dp[0][0]=0
        dp[0][1]=-float('inf')
        for i in range(n):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
        return dp[n-1][0]

时间复杂度:O(n)
空间复杂度:O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp_i_0=0
        dp_i_1=-float('inf')
        for i in range(n):
            tmp=dp_i_0
            dp_i_0=max(dp_i_0,dp_i_1+prices[i])
            dp_i_1=max(dp_i_1,tmp-prices[i])
        return dp_i_0

309. 最佳买卖股票时机含冷冻期

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

思路:
K=+infinity with cooldown
每次sell后要等一天才能继续交易;

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp12.jpg

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n=len(prices)
        if n == 0 or n==1:
            return 0
        dp=[[0]*2 for i in range(n)]
        dp[-1][0]=0
        dp[-1][1]=-float('inf')
        dp[-2][0]=0 # 不要这个初始值也可以,前面已经初始化。
        dp[0][0]=0
        dp[0][1]=-float('inf')
        for i in range(n):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i])
        return dp[n-1][0]
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        if len(prices) == 1: return 0
        n = len(prices)
        dp = [[0 for i in range(2)] for _ in range(n)]
        dp[-1][1] = -float('inf')
        dp[-2][1] = -float('inf')
        dp[0][1] = -float('inf')
        for i in range(n):
            dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1],dp[i-2][0] - prices[i])
        return dp[-1][0]
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        if len(prices) == 1: return 0
        n = len(prices)
        dp_i_0=0
        dp_i_1=-float('inf')
        dp_pre_0=0 # 代表dp[i-2][0]
        for i in range(n):
            tmp=dp_i_0
            dp_i_0=max(dp_i_0,dp_i_1+prices[i])
            dp_i_1=max(dp_i_1,dp_pre_0-prices[i])
            dp_pre_0=tmp
        return dp_i_0

714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

示例 1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

思路:

K=+infinity with fee
每次交易要支付手续费,只要把手续费从利润中减去即可;

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp13.jpg

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp=[[0]*2 for i in range(n)]
        dp[-1][0]=0
        dp[-1][1]=-float('inf')
        dp[0][0]=0
        dp[0][1]=-float('inf')
        for i in range(n):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]-fee)
        return dp[n-1][0]
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp_i_0=0
        dp_i_1=-float('inf')
        for i in range(n):
            tmp=dp_i_0
            dp_i_0=max(dp_i_0,dp_i_1+prices[i])
            dp_i_1=max(dp_i_1,tmp-prices[i]-fee)
        return dp_i_0

123. 买卖股票的最佳时机 III

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
     随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。   
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

思路:

K=2

k = 2 和前面题目的情况稍微不同,因为上面的情况都和 k 的关系不太大。要么 k 是正无穷,状态转移和 k 没关系了;要么 k = 1,跟 k = 0 这个 base case 挨得近,最后也被消掉了。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp14.jpg

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        dp=[[[0]*2 for i in range(3)] for i in range(n)]
        for k in range(3):
            dp[0][k][1]=-float('inf')
            dp[-1][k][1]=-float('inf')
        for i in range(n):
            for k in range(1,3):
                dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
                dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
        return dp[n-1][2][0]

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/dp15jpg

188. 买卖股票的最佳时机 IV

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

思路:

K=any integer

这题和 k = 2 没啥区别,可以直接套上一题的第一个解法。但是提交之后会出现一个超内存的错误,原来是传入的 k 值可以任意大,导致 dp 数组太大了。现在想想,交易次数 k 最多能有多大呢?

一次交易由买入和卖出构成,至少需要两天。所以说有效的限制次数 k 应该不超过 n/2,如果超过,就没有约束作用了,相当于 k = +infinity。这种情况是之前解决过的。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0
        n=len(prices)
        if k >= n//2:
            res=0
            for i in range(1,n):
                if prices[i] > prices[i-1]:
                    res += prices[i] - prices[i-1]
            return res
        else:
            dp=[[[0]*2 for i in range(k+1)] for i in range(n)]
            for t in range(k+1):
                dp[0][t][1]=-float('inf')
                dp[-1][t][1]=-float('inf')
            for i in range(n):
                for t in range(1,k+1):
                    dp[i][t][0]=max(dp[i-1][t][0],dp[i-1][t][1]+prices[i])
                    dp[i][t][1]=max(dp[i-1][t][1],dp[i-1][t-1][0]-prices[i])
            return dp[n-1][k][0]

原文:https://mp.weixin.qq.com/s/M1KfTfNlu4OCK8i9PSAmug

一、二分查找框架

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

技巧:

不要出现 else,而是把所有情况用 else if 写清楚,这样可以清楚地展现所有细节;

计算 mid 时需要防止溢出,代码中left + (right - left) / 2就和(left + right) / 2的结果相同,但是有效防止了left和right太大直接相加导致溢出。

二、寻找一个数

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

1、为什么while 循环的条件中是 <=,而不是 < ?

因为初始化right的赋值是nums.length - 1,即最后一个元素的索引,而不是nums.length。

三、寻找左侧边界的二分搜索

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

1、为什么 while 中是<而不是<=?

答:用相同的方法分析,因为right = nums.length而不是nums.length - 1。因此每次循环的「搜索区间」是[left, right)左闭右开。

while(left < right)终止的条件是left == right,此时搜索区间[left, left)为空,所以可以正确终止。

2、为什么没有返回 -1 的操作?如果nums中不存在target这个值,怎么办?

改写:

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

四、寻找右侧边界的二分查找

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

五、逻辑统一

第一个,最基本的二分查找算法:

因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回

第二个,寻找左侧边界的二分查找:

因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid

因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界

第三个,寻找右侧边界的二分查找:

因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid

因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right,必须减一

对于寻找左右边界的二分搜索,常见的手法是使用左闭右开的「搜索区间」,我们还根据逻辑将「搜索区间」全都统一成了两端都闭,便于记忆,只要修改两处即可变化出三种写法:

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回,锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}


int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回,锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}


title: 数据结构与算法-3-BFS和DFS
date: 2020-06-05 14:38:46
tags: 数据结构与算法
categories:
- 数据结构与算法

一、综述

BFS 和 DFS 的最主要的区别是:BFS 找到的路径一定是最短的,但代价就是空间复杂度比 DFS大很多。

二、BFS

1、常见场景

问题的本质就是让你在一幅「图」中找到从起点start到终点target的最近距离。

2、框架

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点:这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点:更新步数在这里 */
        step++;
    }
}

python模版:

# 计算从起点 start 到终点 target 的最近距离
from collections import deque
def BFS(start,target):
    queue=deque([n]) # 核心数据结构,将起点加入队列
    visited=set()  # 避免走回头路
    step=0 # 记录扩散的步数
    while queue:
        size=len(queue)
        # 将当前队列中的所有节点向四周扩散
        for i in range(size):
            cur=queue.pop()
            if cur == target: # 这里判断是否到达终点 
                return step
            for j in range(cur.XXX): # 将 cur 的相邻节点加入队列 
                if j not in visited:
                    queue.appendleft(j)
                    visited.add(j)
        step+=1 # 更新步数在这里

3、例子

111. 二叉树的最小深度
from collections import deque
def minDepth(root):
    if not root:
        return 0
    queue=deque([root])
    depth=1
    while queue:
        size=len(queue)
        for i in range(size):
            cur=queue.pop()
            if not cur.left and not cur.right:
                return depth
            if cur.left:
                queue.appendleft(cur.left)
            if cur.right:
                queue.appendleft(cur.right)
        depth+=1
    return depth
279. 完全平方数
from collections import deque
class Solution:
    def numSquares(self, n: int) -> int:
        if n==0:
            return 0
        queue=deque([n])
        visited=set()
        step=0
        while queue:
            step+=1
            length=len(queue)
            for _ in range(length):
                tmp=queue.pop()
                for j in range(1,int(tmp**0.5)+1):
                    node=tmp-j**2
                    if node==0:
                        return step
                    if node not in visited:
                        queue.appendleft(node)
                        visited.add(node)
        return step

112.路径总和

链接:https://leetcode-cn.com/problems/path-sum/

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

题解一|递归:

时间复杂度:我们访问每个节点一次,时间复杂度为 O(N) ,其中 N 是节点个数。
空间复杂度:最坏情况下,整棵树是非平衡的,例如每个节点都只有一个孩子,递归会调用 N 次(树的高度),因此栈的空间开销是 O(N) 。但在最好情况下,树是完全平衡的,高度只有 log(N),因此在这种情况下空间复杂度只有 O(log(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 hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        sum-=root.val # 不能交换顺序
        if not root.left and not root.right:
            return sum==0
        return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)

题解二|迭代:

时间复杂度:和递归方法相同是 O(N)。
空间复杂度:当树不平衡的最坏情况下是 O(N) 。在最好情况(树是平衡的)下是 O(logN)。

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False

        stack=[(root,sum-root.val)]
        while stack:
            node,curr=stack.pop()
            if not node.left and not node.right and curr==0:
                return True
            if node.left: 
                stack.append((node.left,curr-node.left.val))
            if node.right:
                stack.append((node.right,curr-node.right.val))
        return False

113. 路径总和 II

链接:https://leetcode-cn.com/problems/path-sum-ii/

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

题解一|递归:

# 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) -> List[List[int]]:
        paths=[]
        def helper(root,sum,path=[]):
            if not root:
                return
            if not root.left and not root.right and sum-root.val==0:
                path+=[root.val]
                paths.append(path)

            helper(root.left,sum-root.val,path+[root.val])
            helper(root.right,sum-root.val,path+[root.val])
        helper(root,sum)
        return paths
# 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) -> List[List[int]]:
        res=[]
        def helper(root,sum,path):
            if not root:
                return
            if not root.left and not root.right and sum-root.val==0:
                path+=[root.val]
                res.append(path)
            sum-=root.val
            helper(root.left,sum,path+[root.val])
            helper(root.right,sum,path+[root.val])
        helper(root,sum,[])
        return res

?题解二|迭代|超时:

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if not root:
            return []
        res=[]
        stack=[(root,[root.val])]
        while stack:
            node,curr=stack.pop()
            if not node.left and not node.right and sum(curr)==sum:
                res.append(curr)
            if node.left:
                stack.append((root.left,curr+[root.left.val]))
            if node.right:
                stack.append((root.right,curr+[root.right.val]))
        return res

437. 路径总和 III

链接:https://leetcode-cn.com/problems/path-sum-iii/

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

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

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

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

示例:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

题解一|递归:

# 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:
        def helper(root,sum):
            if not root:
                return 0
            res=0
            if sum-root.val == 0:
                res+=1
            res+=helper(root.left,sum-root.val)
            res+=helper(root.right,sum-root.val)
            return res

        if not root:
            return 0
        return helper(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)

面试题 04.10. 检查子树

链接:https://leetcode-cn.com/problems/check-subtree-lcci/

检查子树。你有两棵非常大的二叉树:T1,有几万个节点;T2,有几万个节点。设计一个算法,判断 T2 是否为 T1 的子树。

如果 T1 有这么一个节点 n,其子树与 T2 一模一样,则 T2 为 T1 的子树,也就是说,从节点 n 处把树砍断,得到的树与 T2 完全相同。

示例1:

 输入:t1 = [1, 2, 3], t2 = [2]
 输出:true
示例2:

 输入:t1 = [1, null, 2, 4], t2 = [3, 2]
 输出:false
提示:

树的节点数目范围为[0, 20000]。

题解一|递归:

一:在 t1 中找到 t2 的起点。先判断 t1 当前节点,如果不对就判断 t1 左子树和 t1 右子树。
二:从找到的起点开始判断剩下的点,t1 和 t2 同步左右子树搜索。
class Solution:
    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:

        def helper(t1,t2):
            if not t2:
                return True
            elif not t1 and t2:
                return False
            elif t1.val != t2.val:
                return False
            else:
                return helper(t1.left,t2.left) and helper(t1.right,t2.right)

        if not  t1:
            return False
        if not t2:
            return True
        return helper(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)
class Solution:
    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
        if not  t1:
            return False
        if not t2:
            return True
        return self.helper(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)

    def helper(self,t1,t2):
        if not t2:
            return True
        elif not t1 and t2:
            return False
        elif t1.val != t2.val:
            return False
        else:
            return self.helper(t1.left,t2.left) and self.helper(t1.right,t2.right)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:
            return False
        return self.helper(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

    def helper(self,A,B):
        if not A and B:
            return False
        elif not B:
            return True
        elif A.val != B.val:
            return False
        else:
            return self.helper(A.left,B.left) and self.helper(A.right,B.right)
class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def helper(A,B):
            if not B:
                return True
            if not A or (A.val != B.val):
                return False
            return helper(A.left,B.left) and helper(A.right,B.right)
        return bool(A and B) and (helper(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))

面试题 17.12. BiNode

链接:https://leetcode-cn.com/problems/binode-lcci/

二叉树数据结构TreeNode可用来表示单向链表(其中left置空,right为下一个链表节点)。实现一个方法,把二叉搜索树转换为单向链表,要求值的顺序保持不变,转换操作应是原址的,也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意:本题相对原题稍作改动

示例:

输入: [4,2,5,1,3,null,6,0]
输出: [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示:

节点数量不会超过 100000。

题解一|迭代|中序遍历:

root.left=None
pre.right=root
pre=root
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def convertBiNode(self, root: TreeNode) -> TreeNode:
        head=TreeNode(0)
        pre=head
        stack=[]
        while stack or root:
            if root:
                stack.append(root)
                root=root.left
            else:
                root=stack.pop()

                root.left=None
                pre.right=root
                pre=root

                root=root.right
        return head.right

题解二|递归:

class Solution:
    def convertBiNode(self, root: TreeNode) -> TreeNode:
        head=TreeNode(0)
        self.helper(root,head)
        return head.right

    def helper(self,root,pre):
        if root:
            pre=self.helper(root.left,pre)
            root.left=None
            pre.right=root
            pre=root
            pre=self.helper(root.right,pre)
        return pre
class Solution:
    def convertBiNode(self, root: TreeNode) -> TreeNode:
        head=TreeNode(0)
        self.pre=head
        self.helper(root)
        return head.right

    def helper(self,root):
        if not root:
            return
        self.helper(root.left)

        root.left=None
        self.pre.right=root
        self.pre=root

        self.helper(root.right)

面试题 04.12. 求和路径

链接:https://leetcode-cn.com/problems/paths-with-sum-lcci/

给定一棵二叉树,其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法,打印节点数值总和等于某个给定值的所有路径的数量。注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。

示例:
给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

3
解释:和为 22 的路径有:[5,4,11,2], [5,8,4,5], [4,11,7]
提示:

节点总数 <= 10000

题解一|递归:

# 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 not root:
            return 0
        return self.helper(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)

    def helper(self,root,sum):
        count=0
        if not root:
            return 0
        if sum-root.val==0:
            count+=1
        count+=self.helper(root.left,sum-root.val)
        count+=self.helper(root.right,sum-root.val)
        return count

面试题54. 二叉搜索树的第k大节点

链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

给定一棵二叉搜索树,请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

限制:

1 ≤ k ≤ 二叉搜索树元素个数

注意:和二叉搜索树的第k小节点的区别。

题解一|迭代:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root:
            return 0
        stack=[]
        while stack or root:
            if root:
                stack.append(root)
                root=root.right
            else:
                root=stack.pop()
                k-=1
                if k==0:
                    return root.val
                root=root.left

题解二|递归:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.k=k
        self.res=0
        self.helper(root)
        return self.res
    def helper(self,root):
        if not root:
            return 0
        self.helper(root.right)
        if self.k==0: return # ??提高性能,提前返回。
        self.k-=1        
        if self.k==0:
            self.res=root.val # 直接return不行,需要存入全局变量中
        self.helper(root.left)
        return self.res
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.k=k
        self.res=0
        self.helper(root)
        return self.res
    def helper(self,root):
        if not root or self.k == 0:
            return 0
        self.helper(root.right)
        self.k-=1        
        if self.k==0:
            self.res=root.val # 直接return不行,需要存入全局变量中
        self.helper(root.left)
        return self.res

面试题55 - I. 二叉树的深度

链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

例如:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

提示:节点总数 <= 10000

题解一(递归):

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left=self.maxDepth(root.left)
        right=self.maxDepth(root.right)
        return max(left,right)+1

题解二(迭代):

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack=[root]
        depth=0
        while stack:
            tmp=[]
            for i in range(len(stack)):
                root=stack.pop() 
                if root.left:
                    tmp.append(root.left)
                if root.right:
                    tmp.append(root.right)
            stack=tmp
            depth+=1
        return depth
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack=[root]
        depth=0
        while stack:
            tmp=[]
            for root in stack:
                if root.left:
                    tmp.append(root.left)
                if root.right:
                    tmp.append(root.right)
            stack=tmp
            depth+=1
        return depth

面试题55 - II. 平衡二叉树

链接:https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

限制:1 <= 树的结点个数 <= 10000

题解一(递归):

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        return abs(self.helper(root.left)-self.helper(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

    def helper(self,root):
        if not root:
            return 0
        left=self.helper(root.left)
        right=self.helper(root.right)
        return max(left,right)+1

面试题68 - I. 二叉搜索树的最近公共祖先

链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

最近公共祖先(最近公共节点):

根据题目给定的前提:

    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。

说明有以下几种情况:

    二叉树本身为空,root == null ,return root
    p.val == q.val ,一个节点也可以是它自己的祖先
    p.val 和 q.val 都小于 root.val
    (两个子节点的值都小于根节点的值,说明它们的公共节点只能在二叉树的左子树寻找)
    p.val 和 q.val 都大于 root.val
    (两个子节点的值都大于根节点的值,说明它们的公共节点只能在二叉树的右子树寻找)
    如果上述的情况皆不满足,说明其公共节点既不在左子树也不在右子树上,只能为最顶端的公共节点,return root
    p.val < root.val && q.val > root.val 或 p.val > root.val && q.val < root.val

题解一(递归):

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # if not root:
        #     return
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right,p,q)
        elif root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left,p,q)
        return root

题解二(后序遍历):

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root==p or root==q:
            return root
        l=self.lowestCommonAncestor(root.left,p,q)
        r=self.lowestCommonAncestor(root.right,p,q)
        if not l:
            return r
        elif not r:
            return l
        else:
            return root

题解三(迭代):

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val < p.val and root.val < q.val:
                root=root.right
            elif root.val > p.val and root.val > q.val:
                root=root.left
            else:
                break
        return root

面试题68 - II. 二叉树的最近公共祖先

链接:https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

题解一(后序遍历):

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root==p or root==q:
            return root
        l=self.lowestCommonAncestor(root.left,p,q)
        r=self.lowestCommonAncestor(root.right,p,q)
        if not l:
            return r
        elif not r:
            return l
        else:
            return root
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left and not right: return # 1.
        if not left: return right # 3.
        if not right: return left # 4.
        return root # 2. if left and right:

参考:https://segmentfault.com/a/1190000003914228

一、Manacher

Manacher用来在字符串中求最长回文串。

二、代码

def manacher(s):
    s='#'+'#'.join(s)+'#'

    RL=[0]*len(s)
    maxRight=0
    pos=0
    maxLen=0

    for i in range(len(s)):
        if i<MaxRight:
            RL[i]=min(RL[2*pos-i], MaxRight-i)
        else:
            RL[i]=1
        #尝试扩展,注意处理边界
        while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
            RL[i]+=1
        #更新MaxRight,pos
        if RL[i]+i-1>MaxRight:
            MaxRight=RL[i]+i-1
            pos=i
        #更新最长回文串的长度
        maxLen=max(maxLen, RL[i])
    return maxLen-1

参考:
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
https://www.bilibili.com/video/BV1jb411V78H?from=search&seid=3722651774629068033
https://www.bilibili.com/video/BV1Px411z7Yo?from=search&seid=3722651774629068033
https://www.bilibili.com/video/BV1hW411a7ys?from=search&seid=3722651774629068033
https://www.cnblogs.com/dahu-daqing/p/9302668.html

一、KMP

KMP算法,又称模式匹配算法,能够在线性时间内判定字符串 T 是否为 S 的子串,并求出字符串 T 在 S 中各次出现的位置。

二、代码

1、解决奇偶数问题
    在原字符串的每个相邻两个字符中间插入一个分隔符,同时在首尾也添加分隔符,如何#
2、字符串观察
    s:aaaba
    t:#a#a#a#b#a#
    回文半径数组:RL

    RL[i]-1等于回文串的长度

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/manacher.jpg

时间复杂度:O(m+n)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @contact: voidqueens@hotmail.com
# @software: PyCharm
# @time: 2020/4/26 下午6:50
# @site: www.gongyanli.com
# @file: kmp.py

def getNext(p):
    '''
    p为模式串
    返回next数组,即部分匹配表,使用p字符的前缀和后缀计算得到。
    等同于从模式字符串的第1位(注意,不包括第0位)开始对自身进行匹配运算。
    :param p:
    :return:
    '''
    next = [0] * len(p)
    next[0] = -1
    i = 0
    j = -1
    while i < len(p) - 1:
        if j == -1 or p[i] == p[j]: # i遍历的是数组下标,j则为next赋值
            i += 1
            j += 1
            next[i] = j
        else:
            j = next[j]
    return next


def kmp(s, p):
    '''
    s为主串
    p为模式串
    如果t里有p,返回打头下标
    :param s:
    :param p:
    :return:
    '''
    next = getNext(p)
    i = j = 0
    while i < len(s) and j < len(p):
        if j == -1 or s[i] == p[j]: 
            i += 1
            j += 1
        else:
            j = next[j]
    if j == len(p):
        return i - j
    else:
        return -1


s = 'ababababca'
p = 'abababca'
print(getNext(p))
print(kmp(s, p))

三、中心扩散–验证回文串

中心扩散主要用于验证字符串是否是回文串。

思路:

    每个字母当成回文串的中心
    考虑两种情况:回文串的长度为奇数或者偶数情况。

缺点:
    奇数和偶数需要分开讨论
    没有充分利用前面查找的结果
    没有思考回文字符本身的特性--对称性
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        self.res=''
        def helper(i,j):
            while i>= 0 and j<n and s[i]==s[j]:
                i-=1
                j+=1
            if len(self.res) < j-i-1:
                self.res=s[i+1:j]
                # print(i,self.res)

        for i in range(n):
            helper(i,i)
            helper(i,i+1) # 解决case为"cbbd",即解决回文串为偶数的情况
        return self.res

https://www.cnblogs.com/wanghui-garcia/p/10775859.html

https://www.cnblogs.com/wanghui-garcia/p/10775859.html
https://blog.csdn.net/Haiqiang1995/article/details/90300686
https://medium.com/@pkqiang49/%E4%B8%80%E6%96%87%E7%9C%8B%E6%87%82%E5%8D%B7%E7%A7%AF%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C-cnn-%E5%9F%BA%E6%9C%AC%E5%8E%9F%E7%90%86-%E7%8B%AC%E7%89%B9%E4%BB%B7%E5%80%BC-%E5%AE%9E%E9%99%85%E5%BA%94%E7%94%A8-6047fb2add35

https://blog.csdn.net/r1254/article/details/104888502

https://blog.csdn.net/dyk4ever/article/details/102841518
https://blog.csdn.net/weixin_44307764/article/details/102353344
https://blog.csdn.net/yz2zcx/article/details/100187471/

https://www.jianshu.com/p/a2b536945e3c
https://blog.csdn.net/lzy2014/article/details/25916235
https://yq.aliyun.com/articles/373368
https://www.cnblogs.com/luxiaoxun/archive/2012/11/10/2764056.html
https://www.cnblogs.com/fzz9/p/8973315.html
https://www.jianshu.com/p/6f9d99f7ad54
https://blog.csdn.net/weixin_42042680/article/details/80994726

1、卷积运算函数

torch.nn.Conv2d的功能是:对由多个输入平面组成的输入信号进行二维卷积。

layer = nn.Conv2d(in_channels=1,out_channels=3,kernel_size=3,stride=1,padding=0)

in_channels:
    1)输入通道数,对于图片层一般为1(灰度)3(RGB)
    2)定义一种输入规则,要求上一层的输出必须和这个输入一致,也可以理解为并发in_channels个channel在上一层feature_map(特征映射)上进行卷积运算

out_channels:
    1)直观理解是输出层通道数,              
    2)换一种理解是kernels(卷积核)个数,其中,每个卷积核会输出局部特征,比如面部中有头发feature,衣服颜色的feature都是由不同的kernel进行卷积运算得到的。

stride(步长):控制cross-correlation的步长,可以设为1个int型数或者一个(int, int)型的tuple。

padding(补0):控制zero-padding的数目。

dilation(扩张):控制kernel点(卷积核点)的间距; 也被称为 "à trous"算法. 可以在此github地址查看:Dilated convolution animations

groups(卷积核个数):这个比较好理解,通常来说,卷积个数唯一,但是对某些情况,可以设置范围在1 —— in_channels中数目的卷积核:

输出[b,out_channels,w,h],其中w和h是输出的shape.
    mylayer=torch.nn.Conv2d(3,2,kernel_size=3,stride=2,padding=0)
    print(l1.weight.shape)
    input=torch.rand(1,3,7,7)
    out=l1.forward(input)
    print(out.shape)
-----------------------------------------------
    torch.Size([2, 3, 3, 3])
    torch.Size([1, 2, 3, 3])

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/cnn1.gif

1、padding的方式:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/padding.jpeg

说明:

1、摘录自http://stackoverflow.com/questions/37674306/what-is-the-difference-between-same-and-valid-padding-in-tf-nn-max-pool-of-t

2、不同的padding方式,VALID是采用丢弃的方式,比如上述的input_width=13,只允许滑动2次,多余的元素全部丢掉

3、SAME的方式,采用的是补全的方式,对于上述的情况,允许滑动3次,但是需要补3个元素,左奇右偶,在左边补一个0,右边补2个0

4、For the SAME padding, the output height and width are computed as:

out_height = ceil(float(in_height) / float(strides[1]))

out_width = ceil(float(in_width) / float(strides[2]))

For the VALID padding, the output height and width are computed as:

out_height = ceil(float(in_height - filter_height + 1) / float(strides[1]))

out_width = ceil(float(in_width - filter_width + 1) / float(strides[2]))

2、conv2d的参数:

1、strides[0] = strides[3] = 1

3、conv2d的参数解释:

tf.nn.conv2d(input, filter, strides, padding, use_cudnn_on_gpu=None, name=None)
除去name参数用以指定该操作的name,与方法有关的一共五个参数:

第一个参数input:指需要做卷积的输入图像,它要求是一个Tensor,具有[batch, in_height, in_width, in_channels]这样的shape,具体含义是[训练时一个batch的图片数量, 图片高度, 图片宽度, 图像通道数],注意这是一个4维的Tensor,要求类型为float32和float64其中之一

第二个参数filter:相当于CNN中的卷积核,它要求是一个Tensor,具有[filter_height, filter_width, in_channels, out_channels]这样的shape,具体含义是[卷积核的高度,卷积核的宽度,图像通道数,卷积核个数],要求类型与参数input相同,filter的通道数要求与input的in_channels一致,有一个地方需要注意,第三维in_channels,就是参数input的第四维

第三个参数strides:卷积时在图像每一维的步长,这是一个一维的向量,长度4,strides[0]=strides[3]=1

第四个参数padding:string类型的量,只能是”SAME”,”VALID”其中之一,这个值决定了不同的卷积方式(后面会介绍)

第五个参数:use_cudnn_on_gpu:bool类型,是否使用cudnn加速,默认为true

结果返回一个Tensor,这个输出,就是我们常说的feature map

4、conv2d的例子:

那么TensorFlow的卷积具体是怎样实现的呢,用一些例子去解释它:

import tensorflow as tf
#case 2
input = tf.Variable(tf.random_normal([1,3,3,5]))
filter = tf.Variable(tf.random_normal([1,1,5,1]))
op = tf.nn.conv2d(input, filter, strides=[1, 1, 1, 1], padding=’VALID’)

with tf.Session() as sess:
sess.run(tf.initialize_all_variables())
res = (sess.run(op))
print (res.shape)

import tensorflow as tf

input = tf.Variable(tf.random_normal([1,5,5,5]))
filter = tf.Variable(tf.random_normal([3,3,5,1]))
op = tf.nn.conv2d(input, filter, strides=[1, 1, 1, 1], padding=’VALID’)

with tf.Session() as sess:
sess.run(tf.initialize_all_variables())
res = (sess.run(op))
print (res.shape)

说明:

1、使用VALID方式,feature map的尺寸为
out_height = ceil(float(in_height - filter_height + 1) / float(strides[1]))=(5-3+1)/1 = 3

out_width = ceil(float(in_width - filter_width + 1) / float(strides[2])) = (5-3+1)/1 = 3

所以,feature map的尺寸为3*3

2、filter的参数个数为3351,也即对于输入的每个通道数都对应于一个33的滤波器,然后共5个通道数,conv2d的过程就是对5个输入进行点击然后求和,得到一张feature map。如果要得到3张feature map,那么应该使用的参数为335*3个参数.

转载于:https://blog.csdn.net/u011995719/article/details/85107009

本文截取自《PyTorch 模型训练实用教程》,获取全文pdf请点击:https://github.com/tensor-yu/PyTorch_Tutorial

本文对transforms.py中的各个预处理方法进行介绍和总结。主要从官方文档中总结而来,官方文档只是将方法陈列,没有归纳总结,顺序很乱,这里总结一共有四大类,方便大家索引:

裁剪——Crop 中心裁剪:transforms.CenterCrop 随机裁剪:transforms.RandomCrop 随机长宽比裁剪:transforms.RandomResizedCrop 上下左右中心裁剪:transforms.FiveCrop 上下左右中心裁剪后翻转,transforms.TenCrop
翻转和旋转——Flip and Rotation 依概率p水平翻转:transforms.RandomHorizontalFlip(p=0.5) 依概率p垂直翻转:transforms.RandomVerticalFlip(p=0.5) 随机旋转:transforms.RandomRotation
图像变换 resize:transforms.Resize 标准化:transforms.Normalize 转为tensor,并归一化至[0-1]:transforms.ToTensor 填充:transforms.Pad 修改亮度、对比度和饱和度:transforms.ColorJitter 转灰度图:transforms.Grayscale 线性变换:transforms.LinearTransformation() 仿射变换:transforms.RandomAffine 依概率p转为灰度图:transforms.RandomGrayscale 将数据转换为PILImage:transforms.ToPILImage transforms.Lambda:Apply a user-defined lambda as a transform.
对transforms操作,使数据增强更灵活 transforms.RandomChoice(transforms), 从给定的一系列transforms中选一个进行操作 transforms.RandomApply(transforms, p=0.5),给一个transform加上概率,依概率进行操作 transforms.RandomOrder,将transforms中的操作随机打乱
一、 裁剪——Crop
1.随机裁剪:transforms.RandomCrop
class torchvision.transforms.RandomCrop(size, padding=None, pad_if_needed=False, fill=0, padding_mode=’constant’) 功能:依据给定的size随机裁剪 参数: size- (sequence or int),若为sequence,则为(h,w),若为int,则(size,size) padding-(sequence or int, optional),此参数是设置填充多少个pixel。 当为int时,图像上下左右均填充int个,例如padding=4,则上下左右均填充4个pixel,若为3232,则会变成4040。 当为sequence时,若有2个数,则第一个数表示左右扩充多少,第二个数表示上下的。当有4个数时,则为左,上,右,下。 fill- (int or tuple) 填充的值是什么(仅当填充模式为constant时有用)。int时,各通道均填充该值,当长度为3的tuple时,表示RGB通道需要填充的值。 padding_mode- 填充模式,这里提供了4种填充模式,1.constant,常量。2.edge 按照图片边缘的像素值来填充。3.reflect,暂不了解。 4. symmetric,暂不了解。

2.中心裁剪:transforms.CenterCrop
class torchvision.transforms.CenterCrop(size) 功能:依据给定的size从中心裁剪 参数: size- (sequence or int),若为sequence,则为(h,w),若为int,则(size,size)

3.随机长宽比裁剪 transforms.RandomResizedCrop
class torchvision.transforms.RandomResizedCrop(size, scale=(0.08, 1.0), ratio=(0.75, 1.3333333333333333), interpolation=2) 功能:随机大小,随机长宽比裁剪原始图片,最后将图片resize到设定好的size 参数: size- 输出的分辨率 scale- 随机crop的大小区间,如scale=(0.08, 1.0),表示随机crop出来的图片会在的0.08倍至1倍之间。 ratio- 随机长宽比设置 interpolation- 插值的方法,默认为双线性插值(PIL.Image.BILINEAR)

4.上下左右中心裁剪:transforms.FiveCrop
class torchvision.transforms.FiveCrop(size) 功能:对图片进行上下左右以及中心裁剪,获得5张图片,返回一个4D-tensor 参数: size- (sequence or int),若为sequence,则为(h,w),若为int,则(size,size)

5.上下左右中心裁剪后翻转: transforms.TenCrop
class torchvision.transforms.TenCrop(size, vertical_flip=False) 功能:对图片进行上下左右以及中心裁剪,然后全部翻转(水平或者垂直),获得10张图片,返回一个4D-tensor。 参数: size- (sequence or int),若为sequence,则为(h,w),若为int,则(size,size) vertical_flip (bool) - 是否垂直翻转,默认为flase,即默认为水平翻转

二、翻转和旋转——Flip and Rotation
6.依概率p水平翻转transforms.RandomHorizontalFlip
class torchvision.transforms.RandomHorizontalFlip(p=0.5) 功能:依据概率p对PIL图片进行水平翻转 参数: p- 概率,默认值为0.5

7.依概率p垂直翻转transforms.RandomVerticalFlip
class torchvision.transforms.RandomVerticalFlip(p=0.5) 功能:依据概率p对PIL图片进行垂直翻转 参数: p- 概率,默认值为0.5

8.随机旋转:transforms.RandomRotation
class torchvision.transforms.RandomRotation(degrees, resample=False, expand=False, center=None) 功能:依degrees随机旋转一定角度 参数: degress- (sequence or float or int) ,若为单个数,如 30,则表示在(-30,+30)之间随机旋转 若为sequence,如(30,60),则表示在30-60度之间随机旋转 resample- 重采样方法选择,可选 PIL.Image.NEAREST, PIL.Image.BILINEAR, PIL.Image.BICUBIC,默认为最近邻 expand- ? center- 可选为中心旋转还是左上角旋转

三、图像变换
9.resize:transforms.Resize
class torchvision.transforms.Resize(size, interpolation=2) 功能:重置图像分辨率 参数: size- If size is an int, if height > width, then image will be rescaled to (size * height / width, size),所以建议size设定为h*w interpolation- 插值方法选择,默认为PIL.Image.BILINEAR

10.标准化:transforms.Normalize
class torchvision.transforms.Normalize(mean, std) 功能:对数据按通道进行标准化,即先减均值,再除以标准差,注意是 hwc

11.转为tensor:transforms.ToTensor
class torchvision.transforms.ToTensor 功能:将PIL Image或者 ndarray 转换为tensor,并且归一化至[0-1] 注意事项:归一化至[0-1]是直接除以255,若自己的ndarray数据尺度有变化,则需要自行修改。

12.填充:transforms.Pad
class torchvision.transforms.Pad(padding, fill=0, padding_mode=’constant’) 功能:对图像进行填充 参数: padding-(sequence or int, optional),此参数是设置填充多少个pixel。 当为int时,图像上下左右均填充int个,例如padding=4,则上下左右均填充4个pixel,若为3232,则会变成4040。 当为sequence时,若有2个数,则第一个数表示左右扩充多少,第二个数表示上下的。当有4个数时,则为左,上,右,下。 fill- (int or tuple) 填充的值是什么(仅当填充模式为constant时有用)。int时,各通道均填充该值,当长度为3的tuple时,表示RGB通道需要填充的值。 padding_mode- 填充模式,这里提供了4种填充模式,1.constant,常量。2.edge 按照图片边缘的像素值来填充。3.reflect,? 4. symmetric,?

13.修改亮度、对比度和饱和度:transforms.ColorJitter
class torchvision.transforms.ColorJitter(brightness=0, contrast=0, saturation=0, hue=0) 功能:修改修改亮度、对比度和饱和度

14.转灰度图:transforms.Grayscale
class torchvision.transforms.Grayscale(num_output_channels=1) 功能:将图片转换为灰度图 参数: num_output_channels- (int) ,当为1时,正常的灰度图,当为3时, 3 channel with r == g == b

15.线性变换:transforms.LinearTransformation()
class torchvision.transforms.LinearTransformation(transformation_matrix) 功能:对矩阵做线性变化,可用于白化处理! whitening: zero-center the data, compute the data covariance matrix 参数: transformation_matrix (Tensor) – tensor [D x D], D = C x H x W

16.仿射变换:transforms.RandomAffine
class torchvision.transforms.RandomAffine(degrees, translate=None, scale=None, shear=None, resample=False, fillcolor=0) 功能:仿射变换

17.依概率p转为灰度图:transforms.RandomGrayscale
class torchvision.transforms.RandomGrayscale(p=0.1) 功能:依概率p将图片转换为灰度图,若通道数为3,则3 channel with r == g == b

18.将数据转换为PILImage:transforms.ToPILImage
class torchvision.transforms.ToPILImage(mode=None) 功能:将tensor 或者 ndarray的数据转换为 PIL Image 类型数据 参数: mode- 为None时,为1通道, mode=3通道默认转换为RGB,4通道默认转换为RGBA

19.transforms.Lambda
Apply a user-defined lambda as a transform. 暂不了解,待补充。

四、对transforms操作,使数据增强更灵活
PyTorch不仅可设置对图片的操作,还可以对这些操作进行随机选择、组合

20.transforms.RandomChoice(transforms)
功能:从给定的一系列transforms中选一个进行操作,randomly picked from a list

21.transforms.RandomApply(transforms, p=0.5)
功能:给一个transform加上概率,以一定的概率执行该操作

22.transforms.RandomOrder
功能:将transforms中的操作顺序随机打乱