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。

代码如下

阅读全文

Java中四种引用

为了使能更加灵活地控制对象的生命周期。从JDK 1.2版本开始,把对象的引用分为4种级别。这4种级别由高到低依次为:强引用、软引用、弱引用和虚引用。

阅读全文


Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :