Loading...
墨滴

公众号:offer多多

2021/08/26  阅读:34  主题:橙心

每日一题 【第13天】LeetCode 151. 翻转字符串里的单词

每日一题 【第13天】LeetCode 151. 翻转字符串里的单词

一、题目

Reverse Words in a String

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。


示例 4:

输入:s = "  Bob    Loves  Alice   "
输出:"Alice Loves Bob"
示例 5:

输入:s = "Alice does not even like bob"
输出:"bob like even not does Alice"


二、举一反三 字符串面试题系列

请实现一个函数,把字符串 s 中的每个空格替换成"%20"
输入:s = "We are happy."
输出:"We%20are%20happy."
前面有空格
前面有空格
  • 写一个去除字符串左边空格,右边空格,字符串中如果出现多个空格,则合并成一个空格的程序 字符串面试题系列之五:删除字符串空格 【✅】

    删除:整体前移 怎么办?

  • 在字符串中删除特定的字符

    删除:整体前移 怎么办? 分为2个情况考虑。相等 和不相等

  这是一道微软面试题
题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。
例如,输入”They are students.” 和”aeiou” ,
则删除之后的第一个字符串变成”Thy r stdnts.” 。
  • 实现删除字符串中出现次数最少的字符
实现删除字符串中出现次数最少的字符,若多个字符出现次数一样,则都删除。
输出删除这些单词后的字符串,字符串中其它字符保持原来的顺序。

输入描述:
字符串只包含小写英文字母, 不考虑非法输入,输入的字符串长度小于等于20个字节。

输出描述:
删除字符串中出现次数最少的字符后的字符串。

输入例子:
abcdd

输出例子:
dd

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

核心思想: (A⁻¹B⁻¹) ⁻¹ = BA

   思路一:c++,操作字符,直接采用指针形式

  通过举个例子直白看,比如abcdefg 2,结果是cdefgab

  第一步将ab翻转。bacdefg

  第二步将后面的翻转。bagfedc

  第三步全部翻转便可得到。cdefgab

三、思路

提示:看似容易,能说出来嘛?

3.1 青铜算法描述

  1. 删除多余空格
  2. 翻转每个单词
  3. 翻转整个句子

3.2 图解

例子和步骤演示想法
例子和步骤演示想法

3.2 复杂度

3.3 最重要一点是什么,也是最容易忽视地方

  • 最后一个单词该怎么办? “hi hi”
  • 遇到空格 说明 一个新字符产生。

四、测试用例

提示:在不运行代码情况下。通过简单例子验证 是否正确。逻辑推理能力。

你检查不正确,第一个字符串 你忘记检查了。检查根本不仔细。投入时间过少
你检查不正确,第一个字符串 你忘记检查了。检查根本不仔细。投入时间过少
在不运行代码情况下。通过简单例子验证 是否正确。逻辑推理能力
在不运行代码情况下。通过简单例子验证 是否正确。逻辑推理能力
for循环改为while循环 一个continue出现问题 索引不会发生变化
for 循环改为while循环 一个continue 出现问题 索引不会发生变化
#include <string>
using namespace std;
// 翻转单词顺序
/***
 * 第一个拦路虎:有空格怎么办?
 * 第二个拦路虎:都是字符怎么区分,前面一个字符,后面一个字符 【回到问题1】
 * 第三个拦路虎:翻转后的字符串中不应包含额外的空格
 * 
 *  前缀空格怎么办?这个需要删除
 *  中间多余的空格怎么办?
 * 
 *  
 *  https://leetcode-cn.com/problems/reverse-words-in-a-string/solution/tu-wen-bing-mao-cchao-xiang-xi-ti-jie-by-ary7/
 **/
class Solution1 {
public:
    string reverseWords(string s) {
      //1. 删除多余空格
      string input =delSpace(s);
      //翻转每个单词
      int begin =0; //单词开始位置
      int end =0;//单词结束位置
      //"a good example"
      while (end <input.size())
      {    
          //第一个拦路虎:有空格怎么办?
          //第二个拦路虎:都是字符怎么区分,前面一个字符,后面一个字符 【回到问题1】
          if(input[end] ==' ')
          {
             //前闭后开【begin,end)
            //reverse(input.begin()+begin,input.begin()+end); //[a]
            myreverse(input,begin,end);
             
             //reverses the order of the elements in the range [first,last).
             begin =end+1;  ////单词开始位置
          }   

          end++;
      }
      //[abc] 最后一个单词
      //reverse(input.begin()+begin,input.begin()+end);
      myreverse(input,begin,end);

      //reverse(input.begin(),input.end());
      myreverse(input,0,input.size());
      return input;
    }
    
    //input:"    Hello my    word!    "
    //outout:"Hello my word!"
    //数组特点:删除一个字符,整体都要移动。
    //如果做到移动一次呢。利用数组空间大小不变假设,然后双指针
    //原地构造一个新的字符串
    string delSpace(string input)
    {
        int end =0;// 新字符串结束位置。
        int count =0;
        for(char key :input)
        {
            if(key == ' ')
            {
                if(end ==0) //[   Hello]
                {
                    continue;
                }else
                {
                    count++;
                }
                //细节2:空格分为2个情况:中间空格 和首位空格
            }else
            {   
                if(count >0)
                {
                    input[end++] =' ';
                    count =0;
                } //最重要地方:这里不能else 

                input[end++] =key;
                
            }
            
        }
        return input.substr(0,end);
    }
    //https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/solution/mian-shi-ti-05-ti-huan-kong-ge-ji-jian-qing-xi-tu-/

    //输入:s = "We are happy."
   //输出:"We%20are%20happy."

   string replaceSpace(string input)
   {
      //步骤01 计算新字符串长度 
       int n1 =input.size();
       int spaceCount =0;
       for(char key:input)
       {
           if(' ' == key)
           {
               spaceCount++;
           }
       }
       //空格1个字符串 %20三个字符 比原来多2个字符串

       input.resize(n1+2*spaceCount);

      //步骤02 
      //字符串特点:插入一个元素,回导致整体后移,覆盖后面的元素 怎么办呢?
      //倒叙遍历 构造新字符串 。假如是链表的 仿照stlclass insert_iterator;
      
      int oldIndex =n1-1;
      int newIndex =input.size()-1;
      //[We are happy.xxxx]
      //           |     |
      //    oldIndex  newIndex
      //"     "
      //while(oldIndex >0)
      //边界要相等这么简单 判断你忘记了 
      //【0 n);
      //最重要地方!!!!!!果然出错了 哈哈哈 
      while(oldIndex >=0) //循环条件是什么想清楚???? 全部遍历一遍。【0,n)
      {    
          //最重要地方!!!!!!果然出错了 哈哈哈 
          if(input[oldIndex] == ' ')
          { 
              //%20
              input[newIndex--] = '0';
              input[newIndex--] = '2';
              input[newIndex] = '%';
              //这里放三个字符
          }else
          {   

             input[newIndex] =input[oldIndex];
          }
          //变化条件是什么?
          newIndex --;
          oldIndex --;
      }

      return input;
   }
   //前闭后开【begin,end)
   void myreverse(string &input,int begin,int end)
   {   
       if(begin>=end)
       {
           return ;
       }
       end --;
       //[abax]
       while (end >begin)
       {
           char temp =input[begin];
           input[begin++] =input[end];
           input[end--] =temp;

       }
       
   }

};

公众号:offer多多

2021/08/26  阅读:34  主题:橙心

作者介绍

公众号:offer多多