发表于 | 更新于 | 分类于

题目描述

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

1
2
3
4
5
6
7
8
9
输入:

   1         1
  / \       / \
 2   3     2   3

[1,2,3],   [1,2,3]

输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:

   1          1
  /           \
 2             2

[1,2],     [1,null,2]

输出: false

示例 3:

1
2
3
4
5
6
7
8
9
输入:

   1         1
  / \       / \
 2   1     1   2

[1,2,1],   [1,1,2]

输出: false

题目分析

这道题可以用深度搜索来解决, 也可以用递归来解决.

源码(递归)

1
2
3
4
5
6
7
8
9
10
11
class Solution { // 递归方法
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL || q == NULL) { // 两个节点有一个为空
            return p == q;
        }else {
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
            // p节点的左子树和q节点左子树相等并且p节点的右子树和q节点的右子树相等
        }
    }
};

源码(深度优先搜索)

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
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q != NULL) return false; // 左树空树 右树非空树
        if(q == NULL && p != NULL) return false; // 右树空树 左树非空树
        if(p == NULL && q == NULL) return true;  // 同时为空树
        stack<TreeNode*> q1, q2; // 声明两个栈用来储存节点
        q1.push(p);
        q2.push(q);
        while(!q1.empty() && !q2.empty()) { // 有任意一个栈为空时停止循环
            TreeNode *cur1 = q1.top(), *cur2 = q2.top(); // 将栈首节点设为当前操作节点
            q1.pop(); // 将两个当前操作节点弹出
            q2.pop();
            if((cur1 == NULL && cur2 != NULL) || (cur1 != NULL && cur2 == NULL)) return false;
            // 判断是否只有一个节点为空
            if(cur1 != NULL){ // 如果两个节点都不为空则对比两个节点值, 如果相等则将其子节点压入栈
                if(cur1->val != cur2->val) return false;
                q1.push(cur1->left);
                q1.push(cur1->right);
                q2.push(cur2->left);
                q2.push(cur2->right);
            }
        }
        return true;
    }
};

发表于 | 更新于 | 分类于

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

1
2
输入: m = 3, n = 2
输出: 3

解释:

1
2
3
4
5
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

1
2
输入: m = 7, n = 3
输出: 28

题目分析

到达(m, n)点的路径数应等于到达(m, n-1) + (m-1, n)的路径数和. 由此得出状态转移方程:

但是用递归解决这个问题在m, n较大时会存在效率低的问题, 因为有些m, n的情况被重复计算, 这样我们可以使用一个数组来存放计算结果, 在遇到重复计算时便可以从数组之中直接得到值.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int num[10000][10000] = {0}; // 初始化所有元素为0

class Solution {
public:

    int uniquePaths(int m, int n) {
        if(m == 1 || n == 1) { // 在m == 1 或者 n == 1 时返回1
            return 1;
        }else {
            if(num[m][n] != 0) { // 如果num[m][n]存在, 则说明已经运算过此情况, 直接从数组中获取结果
                return num[m][n];
            }else {
                num[m][n] = uniquePaths(m-1, n) + uniquePaths(m, n-1);
                // 将结果存在num[m][n]中后返回num[m][n]
                return num[m][n];
            }
        }
    }
};

发表于 | 更新于 | 分类于

题目描述

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1:

1
2
3
输入：00000000000000000000000000001011  
输出：3  
解释：输入的二进制串 00000000000000000000000000001011 中，'1'。

示例 2:

1
2
3
输入：00000000000000000000000010000000  
输出：1  
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3:

1
2
3
输入：11111111111111111111111111111101  
输出：31  
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为'1'。

进阶:

如果多次调用这个函数，你将如何优化你的算法？

题目分析

可以循环的对输入数与1取与, 如结果为1则返回结果加1, 后右移1位.

源码

1
2
3
4
5
6
7
8
9
10
11
class Solution { // 手动取每一位
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n != 0) {
            if(n&1 == 1) ++count; // 如数和1取与为1则结果加1
            n >>=1;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
class Solution { // 使用STL的bitset
public:
    int hammingWeight(uint32_t n) {
        bitset<32> b(n);
        // 由于题中已说是32位无符号整数, 则可以使用bitset
        return b.count();
    }
};

发表于 | 更新于 | 分类于

题目描述

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

1
2
输入: 1
输出: true

解释: $2^0$ = 1

示例 2:

1
2
输入: 16
输出: true

解释: $2^4$ = 16

示例 3:

输入: 218
输出: false

题目分析

如果一个数是2的幂, 则它的二进制一定只有第一位是1, 其他位为0. 这样我们取它与比它小1的与. 如果所得为0, 则为2的幂, 反之则不是2的幂.

源码

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n<=0) return false; // 2的幂一一定大于0
        return n&(n-1) == 0;
};

发表于 | 更新于 | 分类于

题目描述

写一个程序，输出从 1 到 n 数字的字符串表示。

1. 如果 n 是3的倍数，输出“Fizz”；

2. 如果 n 是5的倍数，输出“Buzz”；

3. 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

题目分析

筛素法类似思想, 先初始化所有元素为空字符串, 之后将3的倍数的元素加上”Fizz”, 5的倍数的元素加上”Buzz”, 后遍历整个数组并将数组中空的字符串赋值为次序.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<string> fizzBuzz(int n) { //筛选法
        vector<string> res;
        res.resize(n);
        for(int i=1; i<=n/3; ++i) {
            res[i*3-1] += "Fizz";
        }
        for(int i=1; i<=n/5; ++i) {
            res[i*5-1] += "Buzz";
        }
        for(int i=0; i<n; ++i) {
            if(res[i] == "") res[i]+=to_string(i+1);
        }
        return res;
    }
};

发表于 | 更新于 | 分类于

题目描述

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false
解释:
如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

题目分析

拿到第4块则输.

源码

1
2
3
4
5
6
class Solution {
public:
    bool canWinNim(int n) {
        return n%4 != 0;
    }
};

发表于 | 更新于 | 分类于

题目描述

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

1
2
3
4
5
给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

1
2
3
4
5
给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。
说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
9
10
11
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝

int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。

// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。

for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题目分析

输入的是动态数组vector, 则可以使用迭代器遍历数组, 删除每一个等于val的元素.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        vector<int>::iterator iter = nums.begin(); //声明一个vector<int>的迭代器 iter, 使其初始位置为nums数组的首元素.
        while(iter != nums.end()) {
            if(*iter == val) { //如果iter所在元素的值等于val
                nums.erase(iter); //*删除iter所在元素.*
                // iter++; //*如果加上这条则出错, 因为删除iter所在元素后iter就已变为被删除元素的下一元素了.*
            }else {
                iter++; //没有删除元素, iter变为下一元素.
            }
        }
        return nums.size(); //返回删除重复元素后的数组大小.
    }
};

发表于 | 更新于 | 分类于

题目描述

给定一个整数数组 nums 和一个目标值 target

请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题目分析

这道题可以硬核的用两个循环对每两个元素相加求下标, 但是时间复杂度会到O($n^2$), 所以使用哈希表来存储.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int completion;
        vector<int> res;
        unordered_map<int, int> m; // 哈希表, 牺牲空间复杂度获得低时间复杂度.
        for(int i=0; i<nums.size(); ++i) { // 遍历nums数组.
            completion = target - nums[i]; // completion 为与nums[i]相加获得target的数.
            if(m.find(nums[i]) == m.end()) { // 之前没有能和nums[i]相加得到target的元素.
                m[completion] = i; // 用哈希表保存completion和nums[i]的位置.
            }else {
                res.push_back(m[nums[i]]); // 压入之前的位置
                res.push_back(i); // 压入找到时的位置
                return res; // 返回答案
            }
        }
        return res; // 没有找到时返回空数组
    }
};
0%