贪婪算法

贪婪算法

贪婪算法(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.最长的回文字符串

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"

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

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

Read More
Share

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

Read More
Share

Binary Search(二分搜索)

Binary Search(二分搜索)

二分搜索(binary search),也叫做 折半搜索(half-interval search),对数搜索(logarithmic search),对半搜索(binary chop),是一种在有序数组中查找某一特定元素的搜索算法.

二分搜索有几个变体.特别是,分散层叠(fractional cascading)(将每个数组里的值集合成一个数组,元素为11[0,3,2,0] 的形式,括号内的数字是该值在对应数组中应该返回的数字)提高了在多个数组中查找相同值的效率,高效的解决了一系列计算几何和其他领域的查找问题).指数查找(Exponential search)延伸了二分查找到一个没有边界的 list.binary search treeB-tree是基于 binary search 延伸的.

原理

搜索时从数组中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果中间元素大于或者小于要查找的元素,则在数组中大于或者小于查找元素的一半中继续查找,重复这个过程直到找到这个元素,或者这一半的大小为空时则代表找不到.这样子每一次比较都使得搜索范围缩小一半.

步骤

给定一个有序数组 A 是 A0,…,An-1并保证 A0<=…<=An-1,以及目标值 T.

Read More
Share