Day18 礼物的最大价值 + 翻转单词顺序 + 在排序数组中查

TODO

1. 重做礼物的最大价值
2. 翻转单词顺序的方法一(栈)和三再看一下(stringstream)
3. 在排序数组中查找数字 I 的方法二可以再看看
4. 二三题不同方法做出来，时间为什么差那么多。留给以后解决吧

一、剑指 Offer 47. 礼物的最大价值(中等)

出门级的动态规划问题，限制了只能向左和向下走，从而简化了问题。

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(); 
        vector<vector<int>> dp(n,vector<int>(m,0));
        dp[0][0] = grid[0][0];
        for(int i =1; i < n; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j =1; j< m; j++){
            dp[0][j] = grid[0][j] + dp[0][j-1];
        }
        for(int i = 1; i < n; i++){
            for(int  j = 1; j < m; j++){
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }
};

二、 剑指 Offer 58 - I. 翻转单词顺序(简单)

方法一 自己写的一次遍历

image.png

class Solution {
public:
    string reverseWords(string s) {
        if(s.empty()) return s;
        int j = 0;
        while(j < s.size() && s[j]==' '){
            j++;
        } 
        string res,temp;

        while(j < s.size()){
            temp = "";
            while(j < s.size() && s[j] != ' '){ 
                temp.push_back(s[j]);
                j++;
            }
            if(j <= s.size()){
                res = temp + " "+res;
                j++;
             }
            while(j < s.size() && s[j] ==' '){
                j++;
            }
        }
        return res.substr(0,res.size()-1);
    }
};

方法二 利用栈🐱🏍(效果最好的一个方法)

感觉思路差不多怎么空间开销和时间开销就差那么多呢...

class Solution {
public:
    string reverseWords(string s) {
        stack<char> word;
        string result = "";
        for (int i = s.size() - 1; i >= 0; --i)
        {
            if (s[i] != ' ') //遇到单词则入栈
            {
                word.push(s[i]);
            }
            if (s[i] == ' ' || i == 0) //遇到空格或第一个字符都要检查一下栈中是否有单词可以弹出
            {
                bool flag = false; //标记是否发生出栈
                while (word.empty() == false)
                {
                    result.push_back(word.top()); //因为word栈存储的元素为char型，而result为string型，故不能相加，只能使用push_back()
                    word.pop();
                    flag = true;
                }
                if (flag)
                {
                    result += " ";
                }
            }
        }
        return result.substr(0, result.size() - 1); //最后一个单词后面会多加一个空格
    }
};

image.png

方法三 字符流法⭐

利用istringstream对象以空格为分隔符把字符串分开的特性，将分开得到的单词逐一流入字符串word并进行拼接

class Solution {
public:
    string reverseWords(string s) {
        if(s.empty()) return "";
        stringstream ss(s);
        string t，res;
        while(ss>>t){
            res = t + " "+res;
        }
        res.pop_back();//⭐
      return res;
    }
};

image.png

方法四 原地翻转法⭐

就是把s,从最后一个不为空的字符，往前插入...并没有自己做一遍。只是看了下题解的答案，有时间再自己做一做。🐱👤

class Solution {
public:
    string reverseWords(string s) {
        if (s == "") //处理特殊情况 ""
        {
            return s;
        }
        bool rIsblank = true; //标记原始字符串中的当前字符的右边是否为空格
        int insertIndex = 0; //指向字符插入的位置
        int count = 0; //记录翻转后的新字符串长度
        int end = s.size() - 1; //永远指向当前字符串s的最后一个字符位置
        for (int i = s.size(); i > 0; --i)
        {
            if (rIsblank && s[end] == ' ') //遇到多余空格则删除
            {
                s.erase(end--, 1);
                rIsblank = true;
            }
            else if (!rIsblank && s[end] == ' ') //遇到单词左边空格
            {
                insertIndex = count;
                s.insert(insertIndex++, 1, s[end++]);
                s.erase(end--, 1);
                rIsblank = true;
                ++count;
            }
            else //遇到单词
            {
                s.insert(insertIndex, 1, s[end++]);
                s.erase(end--, 1);
                rIsblank = false;
                ++count;
            }
        }
        if (s == "") //处理特殊情况 " "
        {
            return s;
        }
        if (s[s.size() - 1] == ' ') //当输入的字符串第一个单词左边存在空格时，翻转后的字符串最后会多一个多余的空格
        {
            s.erase(s.size() - 1, 1);
        }
        return s;
    }
};

一些string的用法，string s.substr(pos,n);返回一个string，包含s中从pos开始的n个字符的拷贝(pos的默认值是0)，n的默认值是s.size()-pos,即不加参数会默认拷贝整个s，若pos的值超过了string```的大小，则substr函数会抛出一个out_of_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾。

三、 剑指 Offer 53 - I. 在排序数组中查找数字 I(简单)

一看到排序数组几个字，就觉得该用二分法。
于是写了个劣质二分法hhh：

class Solution {
public:
    int part(vector<int>& nums, int left ,int right,int target){
        if(left >= right) return nums[left] == target?left:-1;
        int mid = left + ( right - left)/2;
        if(nums[mid] == target) return mid;
        else if((nums[mid] > target)){   
            right = mid - 1;
        }
        else {
            left = mid+1;
        }
        return part(nums,left,right,target);
    }
    int search(vector<int>& nums, int target) {
        if(nums.size() == 0) return 0;
        int k = part(nums,0,nums.size()-1,target);
        int i = k, j =k;
        if(k==-1) return 0;
        else{
            while(i >=0 && nums[i] == target){
                i--;
            }
            while(j< nums.size() && nums[j] == target){
                j++;
            }
        }
        return j - i -1;

    }
};

image.png

方法二 完全二分法⭐

class Solution {
public:
    int part(vector<int>& nums, int left ,int right,int target){
        while(left <= right){
            int mid = left + ( right - left)/2;
            if(nums[mid] <= target) left = mid+1;
            else right= mid-1;
        }
        return left;
    }
    int search(vector<int>& nums, int target) {
        if(nums.size() == 0) return 0;
        return part(nums,0,nums.size()-1,target)-part(nums,0,nums.size()-1,target-1);//⭐注意这个target-1

    }
};

image.png

方法三 细化了很多判断条件的两次二分

class Solution {
public:
    int getK(vector<int>&nums, int len,int k,int start,int end,int flag){
        if(start>end) return -1;
        int mid = start + (end-start)/2;
        if(nums[mid] == k){
            if(flag == 0)//左边
            {
                if(mid==0 ||mid>0 &&(nums[mid-1]!=k)){
                    return mid;
                }
                else{
                    end = mid-1;
                }
            }else{
                if(mid==len-1 ||mid<len-1 &&(nums[mid+1]!=k)){
                    return mid;
                }
                else{
                    start = mid+1;
                }
            }
        }else if(nums[mid] < k){
            start = mid+1;
        }else{
            end = mid-1;
        }
        return getK(nums,len,k,start,end,flag);
    }
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        if(len <=0) return 0;
        int left = getK(nums,len,target,0,len-1,0);
        int right = getK(nums,len,target,0,len-1,1);
        if(left>=0 && right >=0) return (right-left+1);
        else return 0;

    }
};

image.png