力扣Day2

4道easy+6道medium+1道hard，今天做起来明显比昨天难受，做了一下午，字符串确实学的是一坨啊(悲)

(easy)2591. 将钱分给最多的儿童

说实话，一眼数学题，但想了想不好推公式，所以直接开始经典分类讨论了，反正数据量少(

首先，先算出最多能给k个人8美元，然后看如果给k个人分配8美元剩下的能否成功。不能成功的情况：有人获得4美元、每个人8美元还有剩。代码如下：

class Solution {
public:
    int distMoney(int money, int children) {
        if(money < children)
            return -1;
        int k = (money - children) / 7;
        int res = money - children - 7*k;
        if(children > k)
        {
            int res_c = res / (children - k);
            //有一个人获得4美元
            if((res == 3 && children - k ==1 ) && k >= 1)
                k--;
        }
        else if(children == k)
        {
            //每个人8美元还有剩，那么把剩的全给其中一个人
            if(money > children + 7*k)
            {
                k--;
            }
        }
        else
        {
            //每个人8美元还多的多，那么把剩余的钱全给一个人，只会有1个人拿不到8美元
            k = children - 1;
        }
        return k;
    }
};

(hard)42. 接雨水

早有耳闻的一道题，其实是道非常简单的大化小思路题—即每个位置能装最多水的量仅仅取决于其左右两边各最高位置的值，若用l[i]表示i点左方最高的值，用r[i]表示i点右方最高的值，则雨水在该点能接至最高min(l[i],r[i])—即木桶效应。思路清晰了那就很简单了，代码如下：

int l[20010];
int r[20010];
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        //l[i]表示左边最高，r[i]表示右边最高
        l[0] = height[0];
        r[n-1] = height[n-1];
        int ans = 0;
        for(int i=1;i<n;i++)
        {
            l[i] = max(height[i - 1],l[i - 1]);
        }
        for(int i=n-2;i>=0;i--)
        {
            r[i] = max(height[i + 1], r[i + 1]);
        }
        for(int i = 0;i<n;i++)
        {
            int temp = min(l[i],r[i]);
            if(temp > height[i])
                ans = ans + temp - height[i];
        }
        return ans;
    }
};

(easy)13. 罗马数字转整数

一道简单的小模拟，因为罗马数字中小的数字在大的数字的右边，所以从右往左遍历，遇到匹配的就进行处理即可。具体代码如下：

class Solution {
public:
    int single(char c) {
        if(c == 'I')
            return 1;
        if(c == 'V')
            return 5;
        if(c == 'X')
            return 10;
        if(c == 'L')
            return 50;
        if(c == 'C')
            return 100;
        if(c == 'D')
            return 500;
        if(c == 'M')
            return 1000;
        return 0;
    }
    int romanToInt(string s) {
        int n = s.length();
        int ans = 0;
        int sp = 0;
        for(int i=n-1;i>=0;i--)
        {
            int temp = single(s[i]);
            if(sp == 5 * temp || sp == 10 * temp)
                ans = ans - temp;
            else
            {
                ans = ans + temp;
                sp = temp;
            }
        }
        return ans;
    }
};

(medium)12. 整数转罗马数字

也是一道小模拟，过程中遇到最大的问题反而是不知道字符串咋清零(再次骂一遍啥批力扣，byd多个数据同时跑，因而函数里面需要清零，全局定义的不管用)。就是10*x 9*x 5*x 4*x的套路重复，代码如下：

char ans[200] = {};
class Solution {
public:
    string intToRoman(int num) {
        memset(ans,'\0',sizeof(ans));
        int temp = 0;
        //一整套的开始
        while(num >= 1000)
        {
            ans[temp] = 'M';
            temp++;
            num = num - 1000;
        }
        if(num >= 900)
        {
            ans[temp] = 'C';
            temp++;
            ans[temp] = 'M';
            temp++;
            num = num - 900;
        }
        if(num >= 500)
        {
            ans[temp] = 'D';
            temp++;
            num = num - 500;
        }
        if(num >= 400)
        {
            ans[temp] = 'C';
            temp++;
            ans[temp] = 'D';
            temp++;
            num = num - 400;
        }
        //一整套的结束
        //一整套的开始
        while(num >= 100)
        {
            ans[temp] = 'C';
            temp++;
            num = num - 100;
        }
        if(num >= 90)
        {
            ans[temp] = 'X';
            temp++;
            ans[temp] = 'C';
            temp++;
            num = num - 90;
        }
        if(num >= 50)
        {
            ans[temp] = 'L';
            temp++;
            num = num - 50;
        }
        if(num >= 40)
        {
            ans[temp] = 'X';
            temp++;
            ans[temp] = 'L';
            temp++;
            num = num - 40;
        }
        //一整套的结束
        //一整套的开始
        while(num >= 10)
        {
            ans[temp] = 'X';
            temp++;
            num = num - 10;
        }
        if(num >= 9)
        {
            ans[temp] = 'I';
            temp++;
            ans[temp] = 'X';
            temp++;
            num = num - 9;
        }
        if(num >= 5)
        {
            ans[temp] = 'V';
            temp++;
            num = num - 5;
        }
        if(num >= 4)
        {
            ans[temp] = 'I';
            temp++;
            ans[temp] = 'V';
            temp++;
            num = num - 4;
        }
        //一整套的结束
        while(num)
        {
            ans[temp] = 'I';
            temp++;
            num--;
        }
        return ans;
    }
};

(easy)58. 最后一个单词的长度

也是很简单的一道，从后往前数，第一个碰到的空格和第一个碰到的非空格记录下来即可。代码如下：

class Solution {
public:
    int lengthOfLastWord(string s) {
        int n = s.length();
        int s_start = 0;
        int s_end = 0;
        for(int i = n-1;i>=1;i--)
        {
            if(s[i] != ' ' && s[i-1] == ' ')
            {
                s_start = i;
                break;
            }
        }
        for(int i = n-1;i>=0;i--)
        {
            if(s[i] != ' ')
            {
                s_end = i;
                break;
            }
        }
        return s_end-s_start+1;
    }
};

(easy)14. 最长公共前缀

纯纯的暴力做法，懒得写马拉车那些了(。代码如下：

char s[201];
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        int maxn = 0;
        memset(s,0,sizeof(s));
        for(int i = 0; i<n;i++)
        {
            string s2 = strs[i];
            int m = s2.size();
            for(int j = 1; j<=m; j++)
            {
                string s3 = s2.substr(0,j);
                bool check = 1;
                bool islengthok = 1;
                for(int k = 0;k<n;k++)
                {
                    if(k == i)
                        continue;
                    if(j>strs[k].size())
                    {
                        islengthok = 0;
                        check = 0;
                        break;
                    }
                    string temp = strs[k].substr(0,j);
                    if(temp != s3)
                    {
                        check = 0;
                        break;
                    }
                }
                if(islengthok == 0)
                {
                    break;
                }
                if(check)
                {
                    if(j>maxn)
                    {
                        strcpy(s, s3.c_str());
                        maxn = j;
                    }
                }
            }
        }
        return s;
    }
};

(medium)151. 反转字符串中的单词

或许是我今天耗时最长的一道？(字符串我是真学的菜啊，oi时代欠的债现在补😭)转换思路为记录空格位置之后就好做了，代码如下：

char s1[10010];
int kongge[10010];
class Solution {
public:
    string reverseWords(string s) {
        memset(s1,0,sizeof(s1));
        memset(kongge,0,sizeof(kongge));
        int n = s.size();
        int kongge_cnt = 0;
        int s1_cnt = 0;
        for(int i=0;i<n;i++)
        {
            if(s[i] == ' ')
            {
                kongge[kongge_cnt] = i;
                kongge_cnt++;
            }
        }
        if(kongge_cnt>=1)
        {
            if(kongge[kongge_cnt-1] != n-1)
            {
                kongge[kongge_cnt] = n;
                kongge_cnt++;
            }
            for(int i=kongge_cnt-1;i>=1;i--)
            {
                if(kongge[i]-kongge[i-1]>1)
                {
                    for(int j=kongge[i-1]+1;j<kongge[i];j++)
                    {
                        s1[s1_cnt] = s[j];
                        s1_cnt++;
                    }
                    s1[s1_cnt] = ' ';
                    s1_cnt++;
                }
            }
            if(kongge[0]!=0)
            {
                for(int j=0;j<kongge[0];j++)
                {
                    s1[s1_cnt] = s[j];
                    s1_cnt++;
                }
            }
            if(s1[s1_cnt-1] == ' ')
                s1[s1_cnt-1] = '\0';
        }
        else
        {
            for(int i=0;i<n;i++)
                s1[i] = s[i];
        }
        return s1;
    }
};

(medium)6. N 字形变换

这下真字符串苦手了😭。主要是找规律，多少个为一个轮回，然后横纵坐标进行计算即可。代码如下：

char s1[1010][1010];
class Solution {
public:
    string convert(string s, int numRows) {
        memset(s1,'\0',sizeof(s1));
        int n = s.size();
        //2*numRows-2为一个循环
        //有n/2列
        int xx=1,yy=1;
        int maxn = 2*numRows - 2;
        int cnt = 0;
        for(int i=0;i<n;i++)
        {
            s1[yy][xx] = s[i];
            cnt++;
            if(cnt<numRows)
                yy++;
            else
            {
                if(cnt <= maxn)
                {
                    xx++;
                    yy--;
                }
                else
                {
                    cnt = 1;
                    yy++;
                }
            }
        }
        cnt = 0;
        int k = n/2;
        if(2*k != n)
            k++;
        for(int i=1;i<=numRows;i++)
        {
            for(int j=1;j<=k;j++)
            {
                if(s1[i][j]!='\0')
                {
                    s[cnt] = s1[i][j];
                    cnt++;
                }
            }
        }
        return s;
    }
};

(medium)15. 三数之和

纯折磨，优化过程想死，最后还是看的题解才发现双向指针二分可以。代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        int temp2 = -nums[n-2]-nums[n-1];
        for(int i=0;i<n;i++)
        {
            if(i>0&&nums[i] == nums[i-1])
                continue;
            if(nums[i]<temp2)
                continue;
            if(i<n-2&&nums[i]+nums[i+1]+nums[i+2]>0)
                break;
            int k = n - 1;
            for(int j=i+1;j<n;j++)
            {
                if(j>i+1&&nums[j] == nums[j-1])
                    continue;
                int temp = -nums[i]-nums[j];
                while(k>j&&nums[k]>temp)
                {
                    k--;
                }
                if(k == j)
                    break;
                if(nums[k] == temp)
                    ans.push_back({nums[i],nums[j],nums[k]});
            }
        }
        return ans;
    }
};

(medium)167. 两数之和 II - 输入有序数组

做了三数之和之后很easy。感觉两题本质不都是暴力优化吗(。代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n=numbers.size();
        for(int i=0;i<n;i++)
        {
            int temp = target - numbers[i];
            if(i>0&&numbers[i] == numbers[i-1])
                continue;
            for(int j=i+1;j<n;j++)
            {
                if(numbers[j]>temp)
                    break;
                if(numbers[j] == temp)
                    return {i+1,j+1};
            }
        }
        return {1,2};
    }
};

(medium)11. 盛最多水的容器

我承认，我的双指针知识早已忘却，但我能卡常！

言归正传，既然是双指针，那就需要证明这样跳的双指针是正确的。本题需要的是求一个min(height[r],height[l])*(r-l)的最大值。双指针那自然会移动指针，则我们需要找到正确移动指针的方式。我最开始是只按height[l] height[r]的比较来进行移动，发现会有问题；后面看到题解才恍然大悟，不需要在意是l还是r，当向内移动的一边为长板时，则最大值肯定是在减小；而移动的为短板时则不一定，这样就出来思路了：即移动短板，无所谓是l还是r。代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int maxn = 0;
        int l = 0;
        int r = n-1;
        while(l<r)
        {
            if(height[r]<height[l])
            {
                maxn = max(maxn,(r - l) * height[r]);
                r--;
            }
            else
            {
                maxn = max(maxn,(r - l) * height[l]);
                l++;
            }
        }
        return maxn;
    }
};