面试题39：数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
- 解法一：多数投票算法
- 出现次数超过一半的数字则超过其他所有数字出现次数之和
- 保存两个变量，result和times，遍历数组
- 如果当前数字等于result，times加一
- 如果当前数字不等于result，且times不等于0，times减一
- 如果当前数字不等于result，且times等于0，置result为当前数字，times为1
public int majorityElement(int[] nums) {
checkArguments(nums);
int result = nums[0];
int times = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == result) {
times++;
} else {
if (times > 0) {
times--;
} else {
result = nums[i];
times = 1;
}
}
}
if (!checkMoreThanHalf(nums, result)) {
throw new RuntimeException("Invalid times");
}
return result;
}
private boolean checkMoreThanHalf(int[] nums, int number) {
int times = 0;
for (int num : nums) {
if (num == number) {
times++;
}
}
return (times << 1) > nums.length;
} - 解法二：
- 出现次数超过一半的数字在数组排序后一定位于middle位置
- 基于快排partition函数找到middle的数字
public int majorityElement(int[] nums) {
checkArguments(nums);
int start = 0;
int end = nums.length - 1;
int middle = nums.length >> 1;
int index = partition(nums, start, end);
while (index != middle) {
if (index < middle) {
start = index + 1;
} else {
end = index - 1;
}
index = partition(nums, start, end);
}
if (!checkMoreThanHalf(nums, nums[index])) {
throw new RuntimeException("Invalid times");
}
return nums[index];
}
private int partition(int[] array, int start, int end) {
int index = new Random().nextInt(end-start+1) + start;
int temp = array[index];
array[index] = array[end];
array[end] = temp;
int small = start - 1;
for (index = start; index < end; index++) {
if (array[index] < array[end]) {
small++;
if (small != index) {
temp = array[small];
array[small] = array[index];
array[index] = temp;
}
}
}
temp = array[++small];
array[small] = array[end];
array[end] = temp;
return small;
} 面试题40：最小的k个数
题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
- 解法一：最大堆
- result中数字少于k个，继续添加
- result中数字等于k个，建堆比较最大值
public int[] getLeastNumbers(int[] arr, int k) {
checkArguments(arr, k);
int[] result = new int[k];
if (k == 0) {
return result;
}
if (k == arr.length) {
return arr;
}
System.arraycopy(arr, 0, result, 0, k);
buildMaxHeap(result);
for (int i = k; i < arr.length; i++) {
if (arr[i] < result[0]) {
result[0] = arr[i];
maxHeapify(result, 0, k);
}
}
return result;
}
public void buildMaxHeap(int[] array) {
for (int i = (array.length >> 1) - 1; i >= 0; i--) {
maxHeapify(array, i, array.length);
}
}
public void maxHeapify(int[] array, int index, int headSize) {
int left = (index << 1) + 1;
int right = (index << 1) + 2;
int indexOfLargest = index;
if (left < headSize && array[left] > array[indexOfLargest]) {
indexOfLargest = left;
}
if (right < headSize && array[right] > array[indexOfLargest]) {
indexOfLargest = right;
}
if (indexOfLargest != index) {
swap(array, index, indexOfLargest);
maxHeapify(array, indexOfLargest, headSize);
}
}
public void checkArguments(int[] array, int k) {
if (array == null) {
throw new RuntimeException("Null array");
}
if (array.length == 0) {
throw new RuntimeException("Empty array");
}
if (k < 0 || array.length < k) {
throw new RuntimeException("Invalid k");
}
} - 解法二：快排的partition函数
public int[] getLeastNumbers(int[] arr, int k) {
checkArguments(arr, k);
int[] result = new int[k];
if (k == 0) {
return result;
}
if (k == arr.length) {
return arr;
}
int start = 0;
int end = arr.length - 1;
int index = partition(arr, start, end);
while (index != k-1 ) {
if (index < k) {
start = index + 1;
} else {
end = index - 1;
}
index = partition(arr, start, end);
}
System.arraycopy(arr, 0, result, 0, index+1);
return result;
}
public int partition(int[] array, int start, int end) {
int index = new Random().nextInt(end-start+1) + start;
swap(array, index, end);
int small = start - 1;
for (index = start; index < end; index++) {
if (array[index] < array[end]) {
small++;
if (small != index) {
swap(array, small, index);
}
}
}
swap(array, ++small, end);
return small;
} 面试题41：数据流中的中位数
题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
- 算法：
- 最大堆+最小堆
- 最大堆存放小的那一半数据
- 最小堆存放大的那一半数据
class MedianFinder {
PriorityQueue<Integer> min;
PriorityQueue<Integer> max;
public MedianFinder() {
min = new PriorityQueue<Integer>();
max = new PriorityQueue<Integer>((o1, o2) -> o2 - o1);
}
public void addNum(int num) {
if (((min.size() + max.size()) & 1) == 1) { // 最大堆里面插小的数据，如果最小堆里面有比num小的就插它
if (min.size() > 0 && min.peek() < num) {
min.offer(num);
num = min.poll();
}
max.offer(num);
} else { // 最小堆里面插大的数据，如果最大堆里面有比num大的就插它
if (max.size() > 0 && max.peek() > num) {
max.offer(num);
num = max.poll();
}
min.offer(num);
}
}
public double findMedian() {
if ((min.size() + max.size()) == 0) {
throw new RuntimeException("Empty heap");
}
return (min.size() == max.size()) ? (max.peek() + min.peek()) / 2.0 : min.peek();
}
} - 算法：
- 两个最小堆
- 一个存放原值
- 另一个存放负原值
- 时间更长
class MedianFinder {
PriorityQueue<Long> max;
PriorityQueue<Long> min;
public MedianFinder() {
max = new PriorityQueue<Long>(); // Long避免Integer取负时溢出
min = new PriorityQueue<Long>();
}
public void addNum(int num) {
max.offer((long)num);
min.offer(- max.poll());
if (max.size() < min.size()) {
max.offer(- min.poll()); // min是最小堆！所以取负后的最小就是原来的最大
}
}
public double findMedian() {
return max.size() > min.size() ? max.peek() : (max.peek() - min.peek()) / 2.0;
}
}; 面试题42：连续子数组的最大和
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
算法：
- 遍历数组，保存最大值
- 累加大于0，累加和加上当前值
- 累加不大于0，累加和置为当前值
动态规划，找到max(f(i))
f(i) = { A[i] i = 0 或 f(i-1) <= 0
{ f(i-1) + A[i] i ≠ 0 且 f(i-1) > 0public int maxSubArray(int[] nums) {
checkArguments(nums);
int sum = 0;
int max = Integer.MIN_VALUE;
for (int x : nums) {
sum = sum <= 0 ? x : (sum + x);
max = sum < max ? max : sum;
}
return max;
} 面试题43：从1到n整数中1出现的次数
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
- 算法：每次去掉最高位进行递归
public int countDigitOne(int n) {
checkArguments(n);
return countDigitOne(Integer.toString(n));
}
private int countDigitOne(String s) {
int first = s.charAt(0) - '0';
int length = s.length();
if (first == 0 && length == 1) {
return 0;
}
if (first > 0 && length == 1) {
return 1;
}
// 以21345为例，先递归最高位1346-21345范围1的个数
// 最高位为1的范围内1的个数：10000-19999共10000个
int numFirstDigit = 0;
if (first > 1) {
numFirstDigit = powerBase10(length-1);
}
if (first == 1) { // 最高位是1时：比如12345，则最高位有2345+1个1
numFirstDigit = Integer.parseInt(s.substring(1))+1;
}
// 其余四位范围内1的个数：2 * 4 * 10^3
int numOtherDigit = first * (length - 1) * powerBase10(length-2);
// 递归1345：346-1345 --> 递归345：46-345 --> 递归45：6-45 --> 递归5：1-5
return numFirstDigit + numOtherDigit + countDigitOne(s.substring(1));
}
private int powerBase10(int n) {
int result = 1;
for (int i = 0; i < n; i++) {
result *= 10;
}
return result;
}
private void checkArguments(int n) {
if (n <= 0) {
throw new RuntimeException("Invalid arguments");
}
} - 算法：???
public int countDigitOne(int n) {
int ones = 0;
for (int m = 1; m <= n; m *= 10) {
int a = n / m;
int b = n % m;
ones += (a + 8) / 10 * m
+ (a % 10 == 1 ? b + 1 : 0);
}
return ones;
} 面试题44：数字序列中某一位的数字
题目：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数求任意位对应的数字。
- 算法：
- 同下
public int findNthDigit(int n) {
checkArguments(n);
int lengthOfDigit = 1;
long count = 9;
int start = 1;
while (n > lengthOfDigit * count) {
n -= lengthOfDigit * count;
lengthOfDigit += 1;
count *= 10;
start *= 10;
}
start += (n - 1) / lengthOfDigit; // n - 1减去第一个数字0
String s = Integer.toString(start);
return Character.getNumericValue(s.charAt((n - 1) % lengthOfDigit));
} - 算法：
- 逐个计算一位数（10）两位数（90）三位数（900）等等共占了多少位，找到包含目标位数的范围后进入查找
public int findNthDigit(int n) {
checkArguments(n);
int digits = 1;
while (true) {
int numbers = countNumberOfDigit(digits);
if (n < (long) digits * numbers) {
return findNthDigit(n, digits);
}
n -= digits * numbers;
digits++;
}
}
private int countNumberOfDigit(int digits) {
if (digits == 1) {
return 10;
}
return 9 * (int)Math.pow(10, digits-1);
}
private int findNthDigit(int n, int digits) {
// 目标数字
int number = beginNumberOfDigit(digits) + n / digits;
// 目标位数在目标数字中的偏移
// 比如：目标数字是34567，由于从0开始奇数，3是余数为0时的结果，4是余数为1时的结果......
// n % digits = 2; indexFromRight = 5 - 2 = 3;
// 则倒数第三个数5是余数为2时的数字
int indexFromRight = digits - n % digits;
for (int i = 1; i < indexFromRight; i++) {
number /= 10;
}
return number % 10;
}
private int beginNumberOfDigit(int digits) {
if (digits == 1) {
return 0;
}
return (int)Math.pow(10, digits-1);
}
private void checkArguments(int n) {
if (n < 0) {
throw new RuntimeException("Invalid arguments");
}
} 面试题45：把数组排成最小的数
题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3, 32, 321}，则打印出这3个数字能排成的最小数字321323。
- 算法：
- 首先可以证明任意两个数字拼成的新数字满足如下有效的比较规则
- a和b如果有ab<ba，定义这时a小于b
- 反之如果有ba>ab，定义这时a大于b
- 证明：一个有效的比较规则需要满足自反性，对称性和传递性
- 然后可以证明利用以上定义的大小规则可以证明多个数字只要按照它排序从小到大拼接出来的数字就是最小的
- 证明：反证法，假设不是最小的，则存在两个数字交换位置后比它更小
- 首先可以证明任意两个数字拼成的新数字满足如下有效的比较规则
public String minNumber(int[] nums) {
checkArguments(nums);
if (nums.length == 0) {
return "";
}
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = Integer.toString(nums[i]);
}
Arrays.sort(strs, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String temp1 = o1 + o2;
String temp2 = o2 + o1;
return temp1.compareTo(temp2);
}
});
StringBuilder result = new StringBuilder();
for (String str : strs) {
result.append(str);
}
return result.toString();
}
public void checkArguments(int[] nums) {
if (nums == null) {
throw new RuntimeException("Null array");
}
} 面试题46：把数字翻译成字符串
题目：给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成"a"，1翻译成"b"，……，11翻译成"l"，……，25翻译成"z"。一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是"bccfi"、"bwfi"、"bczi"、"mcfi"和"mzi"。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
- 算法：自上而下分析
- f(i) = f(i+1) + g(i,i+1) * f(i+2)
- 当i和i+1位数字在10-25范围中时，可以把他们放在一起翻译，所以g(i, i+1) = 1；否则g(i, i+1) = 0
public int translateNum(int num) {
checkArguments(num);
String str = Integer.toString(num);
return translateNum(str, 0);
}
private int translateNum(String str, int index) {
if (index >= str.length() - 1) {
return 1;
}
int digit1 = str.charAt(index) - '0';
int digit2 = str.charAt(index+1) - '0';
if (digit1*10+digit2 >= 10 && digit1*10+digit2 <= 25) {
return translateNum(str, index+1) + translateNum(str, index+2);
} else {
return translateNum(str, index+1);
}
}
public void checkArguments(int num) {
if (num < 0) {
throw new RuntimeException("Invalid arguments");
}
} - 算法：自下而上解题
- counts[length-1] = 1;
- counts[i] = counts[i+1] + g(i,i+1)*counts[i+2], i+2 < length
- counts[i] = counts[i+1] + g(i,i+1), i+2 > length
public int translateNum(int num) {
checkArguments(num);
String str = Integer.toString(num);
return translateNum(str);
}
public int translateNum(String str) {
int length = str.length();
int[] counts = new int[length];
for (int i = length - 1; i >= 0; i--) {
if (i < length - 1) {
counts[i] = counts[i+1];
} else {
counts[i] = 1;
}
if (i < length - 1) {
int digit1 = str.charAt(i) - '0';
int digit2 = str.charAt(i+1) - '0';
if (digit1*10+digit2 >= 10 && digit1*10+digit2 <= 25) {
if (i < length - 2) {
counts[i] += counts[i+2];
} else {
counts[i] += 1;
}
}
}
}
return counts[0];
} 面试题47：礼物的最大价值
题目：在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？
- 算法：自上而下分析
- 递归，极易TLE
- f(i,j) = gift(i,j) + max(f(i-1,j),f(i,j-1))
- f(i,j) = gift(0,j) + f(0,j-1)); i = 0
- f(i,j) = gift(i,0) + f(i-1,0)); j = 0
public int maxValue(int[][] grid) {
checkArguments(grid);
return maxValue(grid, grid.length-1, grid[0].length-1);
}
public int maxValue(int[][] matrix, int row, int col) {
if (row == 0 && col == 0) {
return matrix[0][0];
}
if (row == 0) {
return matrix[0][col] + maxValue(matrix, 0, col-1);
}
if (col == 0) {
return matrix[row][0] + maxValue(matrix, row-1, 0);
}
return matrix[row][col] + Math.max(maxValue(matrix, row-1, col), maxValue(matrix, row, col-1));
} - 算法：动态规划，自下而上解决
- 二维数组保存中间结果
public int maxValue(int[][] grid) {
checkArguments(grid);
int row = grid.length;
int col = grid[0].length;
int[][] maxValues = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int up = 0;
int left = 0;
if (i > 0) {
up = maxValues[i-1][j];
}
if (j > 0) {
left = maxValues[i][j-1];
}
maxValues[i][j] = Math.max(left, up) + grid[i][j];
}
}
return maxValues[row-1][col-1];
} - 算法：动态规划，自下而上解决
- 一维数组保存中间结果
public int maxValue(int[][] grid) {
checkArguments(grid);
int row = grid.length;
int col = grid[0].length;
int[] maxValues = new int[col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int up = 0;
int left = 0;
if (i > 0) {
up = maxValues[j];
}
if (j > 0) {
left = maxValues[j-1];
}
maxValues[j] = Math.max(left, up) + grid[i][j];
}
}
return maxValues[col-1];
} 面试题48：最长不含重复字符的子字符串
题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含从'a'到'z'的字符。
- 算法：动态规划
- f(i)表示以第i位结尾的最长不含重复字符的子字符串
- 第i位字符之前没有出现过：f(i) = f(i-1) + 1
- 第i位字符之前出现过，相隔距离d > f(i-1)：f(i) = f(i-1) + 1
- 第i位字符之前出现过，相隔距离d <= f(i-1)：f(i) = d
- 用HashMap保存出现过字符的位置
public int lengthOfLongestSubstring(String s) {
checkArguments(s);
if (s.length() == 0) {
return 0;
}
int curLength = 0;
int maxLength = 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!map.containsKey(c) || i - (map.get(c)) > curLength) {
curLength++;
} else {
if (curLength > maxLength) { // curLength有可能变小时将结果保存下来
maxLength = curLength;
}
curLength = i - map.get(c);
}
map.put(c, i);
}
if (curLength > maxLength) { // 保存最后一个字符结尾的最长不含重复字符的结果
maxLength = curLength;
}
return maxLength;
} - 算法：双指针
- 遍历字符串
- 如果HashMap中包含当前字符：更新慢指针
- 慢指针的更新规律：max(上一个重复字符的下一个位置，当前重复字符的下一个位置)
- 比如："arabcacfr"遍历到倒数第三个c时，j的位置是上一个重复字符的下一个位置，也就是第二个a的后面，更新j = max("ara'b'cacfr", "arabc'a'cfr")
- 每次遍历都保存最新的字符位置到HashMap中
- 每次遍历都保存最新的最长不含重复字符的子串长度
public int lengthOfLongestSubstring(String s) {
checkArguments(s);
if (s.length() == 0) {
return 0;
}
int max = 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0, j = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
j = Math.max(j, map.get(s.charAt(i))+1);
}
map.put(s.charAt(i), i);
max = Math.max(max, i-j+1);
}
return max;
} 
京公网安备 11010502036488号