快手2019春招筆試程式設計題

• • 第一題
  • • 輸入描述
    • 輸出描述
    • 分析
    • 代碼
  • 第二題
  • • 輸入描述
    • 輸出描述
    • 分析
    • 代碼
  • 第三題
  • • 輸入描述
    • 輸出描述
    • 分析
    • 代碼

個人首頁：http://redtongue.cn or https://redtongue.github.io/

筆試時間為2019年4月13日，包括35道單選題、15道多選題、三道程式設計題。程式設計題如下：

第一題

給定兩個字元串，請編寫代碼，輸出最長公共字串（Longest Common Substring）,是指兩個字元串中的最長公共字串，要求字串一定是連續的。

輸入描述

文本格式，2個非空字元串（字母數字組成）,2個字元串以‘，’英文逗号分隔，字元串長度小于等于100
           

輸出描述

整形，為比對到的最長字串長度
           

分析

代碼

if __name__ == "__main__":
    a,b=list(input().split(','))
    m=0
    for i in range(len(a)):
        for j in range(len(b)):
            ii=i
            jj=j
            while(ii<len(a) and jj < len(b) and a[ii]==b[jj]):
                ii+=1
                jj+=1
            m=max(m,jj-j)
    print(m)
           

第二題

從0,1,2,…,n這n+1個數中選擇n個數，找出這n個數中缺失的那個數，要求O(N)盡可能的小。

輸入描述

給定一個以逗号（，）分割的數字串
           

輸出描述

輸出缺失的數字
           

分析

代碼

第三題

給定

輸入描述

第一行一個整數t（1<=t<=5），表示測試用例組數。
對于每組測試用例：
第一行兩個用空格隔開的整數n和m（1<=n,m<=100000），分别表示團體個數和關系數量。
接下來一行n個用空格隔開的數，第i個數表示val[i]。
接下來m行，每行三個用空格隔開的整數u,v和cost(u,v)（1<=u,v<=n,1<=val[i],cost(u,v)<=20000）
           

輸出描述

輸出
           

分析

代碼

import sys 
for line in sys.stdin:
    A=set(map(int,line.split(',')))
    s=sum(A)
    print(len(A)*(len(A)+1)//2-s)