1
Ariver 2017-06-23 11:14:14 +08:00 1
|
2
Arrowing 2017-06-23 13:22:21 +08:00
982 / 983 test cases passed.
最后一个超时了,T_T。。。 |
3
Chrisplus 2017-06-23 13:24:38 +08:00
双向队列,O(N)的时间复杂度?
|
4
wayne712 2017-06-23 13:48:50 +08:00 1
Longest Palindromic Substring 一点思路,
利用两个下标,如 i, j 假设输入"babad", i 不断向左边走,j 不断向右边走, 即两个下标 i 递减,j 递增 在这过程中判断两个下标所在字符是否相等, 相等则继续下一对下标的比较, 否则就中断循环,通过 substring,得到 i 和 j 之间的字符串。 最坏的时间复杂度是 O(n^2) 文字不太会表达,希望有帮助 |
5
Magic347 2017-06-23 14:52:33 +08:00 1
public class Solution {
public int lengthOfLongestSubstring(String s) { if (s == null || s.length() <= 0) { return 0; } int[] visited = new int[256]; for (int i = 0; i < 256; i++) { visited[i] = -1; } int start = 0; int end = 0; int len = s.length(); int retval = 1; while (end < len) { char ch = s.charAt(end); if (visited[ch] >= 0) { // current char is visited so far int currLen = end - start; if (currLen > retval) { retval = currLen; } int k = visited[ch]; for (int i = start; i <= k; i++) { visited[s.charAt(i)] = -1; } start = k + 1; } else { // current char is not visited so far if (end == len - 1) { // reach the end of the string int currLen = end - start + 1; if (currLen > retval) { retval = currLen; } } } visited[ch] = end; end ++; } return retval; } } |
6
Magic347 2017-06-23 14:56:58 +08:00
O(n)
https://leetcode.com/problems/longest-substring-without-repeating-characters public class Solution { public int lengthOfLongestSubstring(String s) { if (s == null || s.length() <= 0) { return 0; } int[] visited = new int[256]; for (int i = 0; i < 256; i++) { visited[i] = -1; } int start = 0; int end = 0; int len = s.length(); int retval = 1; while (end < len) { char ch = s.charAt(end); if (visited[ch] >= 0) { // current char is visited so far int currLen = end - start; if (currLen > retval) { retval = currLen; } int k = visited[ch]; for (int i = start; i <= k; i++) { visited[s.charAt(i)] = -1; } start = k + 1; } else { // current char is not visited so far if (end == len - 1) { // reach the end of the string int currLen = end - start + 1; if (currLen > retval) { retval = currLen; } } } visited[ch] = end; end ++; } return retval; } } |
7
YuJianrong 2017-06-23 15:20:15 +08:00 via iPhone
这种题目时间不是 O ( n )都肯定不对的,即使过了不过是 case 不好。
|
8
Arrowing 2017-06-23 15:26:29 +08:00 1
终于做出来了,之前思路错了。
983 / 983 test cases passed. Status: Accepted Runtime: 155 ms You are here! Your runtime beats 98.17 % of javascript submissions. ```javascript /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s) { var sLen = s.length, maxLen = 0, maxStr = '', tmpStr, posIndex, i; for( i = 0 ; i < sLen; i++ ){ tmpStr = s[i]; posIndex = maxStr.indexOf(tmpStr); if(posIndex > -1){ maxStr = maxStr.substring(posIndex + 1); } maxStr += tmpStr; maxLen = Math.max(maxLen, maxStr.length); } return maxLen; }; ``` |
9
momocraft 2017-06-23 16:16:14 +08:00
题目有点歧义,叫"最长不含重复子串"可能更好?"最长不重复子串"是另一个问题。
|
10
YuJianrong 2017-06-23 17:05:36 +08:00 via iPhone
这样还是不行的,这是 O(m*n)复杂度,m 是 character 种类。你应该想想怎么做到 O(n)。
提示 hashmap 的添加和查询我们一般认为是 O(1)的 |
11
mengzhuo 2017-06-23 18:06:28 +08:00 1
就是滑动窗口嘛~~87% AC 路过
``` func lengthOfLongestSubstring(s string) int { var dict [256]int for i:=0;i<256;i++{ dict[i] = -1 } start := -1 maxLen := 0 for i, c := range []byte(s) { if dict[uint8(c)] > start { start = dict[uint8(c)] } dict[uint8(c)] = i maxLen = max(i - start, maxLen) } return maxLen } func max(a,b int) int{ if a > b { return a } return b } ``` |
12
yuann72 2017-06-23 21:03:35 +08:00 1
983 / 983 test cases passed.
Status: Accepted Runtime: 158 ms (这 Runtime 一会长的时候 190+ 短的时候 157+) Submitted: 0 minutes ago /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s){ var subStrs = [], curSubStr = '', i=0,len=s.length; for(;i<len;i++){ if(!curSubStr.includes(s[i])){ curSubStr += s[i]; }else{ subStrs.push(curSubStr); curSubStr = curSubStr.slice(curSubStr.indexOf(s[i]) + 1) + s[i]; } } subStrs.push(curSubStr); for(i=0,len=subStrs.length;i<len;i++){ if (subStrs[i].length > curSubStr.length) { curSubStr = subStrs[i]; } } return curSubStr.length; }; |