415. 字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
468. 验证IP地址
给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 "IPv4" ；如果是有效的 IPv6 地址，返回 "IPv6" ；如果不是上述类型的 IP 地址，返回 "Neither" 。
有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。 其中 0 <= xi <= 255 且 xi 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “192.168@1.1” 为无效IPv4地址。
一个有效的IPv6地址 是一个格式为“x1:x2:x3:x4:x5:x6:x7:x8” 的IP地址，其中:
- 1 <= xi.length <= 4
- xi 是一个 十六进制字符串 ，可以包含数字、小写英文字母( 'a' 到 'f' )和大写英文字母( 'A' 到 'F' )。
- 在 xi 中允许前导零。
例如 "2001:0db8:85a3:0000:0000:8a2e:0370:7334" 和 "2001:db8:85a3:0:0:8A2E:0370:7334" 是有效的 IPv6 地址，而 "2001:0db8:85a3::8A2E:037j:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。
解题思路
class Solution {
public String validIPAddress(String queryIP) {
if (queryIP.contains(".")) {
String[] arr = queryIP.split("\\.", -1);
if (!isIPv4(arr)) {
return "Neither";
}
return "IPv4";
}
String[] arr = queryIP.split("\\:", -1);
if (!isIPv6(arr)) {
return "Neither";
}
return "IPv6";
}
private boolean isIPv4(String[] arr) {
if (arr.length != 4) {
return false;
}
for (String ip : arr) {
if (ip.length() < 1 || ip.length() > 3) {
return false;
}
for (char ch : ip.toCharArray()) {
if (!Character.isDigit(ch)) {
return false;
}
}
int ipNum = Integer.parseInt(ip);
if (ipNum > 255 || (String.valueOf(ipNum).length() != ip.length())) {
return false;
}
}
return true;
}
private boolean isIPv6(String[] arr) {
if (arr.length != 8) {
return false;
}
for (String ip : arr) {
if (ip.length() < 1 || ip.length() > 4) {
return false;
}
for (char ch : ip.toCharArray()) {
if (!Character.isDigit(ch) && !(ch >= 'a' && ch <= 'f' || ch >= 'A' && ch <= 'F')) {
return false;
}
}
}
return true;
}
}
func validIPAddress(queryIP string) string {
isIPv4 := func(arr []string) bool {
if len(arr) != 4 {
return false
}
for _, ip := range arr {
if len(ip) < 1 || len(ip) > 3 {
return false
}
ipNum, _ := strconv.Atoi(ip)
if ipNum > 255 || len(ip) != len(strconv.Itoa(ipNum)) {
return false
}
}
return true
}
isIPv6 := func(arr []string) bool {
if len(arr) != 8 {
return false
}
for _, ip := range arr {
if len(ip) < 1 || len(ip) > 4 {
return false
}
for _, ch := range ip {
if !(ch >= '0' && ch <= '9') && !(ch >= 'a' && ch <= 'f' || ch >= 'A' && ch <= 'F') {
return false
}
}
}
return true
}
if strings.Contains(queryIP, ".") {
arr := strings.SplitN(queryIP, ".", -1)
if !isIPv4(arr) {
return "Neither"
}
return "IPv4"
}
arr := strings.SplitN(queryIP, ":", -1)
if !isIPv6(arr) {
return "Neither"
}
return "IPv6"
}
93. 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
解题思路
很典型的dfs问题，具体操作如下：
定义一个字符串向量ans，用于存储最终生成的有效IPv4地址。
定义一个深度优先搜索函数dfs，参数包括：原始字符串s、当前已组合的字符串res、当前遍历的字符串s的位置idx和当前已经组合的有效段的数量cnt。
a. 如果idx遍历到了字符串s的末尾，且已组合的有效段数量cnt等于4，将当前组合的字符串res添加到ans中并返回。
b. 初始化一个临时字符串tmp，用于存储当前遍历的数字。
c. 使用一个for循环，从idx遍历到字符串s的末尾。
i. 如果tmp为"0"，跳出循环。
ii. 将当前字符s[i]追加到tmp中。
iii. 如果tmp的整数值小于等于255（IPv4地址的有效范围），将tmp追加到res中，然后递归调用dfs函数，更新参数为：原始字符串s、当前已组合的字符串res、新的遍历位置i + 1和新的有效段数量cnt + 1。递归返回后，将tmp和一个点从res中删除。
iv. 如果tmp的整数值大于255，跳出循环。
调用dfs函数，参数为：原始字符串s、空字符串res、初始遍历位置0和初始有效段数量0。
遍历结果向量ans中的所有字符串，删除每个字符串末尾多余的点。
返回结果向量ans。
class Solution {
public:
vector<string> ans;
void dfs(string& s, string& res, int idx, int cnt) {
int n = s.size();
if(idx == n && cnt == 4) {
ans.emplace_back(res);
return;
}
string tmp = "";
for(int i = idx; i < n; i++) {
if(tmp == "0") {
break;
}
tmp.push_back(s[i]);
if(stoi(tmp) <= 255) {
res += tmp;
res.push_back('.');
dfs(s, res, i + 1, cnt + 1);
for(int j = 0; j <= tmp.size(); j++) {
res.pop_back();
}
}else {
break;
}
}
}
vector<string> restoreIpAddresses(string s) {
string res = "";
dfs(s, res, 0 ,0);
for(auto& str: ans) {
str.pop_back();
}
return ans;
}
};
class Solution {
private List<String> res;
public List<String> restoreIpAddresses(String s) {
res = new ArrayList<>();
if(s.length() > 12) return res;
dfs(s, 0, new LinkedList<String>());
return res;
}
private void dfs(String s, int i, LinkedList<String> path) {
if(path.size() == 4) {
if(i == s.length()) {
StringBuffer sb = new StringBuffer();
for(String r : path) sb.append(r + ".");
res.add(sb.substring(0, sb.length() - 1));
}
return;
}
for(int j=i;j<i+3 && j<s.length();j++) {
if(s.charAt(i) == '0' && j > i) continue;
int opt = Integer.parseInt(s.substring(i, j + 1));
if(opt > 255) continue;
path.add(s.substring(i, j + 1));
dfs(s, j+1, path);
path.remove(path.size() - 1);
}
}
}
func restoreIpAddresses(s string) []string {
res := []string{}
var dfs func(subRes []string, start int)
dfs = func(subRes []string, start int) {
if len(subRes) == 4 && start == len(s) {
res = append(res, strings.Join(subRes, "."))
return
}
if len(subRes) == 4 && start < len(s) {
return
}
for length := 1; length <= 3; length++ {
if start+length-1 >= len(s) {
return
}
if length != 1 && s[start] == '0' {
return
}
str := s[start : start+length]
if n, _ := strconv.Atoi(str); n > 255 {
return
}
subRes = append(subRes, str)
dfs(subRes, start+length)
subRes = subRes[:len(subRes)-1]
}
}
dfs([]string{}, 0)
return res
}
8. 字符串转换整数 (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 。 返回整数作为最终结果。
解题思路
按位字符串处理即可，先去掉前导0，然后再判断符号。具体操作如下：
初始化整数变量idx为0，表示当前正在处理的字符串s中的字符索引。
使用while循环，跳过字符串s开头的空白字符。
初始化整数变量sign为1，表示结果的符号（1表示正数，0表示负数）。
检查当前字符是否为正号'+'或负号'-'，并根据符号更新sign变量。如果是负号'-'，将sign设置为0。
初始化整数变量ans为0，用于存储转换后的整数。
使用while循环，处理数字字符。循环条件为：idx小于n（字符串s的长度），并且当前字符是数字字符。
a. 计算当前数字字符对应的整数值，用负数表示，将其存储在整数变量cur中。
b. 检查ans是否小于INT_MIN/10或者ans等于INT_MIN/10并且cur小于INT_MIN%10。如果满足条件，说明将要溢出，将ans设置为INT_MIN并跳出循环。
c. 递增idx，更新ans的值为10 * ans + cur。
如果ans等于INT_MIN，并且sign为1，说明结果将要溢出，返回INT_MAX。
如果sign为1，将ans的符号取反（ans = -ans），表示正数。
返回整数ans作为结果。
class Solution {
public:
int myAtoi(string s) {
int idx=0,n=s.size();
while(idx<n && s[idx]==' ') idx++;
int sign=1;
if(s[idx]=='-'){
sign=0;
idx++;
}else if(s[idx]=='+'){
idx++;
}
int ans=0;
while(idx<n && s[idx]>='0' && s[idx]<='9'){
int cur=-(s[idx]-'0');
if(ans<INT_MIN/10 || (ans==INT_MIN/10 && cur<INT_MIN%10)){
ans=INT_MIN;
break;
}
idx++;
ans=10*ans+cur;
}
if(ans==INT_MIN && sign) return INT_MAX;
if(sign) ans=-ans;
return ans;
}
};
class Solution {
public int myAtoi(String str) {
str = str.trim();
int n = str.length();
if(n == 0) return 0;
if(!Character.isDigit(str.charAt(0)) && str.charAt(0) != '+' && str.charAt(0) != '-'){
return 0;
}
long ans = 0l;
boolean neg = str.charAt(0) == '-'? true : false;
int begin = !Character.isDigit(str.charAt(0)) ? 1 : 0;
while(begin < n && Character.isDigit(str.charAt(begin))){
ans = ans * 10 + str.charAt(begin) - '0';
if(!neg && ans > Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
if(neg && ans > 1l + Integer.MAX_VALUE){
return Integer.MIN_VALUE;
}
begin++;
}
return neg?(int)-ans : (int)ans;
}
}
func myAtoi(s string) int {
if s == "" {
return 0
}
i, n := 0, len(s)
for i < n-1 {
if s[i] == ' ' {
i++
} else {
break
}
}
s0 := s[i:]
if s[i] == '-' || s[i] == '+' {
s = s[i+1:]
} else if s[i] >= '0' && s[i] <= '9'{
s = s[i:]
} else {
return 0
}
num := 0
for _, ch := range []byte(s) {
ch -= '0'
if ch > 9 || ch < 0 {
break
}
num = num * 10 + int(ch)
if num >= 1<<31 {
num = 1<<31
break
}
}
if s0[0] == '-' {
num = -num
} else {
if num >= 1 << 31 - 1 {
num = 1 << 31 - 1
}
}
return num
}
165. 比较版本号
给你两个版本号 version1 和 version2 ，请你比较它们。
版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。
返回规则如下：
如果 version1 > version2 返回 1， 如果 version1 < version2 返回 -1， 除此之外返回 0。
解题思路
先划分出来每一位，再比较大小，具体操作如下：
使用split函数将字符串v1和v2根据点（.）分隔符切分成字符串数组ss1和ss2。
获取字符串数组ss1和ss2的长度，分别存储在整数变量n和m中。
初始化两个整数变量i和j，用于遍历字符串数组ss1和ss2。
使用一个while循环，条件为i小于n或者j小于m，表示还有未比较的版本号子串。
a. 初始化两个整数变量a和b为0。
b. 如果i小于n，将ss1[i]的整数值赋给a，并递增i。
c. 如果j小于m，将ss2[j]的整数值赋给b，并递增j。
d. 如果a和b不相等，根据a和b的大小返回1或-1。
如果所有对应子串均相等，返回0，表示版本号相等。
class Solution {
public:
int compareVersion(string version1, string version2) {
version1.push_back('.');
version2.push_back('.');
vector<int> num1, num2;
int i = 0, flag = 0, x = 0;
while (i < version1.size()) {
if (version1[i] == '.') {
num1.push_back(x);
x = 0;
i++;
while (i < version1.size() && version1[i] == '0') i++;
}else {
x = 10 * x + version1[i] - '0';
i++;
}
}
i = 0, flag = 0, x = 0;
while (i < version2.size()) {
if (version2[i] == '.') {
num2.push_back(x);
x = 0;
i++;
while (i < version2.size() && version2[i] == '0') i++;
}else {
x = 10 * x + version2[i] - '0';
i++;
}
}
for (int i = 0; i < min(num1.size(), num2.size()); i++) {
if (num1[i] > num2[i]) return 1;
else if (num1[i] < num2[i]) return -1;
}
if (num1.size() > num2.size()) {
for(int i = num2.size(); i < num1.size(); i++){
if(num1[i] > 0) return 1;
}
return 0;
}else if (num1.size() < num2.size()) {
for(int i = num1.size(); i<num2.size(); i++){
if(num2[i] > 0) return -1;
}
return 0;
}
else return 0;
}
};
class Solution {
public int compareVersion(String v1, String v2) {
String[] ss1 = v1.split("\\."), ss2 = v2.split("\\.");
int n = ss1.length, m = ss2.length;
int i = 0, j = 0;
while (i < n || j < m) {
int a = 0, b = 0;
if (i < n) a = Integer.parseInt(ss1[i++]);
if (j < m) b = Integer.parseInt(ss2[j++]);
if (a != b) return a > b ? 1 : -1;
}
return 0;
}
}
import "strings"
import "strconv"
func compareVersion(version1 string, version2 string) int {
demo1 := strings.Split(version1,".")
demo2 := strings.Split(version2,".")
len1 := len(demo1)
len2 := len(demo2)
for i:=0;i<len1||i<len2;i++{
x,y := 0,0
if i<len1{
x,_= strconv.Atoi(demo1[i])
}
if i<len2{
y,_= strconv.Atoi(demo2[i])
}
if x>y{
return 1
}
if x<y{
return -1
}
}
return 0
}
