笨方法刷 leetcode(一)

最近在看leetcode，并且正在上面刷一些简单级别的题目（不过说真的，这些题真的简单吗？？或许是我太菜，有些感觉也很难……）

本篇记录5道题的解题思路，可能都是最笨的方法

No.1 判断字符是否唯一

题目描述：

实现一个算法，确定一个字符串 s 的所有字符是否全都不同

示例 1：

输入: s = "leetcode"

输出: false

示例 2：

输入: s = "abc"

输出: true

限制：

0 <= len(s) <= 100

原题链接：

https://leetcode-cn.com/problems/is-unique-lcci/

解决思路：

python中有一个内置函数set()，它的一个特性就是->可以利用已有列表、字符串、元组或字典的内容来创建集合，其中重复的值会被丢弃;

所以就可以通过set()来得到一个剔除重复值后的集合，并且比较两者的长度，如果长度相等，则证明字符唯一；如果长度不等，则字符不唯一

代码如下：

class Solution(object):

    def isUnique(self, astr):
        """
        :type astr: str
        :rtype: bool
        """
        len_1 = len(astr)  # 获取传入字符串的长度
        b = set(astr)  # 使用set()函数将传入字符串转为一个集合，该集合剔除了重复的元素
        len_2 = len(b)  # 获取集合的长度
        if len_1 == len_2:  # 对比原字符串和集合的长度，如果两者相等，表明字符串无重复；否则表示有重复元素
            print("true")
            return True
        else:
            print("false")
            return False

No.2 两数之和

题目描述：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。  

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。     

示例:  给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

原题链接：

https://leetcode-cn.com/problems/two-sum/

解决思路：

用第1个数字依次与其后面的数字相加，判断结果是否为目标值；然后用第2个数字依次与其后面数字相加，判断结果是否为目标值;         依此类推，用第n个数，与其后的数字相加，这样就做到了任意2个数字(不重复)的叠加求和

代码如下：

class Solution(object):
    def twoSum(self, nums, target):
        """
        思路：用第1个数字依次与其后面的数字相加，判断结果是否为目标值；然后用第2个数字依次与其后面数字相加，判断结果是否为目标值
        依次类推，用第n个数，与其后的数字相加，这样就做到了任意2个数字的不重复叠加求和
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(0, len(nums)):  # 定义第一个for循环，从第一个数字开始，深度为字符串列表的长度
            for j in range(i + 1, len(nums)):  # 内嵌一个for循环，从第二个数字开始，深度为字符串列表长度，
                if nums[i] + nums[j] == target:  # 先用第一个数字（nums[i]代表加号左侧数字）分别与其后的数字（nums[j]加号右侧数字）叠加，判断结果是否为目标值
                    return i, j  # 如果相加得到目标值，则返回下角标组合的列表
                else:
                    continue  # 如果不是，则继续循环

No.3 回文数

题目描述：

判断一个整数是否是回文数。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121

输出: true

示例 2:

输入: -121

输出: false

解释: 从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10

输出: false

解释: 从右向左读, 为 01 。因此它不是一个回文数。

原题链接：

https://leetcode-cn.com/problems/palindrome-number/

解决思路：

把输入的数字先转换成列表，反向取出来，也就是从最后一个开始提取，然后依次追加到一个新的列表并组合成一个新的字符串，最后与原字符串判断是否相等

代码如下：

class Solution(object):
    def isPalindrome(self, x):
        """
        解决思路：把输入字符串转换成列表，反向取出来，也就是从最后一个开始提取，然后依次追加到一个新的列表并组合成一个新的字符串，然后与原字符串判断是否相等
        :type x: int
        :rtype: bool
        """

        string = str(x)  # 将输入的整数转为字符串
        s_list = list(string)  # 将字符串转为列表
        n_list = []  # 定义一个空列表，用于存储下面反向输出的列表
        for t in range(0, len(s_list)):
            n_list.append(s_list[len(s_list)-t-1])

        n_string = "".join(n_list)  # 将新的列表转为字符串

        if string == n_string:  # 判断2个字符串的值是否相等（注意??：不要用is判断，is是用来判断其id值是否相等，==判断其值是否相等）
            return True
        else:
            return False

另一种写法更简单些，把输入数字转换成字符串后，直接通过切片的方法，反向输出得到一个新的字符串

def isPalindrome_2(self, x):
    string = str(x)
    new_string = string[::-1]

    if string == new_string:
        return True
    else:
        return False

No.4 整数反转

题目描述：

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:输入: 123输出: 321
示例 2:输入: -123输出: -321
示例 3:输入: 120输出: 21
注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [?231,  231 ? 1]。请根据这个假设，如果反转后整数溢出那么就返回 0

原题链接：

https://leetcode-cn.com/problems/reverse-integer/

解决思路：

先把整数转换为字符串，然后利用字符串切片的方法将其进行反转（注意：如果传入的是负数，需要保留"-"前缀，只将后面的字符反转）

代码如下：

class Solution(object):

    def reverse(self, x):
        """

        :type x: int
        :rtype: int
        """
        l = str(x) # 把输入的数字转换为字符串
        if l[0] == "-":  # 如果首位字符是"-"（也就是说输入一个负数）
            s = l[1:]  # 截取"-"之后的部分
            new = s[::-1]  # 将"-"之后的部分进行反转，得到一个新字符串
            i = ""  # 定义一个空字符串
            for t in new:
                i += t  # 遍历新列表中的值，并将结果一个个追加到空字符串中
            i = "-" + i  # 将"-"与最终的字符串i组合，得到最终的字符串
        else:
            new = l[::-1]  # 如果首位字符不是"-"，则直接进行反转

            i = ""
            for t in new:
                i += t

        if -2 ** 31 <= int(i) <= 2 ** 31 - 1:
            return int(i)  # 将反转后的字符串i转换为整型数字，并判断结果是否在允许范围内，如果在，则将其返回；如果不在，则返回0
        else:
            return 0

No.5 最长公共前缀

题目描述：

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:输入: ["flower","flow","flight"]输出: "fl"
示例 2:输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。

原题链接：

https://leetcode-cn.com/problems/longest-common-prefix/

解决思路：

这个把我难住了，后来看了官方题解，里面有一个横向扫描法和一个纵向扫描法，下面根据自己的理解来实现了一下

代码如下：

横向扫描法

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        横向扫描法
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        else:
            prefix = strs[0]  # 把字符串列表中的第一个字符串赋给一个变量
            length = len(strs)  # 获取整个字符串列表的长度

            for t in range(1, length):
                prefix = self.common_start(prefix, strs[t])
                # 调用common_start方法比较2个字符串，提取公共前缀，然后将获取到的公共前缀再与后一个字符串比较
                if not prefix:  # 当在后续比较中没有公共前缀（即公共前缀为空时，退出循环）
                    break
            return prefix  # 循环完成后，返回最终的公共前缀

    @staticmethod
    def common_start(str1, str2):
        """
        获取2个字符的公共前缀
        :param str1:
        :param str2:
        :return:
        """
        length = min(len(str1), len(str2))  # 获取2个字符串的最小长度

        if length == 0:  # 如果最小字符串长度为0，则意味着有空字符串，所以公共前缀为""
            return ""

        else:
            common = ""  # 定义一个空字符串，用来存储公共前缀
            for i in range(0, length):  # 以最小长度字符串的长度作为遍历深度

                common += str1[i]  # 把字符串1的第i个字符追加到common中

                if str2.startswith(common):  # 利用自带的startswith()函数，判断字符串2是否以common为前缀，如果以common为前缀，则继续循环
                    continue

                else:  # 如果字符串2不是以common为前缀，则返回common除掉最后一个字符外的部分
                    return common[:-1]
            return common  # 如果一直满足if条件，则说明字符串2是以common为前缀，所以当循环走完后，返回最后的common字符串

纵向扫描法

class Solution(object):
    @staticmethod
    def longestCommonPrefix2(strs):
        """
        纵向扫描法
        :param strs:
        :return:
        """
        if not strs:  # 如果传入空列表，则返回空字符串
            return ""

        for i in range(0, len(strs[0])):  # 获取第一个字符串的长度，并以此作为循环深度

            c = strs[0][i]  # 获取第一个字符串，并且从其第一个字符开始遍历（以第一个字符串为纵向扫描依据，判断第一个字符串的各列是否与后续字符串的各列相同）

            for j in range(1, len(strs)):  # 获取整个字符串列表的长度，从第二个字符串开始分别与第一个字符串比对

                if i <= len(strs[j])-1:  # 在把第二个字符串的字符与第一个字符串的字符比对前，先判断后续字符串的长度是否大于等于第一个字符串的长度（防止提取后续字符串的字符时，出现溢出）

                    if strs[j][i] == c:  # 从第二个字符串开始，依次判断后续字符串的第i个字符是否与第1个字符串的第i个字符相等，如果相等，则通过，继续下一轮判断；

                        pass
                    else:  # 如果不相等，则退出循环，返回第一个字符串的前i个字符
                        print("第1个return")
                        return strs[0][:i]
                else:  # 如果后续字符串的长度比第一个字符串短，则strs[j][i]最终会溢出，此时退出循环，返回第一个字符串的前i个字符
                    print("第2个return")
                    return strs[0][:i]
        print("第3个return")
        return strs[0]  # 如果一直满足所有if条件，则说明第一个字符串的字符都是公共前缀，最终返回第一个字符串

未完……