【LeetCode】Longest Substring Without Repeating Characters 解题报告
2024-08-26 05:49:49
【题意】
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还是下标做key,总之比較麻烦。
后来看到网上普遍用数组来实现 HashMap 的功能。感觉还是挺新的。
至于为什么数组的大小设为256,始终想不明确。我查了下ASCII码表,上面也仅仅有127个字符。A~Z是65~90,a~z是97~112。
以下的代码我认为是已经相当简洁了。參考出处:Java,C++。大家共同学习。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (s == null || len == 0) return 0; int[] table = new int[256];
Arrays.fill(table, -1); int maxlen = 1;
int begin = 0, end = 1;
table[s.charAt(0)] = 0; //important!
while (end < len) {
char endch = s.charAt(end);
if (table[endch] >= begin) {
begin = table[endch] + 1;
}
table[endch] = end;
maxlen = Math.max(maxlen, end-begin+1);
end++;
} return maxlen;
}
}
上面代码有下面优点:它推断有没有反复是通过当前字母在table中的值是不是比子串的開始位置大,这样就不用每次出现反复字母后都须要把之前的字符在table中的值又一次设为-1。
最新文章
- ubuntu git 使用
- Servlet Request的 getInputStream() getReader() getParameter()
- 35. Search Insert Position
- DEV控件,PopupContainerEdit,PopupContainerControl,TreeList,弹出控制问题
- AC日记——导弹拦截 洛谷 P1020 (dp+模拟)
- Incorrect key file for table &#39;/tmp/#sql_882_0.MYI&#39;; try to repair it
- SVN 命令行 精编版
- 局域网内sqldeveloper客户端连接oracle服务器
- MFC软件工程架构模型-模式窗口-非模式窗口
- angularjs表单
- mysql(4)—— 表连接查询与where后使用子查询的性能分析。
- 使用 Swoole 来加速你的 Laravel 应用
- ReactNative问题随记1 Exception in thread ";main"; java.lang.RuntimeException: gradle-2.14.1-all.zip
- python3 正则表达式点星问号(.*?)能不能匹配换行符?不能的话应该怎么写
- npm 常用命令 查看版本、安装、卸载
- [洛谷P1731][NOI1999]生日蛋糕(dfs)(剪枝)
- python学习之----爬取图片
- java web 中 filter 与 servlet的关系
- Java 将任意数组的任意两个位置的数据进行交换
- Java 基本数据类型 sizeof 功能