一、数组中的逆序对：
1、题目：
数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
2、解题方法：
参考牛客网的“rs勿忘初心”、“流痕”：https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5
（1）看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)这个数字比较，因此这个算法的时间复杂度为O(n^2)。
（2）我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不拿它和后面的每一个数字作比较，否则时间复杂度就是O(n^2)，因此我们可以考虑先比较两个相邻的数字。
(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；
在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图（c）所示， 以免在以后的统计过程中再重复统计。
（3）接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。
（4）过程总结：先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序。
3、代码实现：
/*归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，
合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则后面
数组array[mid]~array[j]都是小于array[i]的，count +=j-mid;
*
*copy数组的作用：
对已经统计了逆序对的数组，我们需要对其排好序，以避免在以后的统计过程中再次重复统计，所以copy数组就是起到这个作用，
当然，这里的有序只是“局部有序”，整体来看还是无序的。既然copy数组是“有序”的，下一次就直接在这个基础上进行统计就可以，
原始数据data用来充当原来copy数组的角色来保存“更加有序”的数组。因此在InversePairsCore()方法中调换array和copy数组的位置。
*/
public class Test16 {
public int InversePairs(int [] array) {
if(array==null || array.length==0){
return 0;
}
int[] copy = new int[array.length];
for(int i=0;i<array.length;i++){
copy[i]=array[i];
}
int count =InversePairsCore(array,copy,0,array.length-1);
return count;
}
private int InversePairsCore(int[] array, int[] copy, int low, int high) {
if(low == high){//low和high分别代表开始下标和末尾下标
return 0;
}
int mid = (low+high)>>1;//中间位置下标
int leftCount = InversePairsCore(copy,array,low,mid)%1000000007;//左边部分的逆序对
int rightCout = InversePairsCore(copy,array,mid+1,high)%1000000007;//右边部分的逆序对
int count = 0;
int i = mid;//左边部分的起始指针位置
int j = high;//右边部分的起始指针位置
int locCopy = high;//复制数组的下标起始位置
while(i>=low && j>mid){
if(array[i]>array[j]){
count = count + j-mid;
copy[locCopy--] = array[i--];
if(count>=1000000007){
count%=1000000007;
}
}else{
copy[locCopy--] = array[j--];
}
}
//下面的两个for循环用于处理边界情况
for(;i>=low;i--){
copy[locCopy--] = array[i];
}
for(;j>mid;j--){
copy[locCopy--] = array[j];
}
return (leftCount+rightCout+count)%1000000007;
}
}
二、最小的K个数：
1、题目：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
2、解题思路：
第一种：使用冒泡排序的思想，不过不需要全部进行排序，只需要对最外层的k层进行排序就可以了。
第二种：利用最大堆，每次只和堆顶比，如果比堆顶的数小，删除堆顶，新数入堆。
第三种：使用快速排序的Partiton思想：
（1）我们选定数组第一个数作为基数pivot，通过快速排序，使得比pivot小的数都位于数组的左边，比pivot大的数字都位于数组的右边。(这几个数字不一定是排序的)
（2）找去基数pivot的下标index，如果index等于k-1，返回调整好的数组的前K个数字。否则进入第3步。
（3）当index大于k-1时，high等于index-1，重复以上操作；当index小于k-1时，low等于index+1,重复以上操作。
3、代码实现：
public class Test18 {
//第三种：使用快速排序的Partiton思想：
//1、我们选定数组第一个数作为基数pivot，通过快速排序，使得比pivot小的数都位于数组的左边，比pivot大的数字都位于数组的右边。(这几个数字不一定是排序的)
//2、找去基数pivot的下标index，如果index等于k-1，返回调整好的数组的前K个数字。否则进入第3步。
//3、当index大于k-1时，high等于index-1，重复以上操作；当index小于k-1时，low等于index+1,重复以上操作。
public ArrayList<Integer> GetLeastNumbers_Solution3(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
int length = input.length;
if(length<k || k==0){
return result;
}
findKMin(input,0,input.length-1,k);
for(int i=0;i<k;i++){
result.add(input[i]);
}
return result;
}
public void findKMin(int[] input,int low,int high,int k){
if(low < high){
int index = partition(input,low,high);
if(index == k-1){
return;
}else if(index < k-1){
findKMin(input,index+1,high,k);
}else{
findKMin(input,low,index-1,k);
}
}
}
//partition思想：
private int partition(int[] input, int low, int high) {
int pivot = input[low];
while(low<high){
//右边指针左移
while(high>low && input[high] > pivot){
high--;
}
input[low] = input[high];
//左边指针右移
while(low<high && input[low] <= pivot){
low++;
}
input[high] = input[low];
}
input[low] = pivot;
return low;
}
//第二种：利用最大堆，每次只和堆顶比，如果比堆顶的数小，删除堆顶，新数入堆
public ArrayList<Integer> GetLeastNumbers_Solution2(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
int length = input.length;
if(k>length || k==0){
return result;
}
PriorityQueue<Integer> maxStack = new PriorityQueue<Integer>(k,new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for(int i=0;i<length;i++){
if(maxStack.size() != k){
maxStack.offer(input[i]);
}else if(maxStack.peek()>input[i]){
Integer temp = maxStack.poll();
temp = null;
maxStack.offer(input[i]);
}
}
for(Integer integer : maxStack){
result.add(integer);
}
return result;
}
//第一种：使用冒泡排序的思想，不过不需要全部进行排序，只需要对最外层的k层进行排序就可以了。
public ArrayList<Integer> GetLeastNumbers_Solution1(int [] input, int k) {
ArrayList<Integer> result = new ArrayList();
if(k==0 || k>input.length){
return result;
}
for(int i = 0;i<k;i++){
for(int j=0;j<input.length-i-1;j++){
if(input[j]<input[j+1]){
Integer temp = input[j];
input[j]=input[j+1];
input[j+1]=temp;
}
}
result.add(input[input.length-i-1]);
}
return result;
}
}
三、从1到n整数中1出现的次数：
1、题目：
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
2、解题思路：
参考牛客网的“藍裙子的百合魂”：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
设N = abcde ,其中abcde分别为十进制中各位上的数字。 如果要计算百位上1出现的次数，它要受到3方面的影响：百位上的数字，百位以下（低位）的数字，百位以上（高位）的数字。
① 如果百位上数字为0，百位上可能出现1的次数由更高位决定。比如：12013，则可以知道百位出现1的情况可能是：100~199，1100~1199,2100~2199，，…，11100~11199，一共1200个。可以看出是由更高位数字（12）决定，并且等于更高位数字（12）乘以 当前位数（100）。
② 如果百位上数字为1，百位上可能出现1的次数不仅受更高位影响还受低位影响。比如：12113，则可以知道百位受高位影响出现的情况是：100~199，1100~1199,2100~2199，，….，11100~11199，一共1200个。和上面情况一样，并且等于更高位数字（12）乘以 当前位数（100）。但同时它还受低位影响，百位出现1的情况是：12100~12113,一共14个，等于低位数字（13）+1。
③ 如果百位上数字大于1（2~9），则百位上出现1的情况仅由更高位决定，比如12213，则百位出现1的情况是：100~199,1100~1199，2100~2199，…，11100~11199,12100~12199,一共有1300个，并且等于更高位数字+1（12+1）乘以当前位数（100）。
3、代码实现：
public class Test30 {
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;//1的个数
int i = 1;//当前位
int current = 0,after = 0,before = 0;
while((n/i)!= 0){
current = (n/i)%10; //当前位数字
before = n/(i*10); //高位数字
after = n-(n/i)*i; //低位数字
//如果为0,出现1的次数由高位决定,等于 高位数字 * 当前位数
if (current == 0)
count += before*i;
//如果为1,出现1的次数由高位和低位决定,等于 高位*当前位+低位+1
else if(current == 1)
count += before * i + after + 1;
//如果大于1,出现1的次数由高位决定,等于（高位数字+1）* 当前位数
else{
count += (before + 1) * i;
}
//前移一位
i = i*10;
}
return count;
}
}
四、正则表达式匹配：
1、题目：
请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配
2、解题思路：
参考牛客网的“披萨大叔”：https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c
2.1 当模式中的第二个字符不是“*”时：
（1）如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
（2）如果 字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
2.2 而当模式中的第二个字符是“*”时：
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
（1）模式后移2字符，相当于x*被忽略；
（2）字符串后移1字符，模式后移2字符；
（3）字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
3、代码实现：
public class Test31 {
public boolean match(char[] str, char[] pattern){
if(str == null || pattern == null){
return false;
}
int strIndex = 0;
int patternIndex = 0;
return matchCore(str,strIndex,pattern,patternIndex);
}
private boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
//有效性检查:str到尾，pattern到尾，匹配成功
if(strIndex == str.length && patternIndex == pattern.length)
return true;
//如果pattern先匹配到末尾，匹配失败
if(strIndex != str.length && patternIndex == pattern.length)
return false;
//模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
if(patternIndex+1 < pattern.length && pattern[patternIndex+1] =='*'){
if((strIndex != str.length && str[strIndex] == pattern[patternIndex]) || (strIndex != str.length && pattern[patternIndex] == '.')){
return matchCore(str,strIndex,pattern,patternIndex+2) //模式后移两位，相当于x*被忽略，即x*匹配0个字符
|| matchCore(str,strIndex+1,pattern,patternIndex+2) //匹配中一个字符，字符串后移1为，模式后移两位
|| matchCore(str,strIndex+1,pattern,patternIndex); //匹配一个，在匹配str中的下一个字符，因为*可以匹配多个字符
}else{
return matchCore(str,strIndex,pattern,patternIndex+2);
}
}
//模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
if((strIndex != str.length && str[strIndex] == pattern[patternIndex]) || (strIndex != str.length && pattern[patternIndex] == '.')){
return matchCore(str,strIndex+1,pattern,patternIndex+1);
}
return false;
}
}
五、数值的整数次方：
1、题目描述：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
2、代码实现：
public class Solution{
public double Power(double base, int exponent) {
double result = 1.0;
if(exponent==0){
return 1;
}else if(exponent > 0 ){
for(int i=0;i<exponent;i++)
result *=base;
}else{
if(base==0){
throw new RuntimeException("分母不能为零");
}
for(int j=1;j<=-exponent;j++)
result *=base;
}
return exponent>0?result:(1/result);
}
}
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/114685.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
