5.最长回文串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

题目链接

思路

1.暴力解法
2.动态规划
3.中心扩展算法
4.Manacher 算法
注：算法详情请参考leetcode题解

几种方法的总结！！！强烈推荐！！！

657.机器人能够返回原点

题目描述

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。
注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

题目链接

思路

起始时机器人的坐标为 (0,0)，在遍历完所有指令并对机器人进行移动之后，判断机器人的坐标是否为 (0,0) 即可。

具体来说，我们用两个变量 x 和 y 来表示机器人当前所在的坐标为 (x,y)，起始时 x=0，y=0。接下来我们遍历指令并更新机器人的坐标：
如果指令是 U，则令 y=y−1
如果指令是 D，则令 y=y+1
如果指令是 L，则令 x=x−1
如果指令是 R，则令 x=x+1
最后判断 (x,y) 是否为 (0,0) 即可。

557.反转字符串中的单词3

题目描述

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：
输入：”Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”

题目链接

思路

1.将字符串按照空格划分开得到字符串中的每一个单词,然后将每个单词反转
，在将反转后的所有单词用空格拼接起来
2.使用额外空间
开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
3.原地解法
此题也可以直接在原字符串上进行操作，避免额外的空间开销。当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符……如此反复，就可以在原空间上翻转单词。
需要注意的是，原地解法在某些语言（比如 Java，JavaScript，python）中不适用，因为在这些语言中 String 类型是一个不可变的类型。
在python中可以先将字符串转为列表然后进行算法设计。

更多思路参考“一行流”，简直牛逼！！！

551.学生出勤记录1

题目描述

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
‘A’：Absent，缺勤
‘L’：Late，迟到
‘P’：Present，到场
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
按 总出勤 计，学生缺勤（’A’）严格 少于两天。
学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（’L’）记录。
如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。

示例 1：
输入：s = “PPALLP”
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。

题目链接

思路

1.一次遍历
可奖励的出勤记录要求缺勤次数少于 2 和连续迟到次数少于 3。判断出勤记录是否可奖励，只需要遍历出勤记录，判断这两个条件是否同时满足即可。
遍历过程中，记录缺勤次数和连续迟到次数，根据遍历到的字符更新缺勤次数和连续迟到次数：
如果遇到 ‘A’，即缺勤，则将缺勤次数加 1，否则缺勤次数不变；
如果遇到 ‘L’，即迟到，则将连续迟到次数加 1，否则将连续迟到次数清零。
如果在更新缺勤次数和连续迟到次数之后，出现缺勤次数大于或等于 2 或者连续迟到次数大于或等于 3，则该出勤记录不满足可奖励的要求，返回 false。如果遍历结束时未出现出勤记录不满足可奖励的要求的情况，则返回 true。

541.反转字符串2

题目描述

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：
输入：s = “abcdefg”, k = 2
输出：”bacdfeg”

题目链接

思路

反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串

521.最长特殊序列

题目描述

给你两个字符串，请你从这两个字符串中找出最长的特殊序列。
「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

刷到这道题目时我表示有点没看懂，然后就看了leetcode的评论，也有许多人没看懂，最后就看了题解。。。
我认为，本题按照leetcode官方题解解法二的解决方案容易理解。

题目链接

思路

字符串 aaa 和 bbb 共有 3 种情况：
a=b。如果两个字符串相同，则没有特殊子序列，返回 -1。
length(a)=length(b) 且 a≠b。例如：abc 和 abd。这种情况下，一个字符串一定不会是另外一个字符串的子序列，因此可以将任意一个字符串看作是特殊子序列，返回 length(a) 或 length(b)。
length(a)≠length(b)。例如：abcd 和 abc。这种情况下，长的字符串一定不会是短字符串的子序列，因此可以将长字符串看作是特殊子序列，返回 max(length(a),length(b))。

520.检测大写字母

题目描述

给定一个单词，你需要判断单词的大写使用是否正确。
我们定义，在以下情况时，单词的大写用法是正确的：
全部字母都是大写，比如”USA”。
单词中所有字母都不是大写，比如”leetcode”。
如果单词不只含有一个字母，只有首字母大写， 比如 “Google”。
否则，我们定义这个单词没有正确使用大写字母。

434.字符串中的单词数

题目描述

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
请注意，你可以假定字符串里不包括任何不可打印的字符。

383.赎金信

题目描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

题目链接

思路

遍历ransomNote中的每一个元素，并查找这个元素是否在magazine中，如果没有查找到，则返回False，如果查找到了，则将这个元素在magazine中移除，以此类推，直到遍历完ransomNote中的每一个元素。

345.反转字符串中的元音字母

题目描述

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 ‘a’、’e’、’i’、’o’、’u’，且可能以大小写两种形式出现。

题目链接+

思路

1. 先将字符串中的元音字母的位置找出来，然后再将各元音字母反转

2. 双指针
   我们可以使用两个指针 i 和 j 对字符串相向地进行遍历。
   具体地，指针 i 初始时指向字符串 s 的首位，指针 j 初始时指向字符串 s 的末位。在遍历的过程中，我们不停地将 i 向右移动，直到 i 指向一个元音字母（或者超出字符串的边界范围）；同时，我们不停地将 j 向左移动，直到 j 指向一个元音字母。此时，如果 i<j，那么我们交换 i 和 j 指向的元音字母，否则说明所有的元音字母均已遍历过，就可以退出遍历的过程。