35.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入1,2,3,4,5,6,7,0 输出7
public class Solution {
public int InversePairs(int [] array) {
if(array == null||array.length == 0) return 0;
int length = array.length;
int[] copy = new int[length];
for(int i = 0;i < length ;i++){
copy[i] = array[i];
}
int count = InversePairsCore(array,copy,0,array.length-1);
return count;
}
public int InversePairsCore(int[] array,int[] copy,int start,int end){
if(start == end){
return 0;
}
int count = 0;
int length = (end-start)/2;
//注意：这里是故意将copy和array调换位置的，因为每次执行InversePairCore之后copy在[start,end]部分都是排好序的
//随意使用data作为array输入，省去了来回复制的资源消耗。
int left = InversePairsCore(copy,array,start,start+length);
int right = InversePairsCore(copy,array,start+length+1,end);
int p1 = start+length;
int p2 = end;
int copyIdx = end;
while(p1 >= start && p2 >= start+length+1){
if(array[p1]>array[p2]){
count += p2-start-length;
//此处先判断一下，以免超出运算范围。
if(count > 1000000007)
count = count%1000000007;
copy[copyIdx--] = array[p1--];
}else{
copy[copyIdx--] = array[p2--];
}
}
while(p1 >= start){
copy[copyIdx--] = array[p1--];
}
while(p2 >= start+length+1){
copy[copyIdx--] = array[p2--];
}
return (count+left+right)%1000000007;
}
}
36.两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。技巧：不适用辅助Stack
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null) return null;
int L1 = getListLength(pHead1);
int L2 = getListLength(pHead2);
if(L1>L2)
for(int i = 0 ;i<(L1-L2);i++)
pHead1 = pHead1.next;
else if(L2>L1)
for(int i = 0 ;i<(L2-L1);i++)
pHead2 = pHead2.next;
while(pHead1!=null){
if(pHead1 == pHead2)
return pHead1;
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return null;
}
public int getListLength(ListNode head){
ListNode temp = head;
int count = 1;
while(temp.next != null){
temp = temp.next;
count++;
}
return count;
}
}