算法训练营——字符串算法(第十四课)

字符串算法

主要是的接扫的字符串的相关的算法题目，并掌握好相关的常用函数，以及面对字符串的算法问题的处理的方式。

String的特点：

• 字符串是常量，一旦被创建就不能改变，这是因为字符串的值是存放在方法区的常量池里面，但是引用可以改变。
• 字符串字面值"ab"也可以看成是一个字符串对象。

String的基本函数 1.常见String类的获取功能

    public int length(): 获取字符串的长度。
    public char charAt(int index): 获取指定索引位置的字符
    public int indexOf(int ch): 返回指定字符在此字符串中第一次出现处的索引。
    public int indexOf(String str): 返回指定字符串在此字符串中第一次出现处的索引。
    public int indexOf(int ch,int fromIndex):返回指定字符在此字符串中从指定位置后第一次出现处的索引。
    public int indexOf(String str,int fromIndex): 返回指定字符串在此字符串中从指定位置后第一次出现处的索引。
    public String substring(int start): 从指定位置开始截取字符串,默认到末尾。
    public String substring(int start,int end): 从指定位置开始到指定位置结束截取字符串。

2.常见String类的判断功能

    public boolean equals(Object obj): 比较字符串的内容是否相同,区分大小写
    public boolean equalsIgnoreCase(String str): 比较字符串的内容是否相同,忽略大小写
    public boolean contains(String str): 判断字符串中是否包含传递进来的字符串
    public boolean startsWith(String str): 判断字符串是否以传递进来的字符串开头
    public boolean endsWith(String str): 判断字符串是否以传递进来的字符串结尾
    public boolean isEmpty(): 判断字符串的内容是否为空串""。

3.常见String类的转换功能

    public byte[] getBytes(): 把字符串转换为字节数组。
    public char[] toCharArray(): 把字符串转换为字符数组。
    public static String valueOf(char[] chs): 把字符数组转成字符串。
    public static String valueOf(int i): 把int类型的数据转成字符串。（String类的valueOf方法可以把任意类型的数据转成字符串。）
    public String toLowerCase(): 把字符串转成小写。
    public String toUpperCase(): 把字符串转成大写。
    public String concat(String str): 把字符串拼接。

4常见String类的其他常用功能

    public String replace(char old,char new) 将指定字符进行互换
    public String replace(String old,String new) 将指定字符串进行互换
    public String trim() 去除两端空格
    public int compareTo(String str) 会对照ASCII 码表 从第一个字母进行减法运算 返回的就是这个减法的结果，如果前面几个字母一样会根据两个字符串的长度进行减法运算返回的就是这个减法的结果，如果连个字符串一摸一样 返回的就是0
    public int compareToIgnoreCase(String str) 跟上面一样 只是忽略大小写的比较

5 常见String类中int与String的相互转换

num + “”
String.valueOf(num)
Integer.toString(num)
  String转int有两种方式
Integer.parseInt(str)
Integer.valueOf(str).intValue()

6.Java中的charAt()方法

java.lang.String.charAt() 方法返回指定索引处的char值。索引范围是从0到length() - 1。
声明java.lang.String.charAt()方法

    public charcharAt(int index)

字符串实战题目 字符串基础问题

• https://leetcode-cn.com/problems/to-lower-case/

package 计算机程序算法分类.字符串类型;

import org.junit.Test;

/**
 * @Classname 转换小写字母709
 * @Description TODO 采用的双指针的思想来遍历的字符串
 * @Date 2021/6/28 15:03
 * @Created by xjl
 */
public class 转换小写字母709 {
    public String toLowerCase(String s) {
        return s.toLowerCase();
    }

    @Test
    public void test() {
        String hello = toLowerCase3("PiTAs");
        System.out.println(hello);
    }

    public String toLowerCase2(String str) {
        char[] array = str.toCharArray();
        for (int i = 0; i < array.length; i++) {
            if (array[i] >= 'A' && array[i]  0) {
                    break;
                }
            }
        }
        return count;
    }
}

• https://leetcode-cn.com/problems/jewels-and-stones/
• https://leetcode-cn.com/problems/first-unique-character-in-a-string/
• https://leetcode-cn.com/problems/string-to-integer-atoi/

字符串操作问题

• https://leetcode-cn.com/problems/longest-common-prefix/description/
• https://leetcode-cn.com/problems/reverse-string
• https://leetcode-cn.com/problems/reverse-string-ii/
• https://leetcode-cn.com/problems/reverse-words-in-a-string/
• https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
• https://leetcode-cn.com/problems/reverse-only-letters/

异位词问题

• https://leetcode-cn.com/problems/valid-anagram/
• https://leetcode-cn.com/problems/group-anagrams/
• https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

回文串问题

• https://leetcode-cn.com/problems/valid-palindrome/
• https://leetcode-cn.com/problems/valid-palindrome-ii/
• https://leetcode-cn.com/problems/longest-palindromic-substring/

最长子串、子序列问题

• https://leetcode-cn.com/problems/longest-common-subsequence/
• https://leetcode-cn.com/problems/edit-distance/
• https://leetcode-cn.com/problems/longest-palindromic-substring/

字符串 +DP 问题

• https://leetcode-cn.com/problems/regular-expression-matching/
• https://leetcode-cn.com/problems/regular-expression-matching/solution/ji-yu-guan-fang-ti-jie-gen-xiang-xi-de-jiang-jie-b/
• https://leetcode-cn.com/problems/wildcard-matching/
• https://leetcode-cn.com/problems/distinct-subsequences/

课后作业

• https://leetcode-cn.com/problems/first-unique-character-in-a-string/
• https://leetcode-cn.com/problems/string-to-integer-atoi/
• https://leetcode-cn.com/problems/reverse-string-ii/
• https://leetcode-cn.com/problems/reverse-words-in-a-string/
• https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
• https://leetcode-cn.com/problems/reverse-only-letters/
• https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
• https://leetcode-cn.com/problems/longest-palindromic-substring/
• https://leetcode-cn.com/problems/isomorphic-strings/
• https://leetcode-cn.com/problems/valid-palindrome-ii/
• https://leetcode-cn.com/problems/wildcard-matching
• https://leetcode-cn.com/problems/longest-valid-parentheses
• https://leetcode-cn.com/problems/distinct-subsequences/

参考链接

• Boyer-Moore 算法
• Sunday 算法
• 字符串匹配暴力法代码示例
• Rabin-Karp 代码示例
• KMP 字符串匹配算法视频
• 字符串匹配的 KMP 算法