剑指 Offer 题解 - 40~49
解题思路
快速选择
- 复杂度:O(N) + O(1)
- 只有当允许修改数组元素时才可以使用
快速排序的 partition() 方法,会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j],且 a[j+1..h] 大于等于 a[j],此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素,这种找第 K 个元素的算法称为快速选择算法。
// java public ArrayList GetLeastNumbers_Solution(int[] nums, int k) { ArrayList ret = new ArrayList<>(); if (k > nums.length || k <= 0)="" return="" ret;="" findkthsmallest(nums,="" k="" -="" 1);="" *="" findkthsmallest="" 会改变数组,使得前="" 个数都是最小的="" 个数="" for="" (int="" i="0;" k) h = j - 1; else l = j + 1; } } private int partition(int[] nums, int l, int h) { int p = nums[l]; /* 切分元素 */ int i = l, j = h + 1; while (true) { while (i != h && nums[++i] < p) ; while (j != l && nums[--j] > p) ; if (i >= j) break; swap(nums, i, j); } swap(nums, l, j); return j; } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }
大小为 K 的最小堆
- 复杂度:O(NlogK) + O(K)
- 特别适合处理海量数据
应该使用大顶堆来维护最小堆,而不能直接创建一个小顶堆并设置一个大小,企图让小顶堆中的元素都是最小元素。
维护一个大小为 K 的最小堆过程如下:在添加一个元素之后,如果大顶堆的大小大于 K,那么需要将大顶堆的堆顶元素去除。
// java public ArrayList GetLeastNumbers_Solution(int[] nums, int k) { if (k > nums.length || k <= 0)="" return="" new="" arraylist(); PriorityQueue maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); for (int num : nums) { maxHeap.add(num); if (maxHeap.size() > k) maxHeap.poll(); } return new ArrayList<>(maxHeap); }
41.1 数据流中的中位数
题目描述
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
解题思路
// java /* 大顶堆,存储左半边元素 */ private PriorityQueue left = new PriorityQueue<>((o1, o2) -> o2 - o1); /* 小顶堆,存储右半边元素,并且右半边元素都大于左半边 */ private PriorityQueue right = new PriorityQueue<>(); /* 当前数据流读入的元素个数 */ private int N = 0; public void Insert(Integer val) { /* 插入要保证两个堆存于平衡状态 */ if (N % 2 == 0) { /* N 为偶数的情况下插入到右半边。 * 因为右半边元素都要大于左半边,但是新插入的元素不一定比左半边元素来的大, * 因此需要先将元素插入左半边,然后利用左半边为大顶堆的特点,取出堆顶元素即为最大元素,此时插入右半边 */ left.add(val); right.add(left.poll()); } else { right.add(val); left.add(right.poll()); } N++; } public Double GetMedian() { if (N % 2 == 0) return (left.peek() + right.peek()) / 2.0; else return (double) right.peek(); }
41.2 字符流中第一个不重复的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符 "go" 时,第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时,第一个只出现一次的字符是 "l"。
解题思路
// java private int[] cnts = new int[256]; private Queue queue = new LinkedList<>(); public void Insert(char ch) { cnts[ch]++; queue.add(ch); while (!queue.isEmpty() && cnts[queue.peek()] > 1) queue.poll(); } public char FirstAppearingOnce() { return queue.isEmpty() ? '#' : queue.peek(); }
42. 连续子数组的最大和
题目描述
{6, -3, -2, 7, -15, 1, 2, 2},连续子数组的最大和为 8(从第 0 个开始,到第 3 个为止)。
解题思路
// java public int FindGreatestSumOfSubArray(int[] nums) { if (nums == null || nums.length == 0) return 0; int greatestSum = Integer.MIN_VALUE; int sum = 0; for (int val : nums) { sum = sum <= 0="" ?="" val="" :="" sum="" +="" val;="" greatestsum="Math.max(greatestSum," sum);="" }="" return="" greatestsum;=""43. 从 1 到 n 整数中 1 出现的次数
解题思路
// java public int NumberOf1Between1AndN_Solution(int n) { int cnt = 0; for (int m = 1; m <= 1="" 10="" n;="" m="" *="10)" {="" int="" a="n" m,="" b="n" %="" m;="" cnt="" +="(a" 8)="" (a="" ?="" :="" 0);="" }="" return="" cnt;=""Leetcode : 233. Number of Digit One-C++JavaPython)
44. 数字序列中的某一位数字
题目描述
数字以 0123456789101112131415... 的格式序列化到一个字符串中,求这个字符串的第 index 位。
解题思路
// java public int getDigitAtIndex(int index) { if (index < 0) return -1; int place = 1; // 1 表示个位,2 表示 十位... while (true) { int amount = getAmountOfPlace(place); int totalAmount = amount * place; if (index < totalAmount) return getDigitAtIndex(index, place); index -= totalAmount; place++; } } /** * place 位数的数字组成的字符串长度 * 10, 90, 900, ... */ private int getAmountOfPlace(int place) { if (place == 1) return 10; return (int) Math.pow(10, place - 1) * 9; } /** * place 位数的起始数字 * 0, 10, 100, ... */ private int getBeginNumberOfPlace(int place) { if (place == 1) return 0; return (int) Math.pow(10, place - 1); } /** * 在 place 位数组成的字符串中,第 index 个数 */ private int getDigitAtIndex(int index, int place) { int beginNumber = getBeginNumberOfPlace(place); int shiftNumber = index / place; String number = (beginNumber + shiftNumber) + ""; int count = index % place; return number.charAt(count) - '0'; }45. 把数组排成最小的数
题目描述
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组 {3,32,321},则打印出这三个数字能排成的最小数字为 321323。
解题思路
可以看成是一个排序问题,在比较两个字符串 S1 和 S2 的大小时,应该比较的是 S1+S2 和 S2+S1 的大小,如果 S1+S2 < S2+S1,那么应该把 S1 排在前面,否则应该把 S2 排在前面。
// java public String PrintMinNumber(int[] numbers) { if (numbers == null || numbers.length == 0) return ""; int n = numbers.length; String[] nums = new String[n]; for (int i = 0; i < n; i++) nums[i] = numbers[i] + ""; Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1)); String ret = ""; for (String str : nums) ret += str; return ret; }46. 把数字翻译成字符串
题目描述
给定一个数字,按照如下规则翻译成字符串:1 翻译成“a”,2 翻译成“b”... 26 翻译成“z”。一个数字有多种翻译可能,例如 12258 一共有 5 种,分别是 abbeh,lbeh,aveh,abyh,lyh。实现一个函数,用来计算一个数字有多少种不同的翻译方法。
解题思路
// java public int numDecodings(String s) { if (s == null || s.length() == 0) return 0; int n = s.length(); int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = s.charAt(0) == '0' ? 0 : 1; for (int i = 2; i <= n;="" i++)="" {="" int="" one="Integer.valueOf(s.substring(i" -="" 1,="" i));="" if="" (one="" !="0)" dp[i]="" +="dp[i" 1];="" (s.charat(i="" 2)="=" '0')="" continue;="" two="Integer.valueOf(s.substring(i" 2,="" (two=""47. 礼物的最大价值
题目描述
在一个 m*n 的棋盘的每一个格都放有一个礼物,每个礼物都有一定价值(大于 0)。从左上角开始拿礼物,每次向右或向下移动一格,直到右下角结束。给定一个棋盘,求拿到礼物的最大价值。例如,对于如下棋盘
// 1 10 3 8 12 2 9 6 5 7 4 11 3 7 16 5礼物的最大价值为 1+12+5+7+7+16+5=53。
解题思路
应该用动态规划求解,而不是深度优先搜索,深度优先搜索过于复杂,不是最优解。
// java public int getMost(int[][] values) { if (values == null || values.length == 0 || values[0].length == 0) return 0; int n = values[0].length; int[] dp = new int[n]; for (int[] value : values) { dp[0] += value[0]; for (int i = 1; i < n; i++) dp[i] = Math.max(dp[i], dp[i - 1]) + value[i]; } return dp[n - 1]; }48. 最长不含重复字符的子字符串
题目描述
输入一个字符串(只包含 a~z 的字符),求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr,最长不含重复字符的子字符串为 acfr,长度为 4。
解题思路
// java public int longestSubStringWithoutDuplication(String str) { int curLen = 0; int maxLen = 0; int[] preIndexs = new int[26]; Arrays.fill(preIndexs, -1); for (int curI = 0; curI < str.length(); curI++) { int c = str.charAt(curI) - 'a'; int preI = preIndexs[c]; if (preI == -1 || curI - preI > curLen) { curLen++; } else { maxLen = Math.max(maxLen, curLen); curLen = curI - preI; } preIndexs[c] = curI; } maxLen = Math.max(maxLen, curLen); return maxLen; }49. 丑数
题目描述
把只包含因子 2、3 和 5 的数称作丑数(Ugly Number)。例如 6、8 都是丑数,但 14 不是,因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。
解题思路
// java public int GetUglyNumber_Solution(int N) { if (N <= 6)="" return="" n;="" int="" i2="0," i3="0," i5="0;" int[]="" dp="new" int[n];="" dp[0]="1;" for="" (int="" i="1;"