|
目录
1、leetcode169多数元素
2、leetcode160相交链表
3、leetcode322零钱兑换
4、leetcode75颜色分类
5、leetcode142环形链表 II
6、leetcode234回文链表
7、leetcode64最小路径和
8、leetcode146LRU 缓存
9、leetcode72编辑距离
10、leetcode347前 K 个高频元素
1、leetcode169多数元素
/**
时间复杂度 O(N)
哈希表的方式
先记录出现次数，然后去比对。
其实这道题的思想是求众数
*/
class Solution {
private Map<Integer, Integer> countNums(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!counts.containsKey(num)) {
counts.put(num, 1);
} else {
counts.put(num, counts.get(num) + 1);
}
}
return counts;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> counts = countNums(nums);
Map.Entry<Integer, Integer> majorityEntry = null;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
majorityEntry = entry;
}
}
return majorityEntry.getKey();
}
}
2、leetcode160相交链表
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode cur1 = headA;
ListNode cur2 = headB;
int n = 0;
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
// n : 链表1长度减去链表2长度的值
cur1 = n > 0 ? headA : headB; // 谁长，谁的头变成cur1
cur2 = cur1 == headA ? headB : headA; // 谁短，谁的头变成cur2
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
}
3、leetcode322零钱兑换
/**
记忆化搜索
时间复杂度O(Sn)
*/
public class Solution {
public int coinChange(int[] coins, int amount) {
if (amount < 1) {
return 0;
}
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int rem, int[] count) {
if (rem < 0) {
return -1;
}
if (rem == 0) {
return 0;
}
if (count[rem - 1] != 0) {
return count[rem - 1];
}
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, rem - coin, count);
if (res >= 0 && res < min) {
min = 1 + res;
}
}
count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return count[rem - 1];
}
}
4、leetcode75颜色分类
/**
荷兰国旗问题
这道题可以用双指针实现
时间复杂度O(N)
*/
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int p0 = 0, p2 = n - 1;
for (int i = 0; i <= p2; ++i) {
while (i <= p2 && nums[i] == 2) {
int temp = nums[i];
nums[i] = nums[p2];
nums[p2] = temp;
--p2;
}
if (nums[i] == 0) {
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
++p0;
}
}
}
}
/**
时间复杂度 O(N)
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
ListNode slow = head.next; // n1 -> slow
ListNode fast = head.next.next; // n2 -> fast
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
// slow fast 相遇
fast = head; // n2 -> walk again from head
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
6、leetcode234回文链表
/**
时间复杂度O(N)
*/
class Solution {
public boolean isPalindrome(ListNode head) {
// 没有node 或者 有1个node 进入if
if (head == null || head.next == null) {
return true;
}
// 1 2 3 4 5 6
ListNode n1 = head;
ListNode n2 = head;
while (n2.next != null && n2.next.next != null) { // find mid node
n1 = n1.next; // n1 -> mid
n2 = n2.next.next; // n2 -> end
}
// n1 中点 或者 上中点
// n2 变 中点或者上中点的右一个
n2 = n1.next; // n2 -> right part first node
n1.next = null; // mid.next -> null
ListNode n3 = null;
while (n2 != null) { // right part convert
n3 = n2.next; // n3 -> save next node
n2.next = n1; // next of right node convert
n1 = n2; // n1 move
n2 = n3; // n2 move
}
// n3 保留
n3 = n1; // n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
while (n1 != null && n2 != null) { // check palindrome
if (n1.val != n2.val) {
res = false;
break;
}
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
// 旋转回去
n1 = n3.next;
n3.next = null;
while (n1 != null) { // recover list
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
}
7、leetcode64最小路径和
/**
时间复杂度 O(M * N) M N 分别为 行数 和 列数
*/
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length, columns = grid[0].length;
int[][] dp = new int[rows][columns];
dp[0][0] = grid[0][0];
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[rows - 1][columns - 1];
}
}
8、leetcode146LRU 缓存
// class LRUCache {
// public LRUCache(int capacity) {
// }
// public int get(int key) {
// }
// public void put(int key, int value) {
// }
// }
public class LRUCache {
public LRUCache(int capacity) {
cache = new MyCache<>(capacity);
}
private MyCache<Integer, Integer> cache;
public int get(int key) {
Integer ans = cache.get(key);
return ans == null ? -1 : ans;
}
public void put(int key, int value) {
cache.set(key, value);
}
public static class Node<K, V> {
public K key;
public V value;
public Node<K, V> last;
public Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public static class NodeDoubleLinkedList<K, V> {
private Node<K, V> head;
private Node<K, V> tail;
public NodeDoubleLinkedList() {
head = null;
tail = null;
}
// 现在来了一个新的node，请挂到尾巴上去
public void addNode(Node<K, V> newNode) {
if (newNode == null) {
return;
}
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.last = tail;
tail = newNode;
}
}
// node 入参，一定保证！node在双向链表里！
// node原始的位置，左右重新连好，然后把node分离出来
// 挂到整个链表的尾巴上
public void moveNodeToTail(Node<K, V> node) {
if (tail == node) {
return;
}
if (head == node) {
head = node.next;
head.last = null;
} else {
node.last.next = node.next;
node.next.last = node.last;
}
node.last = tail;
node.next = null;
tail.next = node;
tail = node;
}
public Node<K, V> removeHead() {
if (head == null) {
return null;
}
Node<K, V> res = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = res.next;
res.next = null;
head.last = null;
}
return res;
}
}
public static class MyCache<K, V> {
private HashMap<K, Node<K, V>> keyNodeMap;
private NodeDoubleLinkedList<K, V> nodeList;
private final int capacity;
public MyCache(int cap) {
keyNodeMap = new HashMap<K, Node<K, V>>();
nodeList = new NodeDoubleLinkedList<K, V>();
capacity = cap;
}
public V get(K key) {
if (keyNodeMap.containsKey(key)) {
Node<K, V> res = keyNodeMap.get(key);
nodeList.moveNodeToTail(res);
return res.value;
}
return null;
}
// set(Key, Value)
// 新增 更新value的操作
public void set(K key, V value) {
if (keyNodeMap.containsKey(key)) {
Node<K, V> node = keyNodeMap.get(key);
node.value = value;
nodeList.moveNodeToTail(node);
} else { // 新增！
Node<K, V> newNode = new Node<K, V>(key, value);
keyNodeMap.put(key, newNode);
nodeList.addNode(newNode);
if (keyNodeMap.size() == capacity + 1) {
removeMostUnusedCache();
}
}
}
private void removeMostUnusedCache() {
Node<K, V> removeNode = nodeList.removeHead();
keyNodeMap.remove(removeNode.key);
}
}
}
9、leetcode72编辑距离
/**
时间复杂度 O ( M *N )
*/
class Solution {
public int minDistance(String word1, String word2) {
return minCost1(word1,word2,1,1,1);
}
public static int minCost1(String s1, String s2, int ic, int dc, int rc) {
if (s1 == null || s2 == null) {
return 0;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int N = str1.length + 1;
int M = str2.length + 1;
int[][] dp = new int[N][M];
// dp[0][0] = 0
for (int i = 1; i < N; i++) {
dp[i][0] = dc * i;
}
for (int j = 1; j < M; j++) {
dp[0][j] = ic * j;
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
dp[i][j] = dp[i - 1][j - 1] + (str1[i - 1] == str2[j - 1] ? 0 : rc);
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
}
}
return dp[N - 1][M - 1];
}
}
/**
时间复杂度 O( N *LOGK)
堆的实现
快速排序实现的时间复杂度会是O(N2)
*/
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 记录出现次数
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1]; //小根堆
}
});
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
}
|