测试工程师社招-算法题

(太难了对于我,我只看了一小部分,侧开的话考的比较多)

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 

全部评论
项目该怎么说呢 不会总结
点赞 回复
分享
发布于 01-21 23:03 北京
这个有没有完整的题库,可以发来看看不
点赞 回复
分享
发布于 01-29 15:28 四川
联想
校招火热招聘中
官网直投

相关推荐

刚开始问了几个&nbsp;Go&nbsp;的简单八股,答的跟&nbsp;shi&nbsp;一样,后面答的也稀烂。面了&nbsp;40&nbsp;分钟,最后反问都不好意思问了,结束后半小时看了下流程已结束。1.&nbsp;自我介绍2.&nbsp;Go&nbsp;的&nbsp;&nbsp;map&nbsp;是并发安全的吗3.&nbsp;channel&nbsp;有无&nbsp;buf&nbsp;有什么区别4.&nbsp;向一个已经关闭的&nbsp;channel&nbsp;发数据会发生什么5.&nbsp;从一个已经关闭的&nbsp;channel&nbsp;读数据会发生什么6.&nbsp;slice&nbsp;len&nbsp;和&nbsp;cap&nbsp;的区别7.&nbsp;slice&nbsp;的扩容8.&nbsp;channel&nbsp;10&nbsp;个数据,读第&nbsp;10&nbsp;个数据的返回值,第&nbsp;11&nbsp;次,这时&nbsp;channel&nbsp;关闭会发生什么9.&nbsp;如何判断一个&nbsp;channel&nbsp;是否是关闭状态10.&nbsp;动态库和静态库的区别11.&nbsp;main&nbsp;函数用了某些&nbsp;so&nbsp;库,进程启动时它是如何找到依赖的动态库的12.&nbsp;堆和栈的区别13.&nbsp;C++&nbsp;局部变量分配在什么地方14.&nbsp;Go&nbsp;局部变量分配在什么地方15.&nbsp;局部变量分配位置的分析在什么阶段完成的16.&nbsp;拷打项目17.&nbsp;程序编译链接过程18.&nbsp;.o&nbsp;文件和&nbsp;.elf&nbsp;文件的区别19.&nbsp;HTTP&nbsp;连接建立过程20.&nbsp;HTTPS&nbsp;加密过程21.&nbsp;TCP&nbsp;三次握手22.&nbsp;SYN&nbsp;洪水攻击23.&nbsp;HTTP1&nbsp;和&nbsp;HTTP2&nbsp;的区别24.&nbsp;HTTP1&nbsp;有什么缺陷25.&nbsp;HTTP&nbsp;连接是怎么被复用的26.&nbsp;keep-alive&nbsp;是怎么实现的27.&nbsp;MySQL&nbsp;有哪些锁、怎么加的、在什么时间段加的28.&nbsp;Docker&nbsp;了解过吗29.&nbsp;平常怎么用&nbsp;git30.&nbsp;怎么知道一个端口是否被监听31.&nbsp;怎么判断远程服务端口是否被监听32.&nbsp;怎么理解递归,它有什么问题33.&nbsp;C++&nbsp;中栈有多大34.&nbsp;怎么解决递归爆栈问题35.&nbsp;用什么命令可以获取域名的&nbsp;ip36.&nbsp;DNS&nbsp;解析过程37.&nbsp;文件&nbsp;A&nbsp;客户端访问&nbsp;ip,文件&nbsp;B&nbsp;为黑名单&nbsp;ip,怎么在文件&nbsp;A&nbsp;中找出不在黑名单中的&nbsp;ip&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;文件&nbsp;A&nbsp;很大、文件&nbsp;B&nbsp;很小&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;文件&nbsp;B&nbsp;也大到内存放不下
点赞 评论 收藏
转发
2 5 评论
分享
牛客网
牛客企业服务