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.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

Read More

LeetCode 8. 字符串转整数

[Chinese ver]

8. 字符串转整数 (atoi)

[TOC]

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

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

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

Read More

LRU 缓存的魔力

LRU 缓存的魔力

场景

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

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

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

解决方案

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

T = 平均内存引用时间

Read More

贪婪算法

贪婪算法

[TOC]

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

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

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

原理

步骤

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 7. 数字反转

[Chinese ver]

7. Reverse Integer

颠倒一个 integer 的前后位数。

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

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


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 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 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
Your browser is out-of-date!

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

×