当前位置:首页 > 问答 > 正文

网友热议:解析几道经典的简单算法题目及其解法

  • 问答
  • 2025-01-26 08:00:38
  • 29
  • 更新:2025-01-26 08:00:38

本文目录导读:

  1. 两数之和
  2. 合并两个有序链表
  3. 判断一个数字是否是2的幂
  4. 阶乘后的零的个数

一、两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标,你可以假设每种输入只会对应一个答案,数组中同一个元素在答案里不能重复出现。

解法

1、暴力解法

- 遍历数组中的每一个数 x,寻找数组中是否存在 target - x。

- 时间复杂度为 O(n^2),n 为数组 nums 的长度。

2、哈希表解法

- 创建一个哈希表,对于每一个 x,首先查询哈希表中是否存在 target - x,然后将 x 插入到哈希表中。

- 时间复杂度为 O(n),n 为数组 nums 的长度。

示例

输入:nums = [2, 7, 11, 15],target = 9

输出:[0, 1]

解释:因为 nums[0] + nums[1] == 9,所以返回 [0, 1]。

二、合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的。

网友热议:解析几道经典的简单算法题目及其解法

解法

1、递归解法

- 如果两个链表中的一个为空,则返回另一个链表。

- 否则,比较两个链表的头节点,将较小的一个节点作为新链表的头节点,并递归地合并两个链表的其余部分。

2、迭代解法

- 创建一个新的链表头节点,以及一个用于遍历新链表的指针。

- 使用两个指针分别遍历两个链表,比较当前节点的值,将较小的节点添加到新链表中,并移动对应链表的指针。

- 当其中一个链表遍历完时,将另一个链表的剩余部分添加到新链表中。

示例

输入:l1 = 1 -> 2 -> 4,l2 = 1 -> 3 -> 4

输出:1 -> 1 -> 2 -> 3 -> 4 -> 4

三、判断一个数字是否是2的幂

题目描述

如何判断一个数字是2的n次方。

解法

利用位运算的性质,一个数是2的幂当且仅当它的二进制表示中只有一位是1,其余位都是0。

可以通过判断 n & (n - 1) 是否等于 0 来判断 n 是否是2的幂,如果等于0,则是2的幂;否则,不是2的幂。

示例

输入:n = 8

输出:true

解释:8是2的3次方,所以返回true。

四、阶乘后的零的个数

题目描述

给定一个数字 n,求 n! 尾数中的 0 的个数。

解法

一个数末尾有0,意味着这个数能被10整除,而10 = 2 * 5,所以问题转化为求 n! 中因子5的个数。

由于在阶乘中,2的个数总是多于5的个数(因为偶数比能被5整除的数多),所以只需计算因子5的个数。

可以通过不断除以5并累加商的方式来计算因子5的个数。

示例

输入:n = 5

输出:1

解释:5! = 120,末尾有1个0。

这些经典的简单算法题目涵盖了数组、链表、位运算和数学等多个方面,通过学习和掌握这些题目的解法,可以提升算法思维和编程能力。