每日OJ题_牛客_小红的ABC_暴力/找规律_C++_Java

目录

牛客_小红的ABC_暴力/找规律

题目解析

C++代码1暴力

C++代码2找规律​编辑

Java代码找规律

---

牛客_小红的ABC_暴力/找规律

小红的ABC (nowcoder.com)

描述：
        小红拿到了一个只包含 'a' , 'b' , 'c' 三种字符的字符串。小红想知道，这个字符串最短的、长度超过 1 的回文子串的长度是多少？
        子串定义：字符串取一段连续的区间。例如"abcca"的子串有"ab"、"bcca"等，但"aca"则不是它的子串。
        回文的定义：一个字符串正着读和倒着读都是相同的，那么定义它的回文的。

输入描述：

一个只包含 'a' , 'b' , 'c' 三种字符的字符串。

数据范围：字符串长度不小于2，且不超过100

输出描述：

如果不存在长度超过1的回文子串，则输出-1。

否则输出长度超过1的最短回文子串的长度。

---

题目解析

• 解法1：模拟。用数组或者链表模拟均可。但是数据量大的话会超时。
• 解法2：数学规律。通过画图可以找到相邻两次删除坐标的规律。通过递推关系，求出剩下的最后一个数是哪个。

C++代码1暴力

#include <climits>
#include <iostream>
using namespace std;
string str;bool isPal(int left, int right)
{while(left < right){if(str[left] == str[right])++left, --right;elsereturn false;}return true;
}
int main()
{cin >> str; // 暴力int n = str.size(), res = INT_MAX;for(int i = 0; i < n; ++i){for(int j = i + 1; j < n; ++j){if(isPal(i, j))res = min(res, j - i + 1);}}res = res == INT_MAX ? -1 : res;cout << res << endl;return 0;
}

C++代码2找规律

#include <iostream>
using namespace std;int main()
{string str;cin >> str;int n = str.size(), res = -1;for(int i = 0; i < n; ++i){if(i - 1 < n && str[i] == str[i + 1]){res = 2;break;}if(i - 2 < n && str[i] == str[i + 2]){res = 3;}}cout << res << endl;return 0;
}

Java代码找规律

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);char[] s = in.next().toCharArray();int ret = -1; // 并没有回⽂串int n = s.length;for(int i = 0; i < n; i++){if(i + 1 < n && s[i] == s[i + 1]) // 判断⻓度为 2 的⼦串{ret = 2;break;}if(i + 2 < n && s[i] == s[i + 2]) // 判断⻓度为 3 的⼦串{ret = 3;}}System.out.println(ret);}
}