c笔试强训第四十八篇
目录
【c++笔试强训】（第四十八篇）
跳台阶扩展问题（规律）
题目解析
1.题目链接：
2.题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
数据范围：1 \le n \le 201≤n≤20
进阶：空间复杂度 O(1)O(1) ， 时间复杂度 O(1)O(1)
输入描述：
本题输入仅一行，即一个整数 n
输出描述：
输出跳上 n 级台阶的跳法
示例1
输入：
3
输出：
4
示例2
输入：
1
输出：
1
讲解算法原理
解法：
算法思路：
没想到吧，居然是⼀道规律题~
编写代码
c++算法代码：
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
cout << (1 << (n - 1)) << endl;
return 0;
}java算法代码：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in); int n = in.nextInt();
System.out.println(1 << (n - 1));
}
}包含不超过两种字符的最⻓⼦串（滑动窗⼝）
题目解析
1.题目链接：
2.题目描述
描述
给定一个长度为 n 的字符串，找出最多包含两种字符的最长子串 t ，返回这个最长的长度。
数据范围： 1 \le n \le 10^5 \1≤n≤105 ，字符串种仅包含小写英文字母
输入描述：
仅一行，输入一个仅包含小写英文字母的字符串
输出描述：
输出最长子串的长度
示例1
输入：
nowcoder
输出：
2
示例2
输入：
nooooow
输出：
6
讲解算法原理
解法：
算法思路：
简单滑动窗⼝~
编写代码
c++算法代码：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
int left = 0, right = 0, n = s.size();
int hash[26] = { 0 }; // 统计窗⼝内每种字符出现了多少次
int count = 0; // 统计窗⼝内⼀共有多少种字符 int ret = 0;
while(right < n)
{
if(hash[s[right] - 'a']++ == 0) count++; // 0->1, 窗⼝内多了⼀种字符 while(count > 2) {
if(hash[s[left++] - 'a']-- == 1) count--; // 1->0, 窗⼝内少了⼀种字符 }
ret = max(ret, right - left + 1); right++;
}
cout << ret << endl;
return 0;
}java算法代码：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in); char[] s = in.next().toCharArray();
int left = 0, right = 0, n = s.length; int count = 0; // 统计窗⼝内有多少种字符
int[] hash = new int[26]; // 统计窗⼝内每种字符出现的次数 int ret = 0;
while(right < n)
{
if(hash[s[right] - 'a']++ == 0) // 0->1，窗⼝内多了⼀种字符 {
count++;
}
while(count > 2)
{
if(hash[s[left++] - 'a']-- == 1) // 1->0，窗⼝内少了⼀种字符 {
count--;
}
}
ret = Math.max(ret, right - left + 1); right++;
}
System.out.println(ret);
}
}