LRU 缓存的魔力

LRU 缓存的魔力

场景

假设这么一个情况,当你需要多次展示同一个图片的时候,如果你重复从硬盘中加载图片的话,那么会造成资源的浪费,甚至可能会OOM.

这个时候我们可以使用 cache 来避免这种情况,我们只从硬盘中加载一次到内存中,然后在需要的时候反复使用这个照片.

但是,当这个 cache 里的资源已经装满的时候,那么我们就必须移除cache里面的某些数据,来给要加入的数据腾出空间.

解决方案

在这种情况下,我们应该选择移除哪些资源才是最有优的呢?显而易见的,我们应该移除之后不会用到的资源,还有就是间隔最久才会用到的资源.这里有一个详细的最优算法如下:
$$
T = m * T_m + T_h + E
$$
其中:

T = 平均内存引用时间

Read More

贪婪算法

贪婪算法

[TOC]

贪婪算法(Greedy Algorithm)也叫算贪心法,贪婪法.它是一个遵循启发式解决问题的算法范式.它的核心思想就是通过在每一步的选择中都选用当前步骤下最优的选择,期望结果是最优的算法.如 旅行推销员问题.

贪婪算法尤其适用于有最优子结构的问题中,最优子结构的意思是局部的最优解可以导出全局的最优解.贪婪算法与动态规划 的不同在于贪婪算法对每一个子问题都作出选择,不能回退;动态规划则会保存以前的运算结果,根据以前的结果对当前进行选择,可以回退.

贪婪算法可以解决一些最优化(如最大值最小值等)问题,比如求图中的最小生成树、求哈夫曼编码…其他大多数的情况都不适用贪婪算法,一旦一个问题可以使用贪婪算法来解决,那么贪婪算法一般是解决这个问题的最好办法.由于贪婪算法的高效性以及其答案比较接近最有结果,也可以作为辅助算法或直接解决一些结果要求不那么精确的问题.

原理

步骤

Read More

LeetCode 7. 数字反转

[Chinese ver]

7. Reverse Integer

颠倒一个 integer 的前后位数。

例子: x = 123, return 321
例子: x = -123, return -321

注意:
输入是一个32位的有符号 integer . 当颠倒的 interger 溢出的时候你的函数应该返回0。


Read More

LeetCode 7. Reverse Integer

[English ver]Easy

7. Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.


Read More

LeetCode 6. 锯齿形转换

[Chinese ver]

6. ZigZag Conversion

字符串”PAYPALISHIRING”是通过一个如下给定行数的锯齿模式书写的:(你可能想要使用一个固定的字体来更好的显示它)

1
2
3
P A H N
A P L S I I G
Y I R

然后一行一行的读取这个字符串:”PAHNAPLSIIGYIR”
编写代码实现获取一个字符串然后根据给出的行数来实现这个锯齿转换:

1
string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) 应该返回 “PAHNAPLSIIGYIR”.

Read More

LeetCode 6. ZigZag Conversion

[English ver]

6. ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3
P A H N
A P L S I I G
Y I R

And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

1
string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.


Read More

LeetCode 5.Longest Palindromic Substring

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:

1
2
3
Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

Example:

1
2
3
Input: "cbbd"
Output: "bb"


I have misunderstood the meaning of the word palindrome , i thought it was the meaning of repeat,finally i know that it was the meaning of a string which is the same when you look from left to right and from right to left.
According to that , we know it has two situation,one the length is odd , another is even .

Read More

LeetCode 5.最长的回文字符串

5. Longest Palindromic Substring

给定一个字符串s,找出其中最长的回文格式的子字符串。你可以假设长度的最大值为1000.

Example:

1
2
3
Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

Example:

1
2
3
Input: "cbbd"
Output: "bb"

一开始以为palindrome是重复的意思,走了很大的弯路,后来才知道指的是回文格式,就是一个顺着读和反过来读都一样的字符串。
由此可知他有两种情况,一种是奇数的情况,中间的一个字符独立,其余的字符以中间为轴两两对应。另一种是偶数的情况,所有的字符都以中间为轴两两对应。

Read More

LeetCode 4. Median of Two Sorted Arrays [English ver]

[English ver]

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

1
2
3
4
5
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
1
2
3
4
5
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

Read More

LeetCode 4. Median of Two Sorted Arrays [Chinese ver]

[Chinese ver]

4. Median of Two Sorted Arrays

这里有两个有序数组nums1和nums2,他们各自的大小为m和n.
找到这两个数组的中间值,总的时间复杂度应该为O(log (m+n)).

1
2
3
4
Example 1:
nums1 = [1, 3]
nums2 = [2]
中间值是 2.0
1
2
3
4
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
中间值是 (2 + 3)/2 = 2.5

方法一:

首先尝试了一种比较笨的方法

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
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//需要几个数值
int needNum = 0;
//数值位置
int needIndex = 0;
//中间值
double median = 0;
int big = 0;
int stand = 0;
//合成的数组
int[] insertnum ;
int m = nums1.length;
int n = nums2.length;
if((m+n)%2==0){
needNum = 2;
needIndex = (m+n)/2-1;
}else{
needNum=1;
needIndex = (m+n)/2;
}
insertnum = new int[m+n];
//nums1的下标
int j =0;
//nums2的下标
int k = 0;
for(int i =0;i<m+n;i++){
if(k==n){
insertnum[i] = nums1[j];
j++;
}
else if(j==m){
insertnum[i] = nums2[k];
k++;
}else if(nums1[j]>nums2[k]){
insertnum[i] = nums2[k];
k++;
}else{
insertnum[i] = nums1[j];
j++;
}
}
if(needNum == 1){
median = Double.valueOf(insertnum[needIndex]);
}else{
median = Double.valueOf(insertnum[needIndex]+insertnum[needIndex+1]) /2.0;
}
return median;
}
}

Read More
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×