系列文章目录

记录一下自己的学习过程

---

---

基础知识

链表

节点定义：

class Node:
    def __init__(self,data = None, next = None):
        self.data = data
        self.next = next

节点创建：

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3

链表两数相加

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def addTwoNumbers(self,l1,l2,carry=0):
        if l1 is None and l2 is None:
            return ListNode(carry) if carry else None  
        if l1 is None:
            l1,l2=l2,l1
        carry+=l1.val+(l2.val if l2 else 0)
        if carry>=10:
            l1.val=carry-10
            carry=1 # 进一位
        else:
            l1.val=carry
            carry=0
        
        l1.next=self.addTwoNumbers(l1.next,l2.next if l2 else None,carry)
        return l1

回文 11.16

思路：把数倒过来相加和原来的进行比较。

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        num = x
        cur = 0

        if x >= 10:
            while (num != 0):
                cur = cur * 10 + num % 10
                num = num / 10
            return cur == x
        elif x >= 0 and x < 10:
            return True
        else:
            return False

罗马数字转换 11.16

思路一：直接暴力求解，先算出单个罗马数字对应的值，然后减去有数字组合的数值

def index_num(index):
    if index=='I':
        return 1
    if index=='V':
        return 5
    if index=='X':
        return 10
    if index=='L':
        return 50
    if index=='C':
        return 100
    if index=='D':
        return 500
    if index =='M':
        return 1000

class Solution(object):
    


    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        result=0
        i=0
        num=s
        while(i<len(num)):
            result=result+index_num(num[i])
            i+=1
        if 'XL' in num:
            result=result-20
        if 'XC' in num:
            result=result-20
        if 'IV' in num:
            result=result-2
        if 'IX' in num:
            result=result-2
        if 'CD' in num:
            result=result-200
        if 'CM' in num:
            result=result-200


        return result

思路二：直接用哈希表存储

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
        return sum(d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s))

作者：⚗ Knife丶👆👆👆
链接：https://leetcode.cn/problems/roman-to-integer/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最长公共前缀 11.16

思路1：暴力求解，将第一个字符作为基准，如果后面的字符没有该前缀或长度大于该前缀，则跳过。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        result = ''
        index = 0
        str1 = strs[0]
        if len(strs) == 1:
            return str1
        for j in range(1, len(str1)+1):
            for k in range(1, len(strs)):
                if str1[0:j] != strs[k][0:j]:
                    index = 0
                    break
                elif j > len(strs[k]):
                    index = 0
                    break
                else:
                    index = 1
            if index == 1 and len(result) <= len(str1[0:j]):
                result = str1[0:j]
        return result

思路2：取每一个字母的同一位置字母，看是否相同

set():创建一个无序不重复元素的集合 ，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。其返回值为一个新的集合对象。

队列

滑动窗口思想：
class Solution(object):
def lengthOfLongestSubstring(self, s):
“”"
:type s: str
:rtype: int
“”"
len_result=0
result=[]
for i in s:
if i not in result:
result.append(i)
else:

            while i in result:
                result=result[1:len(result)]
            result.append(i)
        if len_result<len(result):
            len_result=len(result)
    return len_result