C++每日刷题 day2025.7.09

思路就是利用俩“指针”i和j，每次i遇到空格，j刚好是单词的首字母，此时不仅仅加入，也将j的位置放到i+1的位置上即可，代码如下：

#include <iostream>
using namespace std;

int main() 
{
    string s;
    string ret;
    while (getline(cin, s))
    {
        for (int i = 0, j = 0; i < s.size(); i++)
        {
            if (s[i] == ' ')
            {
                if (s[j] >= 97)
                {
                    s[j] -= 32;
                }
                ret.push_back(s[j]);
                j = i + 1;
            }
            if (i == s.size() - 1)
            {
                if(s[j] >= 97){s[j] -= 32;}
                ret.push_back(s[j]);
            }
        }
        cout << ret;
    }
    return 0;
}

dd爱框框就是一个简单的滑动窗口问题，进窗口，判断，出窗口。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int N = 1e7 + 10;
int n = 0;
int x = 0;
int arr[N];
int ret;
int rightlen = -1;
int leftlen = -1;
int dis = N;
int main()
{
    cin >> n >> x;
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
    
    // 滑动窗口
    int left = 0;
    int right = 0;
    while (right <= n)
    {
        ret += arr[right];
        while (ret >= x)
        {
            
            if (right - left + 1 < dis)
            {
                leftlen = left;
                rightlen = right;
                dis = right - left + 1;
            }
            
            ret -= arr[left];
            left++;
        }
        right++;
    }
    
    cout << leftlen << " " << rightlen;
    return 0;
}

使用dfs这个思路，每次只要是递归层次到了与digits.size()层次的时候，此时就插入先前排列组合过的字母就行了，其他层级就全排列就用的是dfs。

class Solution {
public:
    string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ret;
    string path;
    vector<string> letterCombinations(string digits) {
        if (!digits.size()) return {};
        dfs(0, digits);
        return ret;
    }
    void dfs(int pos, string& digits)
    {
        if (pos == digits.size())
        {
            ret.push_back(path);
            return;
        }

        int index = digits[pos] - '0';
        for (int i = 0; i < hash[index].size(); ++i)
        {
            path += hash[index][i];
            dfs(pos + 1, digits);
            path.pop_back();
        }
    }
};

使用栈，左括号配合右括号，配合到了就返回true，其他都返回false。

class Solution {
public:
    bool isValid(string s) {
        if (s.size() == 0) return false;
        stack<char> st;
        for (int i = 0; i < s.size(); i++)
        {
            
            if (s[i] == '[' || s[i] == '(' || s[i] == '{')
            {
                st.push(s[i]);
            }
            else
            {
                if (st.empty())  return false;
                char top = st.top();
                switch(top)
                {
                    case '[':{
                        if (s[i] != ']') return false;
                        break;
                    }
                    case '(':{
                        if (s[i] != ')') return false;
                        break;
                    }
                    case '{':{
                        if (s[i] != '}') return false;
                        break;
                    }
                    default: break;
                }
                st.pop();
            }

        }
        if (!st.empty()) return false;
        return true;
    }
};