算法问题合集
二分
只要有排他性，就能二分，可以确保一半肯定有答案，直接砍一，不一定要有序
问题1：局部最小值
题目：无需数组，值随机，任意两个相邻的数不相等，找到一个局部最小值，只要一个就行。
局部最小的定义：两个边界，0位置的数比1位置的数小，N-1位置的数比N-2位置的数小就叫局部最小值，如果是中间的数，就要比相邻左右两个数小就叫局部最小值
解题思路：一个数组从0到N-1，先单独看0位置和N-1的位置，如果成功返回，如果都失败，说明0到1是下降，N-1到N-2也是下降，中间肯定有局部最小，这时候找中间位置，分情况如果中间比左边小，又比右边小，直接返回，如果只比左边小，直接砍右边，再继续二分，总会找到的。
注意：重要的是学会思想！！！！
162. 寻找峰值 - 力扣（LeetCode）
下面这个是力扣的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
|
异或运算
异或运算也称为无进位相加，通过这个性质引出了三个特性
- 0异或N = N
- N异或N = 0
- 几个数一起异或之后的结果只有一个数，无论顺序如何改变
问题1：如何不用额外变量交换两个数
1
2
3
| a = a^b;
b = a^b;
a = a^b;
|
136. 只出现一次的数字 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int singleNumber(int[] nums) {
if(nums.length == 1){
return nums[0];
}
int a = nums[0];
for(int i = 1 ; i < nums.length ; i++){
a = a ^ nums[i];
}
return a;
}
}
|
1486. 数组异或操作 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int xorOperation(int n, int start) {
int result = start;
for(int i = 0 ; i < n - 1 ; i++){
result = result ^ (start + 2);
start = start+2;
}
return result;
}
}
|
问题2：一个数组中一个数出现奇数次，其他数出现偶数次，如何找到打印这个数
思路：遍历一次全部异或即可
问题3：如何把一个整形的数，最右侧的1提取出来
思路：a&(-a)即可
-a的操作相当于将a取反+1
题目4：一个数组中有两种数，出现了奇数次，其他数都出现了偶数次，如何找到并且打印这两种数
思路：用一个变量从头到尾异或一遍
得到eor = a异或b
找到右侧第一个1，这个1说明在这一位中a和b不一样一个是1一个是0
这时候在申请一个变量eor2，如果在这一位上有1才异或或者没有1才异或。这样就能拿到a或者b了。
这样就能拿到这两个数了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public class Code01_printOddTimesNum2 {
public static void printOddTimesNum2(int[] arr) {
int eor = 0;
for(int i = 0 ; i < arr.length ; i++){
eor ^= arr[i];
}
int rightOne = eor & (~eor + 1);
int a = 0;
for(int i = 0 ; i < arr.length ; i++){
if((arr[i] & rightOne) != 0){
a ^= arr[i];
}
}
int b = eor ^ a;
a = eor ^ b;
System.out.println(a+" "+b);
}
public static void main(String[] args) {
int[] arr = {1,1,1,2,2,2,4,4,5,5,6,6,7,7};
printOddTimesNum2(arr);
}
}
|
题目5：一个数组中有一种数，出现了K次，其他数都出现了M次，如何找到并且打印这一种数
M>1,K<M
找到出现了K次的数，要求额外空间复杂度0（1）,时间复杂度O（N）
思路：int是4B也就是32byte也就是有32位，然后把每个数取出来，然后把每一个位置上的是1 的就在一个长度32位的数组存储，记录每个位上的1的次数，最终将数组中的数与M进行模运算，由于M比K大所以模上M之后就可以将K得到，并且每一位上都是K的1，最终进行异或把答案得到即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
public static int test(int[] arr, int k, int m) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
for (int num : map.keySet()) {
if (map.get(num) == k) {
return num;
}
}
return -1;
}
public static int onlyKTimes(int[] arr, int k, int m) {
int[] t = new int[32];
for (int num : arr) {
for (int i = 0; i <= 31; i++) {
if (((num >> i) & 1) != 0) {
t[i]++;
}
}
}
int ans = 0;
for (int i = 0; i < 32; i++) {
if (t[i] % m != 0) {
ans |= (1 << i);
}
}
return ans;
}
|
链表
问题1：单双链表的反转
1
2
3
4
5
6
7
8
9
10
11
12
|
public static Node reverseLinkedList(Node head) {
Node prev = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static Node testReverseLinkedList(Node head) {
if (head == null) return null;
ArrayList<Node> array = new ArrayList<>();
while (head != null) {
array.add(head);
head = head.next;
}
array.get(0).next = null;
int N = array.size();
for (int i = 1; i < N; i++) {
array.get(i).next = array.get(i - 1);
}
return array.get(N - 1);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public static DoubleNode reverseDoubleLinkedList(DoubleNode head) {
DoubleNode prev = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = prev;
head.prev = next;
prev = head;
head = next;
}
return prev;
}
|
问题2：如何在链表中删除给定的值
思路：给一个链表的头结点，并且一个给定的值，并且把所有的等于给定值的节点删除，并且返回新头部。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public static Node removeValue(Node head, int num) {
while (head!= null) {
if (head.value!= num) {
break;
}
head = head.next;
}
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
return head;
}
|
容器方法就不写了。
栈和队列
问题1：双向链表实现队列
思路：双链表的头指针和尾指针，一开始头和尾都指向第一个数，第二个数进来，尾指针指向第二个数，弹出的时候弹出头指针。
问题2：双向链表实现双端队列（可以从头部出，也可以从尾部出）
思路：跟上面同理，只是可以头部出和尾部出的区别。
这两个问题是同一个问题，一个是只能头进，尾部出，一个是头能进能出，尾能进能出，这里写一起了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| public static class DoubleNode<T> {
T value;
DoubleNode<T> next;
DoubleNode<T> prev;
public DoubleNode(T value) {
this.value = value;
}
}
public static class DoubleEndQueue<T> {
public DoubleNode<T> head;
public DoubleNode<T> tail;
public void addFromHead(T value) {
DoubleNode<T> cur = new DoubleNode<>(value);
if (head == null) {
head = cur;
tail = cur;
}else{
cur.next = head;
head.prev = cur;
head = cur;
}
}
public void addFromTail(T value) {
DoubleNode<T> cur = new DoubleNode<>(value);
if (head == null) {
head = cur;
tail = cur;
}else{
cur.prev = tail;
tail.next = cur;
tail = cur;
}
}
public T popFromHead() {
if(head == null){
return null;
}
DoubleNode<T> cur = head;
if(head == tail){
head = null;
tail = null;
}else{
head = cur.next;
cur.next = null;
head.prev = null;
}
return cur.value;
}
public T popFromBottom() {
if (head == null) {
return null;
}
DoubleNode<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.prev;
tail.next = null;
cur.prev = null;
}
return cur.value;
}
public boolean isEmpty() {
return head == null;
}
}
|
问题3：双向链表实现栈
思路：只用一个头指针，加一个头指针往后移动,跟上面代码一样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T pop() {
return queue.popFromHead();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
|
问题4：数组实现栈
思路：一个数组+index控制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public static class ArrayToStack {
public int[] arr;
public int index;
public ArrayToStack(int size) {
arr = new int[size];
index = 0;
}
public void push(int value) {
if (index - 1 == arr.length - 1) {
throw new RuntimeException("栈满了，不能再添加了！");
}
arr[index] = value;
index++;
}
public int pop() {
if (index == 0) {
throw new RuntimeException("栈空了，不能再弹出了！");
}
int value = arr[index - 1];
index--;
return value;
}
}
|
问题5：数组实现队列
（比较差）思路1：用一个循环数组实现队列，用两个指针，一个begin指针，一个end指针，begin拿，end加，end到底就回到头，begin到底也回到头。
思路2：begin，end，size，用size管数组满没满，end，begin一样，这样就不需要管太多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| public static class MyQueue {
private int[] arr;
private int end;
private int begin;
private int size;
private final int limit;
public MyQueue(int limit) {
arr = new int[limit];
end = 0;
begin = 0;
size = 0;
this.limit = limit;
}
public void push(int value) {
if (size == limit) {
throw new RuntimeException("队列满了，不能再加了");
}
size++;
arr[end] = value;
end = nextIndex(end);
}
public int pop() {
if (size == 0) {
throw new RuntimeException("队列空了，不能再拿了");
}
size--;
int ans = arr[begin];
begin = nextIndex(begin);
return ans;
}
public boolean isEmpty() {
return size == 0;
}
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}
|
问题6：实现一个特殊的栈，在基本功能的基础上，实现返回栈中最小元素的功能
要求pop，push和getMin的时间复杂度都是O（1）
思路：准备两个栈，一个数据栈，一个最小栈，数据栈就是正常栈，最小栈如果是空就加入，如果不是空，如果加入的数据比最小栈小，压入最小值，如果比最小站相等或者等于都重复压入最小值，而不是新加入的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public static class MyStack {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack2() {
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum < this.getmin()) {
this.stackMin.push(newNum);
} else {
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("你的栈空了");
}
this.stackMin.pop();
return this.stackData.pop();
}
public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("你的栈空了");
}
return this.stackMin.peek();
}
}
|
问题7：如何用栈实现队列
思路：用两个栈一个push栈，一个pop栈，如果用户给数然后想要拿数，先把数放在push栈，导出的时候一次性把数导出导到pop栈再给出。
如果pop栈没有被拿完不能导数据，只有pop栈空了才能导数据！！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| public static class TwoStacksQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
private void pushToPop() {
if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}
public void add(int pushInt) {
stackPush.push(pushInt);
pushToPop();
}
public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("队列空!");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("队列空!");
}
pushToPop();
return stackPop.peek();
}
}
|
问题8：如何用队列实现栈
思路：用两个队列拼栈，一个A队列，一个B队列，来回互相导数，给到只剩一个数导出就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public static class TwoQueueStack<T> {
public Queue<T> queue;
public Queue<T> help;
public TwoQueueStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(T value) {
queue.offer(value);
}
public T poll() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public T peek() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
help.offer(ans);
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
|
递归
从一个例子理解递归
问题1：求arr中求最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static int getMax(int[] arr) {
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int L, int R) {
if (L == R) {
return arr[L];
}
int mid = L + ((R - L) >> 1);
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return Math.max(leftMax, rightMax);
}
|
当遇到递归行为是会将所有的入参和临时信息记录在系统栈里面，然后开始新的递归，直到递归结束。
分析迭代的思路，可以画图：
Master公式(子问题规模一致才可以用)
用来分析递归函数的时间复杂度
哈希表和有序表
哈希表的增删改查都是常数时间O(1)，不管内部数据量多大。
如果哈希表的key和value是基础类型，那么你存入的有多大，哈希表就有多大
如果是自定义类型，那么哈希表内部只会记录内存地址，两个都是8字节。
哈希表里面如果是基础类型是按值传递，如果是自定义类型是按引用传递
1
2
3
4
5
| hashMap.put(1, "我是1");
System.out.println(hashMap.containsKey(1));
System.out.println(hashMap.get(4));
hashMap.put(4, "他是4");
hashMap.remove(4);
|
有序表的增删改查是O(logN)，但是功能更加强大
TreeMap是用红黑树实现的。
有序表是按值传递
1
2
3
4
5
6
7
8
9
10
11
12
13
| treeMap.put(1, "我是1");
System.out.println(treeMap.containsKey(1));
System.out.println(treeMap.get(4));
treeMap.put(4, "他是4");
treeMap.remove(4);
System.out.println("新鲜：");
System.out.println(treeMap.firstKey());
System.out.println(treeMap.lastKey());
System.out.println(treeMap.floorKey(4));
System.out.println(treeMap.ceilingKey(4));
|
在自定义实现TreeMap的时候要自己自定义比较器，就是定义非内置类型如何比较
（可以自定义Compartor接口或者自定义比较器）
排序
归并排序
流程：一个数组排序，O（N x logN)，第一步求重点M，第二步L到M有序，第三步M+1到R有序，第四步合并。
合并的时候用两个指针，然后比较大小 拷贝到数组，最终返回
递归版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int L, int R) {
if (L == R) {
return;
}
int mid = L + ((R - L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int M, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = M + 1;
while (p1 <= M && p2 <= R) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= M) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
|
迭代版本
设计一个变量，步长，先0到1merge，2到3merge…..
然后步长+1,0到1和2到3meger…..
直到超过整个数组长度，停止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public static void mergeSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
int mergeSize = 1;
while (mergeSize < N) {
int L = 0;
while (L < N) {
int M = L + mergeSize - 1;
if (M >= N) {
break;
}
int R = Math.min(M + mergeSize, N - 1);
merge(arr, L, M, R);
L = R + 1;
}
if (mergeSize > N / 2) {
break;
}
mergeSize <<= 1;
}
}
|
问题1：小和问题
给你一个数组,每个数左边比他小的数加起来存在一个数组中，然后最后再全部加起来
思路： 有一个ans，左组小产生小和，看包括自己在内有多少个数比左组大，累加多少个左组，右组小或者相等不产生小和，并且先拷贝右组，不产生小和。
转换思路很重要：之前的思路是看左边有多少个数比自己小累加起来，现在转换思路当我来到i位置看右边多少个数比自己大，累加多少个i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int left, int right) {
if (left == right) {
return 0;
}
int mid = (left + ((right - left) >> 1));
int sum = process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right);
return sum;
}
public static int merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
int sum = 0;
while (p1 <= mid && p2 <= right) {
if (arr[p1] < arr[p2]) {
sum += arr[p1] * (right - p2 + 1);
temp[i++] = arr[p1++];
} else {
temp[i++] = arr[p2++];
}
}
while (p2 <= right) {
temp[i++] = arr[p2++];
}
while (p1 <= mid) {
temp[i++] = arr[p1++];
}
for (i = 0; i < temp.length; i++) {
arr[left++] = temp[i];
}
return sum;
}
public static int comparator(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res += arr[j] < arr[i] ? arr[j] : 0;
}
}
return res;
}
|
问题2：问一个数组中有多少个逆序对
假设一个左边的数和右边的数构成的数是降序关系，这样的数是逆序对。
思路：求一个数右边有多少个数比他小，如果那个数是右组，他不关心左边有多少个数比他小，只有当那个数是左组的时候才会关心右组有多少个数比他小，从右开始拷贝。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| public static int reversePair(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int left, int right) {
if(left == right) {
return 0;
}
int mid = left + ((right - left)>>1);
return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right);
}
public static int merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
int ans = 0;
while(p1 <= mid && p2 <= right) {
if(arr[p1] > arr[p2]) {
ans++;
temp[i++] = arr[p1++];
}
if (arr[p2] >= arr[p1]) {
temp[i++] = arr[p2++];
}
}
while(p1 <= mid) {
temp[i++] = arr[p1++];
}
while(p2 <= right) {
temp[i++] = arr[p2++];
}
for (int j = 0; j < temp.length; j++) {
arr[left++] = temp[j];
}
return ans;
}
|
问题3：一个数组有多少个数的右边有多少个数x2都不如那个数大？
本质mergesort把数组变成有序的东西，有序的东西方便我操作很多东西。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public static int reversePairs(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + ((r - l) >> 1);
return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static int merge(int[] arr, int L, int m, int r) {
int ans = 0;
int windowR = m + 1;
for (int i = L; i <= m; i++) {
while (windowR <= r && (long) arr[i] > (long) arr[windowR] * 2) {
windowR++;
}
ans += windowR - m - 1;
}
int[] help = new int[r - L + 1];
int i = 0;
int p1 = L;
int p2 = m + 1;
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return ans;
}
|
问题4：力扣原题（难）
327. 区间和的个数 - 力扣（LeetCode）
给定一个数组arr，两个整数lower和upper
返回arr中有多少个子数组的累加和在[lower,upper]范围上
前置知识：求累加和但是不要用累加。用前缀和，求累加和=两个前缀和相减，前缀和数组生成O（N）。
思路详解：首先问题是给一个数组，问有多少个子数组在[lower,upper]上？
暴力的方法：求0-0范围0-1范围，0-2范围，把每个子数组列出来，然后累加，然后比较有多少个在[lower,upper]上，这个方法是O(N三次方)。
现在我们转换思路：求以N结尾有多少个子数组在[lower,upper]上，也就是说以0结尾0-0有多少个子数组，以1结尾也就是，1-1,0-1有多少个在里面，以2结尾，2-2,1-2,0-2有多少个在里面…..
现在问题就变成了以N结尾有多少个子数组在[lower,upper]上。
举个例子：现在有个数组arr[0…2]有4个数，求0~2有多少个子数组，在[low,up]上，现在我们要求有多少个子数组以2结尾在[low,up]上，然后求以1结尾在[low,up]上，跟暴力类似，只不过转变了个思路。
再开发一下思路：现在我们知道这个数组的前缀和，并且知道整体的前缀和是X，要求以3结尾有多少个数在[low,up]上，可以转换成以2结尾有多少个前缀和在[x-up,x-low]上（为什么是这个范围，可以自己举例子验证一下，这里有点类似于找规律）。
现在问题又转换了变成了：我们已知前缀和数组sum[0~3]求每个数前有多少个子数组在[x-up,x-low]上。
怎么求呢，这里用MergeSort。把sum分为右组和左组，对于右组来说，求左组有多少个数落在[x-up，x-low]上！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| public static int countRangeSum(int[] nums, int lower, int upper) {
if (nums == null || nums.length == 0) {
return 0;
}
long[] sum = new long[nums.length];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
return process(sum, 0, sum.length - 1, lower, upper);
}
public static int process(long[] sum, int L, int R, int lower, int upper) {
if (L == R) {
return sum[L] >= lower && sum[L] <= upper ? 1 : 0;
}
int M = L + ((R - L) >> 1);
return process(sum, L, M, lower, upper) + process(sum, M + 1, R, lower, upper)
+ merge(sum, L, M, R, lower, upper);
}
public static int merge(long[] arr, int L, int M, int R, int lower, int upper) {
int ans = 0;
int windowL = L;
int windowR = L;
for (int i = M + 1; i <= R; i++) {
long min = arr[i] - upper;
long max = arr[i] - lower;
while (windowR <= M && arr[windowR] <= max) {
windowR++;
}
while (windowL <= M && arr[windowL] < min) {
windowL++;
}
ans += windowR - windowL;
}
long[] help = new long[R - L + 1];
int i = 0;
int p1 = L;
int p2 = M + 1;
while (p1 <= M && p2 <= R) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= M) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return ans;
}
|
快速排序
问题1：荷兰国旗问题
版本1：给你一个数组和一个数x，把小于等于x的放在数组左边，大于x的放在数组右边，并且不用辅助数组，而且时间复杂度是O(N),不要求左边或者右边有序。
思路：设计一个小于等于区域在-1位置，用R表示小于等于区的右边界，然后遍历，
情况1：当前数小于等于目标数，把当前数和小于等于区的下一个数交换，然后小于等于区向右扩，当前数跳下一个数
情况2：档期拿书大于目标数，当前数跳下一个数。
版本2：给你一个数组和一个数x，把小于等于x的放在数组左边，等于x的放在中间，大于x的放在数组右边，并且不用辅助数组，而且时间复杂度是O(N),不要求左边或者右边有序。
思路：两个区域小于区域，大于区域。
情况1：当前数小于目标数，当前数跟小于区域的下一个数交换，小于区域扩大，当前数跳下一个。
情况2：当前数等于目标数，当前数直接跳下一个数。
情况3：当前数大于目标数，当前数和大于区域前一个数交换，大于区域向左扩，当前数停在原地。（因为交换的数没有看过）
当遍历的时候跟大于区域的时候停。
在整个数组中，没有目标了，把最后一个数当目标，然后划分出小于区域，等于区域，大于区域，最后把目标数和大于区域的第一个数交换，返回等于区域的下标边界数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) {
return new int[] { -1, -1 };
}
if (L == R) {
return new int[] { L, R };
}
int less = L - 1;
int more = R;
int index = L;
while (index < more) {
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
swap(arr, index++, ++less);
} else {
swap(arr, index, --more);
}
}
swap(arr, more, R);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
|
快排1.0版本（递归）
思路：先找最后一个数，进行划分区域，然后把小于区域的最后一个数和大于区域的最后的数分别进行划分，周而复始
快排2.0版本（递归但是处理一批数）
思路：找最后一个数，进行划分区域，返回等于区域的下标，然后分别找小于区域和大于区域的最后的数分别进行划分，周而复始。
时间复杂度O(N*N)
快排3.0版本（随机快排）
思路：随机选择一个数，然后和最右边的数交换，然后其他的跟2.0版本的一样。
这时候O(NxlogN)（数学家证明了，收敛到这个）额外空间复杂度logN
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
public static void quickSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = netherlandsFlag(arr, L, R);
process(arr, L, equalArea[0] - 1);
process(arr, equalArea[1] + 1, R);
}
public static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) {
return new int[] { -1, -1 };
}
if (L == R) {
return new int[] { L, R };
}
int less = L - 1;
int more = R;
int index = L;
while (index < more) {
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
swap(arr, index++, ++less);
} else {
swap(arr, index, --more);
}
}
swap(arr, more, R);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
|
快拍非递归版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
public static class Op {
public int l;
public int r;
public Op(int left, int right) {
l = left;
r = right;
}
}
public static void quickSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
swap(arr, (int) (Math.random() * N), N - 1);
int[] equalArea = netherlandsFlag(arr, 0, N - 1);
int el = equalArea[0];
int er = equalArea[1];
Stack<Op> stack = new Stack<>();
stack.push(new Op(0, el - 1));
stack.push(new Op(er + 1, N - 1));
while (!stack.isEmpty()) {
Op op = stack.pop();
if (op.l < op.r) {
swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);
equalArea = netherlandsFlag(arr, op.l, op.r);
el = equalArea[0];
er = equalArea[1];
stack.push(new Op(op.l, el - 1));
stack.push(new Op(er + 1, op.r));
}
}
}
public static void quickSort3(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
swap(arr, (int) (Math.random() * N), N - 1);
int[] equalArea = netherlandsFlag(arr, 0, N - 1);
int el = equalArea[0];
int er = equalArea[1];
Queue<Op> queue = new LinkedList<>();
queue.offer(new Op(0, el - 1));
queue.offer(new Op(er + 1, N - 1));
while (!queue.isEmpty()) {
Op op = queue.poll();
if (op.l < op.r) {
swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);
equalArea = netherlandsFlag(arr, op.l, op.r);
el = equalArea[0];
er = equalArea[1];
queue.offer(new Op(op.l, el - 1));
queue.offer(new Op(er + 1, op.r));
}
}
}
|
