公司网站访问非法网站的作用,企业网站推广的方法有搜索引擎推广,网站开发用什么系统比较好?,wordpress电视主题文章目录 一、题目二、C# 题解 一、题目 实现一个算法#xff0c;确定一个字符串 s 的所有字符是否全都不同#xff0c;点击此处跳转。
示例 1#xff1a; 输入: s “leetcode” 输出: false 示例 2#xff1a; 输入: s “abc” 输出: true 限制#xff1a;
0 le… 文章目录 一、题目二、C# 题解 一、题目 实现一个算法确定一个字符串 s 的所有字符是否全都不同点击此处跳转。
示例 1 输入: s “leetcode” 输出: false 示例 2 输入: s “abc” 输出: true 限制
0 len(s) 100s[i] 仅包含小写字母如果你不使用额外的数据结构会很加分。
二、C# 题解 使用数组记录出现次数时间、空间复杂度均为 O ( n ) O(n) O(n)
public class Solution {public bool IsUnique(string astr) {int[] record new int[26]; // 记录数组for (int i 0; i astr.Length; i) { // 遍历字符串int index (int) (astr[i] - a); // 得到每个字符在数组中对应的下标if (record[index] 0) return false; // 出现则返回 falseelse record[index]; // 未出现则记录 1}return true; // 到此步则返回 true}
}数组记录有些浪费内存空间了因此使用位运算记录也可。因为题目要求是字符串内仅包含小写字母因此只会出现26种不同的字符使用 int 变量有 32 位长度足以覆盖范围。 0000 0000 0000 0000 0000 0000 0000 0000 ↓ ′ c ′ 0000 0000 0000 0000 0000 0000 0000 0100 ↓ ′ g ′ 0000 0000 0000 0000 0000 0000 0100 0100 ↓ ′ a ′ 0000 0000 0000 0000 0000 0000 0100 0101 ↓ ′ c ′ 重复返回 f a l s e 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000\\ ↓ c\\ 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0100\\ ↓ g\\ 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0100 \quad 0100\\ ↓ a\\ 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0000 \quad 0100 \quad 0101\\ ↓ c\\ 重复返回 false 00000000000000000000000000000000↓′c′00000000000000000000000000000100↓′g′00000000000000000000000001000100↓′a′00000000000000000000000001000101↓′c′重复返回false 位运算记录的本质与上述数组记录类似差别仅是内存使用。数组使用一个 int32 位 bit记录而位运算使用 1 个 bit 记录本质无区别。当然运行速度会快些。
public class Solution {public bool IsUnique(string astr) {int record 0; // 记录 intfor (int i 0; i astr.Length; i) { // 遍历字符串int index 1 (int) (astr[i] - a); // 得到每个字符在 int 中对应的 bit 位数if ((record index) ! 0) return false; // 与运算结果不为 0则表示出现过else record | index; // 未出现则或运算记录下该字符}return true; // 到此步则返回 true}
}时间复杂度 O ( n ) O(n) O(n)。空间复杂度取决于出现字符的种类数目此题为 O ( 1 ) O(1) O(1)。
使用位运算的好处
满足题目要求运行效率快些锻炼编程能力。
坏处
处理字符种类有限int 只能处理 32 种long 只能处理 64 种不易于读写与修改。
