0113腾讯一面

150分钟四道手撕代码
1、设定如下的对应关系( A=1,B=2,C=3,...,Z=26,AA=27,AB=28,...,AAA=xxx,... )，
编写一个转换函数，根据上面的规则把一个字符串转换为数字
实现函数：
int StrToInt( const char * str );

def change(s):
    #相当于26进制求和
    ans=0
    for i in s:
        ans=26*ans+ord(i)-ord('A')+1
    return ans

print(change('AB'))

2、倒转单链表（在原链表上倒转）
struct LinkNode {
int value;
struct LinkNode * next;
};

实现函数：
struct LinkNode * reverseList( struct LinkNode * head );

class Node:
    def __init__(self,x):
        self.val=x
        self.next= None

class solution:
    def reverse(head:Node):
        dummy=Node(-1)
        dummy.next=head
        prev=dummy
        curr=head
        while curr:
            # 缓存curr的后驱节点
            tmp=curr.next
            # 反转currnext的指向
            curr.next=prev
            # 把prev和curr移到下一位
            prev=curr
            curr=tmp
        return dummy.next

3、给定一个数组，要求找出第二大的数并返回
int findSecond(int array[], int size);

def find(input,i,j):
    #以当前i位置为基准数，把大于input[i]的放在左边 小的放右边
    # ij分别为子段的首末两个idx
    x=input[i]
    while i<j:
        while i<j and input[j]<x:
            j-=1
        if i<j:
            input[i]=input[j]
            i+=1
        while i<j and input[i]>=x:
            i+=1
        if i<j:
            input[j]=input[i]
            j-=1
    return i

def findSecond(input):
    n=len(input)
    if n<2:
        return -1
    i=0
    j=n-1
    while True:
        #找到input[i]在序列中排第几大
        k=find(input,i,j)
        print(input)
        ##二分法缩小查找区间
        # mid=(i+j+1)//2
        #如果k大于2 说明它input[i]比第二大的数小，要从k左侧的数继续找
        #第二大的idx对应为2-1
        if k>2-1:
            j=k-1
        elif k<2-1:
            i=k+1
        else:
            return input[k]
print(findSecond([5,5,3,4,3,6]))

4、最长的彩虹子序列
彩虹子序列这样定义：
1）序列中有一个最大值
2）最大值的左边子序列严格递增
3）最大值的右边子序列严格递减
注意：子序列不一定连续

struct Result {
int len; // 序列的长度
};
实现函数：
int rainBow(int array[], int size, struct Result * result);

# 分两步 第一步从左往右找最长上升子序列 第二部从右往左找最长上升子序列（相当于把原序列反转）


def findLLongestAscend(array):
    #dp[i]存储array[0:i+1]序列中最长上升子序列的长度
    dp=[0]*len(array)
    dp[0]=1
    for i in range(1,len(array)):
        # 遍历当前位置i之前的
        for j in range(i):
            # 如果之前的有比当前array[i]小的话
            if array[j]<array[i]:
                #更新当前dp[i]的值
                dp[i]=max(dp[i],dp[j]+1)
    return dp

def find(input):
    dp1=findLLongestAscend(input)
    print(dp1)
    dp2=findLLongestAscend(input[::-1])
    dp2=dp2[::-1]
    print(dp2)
    ans=0
    for i in range(len(input)):
        #这里要-1 不然就把自己多算了一次
        ans=max(dp1[i]+dp2[i]-1,ans)
    return ans

print(find([1,2,3,2,1]))

5、项目相关
6、机器学习理论：提升树、残差神经网络中残差块的作用、bagging和boosting的区别
7、计算机基础知识
static函数、 UT8和UNICODE的区别、进程线程区别、虚函数在编译层面是怎么实现的；UDP和TCP的区别、三次握手和四次挥手

0113腾讯一面

全站热榜