加载中...
avatar

LeetCode刷题笔记 一起愉快A题 (C++)(持续更新中)

开始刷LeetCode题库了,既可以准备蓝桥杯,有可以多练习算法题,一起愉快A题呀:彩虹滑稽:

LeetCode 102. 二叉树的层序遍历

题目描述

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

示例

二叉树:[3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

解题思路

  1. 创建辅助队列,依次遍历每一层节点并将下一层节点入队。
  2. 遍历的同时用一个向量存储数据。
  3. 每遍历完一层将存储该层的向量存储到二维向量中。
  4. 直到遍历完成返回最终统计数据。

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode *root) {
vector<vector<int>> result;
queue<TreeNode *> tempQueue; //辅助队列
if (root == nullptr) {
return result;
}
tempQueue.push(root);
TreeNode *tempNode = nullptr; //存放队列首结点
while (!tempQueue.empty()) //队列不为空
{
int QueLength = tempQueue.size();
vector<int> level; //存放此层的值
for (int i = 0; i < QueLength; i++) {
tempNode = tempQueue.front();
tempQueue.pop();
level.push_back(tempNode->val);
if (tempNode->left != nullptr)
tempQueue.push(tempNode->left);
if (tempNode->right != nullptr)
tempQueue.push(tempNode->right);
}
result.push_back(level);
}
return result;
}
};

LeetCode 136. 只出现一次的数字

题目描述

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

示例

1
2
输入: [2,2,1]
输出: 1
1
2
输入: [4,1,2,1,2]
输出: 4

解题思路

这个题目最简单的思路是多次遍历找出只出现一次的数,但是对于时间复杂度就会很高。

我们可以使用异或运算的性质:

  1. 任何数和0做异或,还是原来的数,即:a ^ 0 = a
  2. 任何数和自身做异或,结果为0,即:a ^ a = 0
  3. 异或满足交换律和结合律。

例如输入[4,1,2,1,2],使用异或操作:

4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ ( 1 ^ 1 ) ^ ( 2 ^ 2) = 4 ^ 0 ^ 0 = 4

AC

1
2
3
4
5
6
7
8
9
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for(int i:nums)
result ^= i;
return result;
}
};
文章作者: 云开、见月明
文章链接: https://chenyunxin.cn/posts/1511570690.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 云开の博客
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论