目录
16 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串
思路：回文串也就是从前往后读和从后往前读是同一个字符串，这个题考虑用双指针的方法，一个从前往后一个从后往前，遇到符号跳过，将字母全转换成小写去比较。
代码实现：
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
right = s.length() - 1;
while (left < right) {
//因为题中说了，只考虑字母和数字，所以不是字母和数字的先过滤掉
while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
right--;
//然后把两个字符变为小写，在判断是否一样，如果不一样，直接返回false
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
return false;
left++;
right--;
}
return true;
}
}
17实现 strStr()
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
思路：这个题要求从一个字符串中找到另一个字符串。
在已知一个字符串是长字符串我们设他为主串，另一个短的为子串，我们考虑不断的在主串中匹配子串而不是一个一个字母去判断。
class Solution {
public int strStr(String haystack, String needle) {
int length= needle.length();
int total = haystack.length() - length +1;
for(int i = 0;i < total;i++){
if(haystack.substring(i, i+length).equals(needle)){
return i;
}
}
return -1;
}
}18 外观数列
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
思路：这个题的后一项就是描述前一项有几个几和几个几。注意描述一共有多少个要在前面，描述数字是几放在后面。这里我们用到StringBuilder()类使用append方法来实现字符串连接。
代码：
class Solution {
public String countAndSay(int n) {
//假设是1的情况
String res = "1";
//循环到n去构建外观数列
for (int i = 2; i <= n; ++i) {
//创建StringBuilder对象
StringBuilder stringBuilder = new StringBuilder();
//0对应的是下标
int index = 0;
while (index < res.length()) {
//count对应的是个数
int count = 1;
// 统计当前字符的个数，和下一个比较是否相等
while (index < res.length() - 1 && res.charAt(index) == res.charAt(index + 1)) {
index++;
count++;
}
// 把当前字符的个数和当前字符一起保存起来
stringBuilder.append(count).append(res.charAt(index));
// 统计下一个字符
index++;
}
res = stringBuilder.toString();
}
return res;
}
}19 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
思路：这个就是找每个字符串的前几个字母看有没有一样的，我们找前两个的，然后调用方法去对比第三个，第四个......
代码
、
class Solution {
public String longestCommonPrefix(String[] strs) {
//边界条件判断
if (strs == null || strs.length == 0)
return "";
//默认第一个字符串是他们的公共前缀
String pre = strs[0];
int i = 1;
while (i < strs.length) {
//不断的截取
//indexOf(pre)从一整个字符开始截取，直到有相同的
while (strs[i].indexOf(pre) != 0)
pre = pre.substring(0, pre.length() - 1);
i++;
}
return pre;
}
}20 删除链表中的节点
请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
题目数据保证需要删除的节点 不是末尾节点 。
示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9
示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9
思路：说是删除，其实不然。我们只要找到那个节点把那个结点下一个结点的值赋给当前结点，next指向下下一个结点，也就是删除下一个结点。
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}