当前位置:   article > 正文

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

算法分析-面试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的作用是什么,以及正则表达式怎么用

欢迎交流:
在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/140998
推荐阅读
相关标签
  

闽ICP备14008679号