57 和为 S 的两个数字

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]

示例 2:

输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]

限制:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

题解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i=0;
        int j=nums.size()-1;
        while(i<j)
        {
            if(nums[i]+nums[j]>target)j--;
            else if(nums[i]+nums[j]<target)i++;
            else return {nums[i],nums[j]};
        }
        return {};
    }
};

57.2 和为 S 的连续正数序列

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例 1:

输入:target = 9
输出:[[2,3,4],[4,5]]

示例 2:

输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

限制:

  • 1 <= target <= 10^5

题解

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        vector<int> subRes={1,2};
        
        int i=1,j=2,s=3;
        while(i<j)
        {
            if(s==target)
            {
                res.push_back(subRes);
            }
            if(s>=target)
            {
                s-=i;
                subRes.erase(subRes.begin());
                i++;
            }
            else
            {
                j++;
                s+=j;
                subRes.push_back(j);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        vector<vector<int>> res;
        while(i < j) {
            if(s == target) {
                vector<int> ans;
                for(int k = i; k <= j; k++)
                    ans.push_back(k);
                res.push_back(ans);
            }
            if(s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res;
    }
};

58 - I 翻转单词顺序列

题解

/*
 * @lc app=leetcode.cn id=151 lang=cpp
 *
 * [151] 反转字符串中的单词
 */

// @lc code=start
class Solution {
public:
    string reverseWords(string s) {
        stringstream ss(s);
        string res;
        string subStr;
        while(getline(ss,subStr,' '))
        {
            if(!subStr.empty())
                res = subStr + ' ' + res;
        }

        res.pop_back();//去掉最开始后面的空格 subStr+' '+""
        return res;
    }
};
// @lc code=end

/*LCOF 58-I*/
class Solution {
public:
    string reverseWords(string s) {
        string res;
        for(int j=s.size()-1;j>=0;j--)
        {
            //跳过后方空格
            if(s[j]==' ')
                continue;

            //扫描单词
            int i=j;
            while(i>=0 && s[i]!=' ')i--;

            res.append(s.substr(i+1,j-i));
            res.append(" ");
            j=i;//下一次扫描
        }
        if(!res.empty())
            res.pop_back();//去掉第一次的空格
        return res;
    }
};

58 - II 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1:

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2:

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制:

  • 1 <= k < s.length <= 10000

题解

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string res;
        res.append(s.substr(n,s.size()-n));
        res.append(s.substr(0,n));
        return res;
    }
};

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string res = string(s);
        int len = s.length();
        for(int i=0;i<len;i++)
        {
            res[(i+len-n)%len]=s[i];
        }
        return res;
    }
};

796 旋转字符串

给定两个字符串, sgoal。如果在若干次旋转操作之后,s 能变成 goal ,那么返回 true

s旋转操作 就是将 s 最左边的字符移动到最右边。

  • 例如, 若 s = 'abcde',在旋转一次之后结果就是'bcdea'

示例 1:

输入: s = "abcde", goal = "cdeab"
输出: true

示例 2:

输入: s = "abcde", goal = "abced"
输出: false

提示:

  • 1 <= s.length, goal.length <= 100
  • sgoal 由小写英文字母组成

题解

/*
 * @lc app=leetcode.cn id=796 lang=cpp
 *
 * [796] 旋转字符串
 */

// @lc code=start
class Solution {
public:
    bool rotateString(string s, string goal) {
        return s.size() == goal.size() && (s + s).find(goal) != string::npos;
    }
};
// @lc code=end