算法训练day8: LeetCode 344.541.151.剑指offer05.58.

344.反转字符串

题目

344. 反转字符串 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• class Solution
  {
  public:
      void reverseString(vector<char> &s)
      {
          for (int i = 0, j = s.size() - 1; i < j; i++, j--)
          {
              swap(s[i], s[j]);
          }
      }
  };
  

  代码实现还是很简单的，解题时体现程序主要思想的地方不要使用库函数。

541.反转字符串II

题目

541. 反转字符串 II - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• class Solution {
  public:
      string reverseStr(string s, int k) {
          for(int i=0;i<s.size();i+=(2*k))
          {
              if(i+k<=s.size())
              reverse(s.begin()+i,s.begin()+i+k);
              else
              {
                  reverse(s.begin()+i,s.end());
              }
          }
          return s;
      }
  };
  

• 整体思路没问题，突然有事，先用reverse写完了

剑指Offer 05.替换空格

题目

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1： 输入：s = "We are happy."
输出："We%20are%20happy."

题解

代码随想录 (programmercarl.com)

• 从后向前添加

  • 不开辟新数组
  • 避免从前向后移动每次添加都需要把添加元素之后全部元素移动的问题

  class Solution
  {
  public:
      string replaceSpace(string s)
      {
          int count = 0;
          int sOldsize = s.size();
          for (int i = 0; i < s.size(); i++)
          {
              if (s[i] == ' ')
                  count++;
          }
  
          s.resize(s.size() + count * 2);
          int sNewsize = s.size();
          for (int i = sNewsize - 1, j = sOldsize - 1; j < i; i--, j--)
          {
              if (s[i] != ' ')
              {
                  s[j] = s[i];
              }
              else
              {
                  s[j] = '0';
                  s[j - 1] = '2';
                  s[j - 2] = '%';
                  j -= 2;
              }
          }
          return s;
      }
  };
  

151.翻转字符串里的单词

题目

151. 反转字符串中的单词 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• 整体思路：

  • 去除多余空格

    • 双指针，除第一个单词外，每个单词前加一个空格
    • 快指针识别单词开始，慢指针添加空格后与快指针同步移动实现单词复制
    • 更改去除空格后的结构大小（slow)

  • 整体反转实现单词整体顺序的反转

  • 对单个单词操作，实现单词内部字母顺序的调整

  class Solution
  {
  public:
      void removeExtraSpace(string &s)
      {
          int slow = 0;
          for (int i = 0; i < s.size(); i++)
          {
              if (s[i] != ' ')
              {
                  if (slow != 0)
                      s[slow++] = ' ';
                  while (i < s.size() && s[i] != ' ')
                  {
                      s[slow++] = s[i++];
                  }
              }
          }
          s.resize(slow);
      }
      void reverse(string &s, int start, int end)
      {
          for (int i = start, j = end; i < j; i++, j--)
          {
              swap(s[i], s[j]);
          }
      }
  
      string reverseWords(string s)
      {
          removeExtraSpace(s);
          reverse(s, 0, s.size() - 1);
          int start = 0;
          for (int i = 0; i <= s.size(); ++i)
          {
              if (s[i] == ' ' || i == s.size())
              {
                  reverse(s, start, i - 1);
                  start = i + 1;
              }
          }
          return s;
      }
  };
  

剑指Offer58-II.左旋转字符串

题目

LCR 182. 动态口令 - 力扣（LeetCode）

题解

LCR 182. 动态口令 - 力扣（LeetCode）

• 原本想以首位项链模拟旋转的方式解决，但是时间复杂度很高

• 采用局部反转+整体旋转的方法

• class Solution
  {
  public:
      void reverse(string &s, int start, int end)
      {
          for (int i = start, j = end; i < j; i++, j--)
          {
              swap(s[i], s[j]);
          }
      }
      string dynamicPassword(string password, int target)
      {
          reverse(password, 0, target - 1);
          reverse(password, target, password.size() - 1);
          reverse(password, 0, password.size() - 1);
          return password;
      }
  };