字符串变形
对于一个给定的字符串，我们需要在线性(也就是O(n))的时间里对它做一些变形。首先这个字符串中包含着一些空格，就像”Hello World”一样，然后我们要做的是把着个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。比如”Hello World”变形后就变成了”wORLD hELLO”。
输入描述:
给定一个字符串s以及它的长度n(1≤n≤500)
返回值描述:
请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。
示例1
输入
"This is a sample",16
返回值
"SAMPLE A IS tHIS"
解法
- 从后往前遍历字符串，记录下空格的位置
- 然后把这个单词添加到结果中
import java.util.*;
public class Solution {
private char change(char ch) {
if ('a' <= ch && ch <= 'z') {
return (char)(ch - 'a' + 'A');
} else {
return (char)(ch - 'A' + 'a');
}
}
public String trans(String s, int n) {
// write code here
int p = n - 1;
StringBuilder ans = new StringBuilder();
for (int i = n - 1; i >= 0; i--) {
char c = s.charAt(i);
if (c == ' ') {
for (int j = i + 1; j <= p; j++) {
ans.append(change(s.charAt(j)));
}
ans.append(' ');
p = i - 1;
}
}
for (int j = 0; j <= p; j++) {
ans.append(change(s.charAt(j)));
}
return ans.toString();
}
}
468. 验证IP地址
编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。
如果是有效的 IPv4 地址，返回 “IPv4” ；
如果是有效的 IPv6 地址，返回 “IPv6” ；
如果不是上述类型的 IP 地址，返回 “Neither” 。
IPv4 地址由十进制数和点来表示，每个地址包含 4 个十进制数，其范围为 0 - 255， 用(“.”)分割。比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。
IPv6 地址由 8 组 16 进制的数字来表示，每组表示 16 比特。这些组数字通过 (“:”)分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。
然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。 比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。
示例 1：
输入：IP = “172.16.254.1”
输出：”IPv4”
解释：有效的 IPv4 地址，返回 “IPv4”
示例 2：
输入：IP = “2001:0db8:85a3:0:0:8A2E:0370:7334”
输出：”IPv6”
解释：有效的 IPv6 地址，返回 “IPv6”
示例 3：
输入：IP = “256.256.256.256”
输出：”Neither”
解释：既不是 IPv4 地址，又不是 IPv6 地址
示例 4：
输入：IP = “2001:0db8:85a3:0:0:8A2E:0370:7334:”
输出：”Neither”
示例 5：
输入：IP = “1e1.4.5.6”
输出：”Neither”
提示：
IP 仅由英文字母，数字，字符 ‘.’ 和 ‘:’ 组成。
解法
class Solution {
public String validateIPv4(String IP) {
String[] nums = IP.split("\\.", -1);
for (String x : nums) {
if (x.length() == 0 || x.length() > 3) {
return "Neither";
}
if (x.charAt(0) == '0' && x.length() != 1) {
return "Neither";
}
for (char c : x.toCharArray()) {
if (!Character.isDigit(c)) {
return "Neither";
}
}
if (Integer.parseInt(x) > 255) {
return "Neither";
}
}
return "IPv4";
}
public String validateIPv6(String IP) {
String[] nums = IP.split(":", -1);
String hexdigits = "0123456789abcdefABCDEF";
for (String x : nums) {
if (x.length() == 0 || x.length() > 4) {
return "Neither";
}
for (char c : x.toCharArray()) {
if (hexdigits.indexOf(c) == -1) {
return "Neither";
}
}
}
return "IPv6";
}
public String validIPAddress(String IP) {
if (IP.chars().filter(ch -> ch == '.').count() == 3) {
return validateIPv4(IP);
} else if (IP.chars().filter(ch -> ch == ':').count() == 7){
return validateIPv6(IP);
} else {
return "Neither";
}
}
}
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：
输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”
示例 2：
输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。
提示：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
解法
- 先排序，然后比较首位字符串即可
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
Arrays.sort(strs);
int len = strs.length;
int n = Math.min(strs[0].length(), strs[len - 1].length());
int i = 0;
for (; i < n; i++) {
if (strs[0].charAt(i) != strs[len - 1].charAt(i)) {
break;
}
}
return strs[0].substring(0, i);
}
}
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
解法
class Solution {
public boolean isAnagram(String s, String t) {
char[] array = new char[26];
for (char c : s.toCharArray()) {
array[c - 'a']++;
}
for (char c : t.toCharArray()) {
array[c - 'a']--;
}
for (char c : array) {
if (c != 0) {
return false;
}
}
return true;
}
}
最长回文串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
“abccccdd”
输出:
7
解释:
我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。
解法
class Solution {
public int longestPalindrome(String s) {
char[] array = new char[256];
for (char c : s.toCharArray()) {
array[c]++;
}
int res = 0;
for (char c : array) {
res += (c / 2) * 2;
}
if (res < s.length()) {
res++;
}
return res;
}
}
同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例 1:
输入: s = “egg”, t = “add”
输出: true
示例 2:
输入: s = “foo”, t = “bar”
输出: false
示例 3:
输入: s = “paper”, t = “title”
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。
解法
class Solution {
public boolean isIsomorphic(String s, String t) {
int[] index1 = new int[256];
int[] index2 = new int[256];
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i), tc = t.charAt(i);
if (index1[sc] != index2[tc]) {
return false;
}
index1[sc] = i + 1;
index2[tc] = i + 1;
}
return true;
}
}
回文子串
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例 1:
输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.
示例 2:
输入: “aaa”
输出: 6
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
注意:
输入的字符串长度不会超过1000。
解法
class Solution {
private int count = 0;
public int countSubstrings(String s) {
for (int i = 0; i < s.length(); i++) {
extendSubstrings(s, i, i);
extendSubstrings(s, i, i + 1);
}
return count;
}
private void extendSubstrings(String s, int start, int end) {
while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
start--;
end++;
count++;
}
}
}
回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗？
解法
class Solution {
public boolean isPalindrome(int x) {
if (x == 0) {
return true;
}
if (x < 0 || x % 10 == 0) {
return false;
}
int right = 0;
while (x > right) {
right = right * 10 + x % 10;
x /= 10;
}
return x == right || x == right / 10;
}
}
计数二进制子串
给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数。
示例 1 :
输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
示例 2 :
输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
注意：
s.length 在1到50,000之间。
s 只包含“0”或“1”字符。
解法
class Solution {
public int countBinarySubstrings(String s) {
int preLen = 0, curLen = 1, count = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
curLen++;
} else {
preLen = curLen;
curLen = 1;
}
if (preLen >= curLen) {
count++;
}
}
return count;
}
}
剑指 Offer 58 - I. 翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。Copy to clipboardErrorCopied
解法
class Solution {
public String reverseWords(String s) {
// 去掉收尾空格
s = s.trim();
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while (i >= 0) {
// 搜索首个空格
while (i >= 0 && s.charAt(i) != ' ') {
i--;
}
// 添加单词
res.append(s.substring(i + 1, j + 1) + " ");
// 跳过单词间空格
while (i >= 0 && s.charAt(i) == ' ') {
i--;
}
// j 指向下个单词的尾字符
j = i;
}
return res.toString().trim();
}
}
剑指 Offer 58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
Copy to clipboardErrorCopied
解法
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder();
int size = s.length();
res.append(s.substring(n, size));
res.append(s.substring(0, n));
return res.toString();
}
}
剑指 Offer 67. 把字符串转换成整数
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。Copy to clipboardErrorCopied
解法
class Solution {
public int strToInt(String str) {
if (str == null || str.length() == 0) {
return 0;
}
// 第一个for循环是把符合要求的整数构造出来并存倒StringBuilder里
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == ' ' && sb.length() == 0) {
continue;
} else if ((c == '+' || c == '-') && sb.length() == 0) {
sb.append(c);
} else if (c >= 48 && c <= 57) {
sb.append(c);
} else {
break;
}
}
// 当字符串构造不出来符合条件的整数时直接返回0
if (sb.length() == 0) {
return 0;
}
// 下面的逻辑就是要把字符串例如"12345" 转换为整数 12345
int result = 0;
boolean flag = true;
int i = 0;
if (sb.charAt(0) == '+') {
flag = true;
i = 1;
}
else if (sb.charAt(0) == '-') {
flag = false;
i = 1;
}
while (i < sb.length()) {
int temp = sb.charAt(i) - '0';
// 这两个判断非常重要，如果溢出就直接返回
if(flag == true && (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && temp > 7))){
return Integer.MAX_VALUE;
}
else if (flag == false && (result > Math.abs(Integer.MIN_VALUE / 10) || (-result == Integer.MIN_VALUE / 10 && temp > 8))){
return Integer.MIN_VALUE;
}
result = result * 10 + temp;
i++;
}
// 最终结果
if(flag == true) {
return result;
}
else {
return -result;
}
}
}
欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。
若有收获，就点个赞吧
0 人点赞
