leetcode基础思想特辑 01

概论

记录一些解题最基础的思想。

判断是否互为字符重排

题目链接： https://leetcode-cn.com/problems/check-permutation-lcci/

这种类型的题在于判断两个容器中的元素是否完全相同（不论顺序）。

首先第一步肯定是判断元素个数是否相等。

其次可以用比较简单的方法来判断两边的个数，而且只使用一次循环：

class Solution(object):
    def CheckPermutation(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        dict_char = dict()
        for i in range(len(s1)):
            value_char_s1 = s1[i]
            value_char_s2 = s2[i]

            if value_char_s1 not in dict_char:
                dict_char[value_char_s1] = 0

            if value_char_s2 not in dict_char:
                dict_char[value_char_s2] = 0

            dict_char[value_char_s1] = dict_char[value_char_s1] + 1
            dict_char[value_char_s2] = dict_char[value_char_s2] - 1

        for key in dict_char:
            value = dict_char[key]
            if value != 0:
                return False
        
        return True

原理是弄一个dict或者list，用来记录每个元素的出现次数。遇到第一个容器中的元素时次数+1，遇到第二个容器的元素时-1。最后如果统计出来每个元素的出现次数都是0（因为相互抵消了），那么说明两个容器中所有元素的出现次数相等。

不使用if的递归调用

题目传送门： https://leetcode-cn.com/problems/qiu-12n-lcof/

该题要求计算1~n的总和，且不得使用乘除法，if，while，for，三目运算符等语句。

很明显不使用乘除法，if、while、for，那么就只能用递归了。

然而使用递归有一个问题，就是递归需要一个终止条件。不使用if语句的话怎么终止递归呢？

这里用到了逻辑与和逻辑或的短路。即：

true or statement2 不会执行后面statement2的逻辑
false and statement2 不会执行后面statement2的逻辑

所以解法就是：

class Solution(object):
    def __init__(self):
        self.ret = 0
    
    def sumNums(self, n):
        n > 0 and self.sumNums(n - 1)
        self.ret = self.ret + n
        return self.ret