Leetcode python 06：Valid Parentheses

 技术  No Responses »
Jan 132021
 

这道题是判断输入的符号是否合法。

https://leetcode.com/problems/valid-parentheses/

这道题涉及到所谓栈，stack，所谓的后进先出。这个需要理解一下。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dic={'(':')','[':']','{':'}'}

        for i in s:
            if i in dic:
                stack.append(i)
            elif len (stack)== 0 or dic[stack.pop()]!=i:
                return False

        return len(stack)==0

代码理解

  1. 建立一个字典
  2. 建立一个空的栈，stack
  3. for循环，如果在字典里，例如左括号，那么就会放到stack上。
  4. 当 i 遇到右括号，由于不在字典里，就运行 elif  , 如果这个时候 stack是空的话，说明没有左括号。或者stack刚刚进入的值的字典里，不是左括号，value 不等于 右括号。那么就是False
  5. 最后，必须stack为空，才能确认是合法的，例如只有一个左括号。

把左边的符号，都放到stack里，右边的符号，从stack拿出来，去字典把value取出来，如果等，那么就继续运行下去。一直到stack里为空，才能证明是有效。

Leetcode python 05：Longest Common Prefix

 技术  No Responses »
Jan 132021
 

题目很简单，寻找开头相同的字母，看看最大是多少。

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

每次看到这种题目，都有一种想法，如果python，有一个内置函数搞定这种看上去比较普遍的问题，多好。没想到这个问题，就是这种情况。居然有内置的函数，直接搞定。

Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”

https://medium.com/@d_dchris/10-methods-to-solve-the-longest-common-prefix-problem-using-python-leetcode-14-a87bb3eb0f3a

上面的朋友用了10种方法来解答，我最喜欢的，还是最后一种。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        return os.path.commonprefix(strs)

Leetcode python 04：Roman to Integer

 技术  No Responses »
Jan 122021
 

把罗马数字转换成阿拉伯数字，这个题目让我好好学习了一下罗马数字

https://leetcode.com/problems/roman-to-integer/

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000,'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900}
        result = 0
        i = 0
        while i<len(s):
            if s[i:i+2] in d:
                result=result+d[s[i:i+2]]
                i=i+2
                continue
            elif s[i:i+1] in d:
                result=result+d[s[i:i+1]]
                i=i+1
        return result

代码理解

  1. 创建了一个字典，输入相关的罗马的数字的对应阿拉伯数字
  2. 设置result 变量，作为结果的输出
  3. s = “MCMXCIV” 作为例子来理解代码
  4. 第一轮，对字符串取前两位，MC，如果在字典里，那么就把放到result里，因为MC不在字典，所以为False，不会执行下面的代码，直接跳到elif ，那么这时候，就看第一个字母是否在字典里，如果在，那么就把结果加入到result里，这个时候，result就是1000。并且i 变成1
  5. 第二轮，我们取第二，第三位，CM，看看是否在字典里，刚好在，CM是900，那么就放到result里面，现在result就变成1900，i 变成3. continue 导致继续循环，到下面2位
  6. 第三轮，还是2位，XC，也刚好是在字典，90，
  7. 第四轮，最后2位，也是在字典，4.

写的也是非常巧妙。先拿两位到字典查询，如果没有，再拿一位取查询。

Leetcode python 03：Palindrome Number

 技术  No Responses »
Jan 122021
 

估计没几个人能认识这样的单词。意思倒是不复杂，

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

就是把一个数字，反转过来，数值和原来相对的数字。例如，121，你反转后，还是121

题目专门提到不能使用字符串的方式来解答这个问题，那么就只能老实点。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        num=0
        a=abs(x)

        while a!=0 :
            temp=a%10
            num=num*10+temp
            a=int(a/10)

        if x >= 0 and x == num:
            return True
        else:
            return False

代码理解

  1. 把x取 绝对值
  2. 设置num 变量，他是0
  3. 目标就是a会逐步变成0，而num是逐步变成反转数字
  4. 使用一个临时变量temp，取得当前数字的第一位
  5. 把第一位的数字放到num上，并且把这个数字乘10，左移动一位。
  6. 通过对a的整数，拿掉第一位的数字
  7. 后续就是十位相同的操作。
  8. 一直到a变成0，while 停止
  9. 负数都不能满足这个条件

Leetcode python 02：Reverse Integer

 技术  No Responses »
Jan 122021
 

这是刷的第二题，其实是easy程度的第二题，题目比较简单。

就是把数字反转，要考虑正负，0的处理。

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

就是把数字 321，转换c123，120，转换成 21。需要处理几个特殊的情况，正负和零。

解答1

这个最高效的解决办法，我反而看懂了。

class Solution:
    def reverse(self, x: int) -> int:
        y = abs(x)
        y = str(y)
        y = y.strip()
        y = y [::-1]
        y=int(y)


        if y >= 2**31-1 or y<= -2**31:
            return 0
        elif x < 0:
            return -y
        else:
            return y

说一下我的理解

  1. 设置一个变量，y，把x的绝对值
  2. 变成字符串
  3. 去掉末尾的0
  4. 字符串反转
  5. 变成整数
  6. 做一个边界的判断。
  7. 根据n的正负，确定返回值。

Leetcode python 01：twoSum

 技术  No Responses »
Jan 112021
 

其实我学过好几次Python，基本都中途报废，一个重要的原因，其实就是没做练习。很多东西，看起来，都能看懂，也都能理解，不动手，就很难深入的理解，更别谈使用。

以前老听国外的同行说刷题进大公司，也不清楚他们在说啥。这下总算明白了。Leetcode 是一个非常有名的刷题网站，一道题目，你可以用多种语言来实现。

昨晚注册了一个账号，开始了刷题的生涯。在油管上很多视频帮忙解题，关键还是你要理解，自己能写出来。

据说这道题，Two Sum是网站成立的第一道题目，日后python的水平高低，就看刷题的数量。

网站做的非常不错，帮你验证你的代码是否正确，是否可以满足不同的条件。也让你尝试多个方法来解决一个问题。

关于编程的题目，基本都在这里

https://leetcode.com/problemset/algorithms/

我就选第一题来开始

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9,
we return [0, 1].

上面就是题目，现在至少看到有4种以上的解答，抄过来是没啥意思的，关键还是自己能理解。我就把我能理解的记录下来。

解答1：循环解决

这个应该是最简单直接的解答，不过我也费了半天，理解了，写下来，提交上去。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range (len(nums)-1):
            for j in range (i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return[i,j]

解答二：字典

理解真的比较费劲，这个应该也是我看到最简洁的答案, 我能理解，太过于巧妙，我是敲不出这样的代码。

为了加深我的理解，我把我的理解，也自己描述一遍。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic={}   #key is diff, index as value
        for i,num in enumerate (nums):
            if num in dic:
                return (dic[num],i)
            else:
                diff=target-num
                dic[diff]=i

为了加深理解，我记录一下我的理解过程。

1：把nums的列表，加上索引。

2：dic，字典初始化的时候是空的。

3：当第一次运行，if 语句是False，直接运行else，把差值作为key，索引作为value。写入到字典里

4：第二次运行，检查当前的数字是否在字典里，如果存在，条件为True，就可以把相关数字的索引输出。因为字典里存放的是差值，如果当前数字等于差值，通过字典，获取到这个差值的索引，和当前数字的索引。

参考资料

http://icejoywoo.github.io/2019/03/19/python-iterate-list-and-dict.html

https://draapho.github.io/2017/01/03/1701-python-list-dict/

https://leetcode-cn.com/problems/two-sum/solution/liang-zhi-zhi-he-pythonjie-fa-shi-yong-zi-dian-by-/