算法分析-面试1-字符串

---

前言

提示：任重而道远：
算法：一个刷一段时间很有感觉，然后一段时间内不刷又忘了的一种面试工具。
但是重点还得理解其思想。

---

一、分类：看看就行了

提示：算法问题大致可以归为以下几大类，每一类都有其特定的特点和基本的解题思路。
1、数组和字符串：

• 特点：涉及数组的遍历、操作、变换以及字符串的处理问题。
• 解题思路：熟悉数组索引操作、双指针法、排序、动态规划、字符串匹配算法。

2、链表：

• 特点：包括链表的创建、反转、合并、排序等操作。
• 解题思路：掌握指针和递归技巧，学会追踪节点之间的关系。

3、树和图：

• 特点：主要涉及数据结构中的树（如二叉树、二叉搜索树等）和图的相关算法。
• 解题思路：了解树遍历（前序、中序、后序），学习图的表示、遍历（DFS、BFS）以及特定算法（如Dijkstra和A*搜索算法）。

4、动态规划：

• 特点：考查如何把复杂问题拆解为简单子问题，以及如何利用过往计算结果降低时间复杂度。
• 解题思路：理解状态表示和状态转移方程，从子问题的构建和解决入手，求解原问题。

5、排序和搜索：

• 特点：包括各种排序算法和搜索技术的应用。
• 解题思路：掌握基本排序算法（如快速排序、归并排序）和二分搜索算法。

6、贪心算法：

• 特点：通过局部最优选择来寻求全局最优解的问题。
• 解题思路：识别贪心能够得到全局最优解的问题特点，构造贪心策略得到解决方案。

7、数学和数字操作：

• 特点：涉及数学计算、数字处理，如素数计算、幂运算、位操作等。
• 解题思路：掌握数学运算性质和逻辑运算技巧，处理数学逻辑题目。

8、递归和回溯：

• 特点：解决可以通过回朔尝试找到可能的解集合的问题，常见于排列组合和解谜游戏。
• 解题思路：采取试错的思想，通过递归方式对可能的解进行遍历。

9、分而治之：

• 特点：包括将大问题拆分为若干小问题，单独解决后再合并结果的算法策略。
• 解题思路：理解并运用分治模板，通常结合递归实现问题的拆解和解决。

10、设计问题：

• 特点：设计数据结构或算法来满足特定的性能要求。
• 解题思路：结合实际问题需求，使用合适的数据结构，注意考虑时间和空间复杂度。

二、字符串

提示：具体使用-此篇仅仅描述字符串：其他在后续系列文章中逐渐补充 算法第一步：先背API：

理解：其实字符串也能看成一个集合或者是数组，所谓的操作无非也是对其的增删改查操作。

API：

创建和初始化：

• 使用字面量（例如：String s = “Hello”;）
• 使用new关键字（例如：String s = new String(“Hello”);）

查询操作：

• length()：返回字符串的长度。
• charAt(int index)：返回指定索引处的字符。
• indexOf(String str)：返回指定子字符串首次出现的索引。
• lastIndexOf(String str)：返回指定子字符串最后出现的索引。
• startsWith(String prefix)：测试字符串是否以指定的前缀开始。
• endsWith(String suffix)：测试字符串是否以指定的后缀结束。
• contains(CharSequence s)：检查字符串中是否包含指定序列。

比较操作：

• equals(Object obj)：比较字符串与对象内容是否相等。
• equalsIgnoreCase(String anotherString)：与equals方法类似，但忽略大小写。
• compareTo(String anotherString)：按字典顺序比较两个字符串。

修改操作：

• concat(String str)：将指定字符串连接到此字符串的末尾。
• replace(char oldChar, char newChar)：返回一个新字符串，它是通过用newChar替换此字符串中出现的所有oldChar得到的。
• replaceAll(String regex, String replacement)：使用给定的replacement替换此字符串所有匹配给定的正则表达式的子字符串。
• toUpperCase()：返回一个新字符串，它是通过将此字符串中的所有字符转换为大写来创建的。
• toLowerCase()：返回一个新字符串，它是通过将此字符串中的所有字符转换为小写来创建的。
• trim()：返回一个新字符串，它去除了原始字符串头尾空白符。

截取操作：

• substring(int beginIndex)：返回一个新字符串，它是此原始字符串的一个子字符串。
• substring(int beginIndex, int endIndex)：返回一个新字符串，它是此原始字符串的一个子字符串，从beginIndex开始到endIndex结束。

分割操作：

• split(String regex)：根据匹配给定正则表达式的方式拆分字符串。

格式化操作：

• String.format(String format, Object… args)：返回一个使用指定语言环境、格式字符串和参数格式化的新字符串。
  转换操作：

• getBytes()：使用平台的默认字符集将此 String 编码为字节序列，并将结果存储到一个新的字节数组中。

• toCharArray()：将此字符串转换为一个新的字符数组。

连接操作（Java 8 及以后）：

• String.join(CharSequence delimiter, CharSequence… elements)：返回一个新的字符串，通过使用指定的分隔符连接传入的元素。

构建和操作可变字符串（StringBuilder 和 StringBuffer）：

• StringBuilder 或 StringBuffer 的 append(), insert(), delete(), reverse() 等方法，它们提供了一种改变字符串内容的方式，而不产生新的字符串对象。

对于字符串操作，重要的是可读性和效率的平衡。对于简单的操作，直接使用String类的方法即可。
但是，如果需要在循环中或者在多次连续修改字符串时，建议使用StringBuilder或StringBuffer，因为它们是可变的，而String的每次修改都会生成新的字符串对象，可能导致内存和性能的开销。

正则补充：

1、使用replaceAll方法删除所有非字母字符，用空格替换。

String s = "$bo*y gi!r#l";
s = s.replaceAll("[^a-zA-Z]", " ");
1
2

2、 使用正则表达式 \\s+匹配一个或多个空格字符来分割字符串。

String s = "bo y gi r l";
String[] words = s.split("\\s+");
1
2

3、正则表达式格式匹配 .matches();

String phoneNumber = "123-456-7890";
// 检查电话号码是否匹配特定的格式
boolean isValidPhoneNumber = phoneNumber.matches("\\d{3}-\\d{3}-\\d{4}");

// 在这个例子中，正则表达式 \\d{3}-\\d{3}-\\d{4} 指定了电话号码的一种常见格式，
// 其中 \\d 表示数字，{3} 表示前面的字符（数字）恰好重复3次。整个表达式匹配的格式为：
// 三位数字，一个破折号，三位数字，一个破折号，再后面是四位数字。

String email = "example@email.com";
// 检查电子邮箱是否符合基本的电子邮箱格式
boolean isValidEmail = email.matches("[\\w.-]+@[\\w.-]+\\.[a-z]{2,}");
// 这里的正则表达式 [\\w.-]+@[\\w.-]+\\.[a-z]{2,} 用来匹配电子邮箱地址，
// 其中 \\w 表示字母、数字或下划线，+ 表示前面的字符组合可以出现一次或多次，
// [a-z]{2,} 表示邮箱的顶级域至少有两个字母长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

力扣题CASE：

1、密码匹配：

public class PasswordChecker {
    
    public int passwordStrength(String password) {
        int count = 0; // 用于统计满足条件的正则表达式数量
        
        // 判断密码中是否包含至少一个小写字母
        if (password.matches(".*[a-z].*")) {
            count++;
        }
        
        // 判断密码中是否包含至少一个大写字母
        if (password.matches(".*[A-Z].*")) {
            count++;
        }
        
        // 判断密码中是否包含至少一个数字
        if (password.matches(".*\\d.*")) {
            count++;
        }
        
        // 判断密码中是否包含至少一个非字母数字字符，这里使用了 ^ 表示取反，
        // [^a-zA-Z0-9] 表示除了字母和数字之外的任意字符
        if (password.matches(".*[^a-zA-Z0-9].*")) {
            count++;
        }
        
        // 返回满足的条件数，可以通过这个数来判断密码的强度
        return count;
    }
    
    public static void main(String[] args) {
        PasswordChecker checker = new PasswordChecker();
        String password = "Password123!";
        int strength = checker.passwordStrength(password);
        System.out.println("Password strength: " + strength + " out of 4");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2、字符串翻转

import java.util.*;

public class Solution {
    public String reverseWords(String s) {
        // 使用replaceAll方法删除所有非字母字符，用空格替换。
        s = s.replaceAll("[^a-zA-Z]", " ");
        // 使用trim方法去除可能出现的前后空格。
        s = s.trim();
        // 使用正则表达式\\s+匹配一个或多个空格字符来分割字符串。
        String[] words = s.split("\\s+");
        // 使用StringBuilder构造反转后的字符串。
        StringBuilder reversed = new StringBuilder();
        // 从后向前遍历单词数组，倒序构造字符串。
        for (int i = words.length - 1; i >= 0; i--) {
            reversed.append(words[i]);
            // 在单词之间添加空格，除了最后一个单词外。
            if (i > 0) {
                reversed.append(" ");
            }
        }
        // 返回构造好的字符串。
        return reversed.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String input1 = "I am a student";
        System.out.println(solution.reverseWords(input1)); // 输出：student a am I

        String input2 = "$bo*y gi!r#l";
        System.out.println(solution.reverseWords(input2)); // 输出：l r gi y bo
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

3、寻找最长回文字串—其实使用类似暴力穷举法挨个进行遍历

public class Main {

    public static int longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLength = 1; // 最长回文串的初始长度，至少为1
        
        // 初始化动态规划表中的单个字符和相邻字符对应的值
        for (int i = 0; i < n; i++) {
            dp[i][i] = true; // 任何一个单独的字符都是回文串
            if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true; // 相邻且字符相同的两个字符是回文串
                maxLength = 2;
            }
        }
        
        // 使用动态规划，从长度为3开始一直到字符串总长度
        for (int len = 3; len <= n; len++) {
            // i为开始位置
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1; // j为结束位置
                // 如果开始和结束的字符相同，并且去掉两端的子字符串也是回文串
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true; // 更新动态规划表，标记为回文串
                    maxLength = len; // 更新最长回文子串的长度
                }
            }
        }
        
        return maxLength; // 返回找到的最长回文串的长度
    }
    
    public static void main(String[] args) {
        String input = "12HHHHA";
        System.out.println(longestPalindrome(input)); // 输出：4
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

分析

• 定义名为longestPalindrome的方法来找出最长有效密码串（即最长的回文子串）。
• 首先检查输入字符串s是否为空或长度为0，如果是，则返回0。
• 初始化字符串的长度n和一个二维布尔数组dp来保存动态规划的状态。dp[i][j]将会表示字符串从索引i到索引j之间的子串是否是回文串。
• 然后，对于所有可能的起始点i到终点i + 1之间的情况，检查是否存在长度为2的回文串，并初始化动态规划表中对应项的值为true。
• 接下来是动态规划的主循环，使用变量len从3开始迭代，直到字符串的总长度。对于每一个长度，检查所有可能的子字符串，更新动态规划表，并记录最长回文子串的长度。
• 如果找到更长的回文子串，将maxLength更新为当前子串的长度。
• 最终返回maxLength作为最长回文子串的长度。
• main方法中创建一个输入的测试字符串，调用longestPalindrome方法，并输出结果。

方法2

public class Main2 {

    public static void main(String[] args) {
        String str = "12HHHHA";
        System.out.println("最长的回文子串长度是：" + longestPalindromeSubstringLength(str));
    }

    public static int longestPalindromeSubstringLength(String str) {
        int maxLength = 0; // 最长回文子串的长度

        for (int i = 0; i < str.length(); i++) {
            // 处理奇数长度的回文串
            maxLength = Math.max(maxLength, expandAroundCenter(str, i, i));
            // 处理偶数长度的回文串
            maxLength = Math.max(maxLength, expandAroundCenter(str, i, i + 1));
        }

        return maxLength;
    }

    /**
     * 从left和right指定的中心位置向外扩展，寻找最长的回文子串
     */
    public static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1; // 回文长度
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

4、寻找最长递增子序列（集合或者数组中也会有）同上都是动态规划类似暴力穷举法

总结

其实还是对字符串的增删改查遍历（正序、倒序、修改后或者替换后再遍历），总的来讲这是最简单的，主要是得明确哪些API的作用是什么，以及正则表达式怎么用

欢迎交流：