AmosTian

0%

0.编程能力

发表于 更新于 分类于 >
本文字数 9.7k字 | 阅读时长 ≈ 30 分钟

题目来源于 leetcode 编程能力学习计划

0.1 基本数据类型

1523.在区间范围内统计奇数数目

奇数，第一反应是 n%2==1 ,所以直接写成下面代码，结果超时。计算除法的代价显然比加减法大得多

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int countOdds(int low, int high) {
        int cnt=0;
        for(int i=low;i <= high;++i)
            if(i % 2==1)
                cnt++;

    return cnt;
    }
};

又想整数，一定是 奇、偶、… 或 偶、奇…

所以已经给定区间范围，[左,右]，右-左= (左,右] 或 [左,右) 包含的整数个数，折半则为奇数个数

且分为以下情况

  1. [奇,奇]
  2. [奇,偶]
  3. [偶,奇]
  4. [偶,偶]

故需判断一侧边界是否为奇数，若其为奇数，则个数加1。由于闭区间的对称性，两侧都要判断，且左右判别式间关系为或。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int countOdds(int low, int high) {
        int cnt=0;
        if(low % 2==1  || high%2==1)
            cnt=1;
        cnt += (high-low)/2;

        return cnt;
    }
};

前缀和思想

pre(x)为区间 $[0,x]$ 内奇数个数，显然 $pre(x)=\lfloor \frac{x+1}{2} \rfloor$ ,故区间[low,high]内奇数个数为 pre(high)-pre(low-1)

计算机中乘除法运算没有移位运算快

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int pre(int x) {
        return (x + 1) >> 1;
    }
    
    int countOdds(int low, int high) {
        return pre(high) - pre(low - 1);
    }
};

判断奇偶的方法：x&1

1491. 去掉最低工资和最高工资后的工资平均值

第一想法，简单选择，一轮遍历，以为会超时竟然过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double average(vector<int>& salary) {
        double min = salary[0];
        double max = salary[0];
        double sum = 0;
        for(int i = 0;i < salary.size();++i){
            if(min > salary[i])
                min = salary[i];
            if(max < salary[i])
                max = salary[i];
            sum += salary[i];
        }
        return (sum-min-max)/(salary.size()-2);
    }
};
  • 因为是新手村的入门题，甚至连数据都是唯一的，非常友好了。

题解

答案想法类似，只是用了 容器 的内置方法寻找最值

  • algorithm 库的 max_element()、min_element() 返回容器中最小值和最大值的 指针
  • numeric 库的 accumulate(起点,终点,权值) ：直接计算数组或者容器中C++内置数据类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<algorithm>//max_element()、min_element()
# include<numeric>

class Solution {
public:
    double average(vector<int>& salary) {
        double maxValue = *max_element(salary.begin(), salary.end());
        double minValue = *min_element(salary.begin(), salary.end());
        double sum = accumulate(salary.begin(), salary.end(), - maxValue - minValue);
        return sum / int(salary.size() - 2);
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/average-salary-excluding-the-minimum-and-maximum-salary/solution/qu-diao-zui-di-gong-zi-he-zui-gao-gong-zi-hou-de-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

0.2 运算符

191. 位1的个数

第一想法是位运算，结合上面奇数的判断方法 n&1==1 ，则当前位为1，故1的个数加1。因为输入的二进制字符串长度不变呢，所以右移位数确定，循环判断条件也可是 for(int i = 0;i < 32;++i)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n){
            if(n&1)
                cnt++;
            n>>=1;//右移一位
        }

        return cnt;
    }
};
  • 本题一开始卡在右移， n>>1 忘写赋值符号 n>>=1 导致死循环，判别为超时

题解

答案的第一种做法和上述类似，只是移位方向不同，第一想法是1不动，数字右移，答案第一种是数字不动，用1左移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if (n & (1 << i)) {
                ret++;
            }
        }
        return ret;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode-solution-jnwf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：

这个真想不出来：n&(n - 1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果

就是说

11111111111111111111111111111111 & 11111111111111111111111111111110 变为 11111111111111111111111111111110

11111111111111111111111111111110 & 11111111111111111111111111111101 变为 11111111111111111111111111111100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode-solution-jnwf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  • 真值的二进制为logn,故时间复杂度为logn

1281. 整数的各位积和之差

求每个数位上的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int subtractProductAndSum(int n) {
        int product = 1;
        int sum = 0;
        while(n){
            int a = n%10;
            sum += a;
            product *= a;
            n/=10;
        }
        return product-sum;
    }
};

时间复杂度：$O(logN)$ 由于整数N的位数为 $\lceil log_{10}N = \frac{log_2{N}}{log_210} \rceil$ 即相差常数，故数量级为O(logN)

空间复杂度：O(1)

0.3 条件语句

976. 三角形的最大周长

最初考虑只有三个元素

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(),nums.end());//122 112
        if(nums[0]+nums[1] <= nums[2] || nums[2]-nums[0] >= nums[1])
            return 0;
        return accumulate(nums.begin(),nums.end(),0);
    }
};

显然想简单了

排序+贪心，从数组尾部开始逆序遍历，若找到可以构成三角形的，则直接输出其周长，若迭代器回到 nums.begin()+1 都不能构成三角形，则返回0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(),nums.end()); 
        vector<int>::iterator it = nums.end()-1;
        
        while(it != nums.begin()+1){
            if(*it-*(it-2) < *(it-1) && *(it-2)+*(it-1) > *it)
                return accumulate(it-2,it+1,0);
            it--;
        }    
        return 0;
    }
};

显然效率不够高。还是看题解

题解

这么一看咱思想还是跟的上的。

1779. 找到最近的有相同 X 或 Y 坐标的点

就一些数学库函数的运用，在设置 min 时，一开始用 $10^4$ 不对，以下示例会出错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int min = INT_MAX;
        int idx=-1;
        for(int i = 0;i < points.size();++i){
            if(points[i][0]==x || points[i][1]==y){
                if(min > abs(x-points[i][0])+abs(y-points[i][1])){
                    min = abs(x-points[i][0])+abs(y-points[i][1]);
                    idx = i;
                }
            }
        }
        return idx;
    }
};

0.4 循环

1822. 数组元素积的符号

看完题，发现其返回只有 -1/0/1 三种，那就分三种情况

  • 有0，一定是0
  • 负数个数是偶数，则1
  • 负数个数是奇数，则-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int arraySign(vector<int>& nums) {
        if(find(nums.begin(),nums.end(),0) != nums.end())
            return 0;//如果有0，则product与符号一定是0
        vector<int>::iterator it = nums.begin();
        int negative = 0;
        while(it != nums.end()){
            if(*it<0)
                negative++;
            it++;
        }
            
        if(negative&1)
            return -1;
        else
            return 1;
    }
};

另一种思路是逢-1变号

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
 public:
     int arraySign(vector<int>& nums) {
         int sign = 1;
         for (int n : nums) {
             if (n == 0) return 0;
             if (n < 0) {
                sign *= -1;
             }
         }
         return sign;
     }
 };

1502. 判断能否形成等差数列

等差数列，就是每两个之间步长是相等的，排序后遍历一次，若发现有不相等的步长，则返回 false ，若可遍历到尾部，则返回 true

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(),arr.end());
        int step = arr[1]-arr[0];
        for(int i = 1;i < arr.size()-1;++i)
            if(arr[i+1]-arr[i]!=step)
                return false;
        return true;
    }
};

题解

答案是利用等差数列相邻三项间的和的性质，但。。。加减法效率不应该比乘法效率高吗

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        for (int i = 1; i < arr.size() - 1; ++i) {
            if (arr[i] * 2 != arr[i - 1] + arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
};

202. 快乐数

递归+归纳

  • 终止条件

递归思想要解决的第一个问题是终止条件是什么，即什么情况下不是快乐数

我的做法是已知1一定是快乐数，返回true

最开始想法是 n<10 ，将1剔除出去，剩下的返回 false。但是运行后，有实例没通过(7)

故将10以内的数挨个计算，最后只有 1 和 7 满足快乐数的要求

  • 递归内运算

求出各位数字后平方求和，再调用递归函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isHappy(int n) {
        if(n==1 || n==7)
            return true;
        if(n < 10)
            return false;
        int sum = 0;
        while(n){
            sum += pow(n%10,2);
            n /= 10;
        }

        return isHappy(sum);
    }
};

题解

集合元素的唯一性

若元素是快乐数，则经过运算，最后都会变为1

若元素不是快乐数，则经过运算，会进入循环，即运算过程中的数字会再次出现。

所以利用集合中元素的唯一性，将运算过程中的数字放入一个集合，若无法放入，说明已经有循环，则返回 false。若出现1，则返回 true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
public:
    bool isHappy(int n) {
        set<int> s;
        while (n != 1 && s.find(n) == s.end()) {
            s.insert(n);
            n = getNext(n);
        }
        return n == 1;
    }
};
快慢指针法

思想：将运算过程中的数，抽象为单链表的结点。若单链表有环，则说明运算过程重复，不是快乐数；若无环，说明是快乐数

判断单链表是否有环的方法：快慢指针

  • 初始化快慢指针
  • 快指针转换两次，慢指针转换一次
  • 当快指针==慢指针时，说明有环
    • 此时，当慢指针==1，说明是1的无限环，是快乐数
    • 而慢指针!=1，说明不是快乐数
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
class Solution {
    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

public:
    bool isHappy(int n) {
        int slowRunner = n;
        int fastRunner = getNext(n);
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(getNext(fastRunner));
        }
        return fastRunner == 1;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1790. 仅执行一次字符串交换能否使两个字符串相等

  • 长度不同，则交换一次必不能相等

  • 若本来相等，则返回 true

  • 长度相等且字符串不等，字符串逐字符遍历

    • 字符第一次不等，记录

      漏掉的情况：只有第一次不等，也需返回 false

      • aa 与 ac 就是上面的情况

    • 字符第二次不等，若与第一个不等位置交换后相等，则返回 true

    • 若字符第三次不等，则返回 false

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
class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        if(s1.size()!=s2.size())
            return false;//长度不等必不成立
        if(s1==s2)
            return true;
        
        int beg=-1,end=s2.size();
        for(int i = 0;i < s2.size();++i){
            if(beg==-1 && s2[i]!=s1[i]){
                beg = i;//第一次不等
            }
            else if(end==s2.size() && s2[i]!=s1[i]){
                end=i;
                if(s2[end]==s1[beg]&&s2[beg]==s1[end])
                    continue;
                else
                    return false;
            }//第二次不等
            else if(beg != -1 && end != s2.size()  && s2[i]!= s1[i])
                return false;//还有不等
        }

        if(beg != -1 && end == s2.size())
            return false;//"aa"与"ac"的情况

        return true;
    }
};

题解

构成两个字符串的字符即其出现的次数应该相同，并且最多只会出现两个位置的字符不同

涉及到频次相关的问题，考虑采用哈希表去做。由于题目已提示 s1 和 s2 仅由小写英文字母组成，因此可以采用长度为 26 的整型数组模拟哈希表。

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
class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        int cnt = 0;
        int hash[26] = {0};
        int len = s1.size();
        for (int i = 0; i < len; ++i) {//记录字符串中各字符出现的频次
            hash[s1[i] - 'a']++;
        }

        for (int i = 0; i < len; ++i) {//如果某个字符出现次数是1，则不成立
            if (hash[s2[i] - 'a'] == 1) {
                return false;
            }
        }   

        for (int i = 0; i < len; ++i) {
            if (s1[i] != s2[i]) {
                cnt++;//只有两个字符不等，则一次交换就可成功。才是true
            }
        }
		//若超过两个字符不相等，则必不成立
        return cnt == 2 || cnt == 0;
    }
};

0.5 函数

1232. 缀点成线

基本思路：找出一个线性关系，若所有点都满足该线性关系，则返回 true ,否则返回 false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        //求直线方程
        double k = (coordinates[0][1]-coordinates[1][1])/(coordinates[0][0]-coordinates[1][0]);
        double b = coordinates[0][1] - k*coordinates[0][0];

        //遍历，是否中间有点不在直线上
        for(int i = 1;i < coordinates.size();++i){
            if(coordinates[i][1] != k*coordinates[i][0]+b)
                return false;
        }

        return true;
    }
};

报错原因：除零错误

[[0,0],[0,1],[0,-1]]

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
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        //当斜率无穷大时
        if(coordinates[0][0]-coordinates[1][0]==0){
            //若某一点横坐标值不相等，则不是一条直线
            for(int i = 2;i < coordinates.size();++i){
                if(coordinates[i][0] != coordinates[0][0])
                    return false;
            }
        }else{
            //求直线方程
            double k = (coordinates[0][1]-coordinates[1][1])/(coordinates[0][0]-coordinates[1][0]);
            double b = coordinates[0][1] - k*coordinates[0][0];

            //遍历，是否中间有点不在直线上
            for(int i = 1;i < coordinates.size();++i){
                if(coordinates[i][1] != k*coordinates[i][0]+b)
                    return false;
            }
        }

        return true;
    }
};

还是有错

[[2,1],[4,2],[6,3]] 预期结果 true

原因：整型除法会截取整数结果，最后在转化为double

比如 (double)(1/2)=double(0) = 0 显然是错误的，正确做法是给分母或分子强制转化为浮点数类型，这样二元运算过程中，会将另一小范围数值转化为浮点数类型，使得最后结果为浮点数类型

如 (double)1/2=1.0/2.0=0.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        //当斜率无穷大时
        if(coordinates[0][0]-coordinates[1][0]==0){
            //若某一点横坐标值不相等，则不是一条直线
            for(int i = 2;i < coordinates.size();++i){
                if(coordinates[i][0] != coordinates[0][0])
                    return false;
            }
        }else{
            //求直线方程
            double k = (double)(coordinates[0][1]-coordinates[1][1])/(coordinates[0][0]-coordinates[1][0]);
            double b = coordinates[0][1] - k*coordinates[0][0];
            //遍历，是否中间有点不在直线上
            for(int i = 1;i < coordinates.size();++i){
                if(coordinates[i][1] != k*coordinates[i][0]+b)
                    return false;
            }
        }

        return true;
    }
};

为避免 除0问题 和 精度问题 。将除法转化为乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int len=coordinates.size();

        double dy=coordinates[0][1]-coordinates[1][1];
        double dx=coordinates[0][0]-coordinates[1][0];
        for(int i=2;i<len;i++)
        {
            double x=coordinates[i][0]-coordinates[0][0];
            double y=coordinates[i][1]-coordinates[0][1];
           if(x*dy!=y*dx)      
               return false;
        }
        return true;
    }
};

作者：sui-yi-fan-che
链接：https://leetcode-cn.com/problems/check-if-it-is-a-straight-line/solution/cxie-lu-zhuan-hua-wei-cheng-fa-de-jian-d-4qlr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

496. 下一个更大元素 I

二重循环，暴力破解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> hash(nums1.size(),-1);

        for(int i=0;i < nums1.size();++i){
            vector<int>::iterator it = find(nums2.begin(),nums2.end(),nums1[i]);
            
            if(it != nums2.end()-1){
                for(vector<int>::iterator ij = it+1;ij != nums2.end() ;++ij){
                    if(*(ij) > nums1[i]){
                        hash[i] = *ij;
                        break;
                    }  
                }
            }
        }
        
        return hash;
    }
};

时间复杂度：O(m*n)

乘法阶的时间复杂度来源于每一轮都要查找nums2中的每个元素，若提前对nums2中元素进行O(m)处理，得到nums2中每个元素的目标元素，则整个算法的时间复杂度变为两轮遍历的时间复杂度O(m+n)

求下一个更大的元素(单调栈+哈希表)

  • 从右向左遍历：因要求的是从左到右的第一个，所以预处理时，从右向左处理，最后处理的元素即为最左元素

  • 用单调栈中维护当前位置右边的更大的元素列表

  • 每次我们移动到数组中一个新的位置 ii，就将当前单调栈中所有小于 nums2[i] 的元素弹出单调栈，当前位置右边的第一个更大的元素即为栈顶元素

凡是求最近最XX的元素都可以用单调栈+哈希表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        /*单调栈+哈希表预处理*/
        unordered_map<int,int> hashmap;
        stack<int> st;
        for (int i = nums2.size() - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!st.empty() && num >= st.top()) {
                st.pop();
            }
            hashmap[num] = st.empty() ? -1 : st.top();
            st.push(num);
        }

        //运算过程
        vector<int> res(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            res[i] = hashmap[nums1[i]];
        }
        return res;
    }
};

Next Greater Element模板

给你一个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]

这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> ans(nums.size()); // 存放答案的数组
    stack<int> s;
    for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放
        while (!s.empty() && s.top() <= nums[i]) { // 判定个子高矮
            s.pop(); // 矮个起开，反正也被挡着了。。。
        }
        ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个
        s.push(nums[i]); // 进队，接受之后的身高判定吧！
    }
    return ans;
}

589. N 叉树的前序遍历

一开始以为要建树，想复杂了,所以直接看了答案，就是先序遍历的非递归实现

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
38
39
40
41
42
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        if(root == NULL)
            return ans;

        stack<Node *> s;
        s.push(root);
        
        while(!s.empty()){
            Node *p = s.top();
            ans.push_back(p->val);
            s.pop();
            reverse(p->children.begin(),p->children.end());
            for(int i = 0;i < p->children.size();++i)
                s.push(p->children[i]);
        }

        return ans;
    }
};

附上递归做法

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 Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    void Traverse(Node *root,vector<int> &ans){
        ans.push_back(root->val);
        for(Node *p:root->children)
            Traverse(p,ans);
    }

    vector<int> preorder(Node* root) {
        vector<int> ans;
        if(root == NULL)
            return ans;
        Traverse(root,ans);
        
        return ans;
    }
};

0.6 数组

1588. 所有奇数长度子数组的和

部分和，想到了前缀和的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        //求前缀和
        vector<int> s(arr.size()+1,0);//前缀和数组
        for(int i = 0;i < arr.size();++i)
            s[i+1] = s[i]+arr[i];

        int maxodd = arr.size();
        if((arr.size()&1)==0)
            maxodd = arr.size()-1;
        int sum = 0;
        while(maxodd!=-1){
            for(int i = arr.size();i >= maxodd;i--){
                sum += s[i]-s[i-maxodd];
            }

            maxodd -= 2;
        }

        return sum;
    }
};

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

283. 移动零

借助一个辅助数组，快慢指针，最后末尾补零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        vector<int> tmp(len,0);
        int cnt = 0;
        for(int i = 0;i < len;++i){
            if(nums[i] != 0){
                tmp[cnt++] = nums[i];
            }
        }

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

快慢指针

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
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        int j = 0;//慢指针
        for(int i = 0;i < len;++i){//nums游标为快指针
            if(nums[i] != 0){
                nums[j++] = nums[i];
            }
        }

        for(;j < len;++j)
            nums[j] = 0;
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

1672. 最富有客户的资产总量

求和，遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int max = -1;
        int len = accounts.size();
        
        for(int i = 0;i < len;++i){
            int sum = accumulate(&accounts[i][0],&accounts[i][0]+accounts[i].size(),0);
            if(max < sum)
                max = sum;
        }

        return max;
    }
};

1572. 矩阵对角线元素的和

求对角线元素的和

  • 主对角线：横纵坐标下标相等

  • 副对角线：横+纵=方阵维度-1

  • 当是奇数维方阵，会加两次中心元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int r = mat.size();//矩阵的行
        int sum = r&1?sum = -mat[r/2][r/2]:0;

        for(int i = 0;i < mat.size();++i){
            for(int j = 0;j < mat[i].size();++j){
                if(i == j)
                    sum += mat[i][j];
                if(i+j == r-1)
                    sum += mat[i][j];
            }
        }

        return sum;
    }
};

时间复杂度：$O(n^2)$

题解

由于目标元素下标的关系

  • 主对角线：横纵坐标下标相等

  • 副对角线：横+纵=方针维度-1

第一行(0)：a[0][0]+a[0][n-1-0]

第二行(1)：a[1][1]+a[1][n-1-1]

第三行(2)：a[2][2]+a[2][n-1-2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size(), sum = 0, mid = n / 2;
        for (int i = 0; i < n; ++i) {
            sum += mat[i][i] + mat[i][n - 1 - i];
        }
        return sum - mat[mid][mid] * (n & 1);
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/matrix-diagonal-sum/solution/ju-zhen-dui-jiao-xian-yuan-su-de-he-by-leetcode-so/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：$O(n)$

566. 重塑矩阵

由于vector的二维矩阵行之间不连续，所以不能直接按一维数组使用，需转成一维数组，在转为二维数组

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
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) { 
        //计数
        int ElementCount = 0;
        vector<int> array;//二维变一维
        for(int i = 0;i < mat.size();++i){
            for(int j = 0;j < mat[i].size();++j){
                ElementCount++;
                array.push_back(mat[i][j]);
            }
                
        }
        //不合法输入
        if(r*c > ElementCount){
            return mat;
        }

        vector<vector<int>> ans(r,vector<int>(c));
        int idx = 0;//一维数组下标
        
        for(int i = 0;i < r;++i){
            ans[i].clear();
            for(int j = 0;j < c;++j){
                ans[i].push_back(array[idx++]);
            }
            
        }

        return ans;
    }
};

输入：

[[1,2]] 1 1

输出：

[[1]]

预期结果：

[[1,2]]

这谁顶得住，题意是说 r*c != ElementCount ，就输出原矩阵，我以为目标矩阵元素数小于原矩阵会发生截取

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
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) { 
        //计数
        int ElementCount = 0;
        vector<int> array;//二维变一维
        for(int i = 0;i < mat.size();++i){
            for(int j = 0;j < mat[i].size();++j){
                ElementCount++;
                array.push_back(mat[i][j]);
            }
                
        }
        //不合法输入
        if(r*c != ElementCount){
            return mat;
        }

        vector<vector<int>> ans(r,vector<int>(c));
        int idx = 0;//一维数组下标
        
        for(int i = 0;i < r;++i){
            ans[i].clear();
            for(int j = 0;j < c;++j){
                ans[i].push_back(array[idx++]);
            }
            
        }

        return ans;
    }
};

多个二维数组下标之间的映射关系

来看答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        int m = nums.size();
        int n = nums[0].size();
        if (m * n != r * c) {
            return nums;
        }

        vector<vector<int>> ans(r, vector<int>(c));
        for (int x = 0; x < m * n; ++x) {
            ans[x / c][x % c] = nums[x / n][x % n];
        }
        return ans;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reshape-the-matrix/solution/zhong-su-ju-zhen-by-leetcode-solution-gt0g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

相当于模拟一个一维数组，mat映射到array中，array中数组再映射到ans数组中

$mat[i][j]\Rightarrow array[idx]$

$array[idx]\Rightarrow ans[p][q]$

故可由一维数组下标建立两个二维数组之间关系

1
2
3
4
5
6
vector<vector<int>> ans(r, vector<int>(c));//初始化定义ans的行，每行初值
//ans(行数,每行初值为长度为c的vector<int>类型的一维数组)

for (int x = 0; x < m * n; ++x) {
    ans[x / c][x % c] = nums[x / n][x % n];
}

0.7 字符串

1768. 交替合并字符串

类似于链表合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string ans = "";
        int i = 0,j = 0;
        int len1 = word1.size(),len2 = word2.size();
        for(i = 0;i < len1&&j < len2;++i,++j){
            ans += word1[i];
            ans += word2[j];
        }

        if(i != len1)
            ans += word1.substr(i,len1-i+1);
        if(j != len2)
            ans += word2.substr(i,len2-j+1);

        return ans;
    }
};

1678. 设计 Goal 解析器

字符串遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string interpret(string command) {
        string ans = "";

        for(int i = 0;i < command.size();++i){
            if(command[i] == 'G')
                ans += 'G';
            if(command[i]=='('){
                if(command[i+1]==')'){
                    ans += 'o';
                    i++;
                }
                else if(command[i+1]=='a'){
                    ans += "al";
                    i = i+3;
                }
            }

        }

        return ans;
    }
};

时间复杂度$O(n)$

题解

  • 将”()”replace为”o”
  • 将”(“replace为””
  • 将”)”replace为””
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void replace_all(string &src,string old,int n0,string newStr){
        //用newStr全局替换old中的n0个字符
        int idx = -1;
        while(1){
            idx = src.find(old,idx+1);//从字符串的str[idx]开始查找old,返回找到的第一个
            if(idx == -1){
                break;
            }
            src.replace(idx,n0,newStr);
        }
    }

    string interpret(string command) {
        replace_all(command,"()",2,"o");
        replace_all(command,"(",1,"");
        replace_all(command,")",1,"");
        return command;
    }
};

389. 找不同

一开始以为不同的字符一定只出现一次，所以只要找t中有且其哈希表为0的字符即可，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> bucket(26,0);

        for(int i = 0;i < s.size();++i){
            bucket[s[i]-'a']++;
        }
        int i;
        for(i = 0;i < t.size();++i){
            if(bucket[t[i]-'a']==0)
                break;
        }

        return t[i];
    }
};

输入：

“a” “aa”

输出：

“”

预期结果：

“a”

那就设两个哈希表，对比不相等的字符数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> bucket1(26,0);
        vector<int> bucket2(26,0);

        for(int i = 0;i < s.size();++i){
            bucket1[s[i]-'a']++;
        }
        for(int i = 0;i < t.size();++i)
            bucket2[t[i]-'a']++;

        int i;
        for(i = 0;i < 26;++i){
            if(bucket1[i] != bucket2[i])
                break;
        }

        return 'a'+i;
    }
};

哈希

同样是哈希啊，人家只用了一个辅助数组

s中的+，t中的-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> cnt(26, 0);
        for (char ch: s) {
            cnt[ch - 'a']++;
        }
        for (char ch: t) {
            cnt[ch - 'a']--;
            if (cnt[ch - 'a'] < 0) {
                return ch;
            }
        }
        return ' ';
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-the-difference/solution/zhao-bu-tong-by-leetcode-solution-mtqf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

空间复杂度：$O(n)$

ASCII本质也是数值

每个字符求和，两字符和差值即为添加的字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    char findTheDifference(string s, string t) {
        int as = 0, at = 0;
        for (char ch: s) {
            as += ch;
        }
        for (char ch: t) {
            at += ch;
        }
        return at - as;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-the-difference/solution/zhao-bu-tong-by-leetcode-solution-mtqf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

709. 转换成小写字母

没仔细看题，以为是由大小写字母组成字符串s

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string toLowerCase(string s) {
        // 97-65
        for(int i = 0;i < s.size();++i){
            if(s[i] < 97)
                s[i] += 32;
        }

        return s;
    }
};

改为：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string toLowerCase(string s) {
        // 97-65
        for(int i = 0;i < s.size();++i){
            if(s[i] <= 'Z' && s[i] >= 'A')
                s[i] += 32;
        }

        return s;
    }
};

题解

方法一：algorithm有自带的函数 s.tolower(),s.toupper()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string toLowerCase(string s) {
        for (char& ch: s) {
            ch = tolower(ch);
        }
        return s;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/to-lower-case/solution/zhuan-huan-cheng-xiao-xie-zi-mu-by-leetc-5e29/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：按位或替代加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string toLowerCase(string s) {
        for (char& ch: s) {
            if (ch >= 65 && ch <= 90) {
                ch |= 32;
            }
        }
        return s;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/to-lower-case/solution/zhuan-huan-cheng-xiao-xie-zi-mu-by-leetc-5e29/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1309. 解码字母到整数映射

atoi()的参数是 const char ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char类型的,而stoi()的参数是const string,不需要转化为 const char；

第一想法是正序遍历，找到#后回溯，处理完两位数的在处理一位数的，时间复杂度为 $O(n^2)$,源于for循环内的find

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
class Solution {
public:
    string freqAlphabets(string s) {
        //找到所有#
        int idx = -1;//记录#下标
        int cnt = 0;//记录#个数
        string ss = s;
        for(int i = 0;i < s.size();++i){
            idx = s.find("#",idx+1); 
            if(idx == -1)
                break;

            //替换每个#组合
            string t;
            t.push_back((char)(stoi(s.substr(idx-2,2))+96)); 
            ss.replace(idx-2-2*cnt,3,t);
            cnt++;
        }

        for(int i = 0;i < ss.size();++i){
            if(ss[i] >= '1' && ss[i] <= '9')
                ss[i] = 'a'+ss[i]-49;
        }

        return ss;
    }
};

对上述代码优化，变为 $O(n)$

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
class Solution {
public:
    string freqAlphabets(string s) {
        //找到所有#
        int idx = -1;//记录#下标
        int cnt = 0;//记录#个数
        string ss = s;
        while(1){  
            idx = s.find("#",idx+1); 
            if(idx == -1)
                break;
            //替换每个#组合
            string t;
            t.push_back((char)(stoi(s.substr(idx-2,2))+96)); 
            ss.replace(idx-2-2*cnt,3,t);
            cnt++;
        }
        

        for(int i = 0;i < ss.size();++i){
            if(ss[i] >= '1' && ss[i] <= '9')
                ss[i] = 'a'+ss[i]-49;
        }

        return ss;
    }
};

不管怎么说都算是优化了吧

第二种思路是逆序，不需要两层循环，若是 # ，则回退三步；若是数字，则直接变字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string freqAlphabets(string s) {
        for(int i = s.size()-1;i >= 0;--i){
            if(s[i] == '#'){
                string t;
                t.push_back((char)(stoi(s.substr(i-2,2))+97-1));
                // cout << char(stoi(s.substr(i-2,2))+97-1) << endl;
                s.replace(i-2,3,t);
                i -= 2;
            }else if(s[i] >= 48 && s[i] <= 57){
                // s[i] = s[i]-48+97-1;
                s[i] = s[i]+48;
            }
        }

        return s;
    }
};

这个有点匪夷所思，时间复杂度是$O(n)$ ,空间差这么多

题解

对哈，正序直接新建空字符串开始也行啊。我的麻烦点在于折腾一些库函数浪费了时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string freqAlphabets(string s) {
        string ans;
        for (int i = 0; i < s.size(); ++i) {
            if (i + 2 < s.size() && s[i + 2] == '#') {
                ans += char((s[i] - '0') * 10 + (s[i + 1] - '1') + 'a');
                i += 2;
            }
            else {
                ans += char(s[i] - '1' + 'a');
            }
        }
        return ans;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/decrypt-string-from-alphabet-to-integer-mapping/solution/jie-ma-zi-mu-dao-zheng-shu-ying-she-by-leetcode-so/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

953. 验证外星语词典

建立 $abc…xyz\rightarrow 1,3,…,26$ 映射的哈希表，按 order 顺序，第一个为权值为26，依次递减。

匹配：

  • 相邻单词长度相等，符合字典序
  • 第一个单词时第二个单词的前缀，符合字典序，如：["app","apple"]
  • 第一个单词是第二个单词的后缀，不符合字典序，如：["apple","app"]
  • 一般情况：hash[s1[i]] < hash[s2[i]]，则返回 false
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
class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        //建立哈希表
        vector<int> hash(26,0);
        for(int i = 0;i < 26;++i){
            hash[order[i]-97] = 26-i;
        }
        //遍历单词表
        for(int i = 0;i < words.size()-1;++i){
            //找到相邻单词的第一个不相等字母
            int j;
            for(j = 0;j < words[i].size();++j){
                if(words[i][j] != words[i+1][j])
                    break;
            }

            //相邻单词相等情况
           	if(j == words[i].size() && j == words[i+1].size())
                continue;
            //如果前一个单词时前一个单词后缀，则返回false
            else if(j == words[i+1].size())
                return false;
            //如果前一个单词时后一个单词前缀，继续遍历
            else if(j == words[i].size())
                continue;
            //如果前一个单词的hash小于后一个单词，则犯规false
            else if(hash[words[i][j]-97] < hash[words[i+1][j]-97])
                return false;
        }

        return true;
    }
};

08. 链表&树

1290. 二进制链表转整数

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
/**
 * 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:
    int getDecimalValue(ListNode* head) {
        ListNode *p = head;
        int ans = 0;

        //链表不为空，所以不判断空
        while(p){
            ans <<= 1;
            if(p->val != 0)   
                ans += 1;
            p = p->next;
        }

        return ans;
    }
};

这里就把链表当做一个数组，只不过遍历方式不同

876. 链表的中间结点

笨办法：两轮遍历，第一轮获取长度，第二轮获取结点

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
/**
 * 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* middleNode(ListNode* head) {
        int cnt = 0;
        ListNode *p = head;

        while(p){
            cnt++;
            p = p->next;
        }

        int mid = cnt/2;
        p = head;
        for(int i = 0;i < mid;++i)
            p = p->next;
        
        return p;
    }
};

带点套路：快慢指针，快指针走两步，慢指针走一步

链表判空，给人整不会了

题解——快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            //单数情况为fast->next ==NULL,双数情况是fast为NULL
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

104. 二叉树的最大深度

用递归层数表示树的最大深度

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //r的左子树深度与右子树深度取最大值max,返回max+1
    int maxDepth(TreeNode* r) {
        //根为空
        if(r == NULL)
            return 0;

        //叶子结点
        if(r->left == NULL && r->right == NULL)
            return 1;

        int leftdep = 0;//左子树深度
        int rightdep = 0;//右子树深度
        if(r->left != NULL)
            leftdep = maxDepth(r->left);
        if(r->right != NULL)
            rightdep = maxDepth(r->right);

        if(leftdep > rightdep)
            return leftdep+1;
        else
            return rightdep+1;
    }
};

时间复杂度：$O(n)$，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：$O(height)$，其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

题解

层序遍历，借助一个队列

根入队，队不空

  • 队中所有结点出队
  • 每出一个结点，将其子节点全部入队
  • 每判空一次，深度加一
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
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        //空树，返回0
        if(root == NULL)
            return 0;

        queue<TreeNode*> Q;
        int ans = 0;
        Q.push(root);
        while(!Q.empty()){
            ans++;
            int cnt = Q.size();
            while(cnt){
                TreeNode* p = Q.front();
                Q.pop();//出队
                if(p->left)
                    Q.push(p->left);
                if(p->right)
                    Q.push(p->right);
                cnt--;
            }
        }

        return ans;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

404. 左叶子之和

还是递归，如果直接走到叶子结点，无法判断是左叶子还是右叶子，而且不想引入多余父指针，所以判断叶子结点的父结点

  • 第一种情况是左子树为左叶子，右子树为空，此时只需要返回左叶子值即可

  • 第二种情况是左子树为左叶子，右子树不为空，此时，需要判断右子树是否也有左叶子

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
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //返回左子树左叶子+右子树左叶子
    int sumTree(TreeNode * r){
        int sum = 0;
        //左叶子的上一层结点
        //第一种情况是左子树为左叶子，右子树为空
        if(r->right == nullptr && r->left && r->left->left == nullptr && r->left->right == nullptr)
            return r->left->val;
        //第二种情况是左子树为左叶子，右子树不空
        if(r->right && r->left && r->left->left == nullptr && r->left->right == nullptr)
            sum = r->left->val;

        if(r->left)
            sum += sumTree(r->left);
        if(r->right)
            sum += sumTree(r->right);

        return sum;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr)
            return 0;
            
        //只有一个根结点
        if(root->left == NULL && root->right == NULL)
            return 0;
        
        return sumTree(root);
    }
};

第二种思路是迭代：层序遍历（广搜）

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() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr)
            return 0;
        //只有一个根结点
        if(root->left == NULL && root->right == NULL)
            return 0;
        
        queue<TreeNode *> Q;
        Q.push(root);
        int ans = 0;
        while(!Q.empty()){
            TreeNode *p = Q.front();
            Q.pop();
            if(p->left != nullptr)
                Q.push(p->left);
            if(p->right != nullptr)
                Q.push(p->right);
            if(p->left && p->left->left == nullptr && p->left->right==nullptr)
                ans += p->left->val;
        }

        return ans;
    }
};
-------------本文结束-------------