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 |
AP 2
基于上述,我们重复扫了很多子串,假设固定开始位置一个个扫的话,可以减少重复扫串的运算。这样可以使TC = O(N^2),LEFT-CLOSED AND RIGHT OPEN
// SLIDING WINDOW |
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 |
LEETCODE 5
问题: 给一个串S,找出其中最长的回文子串
官方使用DP的方法以及EXPAND AROUNG CENTER,其中我的代码就是EXPAND AROUND CENTER。还有一个Manacher’s Algorithm,它通过在字母间加#和以$作为起始符,使得串不再分为奇偶的情况,有效地统一起来,核心思想还是基于中央字母的展开策略。
官方解法
我的解法:分为奇偶情况判断,遍历串,寻找以该字符为中心,两边的回文串最大长度,把最长的情况的信息保留,然后返回。TC=O(N^2)
string longestPalindrome(string s) { |
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;
}