您现在的位置是:首页 > 正文

算法题

2024-04-01 07:35:18阅读 1

1,快速排序

题目形式:手写一下快速排序算法。

 

题目难度:中等。

 

出现概率:约50%。手写快排绝对是手撕代码面试题中的百兽之王,掌握了它就是送分题,没有掌握它就是送命题。

 

参考代码:

 

def quick_sort(arr,start=0,end=None):
    if end is None:
        end = len(arr)-1
    if end<=start:
        return(arr)
    i,j = start,end
    ref = arr[start]
    while j>i:
        if arr[j]>= ref:
            j = j - 1
        else:
            # 此处使用一行语句交换3个元素的值
            arr[i],arr[j],arr[i+1] = arr[j],arr[i+1],arr[i]
            i = i + 1
    quick_sort(arr,start=start,end = i-1)
    quick_sort(arr,start=i+1,end = end)
    return(arr)

print(quick_sort([1,1,3,3,2,2,6,6,6,5,5,7]))

 

输出结果:

[1, 1, 2, 2, 2, 3, 5, 5, 6, 6, 6, 7]

 

2,二分查找

题目形式:手写一下二分查找算法。给定一个有序数组 arr 和一个目标元素 target ,返回该 target 在 arr 中的索引,若不存在,返回-1。

 

题目难度:简单。

 

出现概率:约30%。二分查找绝对是手写代码题中的百兽之后,没有妃子可以和她争宠。连个二分查找都写不出来,还来应聘程序员,你是不是对程序员这个职业有什么误解?

 

参考代码:

 

def binary_search(arr,target):
    start,end = 0,len(arr)-1
    while True:
        if end - start <=1:
            if target == arr[start]:
                return(start)
            elif target == arr[end]:
                return(end)
            else:
                return(-1)

        mid = (start + end)//2
        if arr[mid]>=target:
            end = mid
        else:
            start = mid

print(binary_search([1,4,7,8,9,12],9))
print(binary_search([1,4,7,8,9,12],3))

 

输出结果:

4-1

 

3,爬楼梯

题目形式:有一个楼梯,总共有10级台阶,每次只能走一级或者两级台阶,全部走完,有多少种走法?

 

题目难度:简单。

 

出现概率:约20%。爬楼梯问题是手写代码题中的百兽之豹。爬楼梯问题可以用递归来解决,但是如果考虑到时间复杂度,最好用动态规划的思想来处理,这是一个动态规划算法的教科书级别的案例。连个楼梯都爬不明白,这个算法基础令人堪忧啊!

 

参考代码:

 

def climb_stairs(n):
    if n==1:
        return 1
    if n==2:
        return 2
    a,b = 1,2
    i = 3
    while i<=n:
        a,b = b,a+b
        i +=1
    return b

print(climb_stairs(10))

 

输出结果:

89

 

4,两数之和

题目形式:寻找列表中满足两数之和等于目标值的元素的下标。例如:arr = [2,7,4,9],target = 6  则返回 [0,2],若不存在,返回空列表[]。

 

题目难度:简单。

 

出现概率:约20%。两数之和是手写代码题中的百兽之狼。两数之和问题考察候选人对哈希表可以用空间换取时间这个特性的理解。哎呦喂,写个两数之和还整上两重循环了,你这时间复杂度是多少啊?

 

参考代码:

 

def sum_of_two(arr,target):
    dic = {}
    for i,x in enumerate(arr):
        j = dic.get(target-x,-1)
        if j != -1:
            return((j,i))
        else:
            dic[x] = i
    return([])

arr = [2,7,4,9]
target = 6
print(sum_of_two(arr,target))

 

输出结果:

(0, 2)

 

5,最大回撤

题目形式:有一个数组,求其中两个数x,y,满足x的索引小于y的索引,使得 x-y 最大。例如 arr = [3,7,2,6,4,1,9,8,5], 最大回撤是6,对应的x=7,y=1。

 

题目难度:中等。

 

出现概率:约20%。这道题目可能以买卖股票的最佳时机,或者最大抬升等各种形式出现,这也是一道动态规划的史诗级范例。呦呵,又整上两重循环了,这循环写的很可以啊。

 

参考代码:

 

def max_drawdown(arr):
    assert len(arr)>2, "len(arr) should > 2!"
    x,y = arr[0:2]
    xmax = x
    maxdiff = x-y

    for i in range(2,len(arr)):
        if arr[i-1] > xmax:
            xmax = arr[i-1]
        if xmax - arr[i] > maxdiff:
            maxdiff = xmax - arr[i]
            x,y = xmax,arr[i]

    print("x=",x,",y=",y)
    return(maxdiff)

print(max_drawdown([3,7,2,6,4,1,9,8,5]))

 

输出结果:

x= 7 ,y= 16

 

6,合并两个有序数组

题目形式:给定两个按升序排列的有序数组,将它们合并成一个新的有序数组。例如:a = [1,2,6,8], b = [2,4,7,10],输出为 arr = [1,2,2,4,6,7,8,10]

 

题目难度:简单。

 

出现概率:约15%。这道题目考察的是归并排序的基本思想。注意,这两个数组是有序的呢,你怎么可以无视这么有利的条件直接拼接上两个数组开始冒泡了???

 

参考代码:

 

def merge_sorted_array(a,b):
    c = []
    i,j = 0,0
    while True:
        if i==len(a):
            c.extend(b[j:])
            return(c)
        elif j==len(b):
            c.extend(a[i:])
            return(c)
        else:
            if a[i]<b[j]:
                c.append(a[i])
                i=i+1
            else:
                c.append(b[j])
                j=j+1

print(merge_sorted_array([1,2,6,8],[2,4,7,10]))

 

输出结果:

[1, 2, 2, 4, 6, 7, 8, 10]

 

7,最大连续子数组和

题目形式:给定一个数组,求其最大连续子数组的和。例如:arr = [1,5,-10,2,5,-3,2,6,-3,1].  输出为:12。对应的连续子数组为 [2,5,-3,2,6]。

 

题目难度:中等。

 

出现概率:约15%。这道题目也是一道动态规划的祖传范例。同学,你的这个两重循环写的确实很6,但是我们不能认为你的这道题目做对了!

 

参考代码:

 

def max_sub_array(arr):
    n = len(arr)
    maxi,maxall = arr[0],arr[0]
    for i in range(1,n):
        maxi = max(arr[i],maxi + arr[i])
        maxall = max(maxall,maxi)
    return(maxall)

print(max_sub_array([1,5,-10,2,5,-3,2,6,-3,1]))

 

输出结果:

12

 

8,最长不重复子串

题目形式:给定一个字符串,找出没有重复字符的最长的子串。例如输入“abcbefgf”,答案是 “cbefg”。

 

题目难度:困难。

 

出现概率:约10%。这是一道动态规划+哈希查找的综合应用题。这道题能做出来,你的代码功底很可以啊。对了,你的期望薪资是多少?

 

参考代码:

 

def longest_substr(s):    
    dic = {}
    start,maxlen,substr = 0,0,""

    for i,x in enumerate(s):
        if x in dic:
            start = max(dic[x]+1,start)
            dic[x] = i   
        else:
            dic[x] = i

        if i-start+1>maxlen:
            maxlen = i-start+1
            substr = s[start:i+1]
    return(substr)

print(longest_substr("abcbefgf"))
print(longest_substr("abcdef"))
print(longest_substr("abbcddefh"))

 

输出结果:

cbefgabcdefdefh

 

9,全排列

题目形式:给定一个数组,找出其所有可能的排列。例如: arr = [1,1,3],输出为 [[1,1,3],[1,3,1],[3,1,1]]。

 

题目难度:中等

 

出现概率:约10%。这是一道动态规划+排列组合的综合应用题。同学,你这里用递归的话你的这个时间复杂度得有多少?我们这个数组一旦有几十个元素的话,你这还能跑得动吗?

 

参考代码:

 

import numpy as np 
def permutations(arr):
    if len(arr)<=1:
        return([arr])
    t = [arr[0:1]]
    i = 1
    while i<=len(arr)-1:
        a = arr[i]
        t = [xs[0:j]+[a]+xs[j:] for xs in t for j in range(i+1)]
        t = np.unique(t,axis=0).tolist()
        i = i+1
    return(t)
print(permutations([1,1,3]))

 

输出结果:

[[1, 1, 3], [1, 3, 1], [3, 1, 1]]

 

10,三数之和

题目形式:给定一个数组和目标数target,找出数组中a,b,c满足 a+b+c = target 的所有组合。例如:arr = [-3,-1,-2,1,2,3],target = 0。输出为 [(-3,1,2),(-2,-1,3)]

 

题目难度:困难

 

出现概率:约5%。这是一道非常有技巧的题目。你可以尝试先将arr排序。注意,我们的时间复杂度要求为O(n**2) ,空间复杂度要求O(1),对,就是这么严格,你要好好想想……哟,有思路啦……emmm……大体上符合要求……同学,你现在手上还有其他家的offer吗?

 

参考代码:

 

def sum_of_three(arr,target):
    assert len(arr)>=3,"len(arr) should >=3!"
    arr.sort()
    ans = set()
    for k,c in enumerate(arr):
        i,j = k+1,len(arr)-1
        while i<j:
            if arr[i]+arr[j]+c <target:
                i = i+1
            elif arr[i]+arr[j]+c > target:
                j = j-1
            else:
                ans.update({(arr[k],arr[i],arr[j])})
                i = i+1
                j = j-1
    return(list(ans))

print(sum_of_three([-3,-1,-2,1,2,3],0))

 

输出结果:

[(-2, -1, 3), (-3, 1, 2)]

转载于:https://www.cnblogs.com/HHR-SUN/p/11566601.html

网站文章

  • 如何进行python函数参数的传递?

    之前跟大家已经说过了的函数参数,以及路径传递方式,这样大家是否进行联系起来了呢?因为我们的编写内容是个活水,需要我们源源不断的往下流淌,因此关于传递这块内容,大家一定要跟着小编好好学习接下来的内容哦~...

    2024-04-01 07:34:53
  • 剑指offer-数组中重复的数字

    题目描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为...

    2024-04-01 07:34:46
  • Makefile教程

    Makefile教程

    Makefile教程实例一​ 我们刚开始学习使用Linux编译c代码,一般都是使用gcc进行编译,如下:test.c#include <stdio.h>int main(){ printf("Hell...

    2024-04-01 07:34:37
  • js清空fckeditor的值。

    FCKeditorAPI.GetInstance('FCKeditor1').EditorDocument.body.innerHTML = "";

    2024-04-01 07:34:31
  • 计算机学院李成伟,河南科技学院校长李成伟一行看望慰问我院招生录取工作人员...

    计算机学院李成伟,河南科技学院校长李成伟一行看望慰问我院招生录取工作人员...

    7月27日上午,河南科技学院校长李成伟、校长办公室主任张彦军等一行在新科学院院长刘鸣韬,副院长张传来、张宝剑、姚素梅的陪同下,来到我院远程网上录取现场,看望慰问工作人员,检查指导招生录取工作。在录取工...

    2024-04-01 07:34:06
  • [图文] Seata AT 模式分布式事务源码分析

    [图文] Seata AT 模式分布式事务源码分析

    推荐阅读 Seata TCC 分布式事务源码分析公众号 Young_Blog什么是 Seata AT 模式Seata AT 的使用方法第一步,增加全局事务注解第二步,配置代理数据源第三步,新建 undo_log 表Seata AT 的工作流程工作流程总览图解 AT 模式一阶段流程图解二阶段 Commit 流程图解二阶段 Rollback 流程本节小结...

    2024-04-01 07:33:57
  • 去除字符串中的中文 最新发布

    上述代码中,首先定义了一个字符串 str,表示需要处理的字符串。第一次替换使用了正则表达式 [\u4e00-\u9fa5]+,表示匹配任意一个中文字符,并将它们替换为一个空格。第二次替换使用了同样的正...

    2024-04-01 07:33:50
  • 计算机毕业设计django基于python的高校奖学金管理系统(源码+系统+mysql数据库+Lw文档)

    计算机毕业设计django基于python的高校奖学金管理系统(源码+系统+mysql数据库+Lw文档)

    随着互联网时代的到来,同时计算机网络技术高速发展,网络管理运用也变得越来越广泛。因此,建立一个B/S结构的高校奖学金管理系统:高校奖学金管理系统的管理工作系统化、规范化,也会提高平台形象,提高管理效率...

    2024-04-01 07:33:23
  • 使用NFS在多台Linux主机之间共享文件夹

    使用NFS在多台Linux主机之间共享文件夹

    需求 如下图,上传更新文件到在1号机器上的指定陌路上,剩下的所有的机器会自动同步更新到自己本地 NFS定义 NFS是基于UDP/IP协议的应用,其实现主要是采用远程过程调用RPC机制,RPC提供了一组...

    2024-04-01 07:33:16
  • 零拷贝技术(DMA、MMAP、sendfile)

    零拷贝技术(DMA、MMAP、sendfile)

    上述操作多次的上下文切换与拷贝会影响性能。可以使用零拷贝技术mmap+writesendfile和splice来优化。

    2024-04-01 07:33:08