面试编程题刷题~

Author：南岛鹋
发布时间：September 19, 2020
3847 views
One comment
7140 words
Categories： python

题目描述

S和T是两个字符串（它们只由小写字母构成），定义S与T相似当且仅当：
1、S和T长度相同。
2、对于任意两个位置i和j，如果Si和Sj相同，那么Ti和Tj相同；如果Si和Sj不同，那么Ti和Tj不同。（Si的含义为字符串S在第i个位置的字符，Ti的含义为字符串T在第i个位置的字符）
与字符串”abca”相似的串有”abca”,”cdac”,”zetz”等，现在给出一个字符串S，输出与之相似的字典序最小的串。

输入
输入只有一行，一个字符串，长度不超过100000，只由小写字母组成。

样例输入
helloworld

输出
输出一行，与之相似的字典序最小的串（只由小写字母组成的串）。

样例输出
abccdedfcg

data = input()
dict = {}
step = 97
res = ''
for i in data:
    if i not in dict.keys():
        dict[i] = chr(step)
        res += chr(step)
        step += 1
    else:
        res += dict[i]
print(res)

题目描述

大部分论坛、网站等，为了方便管理，都进行了关于敏感词的设定。

在多数网站，敏感词一般是指带有敏感政治倾向、暴力倾向、不健康色彩的词或不文明语，也有一些网站根据自身实际情况，设定一些只适用于本网站的特殊敏感词。比如，当你发贴的时候带有某些事先设定的词时，这个贴是不能发出的。或者这个词被自动替换为星号 (*)，或者说是被和谐掉了。请注意敏感词只有小写字母，文本如果中的大写字母当做小写字母处理，出现敏感单词，即使作为子串出现也要被和谐，多个子串重叠他们都要被和谐。

例如当敏感词是gre，eat 是

Your English is Great.

将被和谐成

Your English is *.

请编程，输入给定的文本和关键字，将所有被和谐的部分都打上星号 (*)

输入

输入的第一行包含一个整数 n，表示敏感词的总数。

接下来的 n 行，每行包含一个长度不超过 100 的敏感词，单词不区分大小写。

接下来的一行包含一段长度不超过 10000的字符串表示待处理的文本。

样例输入

4
revolution
greatwall
democracy
science
Cross the greatwall, we can reach every corner of the world.

输出

输出一行，表示和谐过后的文本。

样例输出

Cross the *, we can reach every corner of the world.

while True:
    num = int(input())
    dis = []
    for i in range(num):
        dis.append(input())
    sentence = input()
    new_sen = []
    for word in dis:
        new_sen.append(sentence.lower().replace(word,len(word)*'*'))
    for n in new_sen:
        for t in range(len(n)):
            if n[t] == '*':
                sentence = sentence[:t] + '*' + sentence[t+1:]
    print(sentence)

题目描述

一队士兵在操场上排成一列，士兵总数为n，士兵按照队伍从前往后的顺序从1到n依次编号。每个士兵有各自的身高，第i个士兵的身高为ai。
士兵列队完毕后，将军走到队列的最前面。因为身高不一，有些士兵可能被前面身高更高的挡住了，这样将军就看不到他们。将军能看到某个士兵当且仅当他的身高严格大于他前面的所有士兵。
问将军一共能看到多少个士兵。

输入
第一行输入一个整数T（T＜=100），表示测试数据的组数。每组数据第一行输入一个数n（1=＜n＜=10000）表示士兵的个数，第二行n个整数a1,a2,...,an（0=＜ai＜=1000000000），依次表示每一个士兵的身高。

样例输入
3
4
1 2 3 4
3
1 1 1
4
1 1 3 2

输出
对于每组数据，输出一行，将军能看到的士兵数。

样例输出
4
1
2

while True:
    group = int(input())
    for i in range(group):
        sum,max = 0,-1
        num = int(input())
        height = input().split()
        for m in range(num):
            if int(height[m]) > max:
                max = int(height[m])
                sum += 1
            else:
                sum,max = sum,max
        print(sum)

分数序列和（百度2017秋招真题）

有一个分数序列 2/1,3/2,5/3,8/5,13/8,21/13,.... 求这个分数序列的前n项之和。

输入
测试数据有多组，其第一行为一个正整数k(0＜k＜=90)，表示测试数据的组数。每组测试数据为一行，为单个正整数n（0＜n＜=90）。

样例输入
1
2

输出
每组测试数据单独输出有一行：分数序列的和（精确到小数点后4位）。

样例输出
3.5000

while True:
    group = int(input())
    for i in range(group):
        num = int(input())
        m,n,sum = 2,1,0
        for t in range(num):
            sum += m/n
            n,m = m,n+m
        print('%.4f'%sum)

题目描述

度度熊收到了一个只有小写字母的字符串S，他对S的子串产生了兴趣，S的子串为S中任意连续的一段。他发现，一些子串只由一种字母构成，他想知道在S中一共有多少种这样的子串。

例如在串”aaabbaa”中，度度熊想找的子串有”a”,”aa”,”aaa”,”b”,”bb”五种。

（本题只考虑子串的种数，相同的子串在多个位置出现只算一次）

输入
输入只有一行，一个字符串，长度不超过100000，只由小写字母组成

样例输入
aaabbaa

输出
输出一行，符合要求的子串种数

样例输出
5

string = input()
str = ''
str1 = ''
res = set()
for i in range(len(string)):
    if string[i] == str1:
        str += string[i]
    else:
        str = string[i]
        str1 = string[i]
    res.add(str)
print(len(res))

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dumy = p = ListNode(None)
        s = 0
        while l1 or l2 or s:
            s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
            p.next = ListNode(s%10)
            p = p.next
            s = s // 10
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dumy.next

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        n = len(s)
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                occ.remove(s[i - 1])
            while rk+1 < n and s[rk+1] not in occ:
                occ.add(s[rk+1])
                rk += 1
            ans = max(ans,rk+1-i)
        return ans

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1.extend(nums2)
        nums1.sort()
        l = len(nums1)
        if l % 2 == 0:
            return (nums1[l//2-1] + nums1[l//2])/2
        else:
            return nums1[(l+1)//2-1]

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size < 2:
            return s
        max_len = 1
        res = s[0]
        for i in range(size):
            js, js_len = self._center(s,size,i,i)
            os, os_len = self._center(s,size,i,i+1)
            max_hw = js if js_len > os_len else os
            if len(max_hw) > max_len:
                max_len = len(max_hw)
                res = max_hw
        return res
    def _center(self,s,size,left,right):
        while left >= 0 and right < size and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right],right-left-1

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G


class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: return s
        res = ["" for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag
        return "".join(res)

Last modification：October 8, 2020

如果觉得我的文章对你有用，请随意赞赏

One comment

list of reputable canadian pharmacies
August 27, 2022

You explained that effectively!

Reply

面试编程题刷题~

南岛鹋 • 2020 年 09 月 19 日

<h2>题目描述</h2>S和T是两个字符串（它们只由小写字母构成），定义S与T相似当且仅当： 1、S和T长度相同。 2、对于任意两个位置i和j，如果Si和Sj相同，那么Ti和Tj相同；如果Si和Sj不同，那么Ti和Tj不同。（Si的含义为字符串S在第i个位置的字符，Ti的含义为字符串T在第i个位置的字符） 与字符串”abca”相似的串有”abca”,”cdac”,”zetz”等，现在给出一个字符串S，输出与之相似的字典序最小的串。输入 输入只有一行，一个字符串，长度不超过100000，只由小写字母组成。样例输入 helloworld输出 输出一行，与之相似的字典序最小的串（只由小写字母组成的串）。样例输出 abccdedfcg<pre><code>data = input()
dict = {}
step = 97
res = ''
for i in data:
 if i not in dict.keys():
 dict[i] = chr(step)
 res += chr(step)
 step += 1
 else:
 res += dict[i]
print(res)

</code></pre><h2>题目描述</h2>大部分论坛、网站等，为了方便管理，都进行了关于敏感词的设定。在多数网站，敏感词一般是指带有敏感政治倾向、暴力倾向、不健康色彩的词或不文明语，也有一些网站根据自身实际情况，设定一些只适用于本网站的特殊敏感词。比如，当你发贴的时候带有某些事先设定的词时，这个贴是不能发出的。或者这个词被自动替换为星号 (*)，或者说是被和谐掉了。请注意敏感词只有小写字母，文本如果中的大写字母当做小写字母处理，出现敏感单词，即使作为子串出现也要被和谐，多个子串重叠他们都要被和谐。例如当敏感词是gre，eat 是Your English is Great.将被和谐成Your English is *.请编程，输入给定的文本和关键字，将所有被和谐的部分都打上星号 (*)输入输入的第一行包含一个整数 n，表示敏感词的总数。接下来的 n 行，每行包含一个长度不超过 100 的敏感词，单词不区分大小写。接下来的一行包含一段长度不超过 10000的字符串表示待处理的文本。样例输入4 revolution greatwall democracy science Cross the greatwall, we can reach every corner of the world.输出输出一行，表示和谐过后的文本。样例输出Cross the *, we can reach every corner of the world.<pre><code>while True:
 num = int(input())
 dis = []
 for i in range(num):
 dis.append(input())
 sentence = input()
 new_sen = []
 for word in dis:
 new_sen.append(sentence.lower().replace(word,len(word)*'*'))
 for n in new_sen:
 for t in range(len(n)):
 if n[t] == '*':
 sentence = sentence[:t] + '*' + sentence[t+1:]
 print(sentence)
</code></pre><h2>题目描述</h2>一队士兵在操场上排成一列，士兵总数为n，士兵按照队伍从前往后的顺序从1到n依次编号。每个士兵有各自的身高，第i个士兵的身高为ai。 士兵列队完毕后，将军走到队列的最前面。因为身高不一，有些士兵可能被前面身高更高的挡住了，这样将军就看不到他们。将军能看到某个士兵当且仅当他的身高严格大于他前面的所有士兵。 问将军一共能看到多少个士兵。输入 第一行输入一个整数T（T＜=100），表示测试数据的组数。每组数据第一行输入一个数n（1=＜n＜=10000）表示士兵的个数，第二行n个整数a1,a2,...,an（0=＜ai＜=1000000000），依次表示每一个士兵的身高。样例输入 3 4 1 2 3 4 3 1 1 1 4 1 1 3 2输出 对于每组数据，输出一行，将军能看到的士兵数。样例输出 4 1 2<pre><code>while True:
 group = int(input())
 for i in range(group):
 sum,max = 0,-1
 num = int(input())
 height = input().split()
 for m in range(num):
 if int(height[m]) &gt; max:
 max = int(height[m])
 sum += 1
 else:
 sum,max = sum,max
 print(sum)
</code></pre><h2>分数序列和（百度2017秋招真题）</h2>有一个分数序列 2/1,3/2,5/3,8/5,13/8,21/13,.... 求这个分数序列的前n项之和。输入 测试数据有多组，其第一行为一个正整数k(0＜k＜=90)，表示测试数据的组数。每组测试数据为一行，为单个正整数n（0＜n＜=90）。样例输入 1 2输出 每组测试数据单独输出有一行：分数序列的和（精确到小数点后4位）。样例输出 3.5000<pre><code>while True:
 group = int(input())
 for i in range(group):
 num = int(input())
 m,n,sum = 2,1,0
 for t in range(num):
 sum += m/n
 n,m = m,n+m
 print('%.4f'%sum)

</code></pre><h2>题目描述</h2>度度熊收到了一个只有小写字母的字符串S，他对S的子串产生了兴趣，S的子串为S中任意连续的一段。他发现，一些子串只由一种字母构成，他想知道在S中一共有多少种这样的子串。例如在串”aaabbaa”中，度度熊想找的子串有”a”,”aa”,”aaa”,”b”,”bb”五种。（本题只考虑子串的种数，相同的子串在多个位置出现只算一次）输入 输入只有一行，一个字符串，长度不超过100000，只由小写字母组成样例输入 aaabbaa输出 输出一行，符合要求的子串种数样例输出 5<pre><code>string = input()
str = ''
str1 = ''
res = set()
for i in range(len(string)):
 if string[i] == str1:
 str += string[i]
 else:
 str = string[i]
 str1 = string[i]
 res.add(str)
print(len(res))
</code></pre>给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：输入：(2 -&gt; 4 -&gt; 3) + (5 -&gt; 6 -&gt; 4) 输出：7 -&gt; 0 -&gt; 8 原因：342 + 465 = 807<pre><code>class Solution:
 def addTwoNumbers(self, l1: ListNode, l2: ListNode) -&gt; ListNode:
 dumy = p = ListNode(None)
 s = 0
 while l1 or l2 or s:
 s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
 p.next = ListNode(s%10)
 p = p.next
 s = s // 10
 l1 = l1.next if l1 else None
 l2 = l2.next if l2 else None
 return dumy.next
</code></pre>给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。<pre><code>class Solution:
 def lengthOfLongestSubstring(self, s: str) -&gt; int:
 occ = set()
 n = len(s)
 rk, ans = -1, 0
 for i in range(n):
 if i != 0:
 occ.remove(s[i - 1])
 while rk+1 &lt; n and s[rk+1] not in occ:
 occ.add(s[rk+1])
 rk += 1
 ans = max(ans,rk+1-i)
 return ans
</code></pre>给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 示例 1：输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2<pre><code>class Solution:
 def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -&gt; float:
 nums1.extend(nums2)
 nums1.sort()
 l = len(nums1)
 if l % 2 == 0:
 return (nums1[l//2-1] + nums1[l//2])/2
 else:
 return nums1[(l+1)//2-1]

</code></pre>给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：输入: "cbbd" 输出: "bb"<pre><code>class Solution:
 def longestPalindrome(self, s: str) -&gt; str:
 size = len(s)
 if size &lt; 2:
 return s
 max_len = 1
 res = s[0]
 for i in range(size):
 js, js_len = self._center(s,size,i,i)
 os, os_len = self._center(s,size,i,i+1)
 max_hw = js if js_len &gt; os_len else os
 if len(max_hw) &gt; max_len:
 max_len = len(max_hw)
 res = max_hw
 return res
 def _center(self,s,size,left,right):
 while left &gt;= 0 and right &lt; size and s[left] == s[right]:
 left -= 1
 right += 1
 return s[left+1:right],right-left-1
</code></pre>将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：<pre><code>L C I R
E T O E S I I G
E D H N
</code></pre>之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows); 示例 1:输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN" 示例 2:输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG" 解释:<pre><code>L D R
E O E I I
E C I H N
T S G

class Solution:
    def convert(self, s: str, numRows: int) -&gt; str:
        if numRows &lt; 2: return s
        res = [&quot;&quot; for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag
        return &quot;&quot;.join(res)

</code></pre>

面试编程题刷题~

题目描述

题目描述

题目描述

分数序列和（百度2017秋招真题）

题目描述

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

One comment

网站标题动态改变，js代码实现

删除WeTypecho插件后，控制台选项存在残留

自制一个简易的随机图片API接口

cute-cnblogs —— 一个好看的博客园魔改主题

百度网盘网页版看考研视频倍速播放

typecho文章内挂载B站视频

网站标题动态改变，js代码实现

哔哩哔哩视频页视频详细信息采集（三连、播放量、标签）(第一版）

百度网盘网页版看考研视频倍速播放

利用rsync写脚本实现多节点多服务器文件一键同步

面试编程题刷题~

题目描述

题目描述

题目描述

分数序列和（百度2017秋招真题）

题目描述

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

One comment

面试编程题刷题~

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款