如何判断链表有环
给定一个链表，判断链表中是否有环。
循环判断
从头节点开始，依次遍历单链表中的每一个节点。没遍历一个新节点，就从头检查新节点之前的所有节点，查看是否相同。若存在相同节点证明链表是有环的。
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
int total = 2;
ListNode cur = head.next;
while (cur != null) {
int start = 1;
ListNode node = head;
while (node != cur) {
node = node.next;
start++;
}
if (start != total) return true;
total++;
cur = cur.next;
}
return false;
}
}该算法遍历一遍的同时，内部也在从头遍历一次，所以时间复杂度为O(n^2)
没有创造新的内存空间，空间复杂度为O(1)
Set集合
创建一个Set集合，遍历链表并将节点加入Set集合，当出现重复的元素，即加入Set集合失败即代表有环出现。
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
Set<ListNode> set = new HashSet<>();
while (head != null) {
if (!set.add(head)) return true;
head = head.next;
}
return false;
}
}该算法是遍历一遍链表，所以时间复杂度为O(n)
将所有节点加入Set集合存储，空间复杂度也为O(n)
双指针
使用两个指针，一个每次前进两个，一个每次前进一个，若是出现两个指针指向一个节点，代表链表有环。因为快指针提前入环，总会追上慢指针。
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) return true;
}
return false;
}
}只用循环一次链表，所以时间复杂度为O(n)
不用创建额外的空间，所以空间复杂度为O(1)
求出环的长度
快慢节点重合的时候，在继续前进并记录前进的次数，下次重合，就是快指针（速度是慢指针的两倍）比慢指针多走了一圈，可以理解为前进的次数就是环的长度。
public class Solution {
public ListNode getCycleLength(ListNode head) {
if (head == null || head.next == null) return false;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
int length = 1;
fast = fast.next.next;
slow = slow.next;
while (fast != slow) {
fast = fast.next.next;
slow = slow.next;
length++;
}
return length;
}
}判断入环点
假设链表头节点到入环点的距离是D，从入环点到两个指针首次相遇点为S1，从两个指针首次相遇点到入环点的距离为S2。
设慢指针的移动速度为一个节点，快指针的移动速度为两个节点。
故两个指针首次相遇时，两个指针所走的距离如下
慢指针行走的距离为D + S1
快指针的速度是慢指针的两倍，所以相当于比慢指针多走了N圈，故行走的距离为D + S1 + N * (S1 + S2)
因为快指针的速度是慢指针的两倍，所以快指针的行走距离应该为慢指针的两倍，所以有
2(D + S1) = D + S1 + N * (S1 + S2)
经过整理可以得到
D = (N - 1)(S1 + S2) + S2
也就是说，链表头节点到入环点的的距离相当于从首次相遇点绕环N - 1圈后再回到入环点的距离。
故从头节点出发，与首次相遇点出发，两者均以一个节点的速度，两者相遇点即为入环点。
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) return null;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
fast = head;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}最小栈的实现
设计一个支持
push，pop，top操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
这里需要使用到辅助栈来实现，将每次最小的元素都放到辅助栈中，若即入栈的元素比最小元素小，辅助栈中就放入该最小元素，否则就放入之前最小的元素。当栈出栈后，辅助栈也跟着出栈。
class MinStack {
Stack<Integer> min;
Stack<Integer> stack;
public MinStack() {
stack = new Stack<>();
min = new Stack<>();
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(val);
min.push(val);
} else {
stack.push(val);
if (val < min.peek()) {
min.push(val);
} else {
min.push(min.peek());
}
}
}
public void pop() {
if (stack.isEmpty()) {}
stack.pop();
min.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/如何求出最大公约数
求出两个正整数的最大公约数。
枚举
从较小整数的一半开始遍历到2，首次出现了两个正整数都整除的数，则该数就是两个正整数的最大公约数。
public static int getGreatestCommonDivisor(int a, int b) {
int max = Math.max(a, b);
int min = Math.min(a, b);
if (max % min == 0) {
return min;
}
for (int i = min / 2; i > 1; i--) {
if (min % i == 0 && max % i == 0) {
return i;
}
}
return 1;
}时间复杂度为O(min(a, b))
辗转相除法（欧几里得算法）
这个方法基于一个定理：
两个正整数a和b（a > b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
public static int getGreatestCommonDivisor(int a, int b) {
int max = Math.max(a, b);
int min = Math.min(a, b);
if (max % min == 0) {
return min;
}
return getGreatestCommonDivisor(max % min, min);
}时间复杂度近似为O(log(max(a, b))，当两个正整数很大的时候，a % b的计算性能很差。
更相减损术
两个正整数a和b（a > b），它们的最大公约数等于a - b的差值c和较小数b的最大公约数。
public static int getGreatestCommonDivisor(int a, int b) {
if (a == b) {
return a;
}
int max = Math.max(a, b);
int min = Math.min(a, b);
return getGreatestCommonDivisor(max - min, min);
}避免了大数取模的计算，但是算法性能不稳定，最坏的时间复杂度为O(max(a, b))
更优算法
- 当a和b均为偶数时，gcd(a,b) = 2 * gcd(a / 2, b / 2) = 2 * gcd(a >> 1, b >> 1) = gcd(a >> 1, b >> 1) << 1;
- 当a为偶数，b为奇数时，gcd(a, b) = gcd(a / 2, b) = gcd(a >> 1, b);
- 当a为奇数，b为偶数时，gcd(a, b) = gcd(a, b / 2) = gcd(a, b >> 1);
- 当a和b均为奇数时，先利用更相减损术运算一次，gcd(a, b) = gcd(b, a - b)，此时a - b必是偶数，然后进行上面情况的运算。
public static int getGreatestCommonDivisor(int a, int b) {
if (a == b) {
return a;
}
if ((a & 1) == 0 && (b & 1) == 0) {
return getGreatestCommonDivisor(a >> 1, b >> 1) << 1;
} else if ((a & 1) == 0 && (b & 1) != 0) {
return getGreatestCommonDivisor(a >> 1, b);
} else if ((a & 1) != 0 && (b & 1) == 0) {
return getGreatestCommonDivisor(a, b >> 1);
} else {
int max = Math.max(a, b);
int min = Math.min(a, b);
return getGreatestCommonDivisor(max - min, min);
}
}进行简化之后为
public static int getGreatestCommonDivisor(int a, int b) {
if (a == b) {
return a;
}
if ((a & 1) == 0 && (b & 1) == 0) {
return getGreatestCommonDivisor(a >> 1, b >> 1) << 1;
} else if ((a & 1) == 0) {
return getGreatestCommonDivisor(a >> 1, b);
} else if ((b & 1) == 0) {
return getGreatestCommonDivisor(a, b >> 1);
} else {
int max = Math.max(a, b);
int min = Math.min(a, b);
return getGreatestCommonDivisor(max - min, min);
}
}这是更相减损法与位运算的结合方法，算法性能稳定，而且使用了位运算，时间复杂度为O(log(max(a, b)))
判断一个数是否为2的整数次幂
判断一个正整数是否为2的整数次幂
枚举
计算出2的整数次幂，依次递增，若是出现了大于该数的2次幂（并没有等于的），就证明该数不是2的整数次幂。
class Solution {
public boolean isPowerOfTwo(int n) {
int num = 1;
while (num <= n) {
if (num == n) return true;
num = num << 1;
}
return false;
}
}算法的时间复杂度为O(logn)。
n & (n - 1) == 0
每一个2的整数次幂转换为二进制，都是1开头后面都是0的数串。
将该整数次幂减一，就得到二进制全为1的数串。
这两个数取按位与运算，就会出现每一位数都不一样，所以结果为0。
所以不为0的就不是2的整数次幂了。
class Solution {
public boolean isPowerOfTwo(int n) {
return (n & n - 1) == 0;
}
}n & -n == n
n & -n可以得到最低位的1的位置，即最低位为1其余全是0的数串，如果是2的整数次幂的话，那么该数串其实表示的就是本身。
class Solution {
public boolean isPowerOfTwo(int n) {
return (n & -n) == n;
}
}无序数组排序后的最大相邻差
有一个无序整数型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？
排序后求最大差值
public static int getMaxSortedDistance(int[] array) {
Arrays.sort(array);
int max = -1;
for (int i = 1; i < array.length; i++) {
int temp = array[i] - array[i - 1];
if (temp > max) {
max = temp;
}
}
return max;
}将数组进行快速排序O(nlogn)，然后进行遍历O(n)，所以总的时间复杂度为O(nlogn)
空间复杂度就是该数组O(n)
计数排序
使用计数排序，找出新数组最多连续出现0的次数加1，就是最大相邻差了。
当数组的数差值不是很大的情况下，效率很高，但是差值很大的情况，数组的长度会很大。
public static int getMaxSortedDistance(int[] array) {
// 求出数组的最大值和最小值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
int d = max - min;
// 最大值和最小值相等，证明数组的所有数相等
if (d == 0) {
return 0;
}
// 计数排序
int[] arr = new int[d + 1];
for (int i : array) {
arr[i - min]++;
}
int maxDistance = 0;
// 寻找最长连续的0
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
int temp = i;
while (arr[temp] == 0) {
temp++;
}
if (temp - i > maxDistance) {
maxDistance = temp - i;
}
}
}
return maxDistance + 1;
}桶排序
记录桶内的最大和最小值，统计出每一个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差即为题目所求，故时间复杂度为O(n)
public static int getMaxSortedDistance(int[] array) {
// 求出数组的最大值和最小值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
int d = max - min;
// 最大值和最小值相等，证明数组的所有数相等
if (d == 0) {
return 0;
}
// 初始化桶
int bucketNum = array.length;
Bucket[] buckets = new Bucket[bucketNum];
Arrays.fill(buckets,new Bucket());
// 遍历原始数组，确定每个桶的最大值和最小值
for (int i : array) {
int index = ((i - min) * (bucketNum - 1) / d);
if (buckets[index].min == null || buckets[index].min > i) {
buckets[index].min = i;
}
if (buckets[index].max == null || buckets[index].max < i) {
buckets[index].max = i;
}
}
// 遍历桶，找到最大差值
int leftMax = buckets[0].max;
int maxDistance = 0;
for (int i = 1; i < buckets.length; i++) {
if (buckets[i].min == null) {
continue;
}
if (buckets[i].min - leftMax > maxDistance) {
maxDistance = buckets[i].min - leftMax;
}
leftMax = buckets[i].max;
}
return maxDistance;
}
private static class Bucket {
Integer min;
Integer max;
}用栈实现队列
用栈来模拟一个队列，要求实现队列的两个基本操作：入队和出队。
使用一个栈明显是不能实现队列的，所以需要一个辅助栈。设这两个栈为a和b。
a栈用来存储入队的元素，入队的元素直接压入a栈就好。
b栈用来存储出队的元素，出队的元素就直接推出b栈就好。
当b栈是空的，就将a栈的所有元素出栈压入a栈，这样出栈的顺序就相反了，即符合先进先出了。
class CQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(!stack2.isEmpty()) {
return stack2.pop();
}
if(stack1.isEmpty()) {
return -1;
}
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/删除k个数字后的最小值
给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数尽可能小。应该如何选取被去掉的数字？
从左往右，第一位大于它右边的数，将该数删了就会让整个数值降低。
public static String removeKDigits(String num, int k) {
int newLength = num.length() - k;
char[] stack = new char[num.length()];
int top = 0;
for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);
while (top > 0 && stack[top - 1] > c && k > 0) {
top -= 1;
k -= 1;
}
stack[top++] = c;
}
int offset = 0;
while (offset < newLength && stack[offset] == '0') {
offset++;
}
return offset == newLength ? "0" : new String(stack,offset,newLength - offset);
}如何实现大整数相加
给出两个很大的正整数，要求实现程序求出两个整数之和。
public static String bigNumberSum(String bigNumberA, String bigNumberB) {
int maxLen = Math.max(bigNumberA.length(), bigNumberB.length()) + 1;
// 将两个大数逆序存储到数组中
int[] arrA = new int[maxLen];
for (int i = 0; i < bigNumberA.length(); i++) {
arrA[i] = bigNumberA.charAt(bigNumberA.length() - i - 1) - '0';
}
int[] arrB = new int[maxLen];
for (int i = 0; i < bigNumberB.length(); i++) {
arrB[i] = bigNumberB.charAt(bigNumberB.length() - i - 1) - '0';
}
// 进行运算
int[] res = new int[maxLen];
for (int i = 0; i < res.length; i++) {
int temp = res[i];
temp += arrA[i] + arrB[i];
if (temp >= 10) {
temp -= 10;
res[i + 1]++;
}
res[i] = temp;
}
// 将结果逆序
StringBuilder str = new StringBuilder();
boolean findFirst = false;
for (int i = res.length - 1; i >= 0; i--) {
if (!findFirst) {
if (res[i] == 0) {
continue;
}
findFirst = true;
}
str.append(res[i]);
}
return str.toString();
}金矿问题
很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如又得金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人来挖掘…
如果参与挖矿的工人的总数是10.每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要用程序求出，要想得到尽可能多的黄金，应该选取挖取那几座金矿？
这题就是一道背包问题，根据题意可知这是01背包的问题，有两种状态转移的情况，选或者是不选。
/**
* @param w 工人数量
* @param p 金矿开采所需的工人数量
* @param g 金矿储量
*/
public static int getBestGoldMining(int w, int[] p, int[] g) {
int[] res = new int[w + 1];
for (int i = 1; i <= g.length; i++) {
for (int j = w; j >= 1; j--) {
if (j >= p[i - 1]) {
res[j] = Math.max(res[j],res[j - p[i - 1]] + g[i - 1]);
}
}
}
return res[w];
}寻找缺少的整数
在一个无序数组里有99个不重复的正整数，范围从1到100，唯独缺少1个1~100中的整数。如何找出整个缺少的整数。
哈希表
创建一个哈希表，将1到100这100个数全部存入key中，遍历整个数组，将存在的key都删掉，剩下的key就是缺少的整数。
public static int getBestGoldMining(int[] arr) {
Map<Integer, Integer> map = new HashMap<>(100);
for (int i = 1; i <= 100; i++) {
map.put(i,i);
}
for (int i : arr) {
map.remove(i);
}
int res = 0;
for (int key : map.keySet()) {
res = key;
}
return res;
}先排序后寻找
将数组进行排序，然后逐个寻找。
public static int getBestGoldMining(int[] arr) {
Arrays.sort(arr);
if (arr[0] != 1) {
return 0;
}
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] + 1 != arr[i + 1]) {
return arr[i] + 1;
}
}
return 100;
}求和
计算出1~100的和，然后减去数组中元素的和，剩下的就是所缺少的整数了。
public static int getBestGoldMining(int[] arr) {
int res = 5050;
for (int i : arr) {
res -= i;
}
return res;
}求只出现一次的数
一个无序数组里有若干个正整数，范围是1~100，其中99个整数都出现了偶数次，只有一个整数出现了奇书次，如何找到这个出现奇数次的整数？
可以将数与数出现的次数当成Key和Value放入哈希表，然后寻找出现次数为1的，和上述哈希表的做法差不多，就不深入了。
这里可以使用异或运算，先了解异或运算的规律。
- 两个相同的数异或，结果等于0
- 任何数与0异或，结果等于本身
- 异或运算符合交换律
故将数组中的数进行异或，偶数次的数异或会变成0，奇数次的数就会留着。
public static int getBestGoldMining(int[] arr) {
int res = 0;
for (int i : arr) {
res ^= i;
}
return res;
}LRU（最近最少使用算法）
package com.yww;
import java.util.HashMap;
/**
* @ClassName LRUCache
* @author yww
*/
public class LRUCache {
/**
* 头节点
*/
private Node head;
/**
* 尾节点
*/
private Node end;
/**
* 缓存的个数
*/
private int limit;
/**
* 哈希表缓存
*/
private HashMap<String, Node> map;
class Node {
public Node pre;
public Node next;
public String key;
public String value;
Node(String key, String value) {
this.key = key;
this.value = value;
}
}
public LRUCache(int limit) {
this.limit = limit;
map = new HashMap<>();
}
/**
* 通过key获取缓存节点
*/
public String get(String key) {
Node node = map.get(key);
if (node == null) {
return null;
}
refreshNode(node);
return node.value;
}
/**
* 放入缓存，若key存在，更新value值
*/
public void put(String key, String value) {
Node node = map.get(key);
if (node == null) {
if (map.size() >= limit) {
String oldKey = removeNode(head);
map.remove(oldKey);
}
node = new Node(key, value);
addNode(node);
map.put(key,node);
} else {
node.value = value;
refreshNode(node);
}
}
/**
* 通过key删除缓存
*/
public void remove(String key) {
Node node = map.get(key);
removeNode(node);
map.remove(key);
}
/**
* 刷新被访问的节点
*/
private void refreshNode(Node node) {
if (node == end) {
return;
}
removeNode(node);
addNode(node);
}
/**
* 删除节点
*/
private String removeNode(Node node) {
if (node == head && node == end) {
head = null;
end = null;
} else if (node == end) {
end = end.pre;
end.next = null;
} else if (node == head) {
head = head.next;
head.pre = null;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
return node.key;
}
/**
* 尾部插入节点
*/
private void addNode(Node node) {
if (end != null) {
end.next = node;
node.pre = end;
node.next = null;
}
end = node;
if (head == null) {
head = node;
}
}
}