@TOC
Offer-03 数组中反复的数字
问题形容：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。
public int findRepeatNumber(int[] nums) {if (nums == null || nums.length < 1) {return -1;}
int len = nums.length;
for (int i = 0; i < len; i++) {int index = nums[i] % len;// 通过取余, 获取数字原来的数, 但仅作为索引应用, 并扭转以后遍历点 i 的值
if (nums[index] >= len) {// 是 index 不是 i, 要判断 index 是否反复
return nums[i] % len;
}
nums[index] += len;// 加 length 不便, 将数还原
}
return -1;
}Offer-66 构建乘积数组
问题形容：给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]，不能应用除法，具体可参考 Offer-66 题。
public int[] constructArr(int[] a) {int[] b = new int[a.length];
b[0] = 1;
for (int i = 1; i < a.length; i++) {b[i] = b[i - 1] * a[i - 1];
}
int tmp = 1;
for (int i = a.length - 2; i >= 0; i--) {tmp = tmp * a[i+1];
b[i] = tmp * b[i];
}
return b;
}Offer-45 把数组排成最小的数
问题形容：输出一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。如果输出: [10,2]，输入: “102”，具体可参考 Offer-45 题。对于排序的规定了解，能够亲自按插入排序试一下。
public String minNumber(Integer[] nums) {if (nums == null || nums.length < 1) {return "";}
Arrays.sort(nums, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {String x = o1.toString() + o2.toString();
String y = o2.toString() + o1.toString();
return x.compareTo(y);
}
});
StringBuilder sb = new StringBuilder();
for (Integer num : nums) {sb.append(num);
}
return sb.toString();}Offer-49 判断丑数
问题形容 ：咱们把只蕴含质因子 2、3 和 5 的数称作丑数（Ugly Number），求按从小到大的程序的第 n 个丑数。 蛮力法 ：依据丑数定义，若一个数能被 2 整除，则间断除以 2；若还能被 3 整除，则间断除以 3；若还能被 5 整除，则间断除以 5；如果最初后果是 1 则是丑数，否则不是； 动静布局：新丑数，是后面曾经生成的丑数的 2 倍或 3 倍或 5 倍。具体详见 Offer-49 题。
Offer-29 顺时针打印矩阵
问题形容：输出一个矩阵，依照从内向里以顺时针的程序顺次打印出每一个数字。输出：matrix = [[1,2,3],[4,5,6],[7,8,9]]，输入：[1,2,3,6,9,8,7,4,5]。
public int[] spiralOrder2(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return new int[0];
}
int cols = matrix[0].length;
int rows = matrix.length;
int[] order = new int[cols * rows];
int top = 0, bottom = rows - 1, left = 0, right = cols - 1;
int index = 0;
while (index < order.length) {for (int column = left; column <= right; column++) {order[index++] = matrix[top][column];
}
if (index == order.length) {break;}
for (int row = top + 1; row <= bottom; row++) {order[index++] = matrix[row][right];
}
if (index == order.length) {break;}
for (int column = right - 1; column > left; column--) {order[index++] = matrix[bottom][column];
}
if (index == order.length) {break;}
for (int row = bottom; row > top; row--) {order[index++] = matrix[row][left];
}
top++; bottom--; left++; right--;
}
return order;
}offer-61 扑克牌中的顺子
从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是间断的。2～10 为数字自身，A 为 1，J 为 11，Q 为 12，K 为 13，而大、小王为 0，能够看成任意数字。A 不能视为 14。输出: [1,2,3,4,5]，输入: True；输出: [0,0,1,2,5]，输入: True；
public boolean isStraight(int[] nums) {Set<Integer> set = new HashSet<>();
int min = 15, max = -1;
for (int num : nums) {if (set.contains(num)) {return false;}
if (num == 0) {continue;}
set.add(num);
min = Math.min(min, num);
max = Math.max(max, num);
}
return (max - min) < 5;
}Offer-57 和为 s 的两个数字
问题形容：输出一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输入任意一对即可。
public int[] twoSum(int[] nums, int target) {if (nums == null || nums.length < 3) {return nums;}
int i = 0, j = nums.length - 1;
while (i < j) {int s = nums[i] + nums[j];
if (s == target) {return new int[]{nums[i], nums[j]};
}
if (s < target) {
i++;
continue;
}
j--;
}
return new int[0];
}Offer-57-II 和为 s 的间断负数序列
输出一个正整数 target，输入所有和为 target 的间断正整数序列（至多含有两个数）。序列内的数字由小到大排列，不同序列依照首个数字从小到大排列。输出：target = 9，输入：[[2,3,4],[4,5]]
public int[][] findContinuousSequence(int target) {
int i = 1; // 滑动窗口的左边界
int j = 1; // 滑动窗口的右边界
int sum = 0; // 滑动窗口中数字的和
List<int[]> list = new ArrayList<>();
while (i <= target / 2) {if (sum < target) {
sum += j;
j++;
continue;
}
if (sum > target) {
sum -=i;
i++;
continue;
}
int[] arr = new int[j-i]; // 记录后果
for (int k = i; k < j; k++) {arr[k-i] = k;
}
list.add(arr);
sum -= i;// 左边界向右挪动
i++;
}
return list.toArray(new int[list.size()][]);
}Offer-59-1 滑动窗口的最大值
问题形容：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
public Integer[] maxSlidingWindow(Integer[] nums, int k) {if (nums == null || nums.length < 1) {return new Integer[0];
}
Integer[] result = new Integer[nums.length - k + 1];
Deque<Integer> queue = new LinkedList<>();
for (int i = 0; i < k; i++) {while (!queue.isEmpty() && queue.peekLast() < nums[i]) { // 查找插入地位
queue.removeLast();}
queue.offer(nums[i]);
}
Integer index = 0;
result[index++] = queue.peekFirst();
for (int j = k; j < nums.length; j++) {if (nums[j - k] == queue.peekFirst()) {queue.removeFirst();
}
while (!queue.isEmpty() && queue.peekLast() < nums[j]) { // 查找插入地位
queue.removeLast();}
queue.offer(nums[j]);
result[index++] = queue.peekFirst();}
return result;
}Offer-44 数字序列中某一位的数字
数字以 0123456789101112131415…的格局序列化到一个字符序列中。在这个序列中，第 5 位（从下标 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。请写一个函数，求任意第 n 位对应的数字。
public int findNthDigit(int n) {
int digit = 1;
long start = 1, count = 9;
while (n > count) { // 求所在的数字的位数
n -= count;
digit++;
start *= 10;
count = 9 * start * digit;
}
long num = start + (n-1)/digit; // 求坐在数字
return Long.toString(num).charAt(((n - 1) % digit)) -'0';
}Offer-39 数组中呈现次数超过一半的数字
数组中有一个数字呈现的次数超过数组长度的一半，请找出这个数字。你能够假如数组是非空的，并且给定的数组总是存在少数元素。
public int majorityElement(int[] nums) {if (nums == null || nums.length < 1) {return -1;}
int vote = 0, x = -1;
for (int num : nums) {if (vote == 0) {x = num;}
vote += num == x ? 1 : -1;
}
return x;
}面试题 -01-08 零矩阵
问题形容：编写一种算法，若 M × N 矩阵中某个元素为 0，则将其所在的行与列清零，具体详见 金典 01-08 题。
public void setZeroes(int[][] matrix) {if (matrix == null || matrix.length < 1) {return;}
boolean[] rows = new boolean[matrix.length];
boolean[] cols = new boolean[matrix[0].length];
for (int i = 0; i < rows.length; i++) {for (int j = 0; j < cols.length; j++) {if (matrix[i][j] == 0) {rows[i] = true;
cols[j] = true;
}
}
}
for (int i = 0; i < rows.length; i++) {for (int j = 0; j < cols.length; j++) {if (rows[i] || cols[j]) {matrix[i][j] = 0;
}
}
}
}面试题 -01-07 旋转矩阵
问题形容：给你一幅由 N × N 矩阵示意的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。不占用额定内存空间是否做到。
本文由 mdnice 多平台公布