python算法面试题(一)

Bertha 。 2024-04-05 07:34 31阅读 0赞

![在这里插入图片描述][642029a9a3fd460ea77e9e095acbe7fc.jpeg_pic_center]

--------------------

## 1、给定一个包含红色、白色和蓝色、共n 个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色；必须在不使用库的sort函数的情况下解决这个问题。（解决：冒泡排序、选择排序） ##

### 不能是快速排序，因为快速排序改变了内存地址 ###

### 选择排序 ###

def select(nums):
        n=len(nums)
        for i in range(n):
            min_idx=i
            for j in range(i+1,n):
                if nums[j]<nums[min_idx]:
                    min_idx=j
    
            nums[i],nums[min_idx]=nums[min_idx],nums[i]
    test=[4,6,3,8,1,2,5]
    select(test)
    print(test)

## 冒泡排序 ##

def mappao(nums):
        n=len(nums)
        for i in range(n-1):
            flag=False
            for j in range(0,n-1-i):
                if nums[j]>nums[j+1]:
                    nums[j],nums[j+1]=nums[j+1],nums[j]
                    flag=True
            if not flag:
                break
    
    test=[4,6,3,8,1,2,5]
    mappao(test)
    print(test)

--------------------

## 2、编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 ##

def solution(nums):
        n=len(nums)
        i=0
        while i<n//2:
            s[i],s[n-i-1]=s[n-i-1],s[i]
            i+=1
    
    s = ["h","e","l","l","o"]
    solution(s)
    print(s)

--------------------

## 3、给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。 ##

class Solution:
        def __init__(self,s,k):
            self.s=s
            self.k=k
    
        def topKFrequent(self):
            d={
        }
            for item in self.s:
                if item not in d:
                    d[item]=1
                else:
                    d[item]+=1
            return d
    
    
        def topKFrequent1(self):
            d=self.topKFrequent()
            d1 = sorted(d.items(), key=lambda x: x[1],reverse=True)
    
            d2={
        }
            for i in d1[0:self.k]:
                d2[i[0]]=i[1]
            return d2
    
        def topKFrequent2(self):
            d2=self.topKFrequent1()
            l=list(d2.keys())
            return l
    
    s=['o', 'l', 'l', 'e', 'h']
    res=Solution(s,2)
    print(res.topKFrequent2())

--------------------

## 4、给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。 ##

> 输入: s = “leetcode”  
> 输出: 0

> 输入: s = “loveleetcode”  
> 输出: 2

> 输入: s = “aabb”  
> 输出: -1

def demo2(str1):
        #str=''
        for i in str1:
            if i not in str1[str1.index(i)+1:]:
                return str1.index(i)
        else:
            return -1
    
    s = "aabb"
    res=demo2(s)
    print(res)

--------------------

## 5、给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 ##

> 输入：nums = \[2,7,11,15\], target = 9  
> 输出：\[0,1\]  
> 解释：因为 nums\[0\] + nums\[1\] == 9 ，返回 \[0, 1\] 。

def demo4(nums,target):
        nums1=[]
        for i in nums:
            if i<target:
                nums1.append(i)
    
        n=len(nums1)
        for j in range(n):
            for z in range(n-1):
                if nums1[j]+nums1[z]==target:
                    return [z,j]
    nums=[2,7,11,15,30,35]
    res=demo4(nums,45)
    print(res)

--------------------

## 6、给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。 ##

> 有效字符串需满足：  
> 左括号必须用相同类型的右括号闭合。  
> 左括号必须以正确的顺序闭合。  
> 每个右括号都有一个对应的相同类型的左括号。

class Solution:
    
        def isValid(self, s):
            dic = {
        '{': '}', '[': ']', '(': ')', '?': '?'}
            stack = ['?']
            for c in s:
                if c in dic:
                    stack.append(c)
                elif dic[stack.pop()]!=c:
                    return False
            print(stack)
            return len(stack)==1
    
    
    res=Solution()
    #s = "()"
    s = "()[]{}"
    #s = "(]"
    print(res.isValid(s))

## 7、给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 ##

> 输入：nums = \[3,2,2,3\], val = 3  
> 输出：2, nums = \[2,2\]

> 输入：nums = \[0,1,2,2,3,0,4,2\], val = 2  
> 输出：5, nums = \[0,1,4,0,3\]

def demo5(nums,target):
        print(id(nums))
        for i in nums:
    
            if i==target:
                nums.remove(target)
        return len(nums),nums
    
    nums = [3,2,2,3]
    val = 3
    len,nums=demo5(nums,val)
    print(len,nums)
    print(id(nums))

2898355569792  
2 \[2, 2\]  
2898355569792

## 8、给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。 ##

> 输入：haystack = “hello”, needle = “ll”  
> 输出：2

class Solution:
        def strStr(self, haystack,needle):
            if needle is None:
                return 0
            for i in haystack:
                if i==needle[0]:
                    return haystack.index(i)
            else:
                return -1
    
    s=Solution()
    haystack = "hello"
    needle = "ll"
    haystack = "aaaaa"
    needle = "bba"
    res=s.strStr(haystack,needle)
    print(res)

## 9、给定一个不含重复数字的数组nums ，返回其所有可能的全排列 。你可以 按任意顺序 返回答案。 ##

> 示例 1：  
> 输入：nums = \[1,2,3\]  
> 输出：\[\[1,2,3\],\[1,3,2\],\[2,1,3\],\[2,3,1\],\[3,1,2\],\[3,2,1\]\]

> 示例 2：  
> 输入：nums = \[0,1\]  
> 输出：\[\[0,1\],\[1,0\]\]

> 示例 3：  
> 输入：nums = \[1\]  
> 输出：\[\[1\]\]

import itertools
    def permute(nums):
        return list(itertools.permutations(nums))
    nums = [1,2,3]
    print(permute(nums))

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

## 10、给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。 ##

> 示例 1:  
> 输入: strs = \[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”\]  
> 输出: \[\[“bat”\],\[“nat”,“tan”\],\[“ate”,“eat”,“tea”\]\]  
> 示例 2:

> 输入: strs = \[“”\]  
> 输出: \[\[“”\]\]  
> 示例 3:

> 输入: strs = \[“a”\]  
> 输出: \[\[“a”\]\]

class Solution:
        def groupAnagrams(self, strs):
            res=[]
            dic={
        }
            for s in strs:
                keys="".join(sorted(s))
                if keys not in dic:
                    dic[keys]=[s]
                else:
                    dic[keys].append(s)
            return list(dic.values())
    s=Solution()
    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    res=s.groupAnagrams(strs)
    print(res)

\[\[‘eat’, ‘tea’, ‘ate’\], \[‘tan’, ‘nat’\], \[‘bat’\]\]

## 11、反转字符串中的单词 ##

> 输入：s = “the sky is blue”  
> 输出：“blue is sky the”  
> 示例 2：

> 输入：s = " hello world "  
> 输出：“world hello”  
> 解释：反转后的字符串中不能存在前导空格和尾随空格。  
> 示例 3：

> 输入：s = “a good example”  
> 输出：“example good a”  
> 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

def demo7(strs):
        li=strs.split(" ")[::-1]
        li1 = []
        print(li)
        for item in li:
            if bool(item) is not False:
                li1.append(item)
    
        l=' '.join(li1)
        return l
    res=demo7(s)
    print(res)

## 12、给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 ##

> 输入: nums = \[1,2,3,4,5,6,7\], k = 3  
> 输出: \[5,6,7,1,2,3,4\]  
> 解释:  
> 向右轮转 1 步: \[7,1,2,3,4,5,6\]  
> 向右轮转 2 步: \[6,7,1,2,3,4,5\]  
> 向右轮转 3 步: \[5,6,7,1,2,3,4\]

def demo8(nums,k):
        j=0
        while j<k:
            nums.insert(0,nums[-1])
            nums.pop(-1)
            j+=1
        return nums
    
    nums = [1,2,3,4,5,6,7]
    k = 3
    res=demo8(nums,k)
    print(res)

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

[642029a9a3fd460ea77e9e095acbe7fc.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/84627e367b7249ab91508cfe28a7e443.jpeg