【直通BAT】剑指Offer-经典试题整理(5)
45 把数组排成最小的数
题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组 [3, 32, 321]，则打印出这3个数字能排成的最小数字321323。
解法
import java.util.Arrays;
class Solution {
/**
* 打印数组元素组成的最小的数字
*
* @param nums 数组
* @return 最小的数字
*/
public String printMinNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return "";
}
int n = nums.length;
String[] strNums = new String[n];
for (int i = 0; i < n; ++i) {
strNums[i] = String.valueOf(nums[i]);
}
Arrays.sort(strNums, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
StringBuilder sb = new StringBuilder();
for (String str : strNums) {
sb.append(str);
}
return sb.toString();
}
}
46 把数字翻译成字符串
来源：AcWing
题目描述
给定一个数字，我们按照如下规则把它翻译为字符串：
0 翻译成 ”a”，1 翻译成 ”b”，……，11 翻译成 ”l”，……，25 翻译成 ”z”。
一个数字可能有多个翻译。例如 12258 有 5 种不同的翻译，它们分别是 ”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
解法
先写入递推式，res 表示共有多少种翻译方法。看最后一个字符，判断它与前一个字符能否构成有效翻译，计算 res[i]：
-
能，那么 res[i] = res[i - 1] + res[i - 2]；
-
不能，那么 res[i] = res[i - 1]。
class Solution {
/**
* 获取翻译字符串的方法个数
*
* @param s 字符串
* @return 个数
*/
public int getTranslationCount(String s) {
if (s == null || s.length() < 2) {
return 1;
}
char[] chars = s.toCharArray();
int n = chars.length;
int[] res = new int[n];
res[0] = 1;
res[1] = isInRange(chars[0], chars[1]) ? 2 : 1;
for (int i = 2; i < n; ++i) {
res[i] = res[i - 1] + (isInRange(chars[i - 1], chars[i]) ? res[i - 2] : 0);
}
return res[n - 1];
}
private boolean isInRange(char a, char b) {
int s = (a - '0') * 10 + (b -'0');
return s >= 10 && s <= 25;
}
}
47 礼物的最大价值
来源：AcWing
题目描述
在一个 m×n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？
解法
写出递推式，res 表示获得的最大礼物。
res[i][j] = Math.max(res[i - 1][j], res[i][j - 1]) + grid[i][j];
class Solution {
/**
* 获取礼物的最大价值
*
* @param grid 数组
* @return 最大价值
*/
public int getMaxValue(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int[][] res = new int[m][n];
res[0][0] = grid[0][0];
for (int j = 1; j < n; ++j) {
res[0][j] = res[0][j - 1] + grid[0][j];
}
for (int i = 1; i < m; ++i) {
res[i][0] = res[i - 1][0] + grid[i][0];
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
res[i][j] = Math.max(res[i - 1][j], res[i][j - 1]) + grid[i][j];
}
}
return res[m - 1][n - 1];
}
}
48 长不含重复字符的子字符串
来源：AcWing
题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
假设字符串中只包含从 a 到 z的字符。
解法
动态规划。
res[i] 表示以 s[i] 字符结尾的最长不重复字符串的长度。判断 s[i]：
-
若 s[i] 在前面没出现过，那么 res[i] = res[i - 1] + 1；
-
若 s[i] 在前面有出现过，判断它上一次出现的位置 index 到 i 的距离 d 与 res[i - 1] 的大小关系：
-
若 d <= res[i - 1]，说明它被包含在 res[i - 1] 构成的子串中，那么 res[i] = d；
-
若 d > res[i - 1]，说明它在 res[i - 1] 构成的子串的左侧，那么 res[i] = res[i - 1] + 1。
需要用一个数组 t 记录一下当前出现的字符在哪个位置。
class Solution {
/**
* 最长不含重复字符的子字符串
*
* @param s 字符串
* @return 最长不重复字符子串
*/
public int longestSubstringWithoutDuplication(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] chars = s.toCharArray();
int[] t = new int[26];
for (int i = 0; i < 26; ++i) {
t[i] = -1;
}
t[chars[0] - 'a'] = 0;
int n = chars.length;
int[] res = new int[n];
res[0] = 1;
int max = res[0];
for (int i = 1; i < n; ++i) {
int index = t[chars[i] - 'a'];
int d = i - index;
res[i] = (index == -1 || d > res[i - 1])
? res[i - 1] + 1
: d;
t[chars[i] - 'a'] = i;
max = Math.max(max, res[i]);
}
return max;
}
}
52 两个链表的第一个公共结点
来源：AcWing
题目描述
输入两个链表，找出它们的第一个公共结点。
样例
给出两个链表如下所示：
A： a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
解法
先遍历两链表，求出两链表的长度，再求长度差 |n1 - n2|。
较长的链表先走 |n1 - n2| 步，之后两链表再同时走，首次相遇时的节点即为两链表的第一个公共节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
/**
* 求两链表第一个公共节点
*
* @param headA 链表A
* @param headB 链表B
* @return 第一个公共节点
*/
public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
int n1 = len(headA), n2 = len(headB);
ListNode p1 = headA, p2 = headB;
if (n1 > n2) {
for (int i = 0; i < n1 - n2; ++i) {
p1 = p1.next;
}
} else if (n1 < n2) {
for (int i = 0; i < n2 - n1; ++i) {
p2 = p2.next;
}
}
while (p1 != p2 && p1 != null && p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
return (p1 == null || p2 == null) ? null : p1;
}
private int len(ListNode head) {
int n = 0;
ListNode cur = head;
while (cur != null) {
++n;
cur = cur.next;
}
return n;
}
}
53.1 数字在排序数组中出现的次数
来源：AcWing
题目描述
统计一个数字在排序数组中出现的次数。
例如输入排序数组 [1, 2, 3, 3, 3, 3, 4, 5] 和数字 3，由于 3 在这个数组中出现了 4 次，因此输出 4。
样例
输入：[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出：4
解法
找出第一个 k 和最后一个 k 出现的位置。
找第一个 k 时，利用二分法，如果 nums[m] == k，判断它的前一个位置是不是也是 k，如果不是，说明这是第一个 k，直接返回。如果是，那么递归在左边查找第一个 k。
找最后一个 k 也同理。
class Solution {
/**
* 求数字k在排序数组中出现的次数
*
* @param nums 数组
* @param k 数字k
* @return k在数组中出现的次数
*/
public int getNumberOfK(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int start = 0, end = nums.length - 1;
int first = getFirstK(nums, start, end, k);
int last = getLastK(nums, start, end, k);
if (first > -1 && last > -1) {
return last - first + 1;
}
return 0;
}
private int getFirstK(int[] nums, int start, int end, int k) {
if (start > end) {
return -1;
}
int m = start + ((end - start) >> 1);
if (nums[m] == k) {
if (m == 0 || (m > 0 && nums[m - 1] != k)) {
return m;
} else {
end = m - 1;
}
} else {
if (nums[m] > k) {
end = m - 1;
} else {
start = m + 1;
}
}
return getFirstK(nums, start, end, k);
}
private int getLastK(int[] nums, int start, int end, int k) {
if (start > end) {
return -1;
}
int m = start + ((end - start) >> 1);
if (nums[m] == k) {
if (m == nums.length - 1 || (m < nums.length - 1 && nums[m + 1] != k)) {
return m;
} else {
start = m + 1;
}
} else {
if (nums[m] > k) {
end = m - 1;
} else {
start = m + 1;
}
}
return getLastK(nums, start, end, k);
}
}
53.2 0到n-1中缺失的数字
来源：AcWing
题目描述
一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n-1 之内。
在范围 0 到 n-1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
样例
输入：[0,1,2,4]
输出：3
解法
找出第一个与下标不对应的数字即可。
特殊情况：
下标都对应，那么应该返回 最后一个数+1；
缺失的数字是第一个，那么返回 0。
class Solution {
/**
* 获取0~n-1缺失的数字
*
* @param nums 数组
* @return 缺失的数字
*/
public int getMissingNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int start = 0, end = n - 1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (nums[mid] != mid) {
if (mid == 0 || nums[mid - 1] == mid - 1) {
return mid;
}
end = mid - 1;
} else {
start = mid + 1;
}
}
return start == n ? n : -1;
}
}
53.3 数组中数值和下标相等的元素
来源：AcWing
题目描述
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
例如，在数组 [-3, -1, 1, 3, 5] 中，数字 3 和它的下标相等。
样例
输入：[-3, -1, 1, 3, 5]
输出：3
注意:如果不存在，则返回 -1。
解法
二分法查找。
-
当前元素等于对应的下标，直接返回该下标；
-
当前元素大于该下标，在左边查找；
-
当前元素小于该下标，在右边查找。
class Solution {
/**
* 找出单调递增数组中数值和下标相等的元素
*
* @param nums 数组
* @return 数值与下标相等的元素
*/
public int getNumberSameAsIndex(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (nums[mid] == mid) {
return mid;
}
if (nums[mid] < mid) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
}
55.1 二叉树的深度
来源：AcWing
题目描述
输入一棵二叉树的根结点，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
样例
输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
8
/
12 2
/
6 4
输出：3
解法
递归即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 求二叉树的深度
*
* @param root 二叉树根结点
* @return 深度
*/
public int treeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int lDepth = treeDepth(root.left);
int rDepth = treeDepth(root.right);
return 1 + Math.max(lDepth, rDepth);
}
}
测试用例
功能测试（输入普通的二叉树；二叉树中所有节点都没有左/右子树）；
特殊输入测试（二叉树只有一个节点；二叉树的头节点为空指针）。
55.2 平衡二叉树
来源：AcWing
题目描述
输入一棵二叉树的根结点，判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
注意：
规定空树也是一棵平衡二叉树。
样例
输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
5
/
7 11
/
12 9
输出：true
解法
解法一
求每个节点左右孩子的深度，判断该节点是否平衡。
这种方法需要重复遍历节点多次，不推荐。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 判断是否是平衡二叉树
*
* @param root 二叉树根结点
* @return 是否是平衡二叉树
*/
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
if (Math.abs(treeDepth(root.left) - treeDepth(root.right)) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int treeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int lDepth = treeDepth(root.left);
int rDepth = treeDepth(root.right);
return 1 + Math.max(lDepth, rDepth);
}
}
解法二
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private boolean isBalanced;
/**
* 判断是否是平衡二叉树
*
* @param root 二叉树根结点
* @return 是否是平衡二叉树
*/
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
isBalanced = true;
treeDepth(root);
return isBalanced;
}
private int treeDepth(TreeNode root) {
if (root == null || !isBalanced) {
return 0;
}
int lDepth = treeDepth(root.left);
int rDepth = treeDepth(root.right);
if (Math.abs(lDepth - rDepth) > 1) {
isBalanced = false;
}
return 1 + Math.max(lDepth, rDepth);
}
}
56.1 数组中只出现一次的两个数字
来源：AcWing
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
样例
输入：[1,2,3,3,4,4]
输出：[1,2]
解法
如果数组有一个数字出现一次，其它数字都出现两次。那么我们很容易通过异或 ^ 运算求出来。
而现在是有两个数字出现一次，那么我们考虑一下怎么将这两个数字隔开，之后我们对隔开的数组分别进行异或，不就求出来了？
我们先异或，求得的结果是两个不相同的数字异或的结果，结果一定不为 0。那么它的二进制表示中一定有 1。我们根据这个 1 在二进制中出现的位置。将数组划分，这样，两个只出现一次的数字就会被隔开，之后求异或即可。
class Solution {
/**
* 求数组中只出现一次的两个数字
*
* @param nums 数字
* @return 两个数字组成的数组
*/
public int[] findNumsAppearOnce(int[] nums) {
if (nums == null || nums.length < 2) {
return null;
}
int xorRes = 0;
for (int e : nums) {
xorRes ^= e;
}
int[] res = new int[2];
int index = indexOf1(xorRes);
for (int e : nums) {
if (isBit1(e, index)) {
res[0] ^= e;
} else {
res[1] ^= e;
}
}
return res;
}
private int indexOf1(int val) {
int index = 0;
while ((val & 1) == 0) {
val = val >> 1;
++index;
}
return index;
}
private boolean isBit1(int val, int index) {
for (int i = 0; i < index; ++i) {
val = val >> 1;
}
return (val & 1) == 1;
}
}
56.2 数组中唯一只出现一次的数字
来源：AcWing
题目描述
在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。
请找出那个只出现一次的数字。
你可以假设满足条件的数字一定存在。
思考题：
如果要求只使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
解法
分别累加数组中每个元素的二进制中出现的数字，那么出现三次的数字，二进制位上最后累加的结果一定能被 3 整除。不能被 3 整除的位，就属于只出现一次的数字。
class Solution {
/**
* 找出数组中只出现一次的数字，其它数字都出现三次
*
* @param nums 数字
* @return 只出现一次的数字
*/
public int findNumberAppearingOnce(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] bits = new int[32];
int n = nums.length;
for (int i = 0; i < n; ++i) {
int val = nums[i];
for (int j = 0; j < 32; ++j) {
bits[j] += (val & 1);
val = val >> 1;
}
}
int res = 0;
for (int i = 0; i < 32; ++i) {
if (bits[i] % 3 != 0) {
res += Math.pow(2, i);
}
}
return res;
}
}
57.1 和为S的两个数字
来源：AcWing
题目描述
输入一个数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。
如果有多对数字的和等于s，输出任意一对即可。
你可以认为每组输入中都至少含有一组满足条件的输出。
样例
输入：[1,2,3,4] , sum=7
输出：[3,4]
解法
利用 set 记录元素即可。
import java.util.HashSet;
import java.util.Set;
class Solution {
/**
* 在数组中找出和为target的两个数
*
* @param nums 数组
* @param target 目标和
* @return 满足条件的两个数构成的数组
*/
public int[] findNumbersWithSum(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return null;
}
int n = nums.length;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; ++i) {
if (set.contains(target - nums[i])) {
return new int[] {target- nums[i], nums[i]};
}
set.add(nums[i]);
}
return null;
}
}
57.2 和为S的连续正数序列
来源：AcWing
题目描述
输入一个正数 s，打印出所有和为 s 的连续正数序列（至少含有两个数）。
例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以结果打印出 3 个连续序列 1～5、4～6 和 7～8。
样例
输入：15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
解法
用两个指针 p, q 指示序列的最小值和最大值。如果序列和大于 s，则从序列中去掉较小的值，即 ++p；如果序列和小于 s，则序列向右再包含一个数字，即 ++q。
当 p 超过 s 的一半时，停止。
import java.util.*;
class Solution {
/**
* 找出和为sum的连续正整数序列
*
* @param sum 和
* @return 结果列表
*/
public List<List<Integer>> findContinuousSequence(int sum) {
List<List<Integer>> res = new ArrayList<>();
if (sum < 3) {
return res;
}
int p = 1, q = 2;
int mid = (1 + sum) >> 1;
int curSum = p + q;
while (p < mid) {
if (curSum == sum) {
res.add(getList(p, q));
}
while (curSum > sum && p < mid) {
curSum -= p;
++p;
if (curSum == sum) {
res.add(getList(p, q));
}
}
++q;
curSum += q;
}
return res;
}
private List<Integer> getList(int from, int to) {
List<Integer> res = new ArrayList<>();
for (int i = from; i <= to; ++i) {
res.add(i);
}
return res;
}
}
58.1 翻转单词顺序
来源：AcWing
题目描述
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
为简单起见，标点符号和普通字母一样处理。
例如输入字符串 "I am a student."，则输出 "student. a am I"。
样例
输入："I am a student."
输出："student. a am I"
解法
先对字符串按空格切割成数组，再逆序数组后，最后将元素拼接并返回。
class Solution {
/**
* 翻转单词
*
* @param s 字符串
* @return 翻转后的字符串
*/
public String reverseWords(String s) {
if (s == null || s.length() < 2) {
return s;
}
String[] arr = s.split(" ");
int p = 0, q = arr.length - 1;
while (p < q) {
swap(arr, p++, q--);
}
return String.join(" ", arr);
}
private void swap(String[] arr, int p, int q) {
String t = arr[p];
arr[p] = arr[q];
arr[q] = t;
}
}
58.2 左旋转字符串
来源：AcWing
题目描述
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
请定义一个函数实现字符串左旋转操作的功能。
比如输入字符串 "abcdefg" 和数字 2，该函数将返回左旋转 2 位得到的结果 "cdefgab"。
注意：
数据保证 n 小于等于输入字符串的长度。
样例
输入："abcdefg" , n=2
输出："cdefgab"
解法
先翻转前 n 个字符，再翻转后面的字符，最后整体翻转。
class Solution {
/**
* 左旋转字符串
*
* @param str 字符串
* @param n 左旋的位数
* @return 旋转后的字符串
*/
public String leftRotateString(String str, int n) {
if (str == null || n < 1 || n > str.length()) {
return str;
}
char[] chars = str.toCharArray();
int len = chars.length;
reverse(chars, 0, n - 1);
reverse(chars, n, len - 1);
reverse(chars, 0, len - 1);
return new String(chars);
}
private void reverse(char[] chars, int p, int q) {
while (p < q) {
swap(chars, p++, q--);
}
}
private void swap(char[] chars, int p, int q) {
char t = chars[p];
chars[p] = chars[q];
chars[q] = t;
}
}
59.1 滑动窗口的最大值
来源：AcWing
题目描述
给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
例如，如果输入数组 [2, 3, 4, 2, 6, 2, 5, 1] 及滑动窗口的大小 3,那么一共存在 6 个滑动窗口，它们的最大值分别为 [4, 4, 6, 6, 6, 5]。
注意：
数据保证 k 大于 0，且 k 小于等于数组长度。
样例
输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3
输出: [4, 4, 6, 6, 6, 5]
解法
利用双向队列，保证队列头部存放的是最大值的下标，当队列头部下标过期时弹出。
细节：
当数组元素小于队列头部下标对应的元素时，在队列尾部中插入数组元素下标。（如果队列尾部有比该元素小的元素，先弹出，再插入。）
当数组元素大于或等于队列头部下标构成的元素时，弹出元素直至队列为空，再插入数组元素下标。
import java.util.Deque;
import java.util.LinkedList;
class Solution {
/**
* 求滑动窗口的最大值
*
* @param nums 数组
* @param k 滑动窗口的大小
* @return 最大值构成的数组
*/
public int[] maxInWindows(int[] nums, int k) {
if (nums == null || k < 1 || k > nums.length) {
return null;
}
Deque<Integer> queue = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < k; ++i) {
if (queue.isEmpty()) {
queue.addLast(i);
} else {
if (nums[queue.getFirst()] < nums[i]) {
while (!queue.isEmpty()) {
queue.removeFirst();
}
} else {
while (nums[queue.getLast()] < nums[i]) {
queue.removeLast();
}
}
queue.addLast(i);
}
}
for (int i = k; i < nums.length; ++i) {
res[i - k] = nums[queue.getFirst()];
if (nums[i] < nums[queue.getFirst()]) {
while (nums[queue.getLast()] < nums[i]) {
queue.removeLast();
}
} else {
while (!queue.isEmpty()) {
queue.removeFirst();
}
}
queue.addLast(i);
if (i - queue.getFirst() == k) {
queue.removeFirst();
}
}
res[nums.length - k] = nums[queue.getFirst()];
return res;
}
}
61 扑克牌的顺子
来源：AcWing
题目描述
从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。
2～10 为数字本身，A 为1，J 为 11，Q 为 12，K 为 13，大小王可以看做任意数字。
为了方便，大小王均以 0 来表示，并且假设这副牌中大小王均有两张。
样例1
输入：[8,9,10,11,12]
输出：true
样例2
输入：[0,8,9,11,12]
输出：true
解法
对数组排序；
计算出 0 的个数 zeroCount；
从第一个不是 0 的数字开始遍历，与后一个数字比较，如果相等，直接返回 false；否则累计 gap；
判断 zeroCount 是否大于等于 gap。
import java.util.Arrays;
class Solution {
/**
* 判断是否是连续的数字
*
* @param numbers 数组
* @return 是否是顺子
*/
public boolean isContinuous(int [] numbers) {
if (numbers == null || numbers.length == 0) {
return false;
}
int zeroCount = 0;
Arrays.sort(numbers);
for (int e : numbers) {
if (e > 0) {
break;
}
++zeroCount;
}
int p = zeroCount, q = p + 1, n = numbers.length;
int gap = 0;
while (q < n) {
if (numbers[p] == numbers[q]) {
return false;
}
gap += (numbers[q] - numbers[p] - 1);
p = q;
++q;
}
return gap <= zeroCount;
}
}
62 圆圈中最后剩下的数字
来源：AcWing
题目描述
0, 1, …, n-1 这 n 个数字 (n>0) 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。
求出这个圆圈里剩下的最后一个数字。
样例
输入：n=5 , m=3
输出：3
解法
解法一
利用循环数组存放每个数字，每走一步，判断对应位置的数是否是 -1，-1 的话不计步数，这样一直走 m 步。将该位数字置为 -1。
当共有 n-1 个数被置为 -1 时，输出唯一的不为 -1 的那个数。
说明：
构建循环链表也可以，每走 m 步，把所在节点删掉。最后剩下一个节点时返回。
这种解法每删除一个数字需要 m 步计算，共有 n 个数字，因此总的时间复杂度为 O(mn)，空间复杂度为 O(n)。
class Solution {
/**
* 求圆圈最后一个数字
*
* @param n n个数 [0..n-1]
* @param m 每次删除第 m 个数
* @return 最后一个数字
*/
public int lastRemaining(int n, int m) {
int cnt = 0;
int s = -1;
int[] nums = new int[n];
for (int i = 1; i < n; ++i) {
nums[i] = i;
}
int e = -1;
while (cnt < n - 1) {
int i = 0;
while (i < m) {
e = (e + 1) % n;
if (nums[e] != -1) {
++i;
}
}
++cnt;
nums[e] = -1;
s = e;
}
for (int i = 0; i < n; ++i) {
if (nums[i] != -1) {
return nums[i];
}
}
return 0;
}
}
解法二
我们这样分析：
第一次被删除的圆圈的编号是 m-1。那么剩下的数字依次是：
0 1 2 3 ... m-2 m ... n-1
由于下一次（共有 n-1 个数）是从 m 开始，因此我们对 m 的编号改为 0，依次改：
old -> new
m -> 0
m+1 -> 1
m+2 -> 2
.
.
.
n-1 -> n-1-m
0 -> n-m
1 -> n-m+1
.
.
.
m-2 -> n-2
我们假设子问题 x' 是最终解，那么对应到原问题 x 应该是什么呢？
new -> old
0 -> m
1 -> m+1
2 -> m+2
.
.
.
n-1-m -> n-1
n-m -> 0
n-m+1 -> 1
.
.
.
n-2 -> m-2
x' -> x
x = (x' + m) % n
所以就有一个递推式：
f(i) = (f(i - 1) + m) % i;
算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
class Solution {
/**
* 求圆圈最后一个数字
*
* @param n n个数 [0..n-1]
* @param m 每次删除第 m 个数
* @return 最后一个数字
*/
public int lastRemaining(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
int res = 0;
for (int i = 2; i <= n; ++i) {
res = (res + m) % i;
}
return res;
}
}
63 股票的最大利润
来源：AcWing
题目描述
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖交易该股票可能获得的利润是多少？
例如一只股票在某些时间节点的价格为 [9, 11, 8, 5, 7, 12, 16, 14]。
如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11。
样例
输入：[9, 11, 8, 5, 7, 12, 16, 14]
输出：11
解法
遍历到 nums[i] 时，求 nums[i] 与前 i 个数的最小值 min 的差值，最后求出最大的差值即可。
class Solution {
/**
* 股票的最大利润
*
* @param nums 数组
* @return 最大利润
*/
public int maxDiff(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int min = nums[0];
int maxGap = nums[1] - nums[0];
for (int i = 2, n = nums.length; i < n; ++i) {
min = Math.min(min, nums[i - 1]);
maxGap = Math.max(maxGap, nums[i] - min);
}
return maxGap > 0 ? maxGap : 0;
}
}
64 求1+2+…+n
来源：AcWing
题目描述
求 1+2+…+n,要求不能使用 乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 A?B:C。
样例
输入：10
输出：55
解法
利用 Stream API。
import java.util.stream.IntStream;
class Solution {
/**
* 求1+2+…+n（不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C））
*
* @param n 1~n
* @return 1~n的和
*/
public int getSum(int n) {
return IntStream.rangeClosed(1, n).sum();
}
}
65 不用加减乘除做加法
来源：AcWing
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷ 四则运算符号。
样例
输入：num1 = 1 , num2 = 2
输出：3
解法
先对两数进行异或，求得相加不仅位的结果。再循环对两数进行按位与运算，并左移一位，直至进位为 0。
class Solution {
/**
* 不用加减乘除做加法
*
* @param num1 数1
* @param num2 数2
* @return 两数之和
*/
public int add(int num1, int num2) {
int sum, carry;
while (true) {
sum = num1 ^ num2;
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
if (num2 == 0) {
break;
}
}
return num1;
}
}
66 构建乘积数组
来源：AcWing
题目描述
给定一个数组 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]。
不能使用除法。
样例
输入：[1, 2, 3, 4, 5]
输出：[120, 60, 40, 30, 24]
思考题：
能不能只使用常数空间？（除了输出的数组之外）
解法
把 B 的每个元素 B[i] 看成两半的乘积，即 A[0]xA[1]x...xA[i-1] 和 A[i+1]xA[i+2]xA[n-1]。
对于左半部分：B[i] = B[i - 1] * A[i - 1]
class Solution {
/**
* 构建乘积数组
*
* @param A 数组A
* @return 乘积数组B
*/
public int[] multiply(int[] A) {
if (A == null || A.length < 1) {
return A;
}
int n = A.length;
int[] B = new int[n];
B[0] = 1;
for (int i = 1; i < n; ++i) {
B[i] = B[i - 1] * A[i - 1];
}
int t = 1;
for (int i = n - 2; i >= 0; --i) {
t *= A[i + 1];
B[i] *= t;
}
return B;
}
}
扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有
扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）
推荐阅读
