Leetcode Practice — 字符串

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

输入:strs = ["flower","flow","flight"]
输出:"fl"
  • 思路解析

string longestCommonPrefix(vector<string>& strs) {
    string res;
    if (strs.empty()) {
        return res;
    }
    for (size_t i = 0; i < strs[0].length(); i++) {
        char pivotChar = strs[0][i];
        for (size_t j = 1; j < strs.size(); j++) {
            if (i >= strs[j].length() || strs[j][i] != pivotChar) {
                return res;
            }
        }
        res += pivotChar;
    }
    return res;
}

151. 反转字符串中的单词

给你一个字符串 s ,请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

输入:s = "the sky is blue"
输出:"blue is sky the"
  • 思路解析

string reverseWords(string s) {
    stack<string> strStack;
    string oneWord;
    for (size_t i = 0; i < s.length(); i++) {
        if (s[i] == ' ') {
            if (!oneWord.empty()) {
                strStack.emplace(oneWord);
            }
            oneWord.clear();
            continue;
        }
        oneWord += s[i];
    }
    if (!oneWord.empty()) {
        strStack.emplace(oneWord);
    }
    string resStr;
    while (!strStack.empty()) {
        resStr += strStack.top() + " ";
        strStack.pop();
    }
    resStr = resStr.substr(0, resStr.length()-1);
    return resStr;
}
graph LR;
ios-->ios_base;
istringstream-->istream;
istream-->ios;
ostream-->ios;
ostringstream-->ostream;
  • istream:从流中读取
  • ostream:写到流中去
  • istringstream:从string对象流中读取
  • ostringstream:写入到string对象流中

ostringstream:

Output stream class to operate on strings. 用于处理字符串的输出流

Objects of this class use a string buffer that contains a sequence of characters. This sequence of characters can be accessed directly as a string object, using member str.

ostringstream类的对象使用一个string buffer来存储一系列的字符,这些字符序列可以直接用string对象访问。

istringstream:

This operator (>>) applied to an input stream is known as extraction operator. It is overloaded as a member function for:

对输入流应用>>,即为提取操作符,有三种接受方式:

  • arithmetic types【算术类型,bool、short、long等等】
  • stream buffers
  • manipulators

使用>>可以从流中提取数据,多个单词使用空格分割。

string reverseWords(string s) {
    istringstream is(s);
    stack<string> strStack;
    string str;
    while (is >> str) {
        strStack.emplace(str);
    }
    string resStr;
    while (!strStack.empty()) {
        resStr += strStack.top() + " ";
        strStack.pop();
    }
    resStr = resStr.substr(0, resStr.length() - 1);
    return resStr;
}

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false 。

  • 思路解析

bool isPalindrome(string s) {
    // 清理字符串
    string cleanStr;
    for (size_t i = 0; i < s.length(); i++) {
        if (isalnum(s[i])) {
            cleanStr += tolower(s[i]);
        }
    }
    // 判断其是否为回文串
    int i = 0;
    int j = cleanStr.length() - 1;
    while (i < j) {
        if (cleanStr[i++] != cleanStr[j--]) {
            return false;
        }
    }
    return true;
}

C++中哪些字符串的判断与处理函数:

  • int isalpha(int c);:判断一个字符是否为字母,是非零,否零
  • int isalnum(int c);:判断一个字符是否为字母或数字,是非零,否零
  • int isdigit(int c);:判断判断一个字符是否为数字,是非零,否零
  • int islower(int c);:判断判断一个字符是否小写字母,是非零,否零
  • int isupper(int c);:判断判断一个字符是否大写字母,是非零,否零
  • int tolower(int c);:将一个字母转为小写字母
  • int toupper(int c);:将一个字母转为大写字母

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。

输入:num1 = "11", num2 = "123"
输出:"134"
  • 思路解析

模拟加法的基本运算步骤。

int charToInt(char c) {
    return c - '0';
}
string addStrings(string num1, string num2) {
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int jinwei = 0;
    stack<int> resStack;
    while (i >= 0 && j >= 0) {
        int tmp = charToInt(num1[i--]) + charToInt(num2[j--]) + jinwei;
        resStack.emplace(tmp % 10);
        jinwei = tmp / 10; // tmp >= 10 ? 1 : 0
    }
    while (i >= 0) {
        int tmp = charToInt(num1[i--])+ jinwei;
        resStack.emplace(tmp % 10);
        jinwei = tmp / 10;
    }
    while (j >= 0) {
        int tmp = charToInt(num2[j--]) + jinwei;
        resStack.emplace(tmp % 10);
        jinwei = tmp / 10;
    }
    if (jinwei) {
        resStack.emplace(jinwei);
    }
    string res;
    while(!resStack.empty()) {
        res += std::to_string(resStack.top());
        resStack.pop();
    }
    return res;
}

3. 无重复字符的最长子串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
  • 思路解析

使用滑动窗口来判断窗口内的子串是否为最长子串。

【找最长子串类似于找最大子数组的和,都需要考虑所有子串/子数组,就可以从每个元素开始找子串或子数组,就可以考虑用滑动窗口了】

设窗口为[left, right],针对当前元素s[right+1],如果该元素不在窗口内,则直接向右扩张窗口:right = right+1;否则,说明该元素之前出现过,判断其之前出现的位置是否在窗口内,如果不在,就不需要考虑,如果在,就需要收缩窗口的左侧边界,即left = 当前元素上次出现的索引位置 + 1;

int lengthOfLongestSubstring(string s) {
    if (s.empty()) {
        return 0;
    }
    // 初始,窗口只有一个元素
    int left = 0;
    int right = 0;
    unordered_map<char, int> charIndexMap;
    charIndexMap[s[0]] = 0;
    int windowSize = 1;
    for (size_t i = 1; i < s.length(); i++) {
        // 当前字符出现过且在当前窗口内,则收缩窗口左边界
        if (charIndexMap.count(s[i]) != 0 && left <= charIndexMap[s[i]]) {
            left = charIndexMap[s[i]] + 1;
        }
        // 窗口一直在向右扩张
        right++;
        charIndexMap[s[i]] = i;
        // 判断窗口大小是否需要更新
        if (right - left + 1 > windowSize) {
            windowSize = right - left + 1;
        }
    }
    return windowSize;
}

8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。

函数 myAtoi(string s) 的算法如下:

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
  3. 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
  5. 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
  6. 返回整数作为最终结果。

注意:

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。

输入:s = "   -42"
输出:-42
解释:
第 1 步:"   -42"(读入前导空格,但忽视掉)
             ^
第 2 步:"   -42"(读入 '-' 字符,所以结果应该是负数)
              ^
第 3 步:"   -42"(读入 "42")
              ^
解析得到整数 -42 。
由于 "-42" 在范围 [-2^31, 2^31 - 1] 内,最终结果为-42 。
  • 0 <= s.length <= 200

  • s 由英文字母(大写和小写)、数字(0-9)、' ''+''-''.' 组成

  • 思路解析

判断输入的字符是否为数字,如果为数字就提取出来。

注意,从前到后,只能访问到' '、‘+’、‘-’或数字,其他的均为无效,"+"、"-"或数字一旦开始就不能再遇到其它了,只能遇到数字,否则就可以终止了。

举例说明:[比较重要的就是理解题意,将所有情况考虑周全]

  • "+-0012" --> 0
  • "+0012" --> 12
  • "+00 12" --> 0
  • " aa 12" --> 0
  • " 12 aa" --> 12
int myAtoi(string s) {
    int sign = 1; // 符号位,默认为正
    bool startFlag = false; // "+"或"-"已经被遍历到,不能再出现了,再出现就属于不合法字符了
    int64_t intNum = 0;
    for (size_t i = 0; i < s.length(); i++) {
        if (isdigit(s[i])) {
            intNum = intNum * 10 + (s[i] - '0');
            if (sign == 1 && intNum > INT_MAX) {
                return INT_MAX;
            }
            if (sign == -1 && -intNum < INT_MIN) {
                return INT_MIN;
            }
            startFlag = true;
        } else if (s[i] == '-' && !startFlag) {
            startFlag = true;
            sign = -1;
        } else if (s[i] == '+' && !startFlag) {
            startFlag = true;
        } else if (s[i] == ' ' && !startFlag) {
            continue;
        } else {
            break;
        }
    }

    intNum = intNum * sign;
    if (intNum > INT_MAX) {
        return INT_MAX;
    }
    if (intNum < INT_MIN) {
        return INT_MIN;
    }
    return static_cast<int>(intNum);
}

原文链接:https://www.cnblogs.com/shuezhang/p/17252789.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Leetcode Practice — 字符串 - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月18日

相关文章

  • Python实现的数据结构与算法之快速排序详解

    下面是关于“Python实现的数据结构与算法之快速排序详解”的完整攻略。 1. 快速排序算法概述 快速排序是一种高效的排序算法,它的基本思想是通过分治的想将一个大问题解成多个小问题,后递归地解决这些小问题。快速排序的复杂度为O(nlogn),是一种非高的排序算法。 2 快速排序算法实现 下面使用Python实现快速排序的代码: def quick_sort(…

    python 2023年5月13日
    00
  • python选择排序算法的实现代码

    Python选择排序算法的实现代码 选择排序是一种简单的排序算法,它的基本思想是每次从未排序的元素中选择最小的元素,将其放到已排序的元素末尾。在本攻略中,我们将介绍如何使用Python实现排序算法。 步骤1:实现选择排序算法 在使用Python实现选择排序算法之前,我们需要了解选择排序算法的本思想。选择排序算法的基本思想是每次从未排序的元素中选择最小的元素,…

    python 2023年5月14日
    00
  • Python优化算法之遗传算法案例代码

    下面是关于“Python优化算法之遗传算法案例代码”的完整攻略。 1. 遗传算法简介 遗传算法是一种基于自然选择和遗传学原理的优化算法,它通过模拟自然界中的进化过程,从而实现对问题的优化。遗传算法的基本思想是将问题转化为染色体编码,然后通过交叉、变异等操作,不断优化染色体,从而得到最优解。 2. Python实现遗传算法 在Python中,我们可以使用 DE…

    python 2023年5月13日
    00
  • python编程实现希尔排序

    下面是关于“Python编程实现希尔排序”的完整攻略。 1. 希尔排序简介 希尔排序是一种高效的排序算法,它是插入排序的一种改进。希尔排序通过将待排序的数组分成若干个子序列,对每个子序列进行插入排序,最后再对整个数组进行一次插入排序。希尔排序的时间复杂度为$O(nlogn)$,是一种比较快速的排序算法。 2. Python实现希尔排序 下面是Python实现…

    python 2023年5月13日
    00
  • 带你了解Java数据结构和算法之数组

    带你了解Java数据结构和算法之数组 在本教程中,我们将学习Java中的数组数据结构和对应的算法。让我们先来了解什么是数组。 什么是数组? 数组是一个同类型数据元素的集合,在内存中连续存储。数组具有索引性,我们可以使用索引值来访问数组中的元素。 声明和初始化数组 在Java中,声明一个数组需要指定以下三个参数: 数组的类型 数组的名称 数组的大小 以下是一个…

    数据结构 2023年5月17日
    00
  • 实现用python算法计算圆周率的小诀窍

    实现用Python算法计算圆周率的小诀窍 计算圆周率是计算机科学中的一个经典问题。本文将介绍使用Python实现计圆周率的小诀窍,包括算法原理、实现步骤和示例。 算法原理 计算圆周率的经典法是蒙特卡罗方法。该方法基于随机采样的思想,通过在一个正方形内随机生成大量的点,并统计落在圆内的点的数量,从而估算圆的面和圆周率。 具体来说,假设有一个半径为r的圆,面积为…

    python 2023年5月14日
    00
  • c语言 数据结构实现之字符串

    下面是详细讲解“c语言 数据结构实现之字符串”的完整攻略。 1. 什么是字符串? 字符串是由一组字符组成的序列,字符可以是字母、数字、标点符号等,字符串常用于文本处理。 在C语言中,字符串是以‘\0’ 结束的字符数组。 2. 字符串的常见操作 常见的字符串操作包括:复制、比较、连接、查找等。 2.1 字符串复制 字符串复制是将一个字符串的内容复制到另一个字符…

    数据结构 2023年5月17日
    00
  • Python实现FIFO缓存置换算法

    以下是关于“Python实现FIFO缓存置换算法”的完整攻略: 简介 FIFO缓存置换算法是一种常用的缓存置换算法,它根据缓存中元素的到达时间来选择要替换的元素。本教程将介绍如何使用Python实现FIFO缓存置换算法,并提供两个示例。 算法实现 FIFO缓存置换算法是一种简单的算法,它使用队列来存储缓存中的元素,并根据队列中元素的到达时间来选择要替换的元素…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部