文章目录

• • • • 1.反转字符串
      • 2.整数反转
      • 3.字符串中的第一个唯一字符
      • 4.有效的字母异位词
      • 5.验证回文串
      • 6.字符串转换整数 (atoi)
      • 7.实现strStr()
      • 8.外观数列
      • 9.最长公共前缀

💎💎💎💎💎

更多资源链接，欢迎访问作者gitee仓库：https://gitee.com/fanggaolei/learning-notes-warehouse/tree/master

哔哩哔哩算法题视频讲解：Java初级算法合集

1.反转字符串

  编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]

class Solution {public void reverseString(char[] s) {int length=s.length;for(int i=0;ichar tmp=s[i];s[i]=s[length-1];s[length-1]=tmp;length--;}}
}

2.整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

class Solution {public int reverse(int x) {long i=0;while(x!=0){i=i*10+x%10;x=x/10;}return (int)i==i?(int)i:0;}
}

3.字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

class Solution {public int firstUniqChar(String s) {int[] count=new int[26];char[] chars=s.toCharArray();for(int i=0;icount[chars[i]-'a']++;}for(int i=0;iif(count[chars[i]-'a']==1){return i;}}return -1;}
}

4.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length())return false;int[] letterCount = new int[26];//统计字符串s中的每个字符的数量for (int i = 0; i < s.length(); i++)letterCount[s.charAt(i) - 'a']++;//减去字符串t中的每个字符的数量for (int i = 0; i < t.length(); i++)letterCount[t.charAt(i) - 'a']--;//如果数组letterCount的每个值都是0，返回true，否则返回falsefor (int count : letterCount)if (count != 0)return false;return true;}
}

5.验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

public boolean isPalindrome(String s) {if (s == null || s.length() == 0)return true;s = s.toLowerCase();for (int i = 0, j = s.length() - 1; i < j; i++, j--) {while (i < j && !Character.isLetterOrDigit(s.charAt(i)))i++;while (i < j && !Character.isLetterOrDigit(s.charAt(j)))j--;if (s.charAt(i) != s.charAt(j))return false;}return true;}

6.字符串转换整数 (atoi)

请你来实现一个 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 。

提示：0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
相关标签

class Solution {public int myAtoi(String s) {char[] chars = s.toCharArray();int length = chars.length;int index = 0;// 先去除空格while (index < length && chars[index] == ' '){index++;}// 再判断符号int sign =  1;if(chars[index] == '-' || chars[index] == '+'){if(chars[index] == '-'){sign = -1;}index++;}int result = 0;int temp = 0;while (index < length){int num = chars[index] - '0';if(num > 9 || num < 0){break;}temp = result;result = result * 10 + num;if(result/10 !=temp){if(sign > 0){return Integer.MAX_VALUE;}else {return Integer.MIN_VALUE;}}index++;}return result*sign;}
}

7.实现strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

public int strStr(String haystack, String needle) {if (needle.length() == 0)return 0;int i = 0;int j = 0;while (i < haystack.length() && j < needle.length()) {if (haystack.charAt(i) == needle.charAt(j)) {i++;j++;} else {//如果不匹配，就回退，从第一次匹配的下一个开始，i = i - j + 1;j = 0;}if (j == needle.length())return i - j;}return -1;}

8.外观数列

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221第一项是数字 1 描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

class Solution {public String countAndSay(int n) { //4String res="1"; //11 21 1211//确定描述的次数for(int i=2;i<=n;i++){int index=0;StringBuilder stringBuilder=new StringBuilder();//可变的字符串while(indexint count=1;while(indexindex++;count++;}stringBuilder.append(count);stringBuilder.append(res.charAt(index));index++;}res=stringBuilder.toString();}return res;}
}

9.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

class Solution {public String longestCommonPrefix(String[] strs) {//边界条件判断if (strs == null || strs.length == 0)return "";//默认第一个字符串是他们的公共前缀String pre = strs[0];int i = 1;while (i < strs.length) {//不断的截取while (strs[i].indexOf(pre) != 0)pre = pre.substring(0, pre.length() - 1);i++;}return pre;}
}