问长度为3的substring, 是不是都是不同字符的
class Solution {
public int countGoodSubstrings(String s) {
int n = s.length();
if(n < 3)
return 0;
int count = 0;
for(int i = 0; i < n - 2; i++)
{
if(s.charAt(i) != s.charAt(i + 1) && s.charAt(i) != s.charAt(i + 2) && s.charAt(i + 1) != s.charAt(i + 2))
count ++;
}
return count;
}
}给一个数组, 求是否能删除一个后,让数组变成严格递增, 这个题有个陷阱, 就是示例二给的[2,3,1,2], 这个是返回false. 观察一下能看出, [2,3,1]这种, 就是不行的, 找规律发现, 不光需要比较相邻元素, 也要比较删除后的元素. 所以要用当前位置i, 记录删除后的前一个元素i-1的大小.
class Solution {
public boolean canBeIncreasing(int[] nums) {
int count = 0;
for(int i = 1; i < nums.length; i++)
{
if(nums[i - 1] >= nums[i])
count++;
if(i >= 2 && nums[i - 2] >= nums[i])
nums[i] = nums[i - 1];
}
return count <= 1;
}
}….太水了
class Solution {
public int maxProductDifference(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
return (nums[n - 1] * nums[n - 2] - (nums[0] * nums[1]));
}
}没啥好说的
class Solution {
public int[] buildArray(int[] nums) {
int n = nums.length;
int[] res = new int[n];
for(int i = 0; i < n; i++)
res[i] = nums[nums[i]];
return res;
}
}给一个数字n, 求[1,n]中有多少勾股数.
class Solution {
public int countTriples(int n) {
Map<Integer, Integer> m = new HashMap<>();
int count = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
int t = i*i + j*j;
m.put(t, m.getOrDefault(t, 0) + 1);
}
}
for(int i = 1; i <= n; i++)
{
count += m.getOrDefault(i*i, 0);
}
return count;
}
}这题没啥可说的吧..
class Solution {
public int[] getConcatenation(int[] nums) {
int n = nums.length;
int[] res = new int[2*n];
int i = 0;
for(int k : nums)
{
res[i] = k;
res[i + n] = k;
i++;
}
return res;
}
}给一个string, 问能不能分解成n个substring, 这些substring由一个长度为2和n个长度为3的连续相同字母组成.
看着很复杂, 其实就是计数一下, 然后每次有新的char的时候, 看mod 3以后是不是能整除. 如果mod后是0, 那么就忽略, mod后是2, 就看是不是唯一的2. 因为必须有1个长度为2的子字符串, 所以最后要检查一下.
class Solution {
public boolean isDecomposable(String s) {
if(s.length() < 2)
return false;
s = s+"1";
int[] m = new int[11];
boolean two = true;
for(int i = 0; i < s.length(); i++)
{
if(i > 0 && s.charAt(i) != s.charAt(i - 1))
{
if(m[s.charAt(i - 1) - '0'] % 3 == 0)
{
m[s.charAt(i - 1) - '0'] = 0;
}
else if(m[s.charAt(i - 1) - '0'] % 3 == 2)
{
if(!two)
return false;
m[s.charAt(i - 1) - '0'] = 0;
two = false;
}
else
{
return false;
}
}
if(i < s.length())
m[s.charAt(i) - '0'] ++;
}
if(two)
return false;
else
return true;
}
}A. Shortest Path with Obstacle
#include "bits/stdc++.h"
using namespace std;
// fast read
const auto fr = [](){
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
std::cout << std::fixed << std::setprecision(12);
return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
int main() {
fr;
int T;
cin >> T;
while (T--)
{
int X1,Y1,X2,Y2,OX,OY;
cin >> X1 >> Y1 >> X2 >> Y2 >> OX >> OY;
ll res = 0;
res += abs(X2 - X1);
res += abs(Y2 - Y1);
if(X1 == X2 && X2 == OX && ((Y1 < OY && OY < Y2) || (Y2 < OY && OY < Y1)))
{
res += 2;
}
else if(Y1 == Y2 && Y2 == OY && ((X1 < OX && OX < X2) || (X2 < OX && OX < X1)))
{
res += 2;
}
cout << res << endl;
}
return 0;
}B. Alphabetical Strings
#include "bits/stdc++.h"
using namespace std;
// fast read
const auto fr = [](){
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
std::cout << std::fixed << std::setprecision(12);
return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
int main() {
fr;
int T;
cin >> T;
while (T--)
{
string s;
cin >> s;
int a = -1;
for(int i = 0; i < s.length(); i++)
{
if(s[i] == 'a')
{
a = i;
break;
}
}
if(a == -1)
{
cout << "NO" << endl;
continue;
}
int i = a - 1;
int j = a + 1;
int flag = 1;
int k = 1;
while (flag)
{
flag = 0;
if(i >= 0 && s[i] == 'a' + k)
{
i--; k++; flag = 1;
}
else if(j <= s.length() - 1 && s[j] == 'a' + k)
{
j++; k++; flag = 1;
}
}
if(i < 0 && j >= s.length())
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}C. Pair Programming
#include "bits/stdc++.h"
using namespace std;
// fast read
const auto fr = [](){
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
std::cout << std::fixed << std::setprecision(12);
return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
int main() {
fr;
int T;
cin >> T;
while (T--)
{
int K,N,M;
cin >> K >> N >> M;
int A[N];
for(int i = 0; i < N; i++)
cin >> A[i];
int B[M];
for(int i = 0; i < M; i++)
cin >> B[i];
int i = 0, j = 0;
ll max = K;
int flag = 1;
vector<int> v;
while (flag)
{
flag = 0;
while (i < N && A[i] <= max)
{
if(A[i] == 0)
max++;
v.push_back(A[i++]);
flag = 1;
}
while (j < M && B[j] <= max)
{
if(B[j] == 0)
max++;
v.push_back(B[j++]);
flag = 1;
}
}
if(i == N && j == M)
{
for(int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
}
else
{
cout << -1 << endl;
}
}
return 0;
}D. Co-growing Sequence
#include "bits/stdc++.h"
using namespace std;
// fast read
const auto fr = [](){
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
std::cout << std::fixed << std::setprecision(12);
return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
int main() {
fr;
int T;
cin >> T;
auto build = [&](int x, int y){return x & ~y;};
while (T--)
{
int N;
cin >> N;
int A[N];
for(int i = 0; i < N; i++)
cin >> A[i];
int B[N]={0};
for(int i = 1; i < N; i++)
B[i] = build(B[i - 1] ^ A[i - 1], A[i]);
for(int i = 0; i < N; i++)
cout << B[i] << " ";
cout << endl;
}
return 0;
}D的题意是通过下面的图推出来的
给两个个数字A,B. 求是否通过同时增加两个数或者同时减少两个数, 得到最大的gcd. 如果能, 需要同时加.减几?
典型的求gcd缺和gcd无关的题, 因为同增加/减少, 所以差值一样, 所以gcd最大就是差值, 因为gcd(0,max(A,B))最大.
然后几步嘛, 就是求比较小的数到差值的倍数的大小, 求余即可.
#include "bits/stdc++.h"
using namespace std;
// fast read
const auto fr = [](){
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
std::cout << std::fixed << std::setprecision(12);
return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
int main() {
fr;
int T;
cin >> T;
while (T--)
{
ll A,B;
cin >> A >> B;
if(A > B)
{
swap(A, B);
}
if(A == B)
{
cout << 0 << " " << 0 << endl;
continue;
}
ll C = B - A;
ll D = min(A % C, C - A % C);
cout << C << " " << D << endl;
}
return 0;
}给一个字符串, *代表羊, .代表空位, 求怎么移动能让羊排成一列.
这题是acwing的那个模板题的衍生, 要先找到中间羊, 然后找到它的位置, 然后平移(坐标 – 第几个), 求和即可.
#include "bits/stdc++.h"
using namespace std;
// fast read
const auto fr = [](){
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
std::cout << std::fixed << std::setprecision(12);
return 1;
}();
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; };
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
// vars:
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vvi = std::vector<vi>;
using vvl = std::vector<vl>;
using pii = std::pair<int,int>;
using pil = std::pair<int,ll>;
using pli = std::pair<ll,int>;
using pll = std::pair<ll,ll>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
// consts
ll M = 0;
// ksm (kuai su mi)
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}
int main() {
fr;
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
string s;
cin >> s;
ll res = 0;
ll count = 0;
for (int i = 0; i < N; i++)
{
if(s[i] == '*')
{
count++;
}
}
if(count == 0 || count == N)
{
cout << 0 << endl;
continue;
}
ll t = -1;
ll med = -1;
for (int i = 0; i < N; i++)
{
if(s[i] == '*')
{
t++;
}
if(t == count / 2)
{
med = i;
break;
}
}
ll tt = med - count / 2;
for (int i = 0; i < N; i++)
{
if(s[i] == '*')
{
res += abs(tt - i);
tt++;
}
}
cout << res << endl;
}
return 0;
}