LeetCode[26] Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

代码:

阅读全文

LeetCode[290] Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

pattern = “abba”, str = “dog cat cat dog” should return true.
pattern = “abba”, str = “dog cat cat fish” should return false.
pattern = “aaaa”, str = “dog cat cat dog” should return false.
pattern = “abba”, str = “dog dog dog dog” should return false.

Notes:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

分析:

用一个HashMap,建立字母和单词的对应关系。

代码:

阅读全文

LeetCode[32] Longest Valid Parentheses!

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

分析:

还是使用栈。不过因为要求的是长度,所以这次入栈的是字符的下标。需要注意的是,”()((()))”的length = 8。

代码:

阅读全文

LeetCode[3] 最大字符不重复的子串

题目描述

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

即给定一个字符串,返回最长的没有重复字符的子串的长度

思路

用一个HashMap来存储字符串。其中key为字符,value为该字符在字符串中的位置。

使用两个指针i,j来指示最长子串的位置。刚开始i,j都为0,指向第一个字符。然后i开始向右遍历。若遍历到的字符已在HashMap中,则更新它的value为现在i的位置。并且将j指向该字符的下一个位置(j只能往右移,或者不移,不能左移)。若未在HashMap中,则将该字符以及它的位置放入HashMap中。最大的(i-j+1)即为最长子串的长度。

代码如下

阅读全文

LeetCode[5] 最长的回文子串

题目描述

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

即给定一个字符串,返回该字符串最长的回文子串
如给出“acabcddcbadike”,返回“abcddcba”。

思路

回文子串分为长度为偶数(中间两个字符相同,就像示例)和长度为奇数两种。
从头往后遍历s.length()趟,第i趟指针j,k从i(奇数)或j从i,k从i+1(偶数)向两边扩散(s.charAt(i)和s.charAt(j)相等才扩散),k-j-1为该回文子串长度,若比之前maxlen大,则更新maxlen。

代码如下

阅读全文

LeetCode[80] Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

Subscribe to see which companies asked this question

代码:

阅读全文


Copyright © 2016 - 2017 LBD's Blog All Rights Reserved.

访客数 : | 访问量 :