java算法笔记(重点 蓝桥杯)
1.最为典型的求最长公共前缀
1.1
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"] 输出:""
解释:输入不存在公共前缀
首先我们在比较几个字符时,会先想到用第一个字符来遍历其他字符,以来比较,而在这题字符串的比较中,我们也可以考虑这种情况,用第一个字符串与其他字符串进行比较,首先我们得到的是一个字符串数组
class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length == 0)//曾经因为没有考虑长度为0的情况而一直错误 { return ""; } String arr = strs[0];//得到第一个字符串用来便利其他字符串 for(int i = 1;i < strs.length;i++) { int j = 0; for(;j < arr.length() && j < strs[i].length();j++)//确保不能出现越界的情况 { if(arr.charAt(j) != strs[i].charAt(j)) { break; }} arr = arr.substring(0,j);//这里我们将得到从0开始到j-1的最长公共前缀 if(arr.equals("")) return ""; } return arr; }}
1.2
除了这一种题目外,更难的是两个字符串里面找出他们最长的相同的字符串
(这里我们只考虑只出现一次最长相同字符串的情况)
题目:
String str1 = "qwertyuhelloop" String str2 = "zxchellods"
求出这两个字符串最长的字符串
这里我们使用的方法有(contains,substring)
public String getMain(String str1,String str2){ if(str1 != null && str2 != null) { String maxString = (str1.length() >= str2.length())?str1:str2; String minString = (str1.length() < str2.length())?str1:str2; //这里需要注意的是如果maxString中出现了=号, //那么minString就不能再出现一次=号,否则两者相同,比较就没有意义了 //这里我们是拿最小的字符串与最长的字符串进行比较 int length = minString.length(); for(int i = 0;i < length;i++) { for(int x = 0,y = length - i;y < length;y++,x++) { String sub = minString.substring(x,y); if(maxString.contains(sub)) { return sub; } } } }}
当找不到时i会逐渐增大,而x会一直从0出发,y出发的下标会一直减小,以此类推
2.有关字符相关算法的长度为26的数组的基本解法
2.1 判断两个字符串是否为字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词,若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
这里我们可以用最为基础的建立一个长度为26的数组来存放26个字母
class Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) { return false; } int[] arr = new int[26]; //利用ASCII表来进行字符之间的运算 for(int i = 0;i < s.length();i++) { arr[s.charAt(i) - 'a']++; arr[t.charAt(i) - 'a']--; } //如果都为0,则true for(int i = 0;i <26;i++) { if(arr[i] != 0) return false; } return true; }}
2.2 当然还有一种利用长度为26数组的一种例子,
就是判断这两个字符串中出现的一个不同的字符是谁.
我们可以将两者字符串的每一个字符-'a'后进行运算相加,
总数大的减去小的,在利用+'a'得到该字符
3 反转字符串中的原因字符
3.1
示例1:输入:s = "hello"
输出:"holle"
这里我们将运用将String放入char型数组
class Solution { public String reverseVowels(String s) { int n = s.length(); char[] arr = s.toCharArray(); int i = 0,j = n - 1; while(i < j) { //利用while循环直到找到元音字母 while(i 0 && !getMain(arr[j])) { j--; } //必须符合i < j才能替换 if(i = 0; } public void gettt(char[] arr,int i,int j){ char temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; }}
目前关于字符串的算法题笔记或小结到此结束,敬请指教