写在前面
- 本系列包含《剑指Offer》66道算法题，预计一周刷完，这是第三篇。
系列汇总：剑指Offer 66题 Java 刷题笔记汇总 - 所有题目均可在牛客网在线编程平台进行调试。
网址：https://www.nowcoder.com/ta/coding-interviews - 本系列包含题目，解题思路及代码（Java）。
代码同步发布在GitHub：https://github.com/JohnnyJYWu/offer-Java
上一篇：算法 | 一周刷完《剑指Offer》 Day2：第17~26题
下一篇：算法 | 一周刷完《剑指Offer》 Day4：第38~49题
Day3：第27~37题
难度上升，多看多想，理解才好做。
- T27. 字符串的排列
- T28. 数组中出现次数超过一半的数字
- T29. 最小的K个数
- T30. 连续子数组的最大和
- T31. 整数中1出现的次数（从1到n整数中1出现的次数）
- T32. 把数组排成最小的数
- T33. 丑数
- T34. 第一个只出现一次的字符位置
- T35. 数组中的逆序对
- T36. 两个链表的第一个公共结点
- T37. 数字在排序数组中出现的次数
T27. 字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：输入一个字符串,长度不超过9(可能有字符重复)，字符只包括大小写字母。
解题思路
同样是递归回溯的思想。先把字符串进行字典序排序，定义hasUsed辅助数组记录各字符是否使用，然后递归对后面的字符排列组合即可。
注意：使用StringBuffer便于字符串操作。每个递归结束后记得回溯，去除此循环加入的字符，回退到上一步的排列，与T24中去除结点道理一样。
private ArrayList<String> result = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if(str == null || str.length() == 0) return result;
char[] chars = str.toCharArray();
Arrays.sort(chars);//字典序排序
permutation(chars,
new boolean[chars.length],//用于记录当前字符是否用过
new StringBuffer());//字符串，便于操作
return result;
}
private void permutation(char[] chars, boolean[] hasUsed, StringBuffer str) {
if(str.length() == chars.length) {//长度相同说明出结果，加入result
result.add(str.toString());
return;
}
for(int i = 0; i < chars.length; i++) {
if(hasUsed[i]) continue;
if(i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1]) continue;//连续两个值相同时，保证不重复
hasUsed[i] = true;
str.append(chars[i]);
//递归对后面的字符进行排列
permutation(chars, hasUsed, str);
//此步重要，去除此循环加入的字符，回退到上一步的排列，与T24中去除结点道理一样
str.deleteCharAt(str.length() - 1);
hasUsed[i] = false;
}
}
T28. 数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解题思路
多数投票问题。
首先明确，若数字出现次数超过一半，那它必为出现最多的数字。因此问题转换为找出现最多的数字，然后判断它出现的次数是否超过一半。
定义count来统计一个元素出现的次数，当遍历到的元素和统计元素不相等时，count --。如果前面查找了 i 个元素，且 count == 0 ，说明前 i 个元素没有【多数】，或者有【多数】但出现的次数少于 i / 2 ，因为如果多于 i / 2 的话 count 就一定不会为 0 。此时剩下的 n - i 个元素中，【多数】的数目依然多于 (n - i) / 2，因此继续查找就能找出【多数】。
最后，找到多数后再判断出现次数是否超过一半即可。
public int MoreThanHalfNum_Solution(int[] array) {//多数投票问题
int num = array[0];
int count = 1;
for(int i = 1; i < array.length; i ++) {
if(array[i] == num) {
count ++;
} else {
count --;
}
if(count == 0) {
num = array[i];
count = 1;
}
}
count = 0;
for(int val: array) {
if(val == num) {
count ++;
}
}
return count > array.length / 2 ? num : 0;//三元
}
T29. 最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
解题思路
快速选择法。快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。
快排的 partition() 方法会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素。
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(k > input.length || k <= 0) return list;
int smallestK = findSmallestK(input, k - 1);
for(int val: input) {
if(val <= smallestK && list.size() < k) {
list.add(val);
}
}
return list;
}
private int findSmallestK(int[] input, int k) {
int low = 0;
int high = input.length - 1;
while(low < high) {
int j = partition(input, low, high);
if(j < k) {
low = j + 1;
} else if(j > k) {
high = j - 1;
} else {
break;
}
}
return input[k];
}
private int partition(int[] nums, int low, int high) {
int i = low;
int j = high + 1;
while(true) {
while(i < high && nums[++ i] < nums[low]) ;
while(j > low && nums[low] < nums[-- j]) ;
if(i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, low, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
或者，直接排序找最小。。。
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(k > input.length || k <= 0) return list;
Arrays.sort(input);
for(int i = 0; i < k; i ++) {
list.add(input[i]);
}
return list;
}
T30. 连续子数组的最大和
题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
解题思路
嗯。。。阅读题，历来都是题目越长题越简单。。。单纯一点，边找边加就行了。
注意查看代码中唯一的一行注释，很关键。
public int FindGreatestSumOfSubArray(int[] array) {
if(array == null || array.length == 0) return 0;
int sum = 0;
int result = Integer.MIN_VALUE;
for(int val: array) {
if(sum < 0) {
sum = val;//关键在此，如果前面n个的和sum已经小于0了，别傻乎乎继续加，直接从新的val开始吧
} else {
sum += val;
}
if(result < sum) {
result = sum;
}
}
return result;
}
T31. 整数中1出现的次数（从1到n整数中1出现的次数）
题目描述
求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300？的整数中1出现的次数？为此他特别数了一下1 ~ 13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他，并把问题更加普遍化，可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
解题思路
这种题靠悟性。。。
public int NumberOf1Between1AndN_Solution(int n) {
int ones = 0;
for(int m = 1; m <= n; m *= 10) {
int a = n / m, b = n % m;
if(a % 10 == 0)
ones += a / 10 * m;
else if(a % 10 == 1)
ones += (a / 10 * m) + (b + 1);
else
ones += (a / 10 + 1) * m;
}
return ones;
}
leetcode大神只用了5行的解法，有兴趣的深入了解一下。。。
https://leetcode.com/problems/number-of-digit-one/discuss/64381/4-lines-olog-n-cjavapython
public int countDigitOne(int n) {
int ones = 0;
for (long m = 1; m <= n; m *= 10)
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
return ones;
}
T32. 把数组排成最小的数
题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
解题思路
可以看做是排序问题，不同点在于此题是比较数字转换成字符串后相加的大小。
例如两个数字转换的字符串S1和S2，应该比较 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面。
public String PrintMinNumber(int[] numbers) {
String[] nums = new String[numbers.length];
for(int i = 0; i < nums.length; i ++) {//int转string，比较string相加的值
nums[i] = String.valueOf(numbers[i]);
}
Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));//排序，s1+s2与s2+s1两个字符串比较，谁小谁放前面
String result = "";
for(String str: nums) {
result += str;
}
return result;
}
T33. 丑数
题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路
此题需要思维灵活。由题意，只需不断从前面已知的丑数中选取合适的丑数分别乘2、3、5，选取最小的丑数加入数组即可。关键在于如何选取合适的丑数。（定义2、3、5对应的下标index2、index3、index5，详见注释）
public int GetUglyNumber_Solution(int index) {
if(index <= 6) return index;//1~6即为前6个丑数
int index2 = 0, index3 = 0, index5 = 0;
int[] uglys = new int[index];//存前n个丑数
uglys[0] = 1;//初始化第一个值为1
int n = 1;//开始计算第二个丑数
while(n < index) {
//找出下一个小的丑数,此步重要需理解，分别用2,3,5在丑数数组里对应的上一个丑数乘2,3,5找出最小的丑数
int ugly2 = uglys[index2] * 2;
int ugly3 = uglys[index3] * 3;
int ugly5 = uglys[index5] * 5;
int min = Math.min(ugly2, Math.min(ugly3, ugly5));
uglys[n] = min;
n ++;
//将2,3,5对应的上一个丑数后移
if(min == ugly2) index2 ++;
if(min == ugly3) index3 ++;
if(min == ugly5) index5 ++;
}
return uglys[index - 1];
}
T34. 第一个只出现一次的字符位置
题目描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符，并返回它的位置，如果没有则返回 -1（需要区分大小写）。
解题思路
char类型一般为一个字节，范围在0 ~ 255。因此定义一个整形计数数组int[256]，对每个char出现次数进行计数即可。
计数后要按照字符串中的字符顺序查找第一个计数次数为1的字符。
public int FirstNotRepeatingChar(String str) {
int[] array = new int[256];//计数数组
for(int i = 0; i < str.length(); i ++) {
array[str.charAt(i)] ++;
}
for(int i = 0; i < str.length(); i ++) {
if(array[str.charAt(i)] == 1) {//按str的字符顺序来，找出第一个计数次数为1的即为所求位置
return i;
}
}
return -1;
}
T35. 数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
解题思路
分治思想，先分后治。先不断将数组一分为二，并对这分开的两部分进行相同操作；然后一边合并相邻的子数组，一边统计逆序对的数目。（实质就是归并排序的思路）
private long cnt = 0;
private int[] tmp;//辅助数组
public int InversePairs(int[] array) {
tmp = new int[array.length];
mergeSortUp2Down(array, 0, array.length - 1);
return (int) (cnt % 1000000007);
}
private void mergeSortUp2Down(int[] nums, int first, int last) {
if(last - first < 1) return;
int mid = (first + last) / 2;
//分治思想
mergeSortUp2Down(nums, first, mid);
mergeSortUp2Down(nums, mid + 1, last);
merge(nums, first, mid ,last);
}
private void merge(int[] nums, int first, int mid, int last) {
int i = first, j = mid + 1, k = first;
while(i <= mid || j <= last) {
if(i > mid) {
tmp[k] = nums[j];
j ++;
}
else if(j > last) {
tmp[k] = nums[i];
i ++;
}
else if(nums[i] < nums[j]) {
tmp[k] = nums[i];
i ++;
}
else {
tmp[k] = nums[j];
j ++;
this.cnt += mid - i + 1;//nums[i] > nums[j]说明nums[i...mid]都大于nums[j]
}
k ++;
}
for(k = first; k <= last; k ++) {
nums[k] = tmp[k];
}
}
T36. 两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。
解题思路
数学问题。
如图，链表1长度为 a+c，链表2长度为 b+c。声明两个指针node1和node2分别指向两个链表表头，同步向后移动。
node1走过 a+c 后指空，此时让它指向链表2的表头并继续向后走；同理node2走过 b+c 后指向链表1表头。
由于 a+c+b = b+c+a ，此时node1和node2刚好相遇，且相遇在两个链表的第一个公共结点。由此得解。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode node1 = pHead1;
ListNode node2 = pHead2;
while(node1 != node2) {//公共结点后面即为公共链表
if(node1 == null) {
node1 = pHead2;
} else {
node1 = node1.next;
}
if(node2 == null) {
node2 = pHead1;
} else {
node2 = node2.next;
}
}
return node1;
}
T37. 数字在排序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
解题思路
顺序查找。
public int GetNumberOfK(int[] array , int k) {
int sum = 0;
for(int val: array) {
if(val == k) {
sum ++;
}
}
return sum;
}
二分查找，找到第一次和最后一次k出现的位置，即可计算次数。
public int GetNumberOfK(int[] array , int k) {
int first = getFirstK(array, k);
int last = getLastK(array, k);
if(first == -1) return 0;
if(last == -1) return 0;
return last - first + 1;
}
private int getFirstK(int[] array , int k) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = (high + low) / 2;
if(array[mid] >= k) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if(low > array.length - 1 || array[low] != k)
return -1;
return low;
}
private int getLastK(int[] array , int k) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = (high + low) / 2;
if(array[mid] > k) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if(high < 0 || array[high] != k)
return -1;
return high;
}
项目地址：https://github.com/JohnnyJYWu/offer-Java
上一篇：算法 | 一周刷完《剑指Offer》 Day2：第17~26题
下一篇：算法 | 一周刷完《剑指Offer》 Day4：第38~49题
希望这篇文章对你有帮助~
