leetcode题目(3)

目录

1.加一

2.二进制求和

3.x的平方根

4.爬楼梯

5.颜色分类

6.二叉树的中序遍历

1.加一

https://leetcode.cn/problems/plus-one/

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for(int i = n -1;i>=0;--i)
        {
            if(digits[i] != 9)
            {
                ++digits[i];
                for(int j = i + 1;j<n;++j)
                {
                    digits[j] = 0;
                }
                return digits;
            }
        }
        //数组全部为9
        vector<int> ans(n+1);
        ans[0] = 1;
        return ans;
    }
};

2.二进制求和

https://leetcode.cn/problems/add-binary/description/

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        string builder;
        //循环相加两个字符串相同长度的低位数部分
        while (i >= 0 && j >= 0) {
            int sum = carry;
            std::cout<<"a---"<<a.at(i)-'0'<<std::endl;
            std::cout<<"b---"<<b.at(j)-'0'<<std::endl;
            sum += a.at(i--) - '0';
            sum += b.at(j--) - '0';
            carry = sum / 2; //是否进位
            builder+=to_string((sum % 2));
        }
        // 如果 a 还没遍历完成（a串比b串长），则继续遍历添加 a 的剩余部分
        while (i >= 0) {
            int sum = carry + a.at(i--) - '0';
            carry = sum / 2;
            builder+=to_string(sum % 2);
        }
        // 如果 b 还没遍历完成（b串比a串长），则继续遍历添加 b 的剩余部分
        while (j >= 0) {
            int sum = carry + b.at(j--) - '0';
            carry = sum / 2;
            builder+=to_string(sum % 2);
        }
        //如果 carry 不等于0 还有个进位数没加进去，需要补充
        if (carry == 1) {
            builder+=to_string(carry);
        }
        //反转字符串获得正常结果
        reverse(builder.begin(),builder.end());
        return builder;
    }
};

3.x的平方根

https://leetcode.cn/problems/sqrtx/

class Solution {
public:
    int mySqrt(int x) {
        //使用库中函数
        int sum = sqrt(x);
        return sum;
    }
};

4.爬楼梯

https://leetcode.cn/problems/climbing-stairs/description/

class Solution {
public:
    int climbStairs(int n) {
        //f(x)=f(x-1)+f(x-2);
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) 
        {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

5.颜色分类

https://leetcode.cn/problems/sort-colors/description/

class Solution {
public:
    void sortColors(vector<int>& nums) {
        //sort(nums.begin(),nums.end());

        //p0交换0,p1交换1
        int p0 = 0,p1 = 0;
        for(int i = 0;i < nums.size();++i)
        {
            if(nums[i] == 1)
            {
                swap(nums[i],nums[p1]);
                ++p1;
            }
            else if(nums[i] == 0)
            {
                swap(nums[i],nums[p0]);
                if(p0 < p1)
                {
                    swap(nums[i],nums[p1]);
                }
                ++p0;
                ++p1;
            }
        }
    }
};

6.二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

class Solution {
public:
    void inorder(TreeNode* root,vector<int>& res)
    {
        if(root == NULL)
            return;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root,res);
        return res;
    }
};