编程面试题

编程面试题

题目一

# 给定一个字符串，编写一个函数判断它是否是回文串。
# 回文串是指正着读和反着读都一样的字符串，忽略大小写和非字母数字字符。

def is_palindrome(s: str) -> bool:
    # 实现你的代码


# 示例测试
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False

答案：

def is_palindrome(s: str) -> bool:
    s = ''.join(filter(str.isalnum, s)).lower()
    return s == s[::-1]

题目二

# 实现一个函数，输入一个整数，输出该整数的二进制表示中 1 的个数。

def count_ones(n: int) -> int:
    # 实现你的代码


# 示例测试
print(count_ones(5))  # 2
print(count_ones(15))  # 4

答案：

def count_ones(n: int) -> int:
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

题目三

# 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

def move_zeros(nums: List[int]) -> None:
    # 实现你的代码


# 示例测试
nums = [0, 1, 0, 3, 12]
move_zeros(nums)
print(nums)  # [1, 3, 12, 0, 0]

答案：

def move_zeros(nums: List[int]) -> None:
    zero_count = nums.count(0)
    nums[:] = [num for num in nums if num != 0]
    nums.extend([0] * zero_count)

题目四

# 给定一个链表，判断链表中是否有环。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head: ListNode) -> bool:
    # 实现你的代码


# 示例测试
head = ListNode(3)
node1 = ListNode(2)
node2 = ListNode(0)
node3 = ListNode(-4)
head.next = node1
node1.next = node2
node2.next = node3
node3.next = node1  # 形成环
print(has_cycle(head))  # True

答案：

def has_cycle(head: ListNode) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

题目五

# 编写一个函数，输入一个整数 n，输出斐波那契数列的第 n 项。

def fibonacci(n: int) -> int:
    # 实现你的代码


# 示例测试
print(fibonacci(0))  # 0
print(fibonacci(1))  # 1
print(fibonacci(5))  # 5

答案：

def fibonacci(n: int) -> int:
    if n <= 1:
        return n

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b

    return b