LeetCode 8. 字符串转整数

[Chinese ver]

8. 字符串转整数 (atoi)

[TOC]

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

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

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

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 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.最长的回文字符串

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 [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

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

LeetCode 3.最长的没有重复字符的子字符串 [Chinese ver]

[Chinese ver]

3.最长的没有重复字符的子字符串

给你一个字符串,得出最长的一个没有重复字符的子字符串的长度。

例子:

给定“abcabcbb”,答案是“abc”,长度为3。

给定“bbbbb”,答案是“b”,长度为1。

Read More

LeetCode 2. Add Two Numbers [Chinese ver]

[Chinese ver]

2. Add Two Numbers

问题:你将获得两个非空 linked lists来表示两个非负整数。 数字以反向的顺序存储,并且它们的每个节点包含一位数字。 将两个数字相加并将其以 linked list的形式返回。

你可以假定这两个数字不包含任何前导零(即不存在首位出现0的情况),除了数字0本身。

输入 :(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出 : 7 -> 0 -> 8

方法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}

Read More

LeetCode 1 Two Sum [Chinese ver]

[Chinese ver]1 Two Sum

Question

两数求和 。给定一个整数的数组,返回两个数字的索引使得这两个数字加起来成为一个指定的目标值。
你可以假设每个输入都至少有一个解决方案,并且你不能使用相同的元素两次。

Read More
Your browser is out-of-date!

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

×