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

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

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

LeetCode 3. Longest Substring Without Repeating Characters [English ver]

[English ver]

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example:

1
2
3
4
5
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

First time i get a very tedious algorithm, because of i did not thinking about the problem carefully in the beginning, it causes that i hava to fix bug again and again because of the situation i haven’t think about . this makes code become very redundant .

Read More
Share

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

[Chinese ver]

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

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

例子:

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

Read More
Share

LeetCode 2. Add Two Numbers [English ver]

[English ver]

2. Add Two Numbers

Question :You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Approach 1:

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
Share