leetcode解题思路分析（八十一）708 - 717 题

╰+攻爆jí腚メ 2022-10-10 09:46 148阅读 0赞

1.  转换成小写字母  
    给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。

class Solution { 
    public:
        string toLowerCase(string s) 
        { 
            for (int i = 0; i < s.size(); i++)
            { 
                int gap = s[i] - 'A';
                if (gap >= 0 && s[i] <= 'Z')
                { 
                    s[i] = 'a' + gap;
                }
            }
            return s;
        }
    };

1.  黑名单中的随机数  
    给定一个包含 \[0，n) 中不重复整数的黑名单 blacklist ，写一个函数从 \[0, n) 中返回一个不在 blacklist 中的随机整数。

**假设黑名单长度为l，则我们映射到n-l的长度即可。如果在黑名单里，则手动映射至l到n的部分**

class Solution { 
    public:
    
        unordered_map<int, int> m;
        int wlen;
    
        Solution(int n, vector<int> b) { 
            wlen = n - b.size();
            unordered_set<int> w;
            for (int i = wlen; i < n; i++) w.insert(i);
            for (int x : b) w.erase(x);
            auto wi = w.begin();
            for (int x : b)
                if (x < wlen)
                    m[x] = *wi++;
        }
    
        int pick() { 
            int k = rand() % wlen;
            return m.count(k) ? m[k] : k;
        }
    };
    
    
    
    /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(n, blacklist); * int param_1 = obj->pick(); */

1.  两个字符串的最小ASCII删除和  
    给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

**动态规划求解dp\[i\]\[j\] = min(dp\[i + 1\]\[j\] + s1.asciiAtPos(i), dp\[i\]\[j + 1\] + s2.asciiAtPos(j))**

class Solution { 
    public:
        int minimumDeleteSum(string s1, string s2) { 
            int n1 = s1.size();
            int n2 = s2.size();
            int** d = new int*[n1+1];
            for (int i = 0; i <= n1; ++i)
            { 
                d[i] = new int[n2+1];
                memset(d[i], 0, sizeof(int)*(n2+1));
            }
    
            // 初始化两个边缘
            for (int j = n2-1; j >= 0; --j)
            { 
                d[n1][j] = d[n1][j+1] + s2[j];
            }
            for (int i = n1-1; i >= 0; --i)
            { 
                d[i][n2] = d[i+1][n2] + s1[i];
            }
    
            // 计算
            for (int i = n1-1; i >= 0; --i)
            { 
                for (int j = n2-1; j >= 0; --j)
                { 
                    if (s1[i] != s2[j])
                    { 
                        d[i][j] = min(d[i+1][j] + (int)s1[i], d[i][j+1] + (int)s2[j]);
                    }
                    else
                    { 
                        d[i][j] = d[i+1][j+1];
                    }
                }
            }
    
            return d[0][0];
        }
    };

1.  乘积小于k的子数组  
    给定一个正整数数组 nums。找出该数组内乘积小于 k 的连续的子数组的个数。

**双指针滑动**

class Solution{ 
    public:
          int numSubarrayProductLessThanK(vector<int>&nums,int k){ 
              int len = nums.size();
              int l   = 0;
              int res = 0;
              int pol = 1 ;
    
              //区间[l,r]形成的连续子数组（size>1）的个数为r-l+1个。
              for (int r =0 ; r < len; r++)
              { 
                  pol *= nums[r];
                  while (pol >= k && l <= r)
                  { 
                      pol /= nums[l];
                      l++;
                  }
                  res += r - l + 1;
              }
              return res;
          }
    };

1.  股票买卖的最佳时机  
    给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

**采用贪心算法：把手续费放在买入时就计算为成本，同时对于可能继续增长的情况，可以假设手上仍有当前价格持有的股票，再用更好的收益减去即可**

class Solution { 
    public:
        int maxProfit(vector<int>& prices, int fee) { 
            int n = prices.size();
            int buy = prices[0] + fee;
            int profit = 0;
            for (int i = 1; i < n; ++i) { 
                if (prices[i] + fee < buy) { 
                    buy = prices[i] + fee;
                }
                else if (prices[i] > buy) { 
                    profit += prices[i] - buy;
                    buy = prices[i];
                }
            }
            return profit;
        }
    };

1.  Range模块

class RangeModule { 
        map<int,int> m;
    public:
        RangeModule() { 
            m.clear();
        }
        
        void addRange(int left, int right) { 
            auto a = m.lower_bound(left);
            auto b = m.lower_bound(right);
            if(a == m.end()) m[right] = left;
            else{ 
                int start = (*a).second;
                auto p = a;
                while(p != b){ 
                    ++a;
                    m.erase(p);
                    p = a;
                }
                if(b == m.end() || (*b).second > right) m[right] = min(start,left);
                else (*b).second = min(start,left);
            }
        }
        
        bool queryRange(int left, int right) { 
            auto p = m.lower_bound(right);
            if(p == m.end() || (*p).second > left) return false;
            return true;
        }
        
        void removeRange(int left, int right) { 
            auto a = m.upper_bound(left);
            auto b = m.lower_bound(right);
            if(a == m.end() || right <= m.begin()->second) return;
            else{ 
                int x = (*a).second;
                auto p = a;
                while(p != b){ 
                    ++a;
                    m.erase(p);
                    p = a;
                }
                if(b != m.end()){ 
                    int y = (*b).first;
                    if((*b).second < right){  
                        m.erase(b);
                        if(right < y) m[y] = right;
                    }
                }
                if(x < left) m[left] = x;
            }
        }
    };
    
    
    
    /** * Your RangeModule object will be instantiated and called as such: * RangeModule* obj = new RangeModule(); * obj->addRange(left,right); * bool param_2 = obj->queryRange(left,right); * obj->removeRange(left,right); */

1.  1比特与2比特字符  
    有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

**因为是1只能加2，是0只能加1，所以遍历一遍即可，非常简单**

class Solution { 
    public:
        bool isOneBitCharacter(vector<int>& bits) 
        { 
            return isOneBit(bits, 0);
        }
    
        bool isOneBit(vector<int>& bits, int pos)
        { 
            if ((pos == bits.size() - 1))
            {            
                return !bits[pos];
            }
            else if (bits[pos])
            { 
                if (pos + 2 == bits.size())
                    return false;
                else
                    return isOneBit(bits, pos + 2);
            }
            else
            {      
                return isOneBit(bits, pos + 1);
            }
        }
    };
    
    class Solution { 
    public:
        bool isOneBitCharacter(vector<int>& bits) { 
            int n = bits.size();
            int i = 0;
            // 这里只遍历到倒数第二个
            while (i < n - 1)
            { 
                i += bits[i] + 1;
            }
    
            return i == n-1;
        }
    };