年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容）
QQ交流群：606939954
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：彩砖拼色
实例2：等差数列
实例3：01串
实例4：逆序n次
实例5：机器人走位
实例6：纸牌博弈
实例1：彩砖拼色
小易有一些彩色的砖块。每种颜色由一个大写字母表示。各个颜色砖块看起来都完全一样。
现在有一个给定的字符串s,s中每个字符代表小易的某个砖块的颜色。
小易想把他所有的砖块排成一行。
如果最多存在一对不同颜色的相邻砖块,那么这行砖块就很漂亮的。
请你帮助小易计算有多少种方式将他所有砖块排成漂亮的一行。(如果两种方式所对应的砖块颜色序列是相同的,那么认为这两种方式是一样的。)
例如: s= "ABAB",那么小易有六种排列的结果:'AABB", "ABAB", "ABBA", "ВAAВ", " ВАВА ", " ВВАА"其中只有"AABB"和"BBAA"满足最多只有一对不同颜色的相邻砖块。
信息提取：
1、最多存在一对不同颜色的相邻砖块
颜色超过2中不满足
2、相邻砖块成对
N 个砖块，有 N-1对
3、筛选条件
1、颜色只有一种，返回1
2、颜色只有两种，返回2
3、颜色超过2，返回0
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Code_15_ColorBrik {
public static int getColorBrik(String str) {
if (str == null || str.length() == 0) {
return 0;
}
Set<Character> set = new HashSet<>();
int res = 0;
for (char c : str.toCharArray()) {
if (!set.contains(c)){
set.add(c);
res++;
}
}
return res > 2 ? 0 : res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
System.out.println(getColorBrik(str));
in.close();
}
}
实例2：等差数列
如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] +d,这里的d也可以是负数和零,我们就称数列S为等差数列。
小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。
小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。
但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列
输入描述:
输入包括两行,
第一行包含整数n(2 <n < 50),即数列的长度。
第二行n个元素x[i] (0 <x[i] < 1000),即数列中的每个整数。
思路：
利用等差数列求和公式
遍历一遍数组求出几个数据
sum 、n
同时找到最小值和次小值，算出 d
代入公式查看是否满足等差数列的求和公式
import java.util.Scanner;
/**
* @description: 等差数列
*/
public class Code_16_ArithmeticSequence {
public static boolean isArithmeticSequence(int[] arr) {
if (arr == null || arr.length == 0) {
return false;
}
int sum = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
min = Math.min(min, arr[i]);
}
int n = arr.length;
if ((2 * (sum - min * n)) % (n * (n - 1)) == 0) { // d 可以为0 或是整数，%后为0
return true;
} else {
return false;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
if (isArithmeticSequence(arr))
System.out.println("Possible");
else
System.out.println("Impossible");
in.close();
}
}
实例3：01串
如果一个01串任意两个相邻位置的字符都是不一样的,我们就叫这个01串为交错01串。
例如: "1","10101","0101010"都是交错01串。
小易现在有一个01串s,小易想找出一个最长的连续子串,并且这个子串是一个交错01串。小易需要你帮帮忙求出最长的这样的子串的长度是多少。
输入描述:
输入包括字符串s,
s的长度length(1 < length < 50),字符串中只包含'0'和'1
题目三扩展小易想找出一个最长的连续子串,并且这个子串是0和1数量相等的。该怎么做?
思路：
维护两个变量，max:记录最大长度， len: 记录当前01串长度
比较 i 位置和 i-1位置，相同 len=0，不同len++
public static int max01Str(String str) {
if (str == null || str.length() == 0) return 0;
int max = 1;
int len = 1;
for (int i = 0; i < str.length(); i++) {
len++;
if (str.charAt(i) == str.charAt(i-1)){
len = 1;
}
max = Math.max(max, len);
}
return max;
}
扩展思路：
再次之前先回忆一下另外一道题
给定数组arr[] ,求子数组累加满足给定值k的最长子数组长度。
https://www.jianshu.com/p/431e9f9f7b74
此题，以某个位置为结尾的子数组，累加和为定值 k
public static int maxSubArrLen(int[] arr, int k) {
if (arr == null || arr.length == 0) return 0;
int len = 0;
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // 处理第一位等于 k 的情况
/*
6 1 2 3 k = 6
上来 sum = 6
sum - k = 0;
len = i - map.get(0) 但是现在不存在map.get(0) 这样len返回的结果是0，而不是 1
*/
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - k)) {
len = Math.max(len, i - map.get(sum - k));
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return len;
}
现在再看扩展，将题目中的0全部置为 -1 ，那么原问题就变成了求 满足子数组累加和为0 的最长子数组。
public static int max01Str2(String str) {
if (str == null || str.length() == 0) return 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
int len = 0;
int k = 0; // 求满足子数组累加等于0 的子数组长度
for (int i = 0; i < str.length(); i++) {
int cNum = (int) str.charAt(i) - '0';
sum += cNum;
if (map.containsKey(sum - k)){
len = Math.max(len, i - map.get(sum - k));
}
if (!map.containsKey(sum - k)){ // 不存在就添加
map.put(sum, i);
}
}
return len;
}
实例4：逆序n次
小易有一个长度为n的整数序列, a_1. .., an。然后考虑在一个空序列b上进行n次以下操作:1、将ai放入b序列的末尾2、逆置b序列小易需要你计算输出操作n次之后的b序列。
输入描述:输入包括两行,第一行包括一个整数n(2 第二行包括n个整数ai(1 < a_i < 10~9),即序列a中的每个整数,以空格分割
思路：双端队列
维护一个双端队列
每次添加都是先添加右边在添加左边
查看最后一次是添加在右边还是添加在左边，右边，逆序，左边，不逆序
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
public class Code_18_NReverse {
public static int[] reverse(int[] arr) {
Deque<Integer> deque = new LinkedList<>();// 双端队列
boolean convert = false; // 标记是否需要逆序
for (int i = 0; i < arr.length; i++) {
if (convert) {
deque.addLast(arr[i]);
} else { // 不需要转换就加入双端队列的尾部
deque.addFirst(arr[i]);
}
convert = !convert;
}
// 查看结果是否需要逆序
int i = 0;
if (convert) {
while (!deque.isEmpty())
arr[i++] = deque.pollFirst();
} else {
while (!deque.isEmpty()) {
arr[i++] = deque.pollLast();
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6};
reverse(arr);
System.out.println(Arrays.toString(arr));
}
}
实例5：机器人走位
一排有N个位置,一个机器人在最开始停留在P位置上,如果 p==0位置,下一分钟机器人一定向右移动到1位置;如果p==N-1,下一分钟机器人一定向左移动到N-2位置。如果P在0和N-1之间,下一分钟机器人一定会向左或者向右移动。求K分钟的时候,机器人到达位置有多少种走法。函数为: int f(int N, int P, int K, int T),返回值为走法的数量
public class Code_19_MachineRoad {
// 暴力尝试
public static int f1(int N, int P, int K, int T) {
if (N < 2 || P < 0 || K < 1 || T < 0 || P >= N || T >= N) {
return 0; // 越界处理
}
if (K == 1) { // 一分钟，一种或没有
return T == P ? 1 : 0;
}
// 两端位置
if (T == 0) {
return f1(N, P, K - 1, 1);
}
if (T == N - 1) {
return f1(N, P, K - 1, T - 1);
}
// 普遍位置
return f1(N, P, K - 1, T - 1) + f1(N, P, K - 1, T + 1);
}
// 动态规划 一维表
public static int f2(int N, int P, int K, int T) {
if (N < 2 || P < 0 || K < 1 || T < 0 || P >= N || T >= N) {
return 0;
}
int[][] dp = new int[K][N];
dp[0][P] = 1;
for (int i = 1; i < K; i++) {
dp[i][0] = dp[i - 1][1];
dp[i][N - 1] = dp[i - 1][N - 2];
for (int j = 1; j < N - 1; j++) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
}
}
return dp[K - 1][T];
}
// 动态规划 二维表
public static int f3(int N, int P, int K, int T) {
if (N < 2 || P < 0 || K < 1 || T < 0 || P >= N || T >= N) {
return 0;
}
int[] dp = new int[N];
dp[P] = 1;
int pre = 0;
int tmp = 0;
for (int i = 1; i < K; i++) {
pre = dp[0];
dp[0] = dp[1];
for (int j = 1; j < N - 1; j++) {
tmp = dp[j];
dp[j] = pre + dp[j + 1];
pre = tmp;
}
dp[N - 1] = pre;
}
return dp[T];
}
public static void main(String[] args) {
for (int i = 0; i < 300; i++) {
int N = (int) (Math.random() * 5) + 5;
int P = (int) (Math.random() * N);
int K = (int) (Math.random() * 10) + 2;
int T = (int) (Math.random() * N);
int res1 = f1(N, P, K, T);
int res2 = f2(N, P, K, T);
int res3 = f3(N, P, K, T);
if (res1 != res2 || res1 != res3) {
System.out.println("Fuck man!");
break;
}
}
}
}
实例6：纸牌博弈
排成一条线的纸牌博弈问题【题目】给定一个整型数组arr,代表数值不同的纸牌排成一条线。玩家 A和玩家B依次拿走每张纸牌,规定玩家A先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌,玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。【举例】arr=[1, 2, 100, 4]。开始时玩家A只能拿走1或4。如果玩家A拿走1,则排列变为 2, 100, 4],接下来玩家B可以拿走2或4,然后继续轮到玩家A。
public class Code_20_SelectedCards {
// 暴力尝试
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
}
public static int f(int[] arr, int i, int j) {
if (i == j) {
return arr[i];
}
return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}
public static int s(int[] arr, int i, int j) {
if (i == j) {
return 0;
}
return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
}
// 单独调用自己的暴力尝试
public static int process(int[] arr, int i, int j) {
if (i == j) {
return arr[i];
}
if (i == j - 1) {
return Math.max(arr[i], arr[j]);
}
return Math.max(arr[i] + Math.min(process(arr, i + 2, j), process(arr, i + 1, j - 1)),
arr[j] + Math.min(process(arr, i + 1, j - 1), process(arr, i, j - 2))
);
}
// 动态规划
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for (int j = 0; j < arr.length; j++) {
f[j][j] = arr[j];
for (int i = j - 1; i >= 0; i--) {
f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
}
}
return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
}
public static void main(String[] args) {
int[] arr = { 1, 9, 1 };
System.out.println(win1(arr));
System.out.println(win2(arr));
}
}
