LRU缓存请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。
class LRUCache {
class Node{
int key;
int value;
Node pre;
Node next;
public Node(){}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private int size = 0;
private HashMap<Integer,Node> cache = new HashMap<>();
private int capacity = 0;
private Node head,tail;
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node();
tail = new Node();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private void removeNode(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void addToHead (Node node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node == null) {
Node newNode = new Node(key,value);
cache.put(key,newNode);
addToHead(newNode);
size++;
if (size > capacity) {
Node tail = removeTail();
cache.remove(tail.key);
}
} else {
node.value = value;
moveToHead(node);
}
}
private Node removeTail() {
Node res = tail.pre;
removeNode(res);
return res;//返回要在cache中删除掉node
}
}
- 时间复杂度：对于 put 和 get 都是O(1)。
- 空间复杂度：O(capacity)，因为哈希表和双向链表最多存储capacity+1个元素。
在圆内随机生成点
给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。
class Solution {
double rad, xc, yc;
public Solution(double radius, double x_center, double y_center) {
rad = radius;
xc = x_center;
yc = y_center;
}
public double[] randPoint() {
double x0 = xc - rad;
double y0 = yc - rad;
while(true) {
double xg = x0 + Math.random() * rad * 2;
double yg = y0 + Math.random() * rad * 2;
if (Math.sqrt(Math.pow((xg - xc) , 2) + Math.pow((yg - yc), 2)) <= rad)
return new double[]{xg, yg};
}
}
}
- 时间复杂度：期望时间复杂度为O(1)，但最坏情况下会达到 O(∞)（一直被拒绝）。
- 空间复杂度：O(1)。
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
int res = 0;
//把所有负数设为n+1，和[1,n]区分开
for (int i = 0; i < n; i++) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}
//将存在的整数i用复数打标记
for (int i = 0; i < n; i++) {
int cur = Math.abs(nums[i]);
if (cur <= n) {
nums[cur-1] = -Math.abs(nums[cur-1]);
}
}
//找到第一个没被负数标记的索引，i+1则是最小正整数
for (int i = 0; i < n; i++) {
if (nums[i] > 0)
return i + 1;
}
return n+1;
}
}
- 时间复杂度：O(N)，其中 N是数组的长度。
- 空间复杂度：O(1)。
多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。
class Solution {
public int majorityElement(int[] nums) {
int candidate = 0;
int count = 0;
for (int n : nums) {
if (count == 0)
candidate = n;
if (candidate == n) {
count++;
} else {
count--;
}
}
return candidate;
}
}
时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
空间复杂度：O(1)。只需要常数级别的额外空间。
IP 到 CIDR
给你一个起始IP地址 ip 和我们需要覆盖的IP地址数量 n 。你的目标是使用 尽可能少的CIDR块 来 覆盖范围 [ip, ip + n - 1] 内的所有IP地址 。不应该覆盖范围之外的其他IP地址。
class Solution {
public List<String> ipToCIDR(String ip, int n) {
long start = ipToLong(ip);
List<String> ans = new ArrayList();
while (n > 0) {
int mask = Math.max(33 - bitLength(Long.lowestOneBit(start)),
33 - bitLength(n));
ans.add(longToIP(start) + "/" + mask);
start += 1 << (32 - mask);
n -= 1 << (32 - mask);
}
return ans;
}
private long ipToLong(String ip) {
long ans = 0;
for (String x: ip.split("\\.")) {
ans = 256 * ans + Integer.valueOf(x);
}
return ans;
}
private String longToIP(long x) {
return String.format("%s.%s.%s.%s",
x >> 24, (x >> 16) % 256, (x >> 8) % 256, x % 256);
}
private int bitLength(long x) {
if (x == 0) return 1;
int ans = 0;
while (x > 0) {
x >>= 1;
ans++;
}
return ans;
}
}
- 时间复杂度：O(N)。其中 N 表示的是
nums的长度 - 空间复杂度：O(1)。
至少有 K 个重复字符的最长子串
class Solution {
public int longestSubstring(String s, int k) {
int ret = 0;
int n = s.length();
for (int t = 1; t <= 26; t++) {
int l = 0, r = 0;
int[] cnt = new int[26];
int tot = 0;
int less = 0;
while (r < n) {
cnt[s.charAt(r) - 'a']++;
if (cnt[s.charAt(r) - 'a'] == 1) {
tot++;
less++;
}
if (cnt[s.charAt(r) - 'a'] == k) {
less--;
}
while (tot > t) {
cnt[s.charAt(l) - 'a']--;
if (cnt[s.charAt(l) - 'a'] == k - 1) {
less++;
}
if (cnt[s.charAt(l) - 'a'] == 0) {
tot--;
less--;
}
l++;
}
if (less == 0) {
ret = Math.max(ret, r - l + 1);
}
r++;
}
}
return ret;
}
}
- 时间复杂度：O(N⋅∣Σ∣+∣Σ∣ *∣Σ∣ )，其中 N 为字符串的长度，Σ 为字符集，本题中字符串仅包含小写字母，因此 ∣Σ∣=26。我们需要遍历所有可能的 t，共 ∣Σ∣ 种可能性；内层循环中滑动窗口的复杂度为 O(N)，且初始时需要 O(∣Σ∣) 的时间初始化 cnt 数组。
- 空间复杂度：O(∣Σ∣)。
堆排序 Heapsort
class Solution {
public void heapSort(int[] nums){
if(nums==null||nums.length<2){
return;
}
for(int i=0;i<nums.length;i++){
heapInsert(nums,i);
}
int heapSize = nums.length;
swap(nums,0,--heapSize);
while(heapSize>0){
heapify(nums,0,heapSize);
swap(nums,0,--heapSize);
}
}
//某个数处在index，往上继续移动
private void heapInsert(int[] nums,int index){
while(nums[(index-1)/2]<nums[index]){
swap(nums,(index-1)/2,index);
index = (index-1)/2;
}
}
private void swap(int[] nums,int left,int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
//和左、右节点比较，小于则往下换
private void heapify(int[] nums,int index,int heapSize){
int left = index*2+1;//从上往下移动,左孩子下标
while(left<heapSize){
int largest=left+1<heapSize&&nums[left+1]>nums[left]?left+1:left;
largest=nums[largest]>nums[index]?largest:index;
if(largest==index){
break;
}
swap(nums,largest,index);
index = largest;
left=index*2+1;
}
}
}
数组中的第K个最大元素 快排 quicksort
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
class Solution {
public int findKthLargest(int[] nums, int k) {
quickSort(nums,0,nums.length-1);
return nums[nums.length-k];
}
private void quickSort(int[] nums,int left,int right){
if(left<right){
swap(nums,(int)(left+Math.random()*(right-left+1)),right);
int[] res = partition(nums,left,right);
quickSort(nums,left,res[0]-1);
quickSort(nums,res[1]+1,right);
}
}
private void swap(int[] nums,int left,int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
private int[] partition(int[] nums,int left,int right){
int less = left-1; //小于区域
int more = right; //大于区域
while(left<more){
if(nums[left]<nums[right]){
swap(nums,++less,left++);
}else if(nums[left]>nums[right]){
swap(nums,--more,left);
}else{
left++;
}
}
swap(nums,more,right);
return new int[]{less+1,more};//返回相等区域
}
}