二刷leetcode--217. 存在重复元素、206. 反转链表、202. 快乐数、191. 位1的个数(c++版本)-爱代码爱编程
217. 存在重复元素
复习知识点:本题常见的方法如下两种,可以排序然后看前后相邻的元素是否相等,也可以将元素依次存入哈希表,然后每次放入新元素的时候看是否当前的元素已经出现在哈希表中。
// class Solution {
// public:
// bool containsDuplicate(vector<int>& nums) {
// sort(nums.begin(), nums.end());
// // 排序后如果前后相等说明存在重复字符
// for(int i = 0;i < nums.size() - 1;++i)
// {
// if(nums[i] == nums[i + 1])
// return true;
// }
// return false;
// }
// };
class Solution{
public:
bool containsDuplicate(vector<int>& nums){
unordered_set<int> hash;
for(int num : nums)
{
if(hash.find(num) != hash.end())
{
return true;
}
// 新插入当前元素看是不是已经存在于哈希表中
hash.insert(num);
}
return false;
}
};
206. 反转链表
复习知识点:本题没有使用头插法,而是用三个节点进行记录,然后将当前节点的后继指针指向其前驱节点,然后每次更新前驱节点和下一个节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = nullptr;
while(cur)
{
// 从head开始,一次将Next指针指向前一个元素
ListNode* behind = cur -> next;
// 当前节点的下一个节点为前驱节点
cur -> next = pre;
// 当前节点记为前驱节点
pre = cur;
// 当前节点后移
cur = behind;
}
return pre;
}
};
202. 快乐数
复习知识点:本题按照题意进行判断,对每一个位置的元素拿出来进行平方和计算,然后每次计算完成之后更新当前的数据,注意,本题需要留意,如果之前已经出现过该结果,那么说明出现死循环,因此我们使用哈希表进行每次结果的保存,然后进行查询。
class Solution {
public:
// 求出全部位数的平方和
int my_sum(int num)
{
int sum = 0;
while(num)
{
sum += (num % 10) * (num % 10);
num /= 10;
}
return sum;
}
bool isHappy(int n) {
// 如果一个结果已经出现,结果后面又出现,
// 那么这个时候再计算就还是会出现死循环,因此需要对之前的元素记录
unordered_set<int> hash;
while(1)
{
if(my_sum(n) == 1)
return true;
else if(hash.find(my_sum(n)) != hash.end())
return false;
else
hash.insert(my_sum(n));
// 更新数据
n = my_sum(n);
}
}
};
191. 位1的个数
复习知识点:1<<i 是将1左移i位,即第i位为1,其余位为0;例如1<<2 则0001->0100;n&(1<<i)是将左移i位的1与n进行按位与,即为保留n的第i位,其余位置零;如果n第i位为0,则n&(1<<i)的值为0;否则不为0;常用if(n&(1<<i)==0)用于判断n的第i位是否为0。
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
for(int i = 0;i < 32;++i)
// 是将左移i位的1与n进行按位与,即为保留n的第i位,其余位置零
if((n & (1 << i)) != 0)
++res;
return res;
}
};