偏门网站建设,零基础免费学编程,网站商城微信支付接口,护卫神 安装wordpress本文章以python为例!
一、力扣第1281题#xff1a;整数的各位积和之差
问题描述#xff1a;
1281. 整数的各位积和之差
给你一个整数 n#xff0c;请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
示例 1#xff1a;
输入#xff1a;n 234
输出…本文章以python为例!
一、力扣第1281题整数的各位积和之差
问题描述
1281. 整数的各位积和之差
给你一个整数 n请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
示例 1
输入n 234
输出15
解释
各位数之积 2 * 3 * 4 24
各位数之和 2 3 4 9
结果 24 - 9 15
示例 2
输入n 4421
输出21
解释
各位数之积 4 * 4 * 2 * 1 32
各位数之和 4 4 2 1 11
结果 32 - 11 21
提示
1 n 10^5 解题思路把n的数值转换为字符串然后分成一个一个的方便逐位处理。然后逐个遍历最后用乘积减去和返回结果。
算法描述
初始化两个变量 x 和 y 分别为1和0用来分别表示各位数字之积和各位数字之和。
将整数 n 转换为字符串 a方便逐位处理。
遍历字符串 a 中的每个字符每次迭代都执行以下步骤 a. 将当前字符转换为整数 s。 b. 计算 x * s将当前字符的值与 x 相乘更新各位数字之积。 c. 计算 y s将当前字符的值与 y 相加更新各位数字之和。
循环结束后计算 result x - y得到各位数字之积与各位数字之和的差值。
返回 result 作为最终结果。
时间复杂度分析
这个算法的时间复杂度取决于整数 n 的位数设 n 有 k 位数字。因为需要将 n 转换成字符串并且对每个位上的数字进行遍历所以时间复杂度为 O(k)。
题解
class Solution:def subtractProductAndSum(self, n: int) - int:x1y0astr(n)for b in a:sint(b)x*sysresultx-yreturn result 讨论与总结
这是一道较为简单的算法题目很容易就有解题思路但是用的是python习惯了c语言的代码编程有点不适应经过这道题目初步掌握了python的一些基础代码。 - 力扣提交结果截图贴到答案框截图应该能看到你的代码以及提交记录 二、力扣面试题 01.01. 判定字符是否唯一
题目
实现一个算法确定一个字符串 s 的所有字符是否全都不同。
示例 1
输入: s leetcode
输出: false 示例 2
输入: s abc
输出: true限制
0 len(s) 100 s[i]仅包含小写字母如果你不使用额外的数据结构会很加分。
方法一
解题方法
利用set特性去重再与原字符串比较长度是否相等。
class Solution:def isUnique(self, astr: str) - bool:return len(set(astr)) len(astr)
这段代码的工作原理 class Solution:这行代码定义了一个名为Solution的类。这个类通常用于封装解决特定问题的方法和功能。 def isUnique(self, astr: str) - bool:这是Solution类中的一个方法定义。它声明了一个名为isUnique的方法接受一个参数astr该参数是一个字符串并且返回一个布尔值- bool表示返回值类型为布尔型。 return len(set(astr)) len(astr)这是isUnique方法的实现。它使用了Python中的一些内置函数和数据结构来判断字符串中的字符是否都是唯一的。具体步骤如下 set(astr)首先将输入字符串astr转换为一个集合set。集合是一种无序、不重复的数据结构它会自动去除重复的元素只保留唯一的元素。 len(set(astr))接下来计算集合的长度也就是集合中唯一元素的个数。 len(astr)同时计算原始字符串astr的长度也就是字符串中字符的总个数。 len(set(astr)) len(astr)最后将集合的长度与原始字符串的长度进行比较。如果它们相等说明字符串中的字符都是唯一的此时返回True否则返回False。
这个代码的核心思想是如果一个字符串中的字符都是唯一的那么将字符串转换为集合后集合的长度应该与原始字符串的长度相等。如果有重复的字符存在集合的长度会小于原始字符串的长度因此返回False表示字符串中存在重复字符。否则返回True表示字符串中的字符全部都是唯一的。这是一种简洁而有效的方法来解决判断字符串中字符唯一性的问题。 方法二
解题思路
一看到题目想到的就是直接暴力使用双重循环逐一比较字符串中的字符是否相同。如果在任何时候找到相同的字符就返回 False否则在遍历完成后返回 True表示字符串中的字符全部都是唯一的。这种实现方式没有使用额外的数据结构适用于不使用额外空间的情况。 算法描述可以使用代码加注释、伪代码、纯文字描述均可、时间复杂度分析
算法描述class Solution: def isUnique(self, astr: str) - bool: # 使用双重循环来比较字符是否相同 for i in range(len(astr)): for j in range(i 1, len(astr)): if astr[i] astr[j]: return False # 如果没有找到相同的字符返回True return True 时间复杂度分析这个算法的时间复杂度是O(n^2)其中n是字符串s的长度。
该算法使用了双重循环来比较字符串中的字符是否相同。外层循环需要遍历整个字符串内层循环从外层循环的下一个字符开始遍历剩余字符。因此上述算法的时间复杂度为O(n^2)。 题解
class Solution:def isUnique(self, astr: str) - bool:for i in range(len(astr)):for j in range(i 1, len(astr)):if astr[i] astr[j]:return Falsereturn True 讨论与总结
直接暴力时间复杂度比较高而且没有什么学习价值但是学习到了python的双重循环是怎么样写的。
方法三
用Python编写一个不使用额外数据结构的算法来确定一个字符串的所有字符是否都不相同。一种方法是使用双重循环但这不是最优解。更好的方法是使用位运算因为你知道输入字符串只包含小写字母。
以下是一个示例代码使用位运算来检查字符串是否包含重复字符
class Solution:def isUnique(self, astr: str) - bool:# 创建一个用于存储出现过的字符的位向量初始值为0char_set 0for char in astr:# 计算字符的ASCII码值char_val ord(char)# 使用位运算检查字符是否已经出现过if (char_set (1 char_val)) 0:return False# 将对应字符位置的位设为1char_set | (1 char_val)return True# 创建Solution类的实例
solution Solution()# 示例
print(solution.isUnique(leetcode)) # 输出: False
print(solution.isUnique(abc)) # 输出: True下面是对代码的详细解释 我们首先定义了一个名为 Solution 的类该类包含了一个名为 isUnique 的方法该方法接受一个字符串 astr 作为输入并返回一个布尔值指示字符串中的字符是否都是唯一的。 在 isUnique 方法内部我们创建了一个名为 char_set 的整数变量用于存储出现过的字符的信息。初始时char_set 的所有位都被设置为0因为我们还没有遇到任何字符。 接下来我们使用 for 循环遍历输入字符串 astr 中的每个字符。 对于每个字符我们使用 ord(char) 来获取其对应的ASCII码值这个值将用于确定该字符在 char_set 中的位置。 我们使用位运算来检查字符是否已经出现过。具体做法是将1左移 char_val 位并与 char_set 进行按位与运算。如果结果大于0说明该字符已经出现过因此我们返回 False 表示字符串中有重复字符。 如果字符没有重复我们将更新 char_set将对应字符位置的位设为1以表示该字符已经出现过。这是通过将1左移 char_val 位并与 char_set 进行按位或运算来实现的。 最终如果我们遍历完整个字符串而没有发现重复字符那么我们返回 True表示字符串中的所有字符都是唯一的。
这个算法的核心思想是使用一个整数的二进制位来表示每个字符是否出现过以达到空间复杂度O(1)的要求。同时它的时间复杂度为O(n)其中n是字符串的长度因为我们需要遍历整个字符串。
注释ord()函数
ord()函数是一个内置的Python函数用于获取一个字符的Unicode码点整数表示。Unicode是一种用于表示世界上大多数字符的标准编码系统包括ASCII字符和许多其他字符因此ord() 函数可以用于获取字符的唯一整数标识。
具体来说ord() 函数接受一个字符作为参数并返回该字符对应的Unicode码点例如
char A
unicode_value ord(char)
print(unicode_value) # 输出: 65在上面的示例中ord(A) 返回65因为大写字母A的Unicode码点是65。
ord() 函数通常在需要将字符与其相应的整数表示进行比较或转换时使用。与之相反的函数是 chr()它接受一个整数Unicode码点作为参数并返回对应的字符。这两个函数一起允许在字符和整数之间进行。 通过一个具体的示例来演示这个方法的整个过程以便理解
假设输入字符串 astr 为 abcabc。 我们首先创建一个整数 char_set初始值为0用于表示字符的出现状态。 开始遍历字符串 astr 的字符 对于第一个字符 a其Unicode码点为97我们计算 char_val ord(a)因此 char_val 等于 97。 我们检查 char_set 中的位看看字符 a 是否已经出现过。首先我们将 1 左移 char_val 位得到一个二进制数只有第 97 位为1其他位都为0即 1 97 等于 158456325028528675187087900672。然后我们使用按位与运算来检查这一位是否已经被设置在 char_set 中即 char_set (1 char_val)。由于 char_set 的初始值为0按位与的结果也为0表示字符 a 还没有出现过。 接下来我们将更新 char_set将字符 a 对应的位设为1使用按位或运算即 char_set | (1 char_val)。此时char_set 的值变为 158456325028528675187087900672表示字符 a 已经出现过。 然后我们继续遍历字符串的下一个字符 b并重复相同的过程。 计算 char_val ord(b)得到 char_val 等于 98。 使用按位与运算检查字符 b 是否已经出现过即 char_set (1 char_val)。此时由于 char_set 的第 97 位已经被设置为1按位与的结果不再是0表示字符 b 已经出现过。 由于字符 b 已经出现过我们不再更新 char_set继续遍历下一个字符 c。 对于字符 c我们执行相同的过程 计算 char_val ord(c)得到 char_val 等于 99。 使用按位与运算检查字符 c 是否已经出现过即 char_set (1 char_val)。此时由于 char_set 的第 97 和 98 位都已经被设置为1按位与的结果不再是0表示字符 c 已经出现过。 由于字符 c 已经出现过我们不再更新 char_set。 最后我们遍历完整个字符串发现字符串中有重复字符 a、b 和 c因此函数返回 False 表示字符串中不是所有字符都唯一。
这就是使用位运算检查字符串中是否有重复字符的过程。通过将字符的Unicode码点映射到整数并使用位运算来表示字符的出现状态我们可以高效地解决这个问题。
