JZ45 扑克牌顺子
（简单）
题目
描述
现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：
1）A为1，J为11，Q为12，K为13，A不能视为14
2）大、小王为 0，0可以看作任意牌
3）如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
例如：给出数据[6,0,2,0,4]
中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4]
这样这五张牌在[2,6]区间连续，输出true
数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]
示例1
输入：
[6,0,2,0,4]
返回值：true
示例2
输入：
[0,3,2,6,4]
返回值：true
示例3
输入：
[1,0,0,1,0]
返回值：false
示例4
输入：
[13,12,11,0,1]
返回值：false
思路
我做这道题时是没想到什么常规的解题方法，而是直接凭感觉写出来的，最后在考虑了所有可能的情况后，最后顺利通过了。
在通过这道题目后，我开始看题解看看有更好的方法没有，发现各位网友都有自己的方法，没有统一的标准方法，不少都是是代码量很少，但可读性差，当然也有很多不错的解法，而且也发现有一个人的代码和我的思维方式很像，总之，以下我将介绍一下我当时的思路和方法。
我打算将我的这种方法命名为：
消耗存储数法
我们拿到 5 张牌的数组后，若想检验是否为顺子，那么按正常的思维来说，我们就应该先让这组牌号序列往有序的方向先靠拢，也就是先进行排序，我这里使用的是冒泡排序（较少量数据的序列的排序，冒泡排序还是可以用一下的），之后大小王的数量，便对应着这个有序序列的前 m 个 0 ，其中 m 的范围是 4 >= m >= 0，因为题目中说了有两副牌，之后我们判断次序列是否为顺子，则可从第 m 个序列开始，因为前面都为大小王，可替代任意排，我们要优先考虑后面的，并通过已有的大小王，也就是 0 ，来弥补后续不能构成连续序列的情况，如果序列中两个数相差 2 ，则可消耗掉 1 个 0 来弥补，如果序列中两个数相等，则不能构成顺子，直接终止并返回 false 即可，因为总共数组中就 5 个数，如果序列中两个数相差数大于2，但此差 - 1 是小于等于 0 的当前剩余个数的，那么可以用 0 进行弥补，反之，则不能构成顺子，如果序列中两个数正好相差 1 ，那么本身两数已是连续数，可进行下一轮循环，如果最终循环结束，仍未退出函数，说明为此情况在循环中已经过充分检验，不满足任何一个不能构成顺子的条件，则返回 true 即可。
实现
public class JZ45扑克牌顺子 {
public static boolean IsContinuous(int[] numbers) {
bubbleSort(numbers);
int len = numbers.length;
int zeroNum = 0;
//求出大小王的个数，即 0 的个数
for (int i = 0; i < len; i++) {
if (numbers[i] == 0) {
zeroNum++;
}
}
//判断顺子，从第 1 个不是 0 的数开始判断 i 与 i+1 的差值
boolean result = false;
for (int i = zeroNum; i < len - 1; i++) {
if (numbers[i + 1] - numbers[i] == 2) {
//情况：两个数直接缺一个数导致不连续
if (zeroNum == 0) {
//不可以弥补这种情况
return false;
}
//消耗掉一个大小王来弥补这种情况的不连续，使之连续
zeroNum--;
} else if (numbers[i + 1] - numbers[i] == 1) {
//情况：正好连续
} else {
//情况：出现两个相邻数相等或大于2的情况
if (numbers[i + 1] == numbers[i]) {
//情况：出现两个相邻数相等
return false;
}
//情况：如果有两张及以上的0（因为题中说了是两副牌），可以弥补大于2的部分情况
//相差2，需要1张0 ----> 相差n，需要n-1张0
else if (zeroNum >= numbers[i + 1] - numbers[i] - 1) {
zeroNum -= (numbers[i + 1] - numbers[i] - 1);
} else {
//情况：大于2中不能弥补的情况
return false;
}
}
}
return true;
}
public static void bubbleSort(int[] numbers) {
int i = 0;
int j = 0;
int len = numbers.length - 1;
boolean flag = true;
for (i = 0; i < len && flag; i++) {
flag = false;
for (j = len - 1; j >= i; j--) {
if (numbers[j] > numbers[j + 1]) {
swap(numbers, j, j + 1);
flag = true;
}
}
}
}
public static void swap(int[] numbers, int x, int y) {
int m = numbers[x];
numbers[x] = numbers[y];
numbers[y] = m;
}
public static void main(String[] args) {
int[] arr1 = {6, 0, 2, 0, 4};
int[] arr2 = {0, 3, 2, 6, 4};
int[] arr3 = {1, 0, 0, 1, 0};
int[] arr4 = {13, 12, 11, 0, 1};
System.out.println("IsContinuous(arr1) = " + IsContinuous(arr1)); //T
System.out.println("IsContinuous(arr2) = " + IsContinuous(arr2)); //T
System.out.println("IsContinuous(arr3) = " + IsContinuous(arr3)); //F
System.out.println("IsContinuous(arr4) = " + IsContinuous(arr4)); //F
}
}
JZ51 构建乘积数组
（简单）
题目
描述
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
示例
输入：
[1,2,3,4,5]
返回值：
[120,60,40,30,24]
思路
方法一：暴力解法
根据题目中给的公式条件，直接无脑地暴力计算出数组B中的各元素值。
【实现】
public class JZ51构建乘积数组 {
public int[] multiply(int[] A) {
int n = A.length;
int[] B = new int[n];
Arrays.fill(B, 1);
for (int i = 1; i < n; i++) {
B[0] *= A[i];
}
for (int i = 0; i < n - 1; i++) {
B[n - 1] *= A[i];
}
for (int i = 1; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
if (j == i) {
continue;
}
B[i] *= A[j];
}
}
return B;
}
}
方法二：数学推导
因为 B[i] = A[0]A[1]…A[i-1]*A[i+1]…A[n-1] ，所以另：
- left[i] = A[0]*…*A[i-1]
- right[i] = A[i+1]*…*A[n-1]
所以：
- B[i] = left[i] * right[i]
又因为：
left[i+1] = A[0] *…A[i-1] * A[i]
right[i+1] = A{i+2] *…*A[n-1]
所以：
left[i+1] = left[i] * A[i] ——> left[i] = left[i-1] * A[i-1]
right[i] = right[i+1] * A[i+1]
【综上】：
left[i] = left[i-1] * A[i-1]————（计算下标为1 ~ n - 1）（说明：因为 B[n-1] = A[0] * A[1] * … * A[n-2] ，因此可直接计算出 B[n-1]）right[i] = right[i+1] * A[i+1]————（计算下标为n - 2 ~ 0）（说明：因为 B[0] = A[1] * A[2] * … * A[n-1] ，因此可直接计算出 B[0]）
此方法十分巧妙，我是参考的官方的题解才知道的这种方法，算是数学推导的一种，两个临界情况 B[0] 和 B[n - 1]，正好可以通过一右（right 公式）一左（left 公式）单独算出，而这中间的序号对应的数据则可先左乘积操作一遍，再右乘积操作一遍得出。
【实现】
public class JZ51构建乘积数组 {
public int[] multiply(int[] A) {
int n = A.length;
int[] B = new int[n];
Arrays.fill(B, 1);
for (int i = 1; i < n; i++) {
B[i] = B[i - 1] * A[i - 1]; // left[i]用B[i]代替
}
int tmp = 1;
for (int j = n - 2; j >= 0; j--) {
tmp *= A[j + 1]; // right[i]用tmp代替
B[j] *= tmp;
}
return B;
}
}
