35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0) return 0;
        for(int i=0;i<n;i++)
        {
            if(nums[i]>=target)
                return i;
        }
        return n;
        
    }
};

053 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int tmp = 0;
        int rst = INT_MIN;
        for(auto x:nums)
        {
            tmp = max(tmp+x,x);
            rst = max(rst,tmp);
        }
        return rst;
    }
};

058 最后一个单词的长度

给定一个仅包含大小写字母和空格 ’ ’ 的字符串，返回其最后一个单词的长度。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指由字母组成，但不包含任何空格的字符串。

示例:

输入: “Hello World”
输出: 5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/length-of-last-word

class Solution {
public:
    int lengthOfLastWord(string s) {
        int rst = 0,i=s.length()-1;
        while(i>=0&&s[i]==' ')
            i--;
        while(i>=0&&s[i]!=' ')
        {
            rst++;
            i--;
        }
        return rst;
    }
};

066 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size()-1;
        while(n>=0)
        {
            if(digits[n]<9)
            {
                digits[n]+=1;
                return digits;
            }
            digits[n--]=0;
        }
        vector<int> rst(digits.size()+1,0);
        rst[0]=1;
        return rst;
    }
};

067 二进制求和

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “1”
输出: “100”
示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary

class Solution {
public:
    string addBinary(string a, string b) {
        int aSize = a.size();
        int bSize = b.size();
        int c = '0';
        string str,rst;
        // string rst;
        
        while(aSize>bSize) //补齐长度
        {
            b='0'+b;
            bSize++;
        }
        while(bSize>aSize)
        {
            a='0'+a;
            aSize++;
        }
        for(int i=a.size()-1;i>=0;i--)
        {
            int numofone=0;//统计1的个数
            if(a[i]=='1')
                numofone++;
            if(b[i]=='1')
                numofone++;
            if(c=='1')
                numofone++;
            
            if(numofone==0)
            {
                str.insert(0, 1, '0');
                // str+='0';
                c='0';
            }
            if(numofone==1)
            {
                str.insert(0, 1, '1');
                //str+='1';
                c='0';
            }
            if(numofone==2)
            {
                str.insert(0, 1, '0');
                //str+='0';
                c='1';
            }
            if(numofone==3)
            {
                str.insert(0, 1, '1');
                // str+='1';
                c='1';
            }
        }
        if(c=='1')
        {
            str.insert(0, 1, '1');
            // str+='1';
        }        
        // for(int i=str.size()-1;i>=0;i--)
        //     rst+=str[i]; 
        return str;
    }
    
};