leetcode刷题（8.13总结）

1、有效的括号

题目描述：https://leetcode.cn/problems/valid-parentheses/

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        count = 0
        if len(s) % 2 != 0:
            return False
        for i in s:
            if i in "([{":
                stack.append(i)
                count = count +1
            else :
                if count:
                    a = stack.pop()
                    count = count - 1
                    if a  == '(':
                        if i != ')':
                            return False
                    elif a == '[':
                        if i != ']':
                            return False
                    else:
                        if i != '}':
                            return False
                else:
                    return False
        if count != 0:
            return False
        return True

2、合并两个有序链表

题目描述：https://leetcode.cn/problems/merge-two-sorted-lists/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        #定义一个新node存放
        nlist = ListNode(0)
        #定义一个操作node
        cur = nlist
        while list1 or list2:
            cur.next = ListNode(0)
            cur = cur.next
            #如果两个都不为空，说明有数据
            if list1 and list2:
                #如果node2大于或等于node1，将node1放到新node里面，然后list1向后移动
                if list1.val <= list2.val:
                    cur.val = list1.val
                    list1 = list1.next
                #反之list2向后移动
                else:
                    cur.val = list2.val
                    list2 = list2.next
            else:
                #如果两个有一个为空，则直接移动不为空的那个list即可
                if list1:
                    cur.val = list1.val
                    list1 = list1.next
                if list2:
                    cur.val = list2.val
                    list2 = list2.next
        return nlist.next

3、删除有序数组中的重复项

题目描述：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow, fast = 0, 1
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow = slow + 1
                nums[slow] = nums[fast]
            fast = fast + 1
        return slow + 1

4、移除元素

题目描述：https://leetcode.cn/problems/remove-element/

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        
        l, i = len(nums), 0

        while l > 0 and i < l:
            if nums[i] == val: 
                del nums[i]
                l -= 1
            else:
                i += 1

        return len(nums)

5、实现strStr()

题目描述：https://leetcode.cn/problems/implement-strstr/

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        if len(haystack) < len(needle):
            return -1
        for i in range(len(haystack)):
            index = i
            for j in range(len(needle)):
                if len(haystack) - index < len(needle):
                    break
                if haystack[i] == needle[j]:
                    i+=1
                    if j == len(needle)-1:
                        return index
                    continue
                else:
                    break
        return -1

6、搜索插入位置

题目描述：https://leetcode.cn/problems/search-insert-position/

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        i,j=0,len(nums) - 1
        while i <= j:
            mid = (i + j) // 2
            if nums[mid] < target:
                i = mid + 1
            else:
                j = mid - 1
        return i