测试工程师社招-算法题

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

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

```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：有效括号，只包括（）[] {}，判断字符串是否有效

```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

```# 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：括号生成，回溯算法

```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:两两交换链表中的节点

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
res = ListNode()
cur = res
while cur.next!=None and cur.next.next != None:
tmp = nxt.next
cur.next = nxt
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
```

2 5 评论