网站空间空间,中国建筑官网超高层,文友胜做的网站,画出网站和目录结构图文章目录 #x1f34a;面试题 01.01. 判定字符是否唯一#x1f96d;题目#x1f351;算法原理#x1f95d;解法一#xff1a;哈希表#x1f95d;解法二#xff1a;位图 #x1f951;代码实现 #x1f33d;268. 丢失的数字#x1f96c;题目#x1f344;算法原理… 文章目录 面试题 01.01. 判定字符是否唯一题目算法原理解法一哈希表解法二位图 代码实现 268. 丢失的数字题目算法原理解法一哈希表解法二高斯求和解法三位运算异或运算的运算律 代码实现 面试题 01.01. 判定字符是否唯一
题目 题目链接面试题 01.01. 判定字符是否唯一 - 力扣LeetCode 实现一个算法确定一个字符串 s 的所有字符是否全都不同。
示例 1
输入: s leetcode
输出: false 示例 2
输入: s abc
输出: true限制
0 len(s) 100 s[i]仅包含小写字母如果你不使用额外的数据结构会很加分。
算法原理
解法一哈希表
这里直接用哈希表我们遍历整个字符串如果不在哈希表里面将这个字符丢进去如果在直接返回false即可如果到末尾还没有则返回true。
时间复杂度为O(N)由于全是小写字符只想要创建一个hash[26]即可空间复杂度为O(1)
解法二位图
在解法一的基础上我们还能继续优化一下借助位图的比特位来标记信息 这样就能用一个int变量做到上面26个int变量做的的事情 在此基础上还能继续优化一下即鸽巢原理由于小写的字符总共才26个所有当这个字符串长度超过26的时候必然有重复的 代码实现
class Solution {
public:bool isUnique(string astr){if(astr.size()26) return false;int bitMap 0;for(auto ch : astr){int i ch-a; //a的ASCII值为97if((bitMapi)1 1) return false;bitMap | 1i; }return true;}
};运行结果 268. 丢失的数字
题目 题目链接268. 丢失的数字 - 力扣LeetCode 给定一个包含 [0, n] 中 n 个数的数组 nums 找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1
输入nums [3,0,1]
输出2
解释n 3因为有 3 个数字所以所有的数字都在范围 [0,3] 内。2 是丢失的数字因为它没有出现在 nums 中。示例 2
输入nums [0,1]
输出2
解释n 2因为有 2 个数字所以所有的数字都在范围 [0,2] 内。2 是丢失的数字因为它没有出现在 nums 中。示例 3
输入nums [9,6,4,2,3,5,7,0,1]
输出8
解释n 9因为有 9 个数字所以所有的数字都在范围 [0,9] 内。8 是丢失的数字因为它没有出现在 nums 中。示例 4
输入nums [0]
输出1
解释n 1因为有 1 个数字所以所有的数字都在范围 [0,1] 内。1 是丢失的数字因为它没有出现在 nums 中。提示
n nums.length1 n 1040 nums[i] nnums 中的所有数字都 独一无二
**进阶**你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
算法原理
这里给的是[0,n]但是只给了n个所以这个是缺少一个数字的。
解法一哈希表
我们创建一个n1大小的哈希表从前往后遍历数组然后看哪个数字没有被标记。
解法二高斯求和
用数学公式求[0,n]的和然后减去这个数组的和即可得到缺少的数字这个相比哈希表空间复杂度为O(1)
ret (0n)*(n1)/2 - sum[nums];解法三位运算异或运算的运算律
异或运算中有一个消消乐相同的数字异或的结果为0所以最后剩下的就是缺少的数字
代码实现
高斯求和
class Solution {
public:int missingNumber(vectorint nums) {int n nums.size();int ret (0n)*(n1)/2;for(auto e:nums)ret-e;return ret;}
};异或运算律
class Solution {
public:int missingNumber(vectorint nums) {int ret 0;for(auto e:nums)ret^e;for(int i0;inums.size();i)ret^i;return ret;}
};运行结果