DFS、异或-LeetCode 257、258、268、283
DFS、异或-LeetCode 257、258、268、283
作者：TeddyZhang，公众号：算法工程师之路
DFS：LeetCode #257 258 268 283
1
编程题
【LeetCode #257】二叉树的所有路径
解题思路：
使用dfs算法获得每条路径，注意在生成字符串时可以使用string类型，可以直接使用加法操作对字符串进行拼接得到最终结果！
/**
* 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<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(root == nullptr) return res;
dfs(root, res, "");
return res;
}
private:
void dfs(TreeNode* root, vector<string>& res, string path){
path += to_string(root->val);
if(root->left == nullptr && root->right == nullptr){
res.push_back(path);
return;
}
if(root->left != nullptr) dfs(root->left, res, path + "->");
if(root->right != nullptr) dfs(root->right, res, path + "->");
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-paths/
【LeetCode #258】各位相加
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例: 输入: 38 输出: 2 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。由于 2 是一位数，所以返回 2。
解题思路：
思路简单，方法二的耗时比方法一的还多，而且方法二还不好想出来！
（使用循环语句）
class Solution {
public:
int addDigits(int num) {
int res = sums(num);
while(res < || res > ){
res = sums(res);
}
return res;
}
private:
int sums(int num){
int sum = ;
while(num){
sum += num % ;
num /= ;
}
return sum;
}
};
(不使用循环语句)
class Solution {
public:
int addDigits(int num) {
if(num > ){
num = num % ;
if(num == ){
return ;
}
}
return num;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-digits
【LeetCode #268】缺失数字
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1: 输入: [3,0,1] 输出: 2 示例 2: 输入: [9,6,4,2,3,5,7,0,1] 输出: 8
解题思路：
这个方法与从n个数中寻找重复的数的方法类似，使用异或运算，我们来复习一下异或的性质： 0 ^ a = a; a ^ b ^ b = a; 由于题中只缺少了一个数，我们可以使用0到n的索引去抵消已存在的数，最终剩余的数即为缺失的数！
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = , i;
for(i = ; i < nums.size(); i++){
res ^= nums[i];
res ^= i;
}
return res ^ i;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/missing-number
【LeetCode #283】移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
解题思路：
将nums中的不为零的数从0开始依次移动，然后start也开始移动，当不为零的数都移动完后，start后面的数均被置为0.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int start = ;
for(auto num: nums){
if(num != ){
nums[start++] = num;
}
}
while(start != nums.size()){
nums[start++] = ;
}
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/move-zeroes
腾讯云开发者
