测试工程师社招-算法题

（太难了对于我，我只看了一小部分，侧开的话考的比较多）

LC1：两数之和，找一个数组中目标值等于val的两数下标

#暴力法
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                total = nums[i] + nums[j]
                if total == target:
                    result.append(i);
                    result.append(j);                    
        return result
#哈希法
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        mapping = {}
        for i in range(0, len(nums)):
            mapping[nums[i]] = i
        for j in range(0, len(nums)):
            diff = target - nums[j]
            if (diff in mapping and mapping[diff] != j):
                result.append(j);
                result.append(mapping[diff]);
                return result

LC2：两数相加，两个非空链表，两个非负整数，每个结点只能存储一位数字

9---9---9

9---9

8（进1）---9（进1）---0（进1）---1

要点：1、空链表接收result 2、依次遍历两个链表 l1.val+l2.val 3、next1 是否进1 4、添加剩余部分

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        total = 0
        next1 = 0
        res = ListNode()
        cur = res
        while (l1 != None and l2 != None):
            total = l1.val + l2.val + next1
            cur.next = ListNode(total % 10)
            next1 = total // 10
            cur = cur.next
            l1 = l1.next
            l2 = l2.next
        
        while l1 != None:
            total = l1.val + next1
            cur.next = ListNode(total % 10)
            next1 = total // 10
            cur = cur.next
            l1 = l1.next
        
        while l2 != None:
            total = l2.val + next1
            cur.next = ListNode(total % 10)
            next1 = total // 10
            cur = cur.next
            l2 = l2.next
        
        if next1 != 0:
            cur.next = ListNode(next1)
        
        return res.next

LC20：有效括号，只包括（）[] {}，判断字符串是否有效

要点：1、字符串为空，有效 2、左括号压栈 3、右括号，看是否匹配 4、剩余是否空栈

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 0:
            return True
        stack = []
        for c in s:
            if c=="(" or c=="[" or c=="{":
                stack.append(c)
            else:
                if len(stack) == 0:
                    return False
                else:
                    temp = stack.pop()
                    if c == ")":
                        if temp != "(":
                            return False
                    elif c == "]":
                        if temp != "[":
                            return False
                    elif c == "}":
                        if temp != "{":
                            return False
        return True if len(stack)==0 else False

LC21：合并两个有序链表

1---2---4

1---4---5

1---1---2---4---4---5

要点：递归法1、新建一个链表接收数据 2、比较两个数，谁小谁进

# 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, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if l1 == None or l2 == None:
            return l1 or l2
        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

LC22：括号生成，回溯算法

要点：1、左括号的数量<=右括号的数量 2、左括号的数量<右括号的数量 （不可）3、左右括号的数量相等且等于N

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        self.backtracking(n,result,0,0,"")
        return result
    def backtracking(self,n,result,left,right,s):
        if right>left:
            return
        if (left == right ==n):
            result.append(s)
            return
        if left<n:
            self.backtracking(n,result,left+1,right,s+"(")
        if right<left:
            self.backtracking(n,result,left,right+1,s+")")

LC24:两两交换链表中的节点

res - 1(head)--2(nxt)---3(tmp)---4

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head:ListNode) -> ListNode:
        if head == None or head.next==None
            return head
        res = ListNode()
        res.next= head
        cur = res
        while cur.next!=None and cur.next.next != None:
            nxt = head.next
            tmp = nxt.next
            cur.next = nxt
            nxt.next = head
            head.next = tmp
            cur = head
            head = head.next
        return res.next    

LC27：移除元素

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums== None or len(nums) == 0:
            return 0
        l,r = 0,len(nums)-1
        while l<r:
            while l<r and nums[l]!=val:
                l+=1
            while l<r and nums[r]==val:
                r-=1
            nums[l],nums[r] =nums[r],nums[l]
        return l if nums[l]==val else l+1