脚本宝典收集整理的这篇文章主要介绍了字符串算法,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
说明:
必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。
class Solution { public void moveZeroes(int[] nums) { int j=0; for(int i=0;i<nums.length;i++) { if(nums[i]!=0) { nums[j++]=nums[i]; } } for(int i=j;i<nums.length;i++){ nums[i]=0; } } }
转载链接:https://leetcode-cn.com/problems/move-zeroes/
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama" 输出: true 解释:"amanaplanacanalpanama" 是回文串 示例 2:
输入: "race a car" 输出: false 解释:"raceacar" 不是回文串
提示:
1 <= s.length <= 2 * 105 字符串 s 由 ASCII 字符组成
public boolean isPalindrome(String s) { if (s.length() == 0) return true; 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; }
转载链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xne8id/
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1:
输入:s = ["h","e","l","l","o"] 输出:["o","l","l","e","h"]
示例 2:
输入:s = ["H","a","n","n","a","h"] 输出:["h","a","n","n","a","H"]
提示:
1 <= s.length <= 105 s[i] 都是 ASCII 码表中的可打印字符
class Solution { public void reverseString(char[] s) { int start=0; int end=s.length-1; while(start<end) { char temp=s[start]; s[start]=s[end]; s[end]=temp; start++; end--; } } }
转载链接:https://leetcode-cn.com/problems/reverse-string
给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
示例:
输入:"Let's take LeetCode contest" 输出:"s'teL ekat edoCteeL tsetnoc"
提示:
在字符串中,每个单词由单个空格分隔,并且字符串中不会有任何额外的空格。
class Solution { public String reverseWords(String s) { char[] st = s.toCharArray(); int end, start=0; Boolean flag = true; StringBuilder str=new StringBuilder(s); for (int i = 0; i < st.length; i++) { //遇到的第一个字母 if (flag == true && st[i] != ' ') { flag = false; start = i; continue; } //遇到的第一个空格 if (flag == false && st[i] == ' ') { flag = true; end = i - 1; reverseString(start, end, str); } } if(st[st.length-1]!=' ') { reverseString(start, st.length-1, str); } return str.toString(); } public static void reverseString(int start, int end, StringBuilder str) { while (start < end) { char temp = str.charAt(start); str.setCharAt(start, str.charAt(end)); str.setCharAt(end, temp); start++; end--; } } }
转载链接:https://leetcode-cn.com/problems/reverse-words-in-a-string-iii
给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2:
输入:nums = [-1,-100,3,99], k = 2 输出:[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
提示:
1 <= nums.length <= 105 -231 <= nums[i] <= 231 - 1 0 <= k <= 105
class Solution { public void rotate(int[] nums, int k) { //1.先把转到前面的数提取出来 int []temp=new int[k]; // if(k>nums.length){ // int t=k-nums.length; // rotate(nums,t); // k=nums.length; // } k=k%nums.length; for(int i=0;i<k;i++) { temp[i]=nums[nums.length-1-i]; } //2.未转到前面的数开始填充 for(int i=nums.length-1;i>=k;i--) { nums[i]=nums[i-k]; } //3.填充转到前面的数 for(int i=0;i<k;i++) { nums[i]=temp[k-1-i]; } } }
转载链接:https://leetcode-cn.com/problems/rotate-array
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。 示例 4:
输入: s = "" 输出: 0
提示:
0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成
class Solution { public int lengthOfLongestSubstring(String s) { //为方便查找元素,采用hashSet int max=0; Set<Character> hashChar=new HashSet<>(); int end=0; for(int i=0;i<s.length();i++) { if(i!=0) { hashChar.remove(s.charAt(i-1)); } while(end<s.length()&&!hashChar.contains(s.charAt(end))) { hashChar.add(s.charAt(end)); end++; } max=Math.max(max, hashChar.size()); } return max; } }
转载链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。
换句话说,s1 的排列之一是 s2 的 子串 。
示例 1:
输入:s1 = "ab" s2 = "eidbaooo" 输出:true 解释:s2 包含 s1 的排列之一 ("ba") 示例 2:
输入:s1= "ab" s2 = "eidboaoo" 输出:false
提示:
1 <= s1.length, s2.length <= 104 s1 和 s2 仅包含小写字母
双指针-map存字母
class Solution { public boolean checkInclusion(String s1, String s2) { int len1 = s1.length(); int len2 = s2.length(); // 如果s2长度比s1还小,自然不可能s2包含s1的排列 if (len2 < len1) { return false; } Map<Character, Integer>map=new HashMap<>(); for (int i = 0; i < len1; i++) { map.put(s1.charAt(i),map.getOrDefault(s1.charAt(i), 0)-1); } int left=0; for(int i=0;i<s2.length();i++) { map.put(s2.charAt(i), map.getOrDefault(s2.charAt(i), 0)+1); while(map.get(s2.charAt(i))>0) { map.put(s2.charAt(left),map.getOrDefault(s2.charAt(left), 0)-1); left++; } if((i-left+1)==len1) { return true; } } return false; } }
双指针-数组存字母
class Solution { public boolean checkInclusion(String s1, String s2) { int len1 = s1.length(); int len2 = s2.length(); // 如果s2长度比s1还小,自然不可能s2包含s1的排列 if (len2 < len1) { return false; } int[] s1Zm = new int[26]; for (int i = 0; i < len1; i++) { s1Zm[s1.charAt(i) - 'a']--; } int left=0; for(int i=0;i<s2.length();i++) { s1Zm[s2.charAt(i)-'a']++; while(s1Zm[s2.charAt(i)-'a']>0) { s1Zm[s2.charAt(left)-'a']--; left++; } if((i-left+1)==len1) { return true; } } return false; } }
移动窗口-数组存字母
class Solution { public boolean checkInclusion(String s1, String s2) { int len1 = s1.length(); int len2 = s2.length(); // 如果s2长度比s1还小,自然不可能s2包含s1的排列 if (len2 < len1) { return false; } // 将他们字母放进数组 int[] s1Zm = new int[26]; int[] s2zM = new int[26]; for (int i = 0; i < len1; i++) { s1Zm[s1.charAt(i) - 'a']++; s2zM[s2.charAt(i) - 'a']++; } if(Arrays.equals(s1Zm, s2zM)) { return true; } for(int i=len1;i<s2.length();i++) { s2zM[s2.charAt(i)-'a']++; s2zM[s2.charAt(i-len1)-'a']--; if(Arrays.equals(s1Zm, s2zM)) { return true; } } return false; } }
转载链接:https://leetcode-cn.com/problems/permutation-in-string
编写一个函数来查找字符串数组中的最长公共前缀。
示例 1:
输入:strs = ["flower","flow","flight"] 输出:"fl" 示例 2:
输入:strs = ["dog","racecar","car"] 输出:"" 解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 仅由小写英文字母组成
class Solution { public String longestCommonPrefix(String[] strs) { String ans = strs[0]; for (int i = 1; i < strs.length; ++i) { while (strs[i].indexOf(ans) != 0) ans = ans.substring(0, ans.length() - 1); } return ans; } }
转载连接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnmav1/
有两个字符串str和str2,求出两个字符串中最长公共子串长度。
比如:str=acbcbcef,str2=abcbced,则str和str2的最长公共子串为bcbce,最长公共子串长度为5。
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等,相等的话值设置为1,否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。
针对于上面的两个字符串我们可以得到的二维矩阵如下:
从上图可以看到,str1和str2共有5个公共子串,但最长的公共子串长度为5。
为了进一步优化算法的效率,我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度,即某个二维矩阵元素的值由dpi=1演变为dpi=1 +dpi-1,这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下:
状态转移方程
package DP; public class LCS_1 { public static void main(String[] args) { LCS_1 lcs = new LCS_1(); String str = lcs.getLSC("acbcbcef","abcbced"); System.out.println(str); } private String getLSC(String A, String B) { int[][] dp = new int[B.length()][A.length()]; int end_index = 0; int maxLength = 0; for(int i = 0; i < A.length(); i++) { for(int j = 0; j < B.length(); j++) { if(B.charAt(j) == A.charAt(i)) { if(i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = dp[i - 1][j - 1] + 1; } if(dp[i][j] > maxLength) { maxLength = dp[i][j]; end_index = j; } } } } System.out.println("maxLength = " + maxLength); System.out.println("end_index = " + end_index); end_index += 1; return B.substring(end_index - maxLength,end_index); } }
转载连接:https://blog.csdn.net/qq_25800311/article/details/81607168
请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。
函数 myAtoi(string s) 的算法如下:
读入字符串并丢弃无用的前导空格 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。 将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。 返回整数作为最终结果。 注意:
本题中的空白字符只包括空格字符 ' ' 。 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。
示例 1:
输入:s = "42" 输出:42 解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。 第 1 步:"42"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"42"(读入 "42") ^ 解析得到整数 42 。 由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。 示例 2:
输入:s = " -42" 输出:-42 解释: 第 1 步:" -42"(读入前导空格,但忽视掉) ^ 第 2 步:" -42"(读入 '-' 字符,所以结果应该是负数) ^ 第 3 步:" -42"(读入 "42") ^ 解析得到整数 -42 。 由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。 示例 3:
输入:s = "4193 with words" 输出:4193 解释: 第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止) ^ 解析得到整数 4193 。 由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。 示例 4:
输入:s = "words and 987" 输出:0 解释: 第 1 步:"words and 987"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"words and 987"(当前没有读入字符,因为这里不存在 '-' 或者 '+') ^ 第 3 步:"words and 987"(由于当前字符 'w' 不是一个数字,所以读入停止) ^ 解析得到整数 0 ,因为没有读入任何数字。 由于 0 在范围 [-231, 231 - 1] 内,最终结果为 0 。 示例 5:
输入:s = "-91283472332" 输出:-2147483648 解释: 第 1 步:"-91283472332"(当前没有读入字符,因为没有前导空格) ^ 第 2 步:"-91283472332"(读入 '-' 字符,所以结果应该是负数) ^ 第 3 步:"-91283472332"(读入 "91283472332") ^ 解析得到整数 -91283472332 。 由于 -91283472332 小于范围 [-231, 231 - 1] 的下界,最终结果被截断为 -231 = -2147483648 。
提示:
0 <= s.length <= 200
s 由英文字母(大写和小写)、数字(0-9)、' '、'+'、'-' 和 '.' 组成
class Solution { public int myAtoi(String str) { str = str.trim();//去掉前后的空格 //如果为空,直接返回0 if (str.length() == 0) return 0; int index = 0;//遍历字符串中字符的位置 int res = 0;//最终结果 int sign = 1;//符号,1是正数,-1是负数,默认为正数 int length = str.length(); //判断符号 if (str.charAt(index) == '-' || str.charAt(index) == '+') sign = str.charAt(index++) == '+' ? 1 : -1; for (; index < length; ++index) { //取出字符串中字符,然后转化为数字 int digit = str.charAt(index) - '0'; //按照题中的要求,读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。 //字符串的其余部分将被忽略。如果读取了非数字,后面的都要忽略 if (digit < 0 || digit > 9) break; //越界处理 if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; else res = res * 10 + digit; } return sign * res; } }
转载链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnoilh/
题解:https://leetcode-cn.com/problems/string-to-integer-atoi/solution/
以上是脚本宝典为你收集整理的字符串算法全部内容,希望文章能够帮你解决字符串算法所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。