LeetCode：53、58、66、67

53、最大子序和

/*
 * @Author: 零泽
 * @Date: 2021/04/26 15:52:56
 * @LastEditors: 零泽
 * @LastEditTime: 2021/04/26 16:09:27
 * @FilePath: \vscode\leetcode\53.最大子序和.cpp
 * @Description:
 */
/*
 * @lc app=leetcode.cn id=53 lang=cpp
 *
 * [53] 最大子序和
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
  public:
    int maxSubArray(vector<int> &nums) {
        int SumMax = nums.at(0);
        int temp;
        for (int i = 0; i < nums.size(); i++) {
            temp = 0;
            for (int j = i; j < nums.size(); j++) {
                temp += nums.at(j);
                if (temp > SumMax) {
                    SumMax = temp;
                }
            }
        }
        return SumMax;
    }
    // 203/203 cases passed (1364 ms)
    // Your runtime beats 5.04 % of cpp submissions
    // Your memory usage beats 91.04 % of cpp submissions (12.7 MB)
    // 觉得可以用递归做，成绩会更好一些
    // TODO:优化这个算法
};
// @lc code=end

58、最后一个单词的长度

/*
 * @Author: 零泽
 * @Date: 2021/04/26 16:11:37
 * @LastEditors: 零泽
 * @LastEditTime: 2021/04/26 17:16:15
 * @FilePath: \vscode\leetcode\58.最后一个单词的长度.cpp
 * @Description:
 */
/*
 * @lc app=leetcode.cn id=58 lang=cpp
 *
 * [58] 最后一个单词的长度
 */

// @lc code=start
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
class Solution {
  public:
    int lengthOfLastWord(string s) {
        vector<int> pos;
        bool judge = 1;
        int len = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.at(i) == ' ') {
                judge = 0;
                len++;
                if ((i > 0 && s.at(i - 1) != ' ') ||
                    (i < s.length() - 1 && s.at(i + 1) != ' ')) {
                    pos.push_back(i);
                    // cout << i << " ";
                }
                // system("pause");
            }
        }
        if (judge) {
            return s.length();
        }
        if (len == s.length()) {
            return 0;
        }
        if (s.at(s.length() - 1) != ' ') {
            pos.push_back(s.length());
        }
        if (pos.size() > 1) {
            return pos.at(pos.size() - 1) - pos.at(pos.size() - 2) - 1;
        } else {
            return pos.at(0);
        }
        // 58/58 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 8.63 % of cpp submissions (6.5 MB)
        // TODO:尽量不用vector，优化
    }
};
// @lc code=end

66、加一

/*
 * @Author: 零泽
 * @Date: 2021/04/27 19:09:58
 * @LastEditors: 零泽
 * @LastEditTime: 2021/04/28 13:22:58
 * @FilePath: \vscode\leetcode\66.加一.cpp
 * @Description:
 */
/*
 * @lc app=leetcode.cn id=66 lang=cpp
 *
 * [66] 加一
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
  public:
    /**
     * @Author: 零泽
     * @param {vector<int>} &digits
     * @return {*}
     * @description:一开始想用递归的，但是失败了
     */
    vector<int> plusOne(vector<int> &digits) {
        int flag = 1;
        bool judge = 1;
        if (digits.at(0) == 0) {
            judge = 0;
        }
        for (int i = digits.size() - 1; i >= 0; i--) {
            digits.at(i) += flag;
            if (digits.at(i) > 9) {
                digits.at(i) -= 10;
                flag = 1;
            } else {
                flag = 0;
            }
        }
        if (digits.at(0) == 0 && judge) {
            digits.push_back(digits.at(digits.size() - 1));
            for (int i = digits.size() - 2; i > 0; i--) {
                digits.at(i) = digits.at(i - 1);
            }
            digits.at(0) = 1;
        }
        return digits;
    }
    // 111/111 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 77.26 % of cpp submissions (8.5 MB)
};
// @lc code=end

67、二进制求和

/*
 * @Author: 零泽
 * @Date: 2021/05/06 18:39:43
 * @LastEditors: 零泽
 * @LastEditTime: 2021/05/06 20:14:13
 * @FilePath: \vscode\leetcode\67.二进制求和.cpp
 * @Description:
 */
/*
 * @lc app=leetcode.cn id=67 lang=cpp
 *
 * [67] 二进制求和
 */

// @lc code=start
#include <iostream>
#include <string.h>
using namespace std;
class Solution {
  public:
    /**
     * @Author: 零泽
     * @param {string} a
     * @return {*}
     * @description: 倒置
     */
    string convert(string a) {
        string c;
        for (int i = a.length() - 1; i >= 0; i--) {
            c.push_back(a.at(i));
        }
        return c;
    }
    /**
     * @Author: 零泽
     * @param {string} a
     * @return {*}
     * @description: 判断进位数是否为0
     */
    bool judge(string a) {
        for (int i = 0; i < a.length(); i++) {
            if (a.at(i) == '1') {
                return 0;
            }
        }
        return 1;
    }
    /**
     * @Author: 零泽
     * @param {string} a
     * @param {string} b
     * @return {*}
     * @description:
     * 把两个数的和数拆为模2加的结果和进位数，再递归相加，本以为很巧妙，但实际上并没什么卵用
     */
    string addBinary(string a, string b) {
        a = convert(a);
        b = convert(b);
        if (a.length() > b.length()) {
            swap(a, b);
        }
        string result, carry;
        carry.push_back('0');
        for (int i = 0; i < a.length(); i++) {
            if (a.at(i) != b.at(i)) {
                result.push_back('1');
                carry.push_back('0');
            } else {
                result.push_back('0');
                if (a.at(i) == '0') {
                    carry.push_back('0');
                } else {
                    carry.push_back('1');
                }
            }
        }
        for (int i = a.length(); i < b.length(); i++) {
            result.push_back(b.at(i));
        }
        if (judge(carry)) {
            if (result == "0") {
                return result;
            }
            int pos = 0;
            while (convert(result).at(pos) == '0') {
                pos++;
            }
            return convert(result).substr(pos);
        } else {
            carry = convert(carry);
            result = convert(result);
            return addBinary(carry, result);
        }
    }
};
// 294/294 cases passed (8 ms)
// Your runtime beats 11.33 % of cpp submissions
// Your memory usage beats 5.14 % of cpp submissions (9 MB)
// TODO:优化
// @lc code=end