leetcode3-6

LeetCode 3

Ques: Find the length of longest substring without repeating characters.

思路:用table记录出现char字符的次数,256个ASCII字符初始化为-1.如果遇到重复,则记录在table里面,

我的代码:

int lengthOfLongestSubstring(string s) {
int tables[256];
fill(tables,tables+256,-1);
int result=0,lastRepeatedPos=-1;
for(int i=0;i<s.size();i++)
{
//当找到重复元素且lastRepeatedPos小于找到重复元素的下表时,更新lastRepeatedPos
if(tables[s[i]]!=-1&&lastRepeatedPos<tables[s[i]])
lastRepeatedPos=tables[s[i]];

//更新最大值
result=max(result,i-lastRepeatedPos);
//元素插入表中
tables[s[i]]=i;
}
return result;
}

官方解题:
LeetCode 3 Solution

AP 1

暴力破解,但超时了,TC = O(N^3),对于字符串中的每个子串都去扫,是否子串为独立的。

// JAVA VERSION
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j <= n; ++j)
//是否存在唯一的子串,记录最长值
if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
return ans;
}

public boolean allUnique(String s, int start, int end) {
Set<Character> set = new HashSet<>();
//将串S从头到尾的放入set匹配一次是否重复
for (int i = start; i < end; ++i) {
Character ch = s.charAt(start);
if (set.contains(ch)) return false;
set.add(ch);
}
return true;
}
AP 2

基于上述,我们重复扫了很多子串,假设固定开始位置一个个扫的话,可以减少重复扫串的运算。这样可以使TC = O(N^2),LEFT-CLOSED AND RIGHT OPEN

// SLIDING WINDOW 
// JAVA VERSION
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
//固定i,先把j搜完,再加i
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
AP 3

SLDING WINDOW OPTIMIZED, TC=N = O(N),SC=m=O(1). m为charset大小

public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; ++j) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}

LEETCODE 4

QUES: 找两个有序数组中的中位数
解法:1.暴力地将两个数组合并然后排序,直接得到中位数
2.求得数组大小,用堆排的合并方法,找到中位数。 复杂度O(log(m+n))

// My Code
//合并两个数组排序,再根据大小分为奇偶情况输出中位数
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l1 = nums1.size();
int l2 = nums2.size();
vector<int> res;
for(int i=0;i<l1;i++)
res.push_back(nums1[i]);
for(int i=0;i<l2;i++)
res.push_back(nums2[i]);
sort(res.begin(),res.end());
if(res.size()%2==0)
{
return (double)(res[(l1+l2-1)>>1]+res[(l1+l2 >>1)])/2.0;
}
else
{
return (double)(res[(l1+l2)>>1]);
}
}

LEETCODE 5

问题: 给一个串S,找出其中最长的回文子串

官方使用DP的方法以及EXPAND AROUNG CENTER,其中我的代码就是EXPAND AROUND CENTER。还有一个Manacher’s Algorithm,它通过在字母间加#和以$作为起始符,使得串不再分为奇偶的情况,有效地统一起来,核心思想还是基于中央字母的展开策略。
官方解法

我的解法:分为奇偶情况判断,遍历串,寻找以该字符为中心,两边的回文串最大长度,把最长的情况的信息保留,然后返回。TC=O(N^2)

string longestPalindrome(string s) {
int len = s.length();
int i,j;
int subTempLength=0;
int subMax=0,subMaxIndex=0;
for(i=0 ; i< len;i++)

{
//Odd
for(j=0;(i-j)>=0&&(i+j)<len;j++)
{
if(s[i-j]!=s[i+j])
break;
subTempLength = j*2+1;

}
if(subTempLength > subMax)
{

subMax = subTempLength;
subMaxIndex = i;

}
//Even
for(j=0;(i-j)>=0&&(i+j+1)<len;j++)
{
if(s[i-j]!=s[i+j+1])
break;
subTempLength = j*2 +2;

}
if(subTempLength > subMax)
{

subMax = subTempLength;
subMaxIndex = i;

}


}
int startIndex ;
if(subMax % 2 ==0)
startIndex= subMaxIndex - subMax/2 +1;
else
startIndex = subMaxIndex - subMax/2;
string result(s,startIndex,subMax);
return result;

}

LEETCODE 6

问题:ZigZag Conversion
一开始没看懂,将串转化成蛇形,然后输出,有点点加密的味道
思路:关键理解到蛇形转化的过渡的字母是怎么在数组表示即可

//My Code
string convert(string s, int nRows) {
if(s.length()==0||nRows <=0)
return "";
if(nRows ==1)
return s;
string res;
//蛇形过渡的位置和行的关系
int size = 2 * nRows - 2;
//逐行输出蛇形字符
for( int i=0;i<nRows;i++)
{
//根据原长转换
for(int j=i;j<s.length();j+=size)
{ //输出竖直的字符
res+=s[j];
//输出斜形的字符
if(i!=0&&i!=nRows-1&& j+size-2*i<s.length())
res+=s[j+size-2*i];
}
}
return res;
}

坚持分享,支持原创