LeetCode 8. 字符串转整数

[Chinese ver]

8. 字符串转整数 (atoi)

实现一个 atoi 方法来将一个 string 转换成一个 integer.

提示:仔细的思考所有可能的输入情况。如果你想要一个挑战,请不要看以下内容并问你自己什么是可能的输入情况。

注意:模糊的指定输入范围就是这个题目的目的(比如没有给输入规范)。你负责收集前面所有的输入要求。

Read More
Share

LeetCode 8. String to Integer (atoi)

[English ver]

8. String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Read More
Share

Serializable

Serializable

通过实现 java.io.Serializable 可以让 class 实现序列化的功能,否则无法使用序列化的功能。一个实现序列化的类的子类都是可以进行序列化的。Serializable 接口没有方法,字段等只是一个标记它是可以序列化的作用。

序列化是指将数据结构或对象状态转换成可取用格式(例如存成文件,存于缓冲,或在网络中传送),并在需要的时候恢复原先状态的过程。

当子类实现了 Serializable 接口而父类没有实现的时候,父类要有一个可以访问的无参构造函数。

在反序列化的时候,没有实现序列化的类字段将会使用 public 或者 protect 的无参构造函数进行初始化。无参构造函数必须是实现序列化的子类可访问的,

Read More
Share

LRU 缓存的魔力

LRU 缓存的魔力

场景

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

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

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

解决方案

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

Read More
Share

贪婪算法

贪婪算法

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

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

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

原理

步骤

Read More
Share

LeetCode 7. 数字反转

[Chinese ver]

7. Reverse Integer

颠倒一个 integer 的前后位数。

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

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

Read More
Share

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
Share

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);

Read More
Share

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
Share

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"


Read More
Share