{"action":"opened","issue":{"url":"https://api.github.com/repos/iamwwc/blogsuepost/issues/14","repository_url":"https://api.github.com/repos/iamwwc/blogsuepost","labels_url":"https://api.github.com/repos/iamwwc/blogsuepost/issues/14/labels{/name}","comments_url":"https://api.github.com/repos/iamwwc/blogsuepost/issues/14/comments","events_url":"https://api.github.com/repos/iamwwc/blogsuepost/issues/14/events","html_url":"https://github.com/iamwwc/blogsuepost/issues/14","id":493593866,"node_id":"MDU6SXNzdWU0OTM1OTM4NjY=","number":14,"title":"最长回文字串-leetcode5","user":{"login":"iamwwc","id":24750337,"node_id":"MDQ6VXNlcjI0NzUwMzM3","avatar_url":"https://avatars0.githubusercontent.com/u/24750337?v=4","gravatar_id":"","url":"https://api.github.com/users/iamwwc","html_url":"https://github.com/iamwwc","followers_url":"https://api.github.com/users/iamwwc/followers","following_url":"https://api.github.com/users/iamwwc/following{/other_user}","gists_url":"https://api.github.com/users/iamwwc/gists{/gist_id}","starred_url":"https://api.github.com/users/iamwwc/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/iamwwc/subscriptions","organizations_url":"https://api.github.com/users/iamwwc/orgs","repos_url":"https://api.github.com/users/iamwwc/repos","events_url":"https://api.github.com/users/iamwwc/events{/privacy}","received_events_url":"https://api.github.com/users/iamwwc/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2019-09-14T07:18:25Z","updated_at":"2019-09-14T07:18:25Z","closed_at":null,"author_association":"OWNER","body":"题目来自\r\n\r\nhttps://leetcode.com/problems/longest-palindromic-substring/\r\n\r\n### 题目介绍\r\n\r\n给定一个字符串 `s` ，输出 `s` 对应的最长回文字串\r\n\r\n比如\r\n\r\n```\r\nInput: s = \"babad\"\r\n\r\nOutput: s = \"bad\"\r\n```\r\n\r\n解释：\r\n\r\n`bad` 是 `babad` 的最长回文字串\r\n\r\n### 解决方案\r\n\r\n之前碰到过类似的一道题，判断 s 是否回文，其中之一的方法是从两边开始向里扫描。但对于这道题，求最长回文字串向里扫描不适用。\r\n\r\n我们采用中间向外扫描， 不断比较记录最大的长度， 跳过肯定是回文的重复字符序列。\r\n\r\n然后利用双指针左右移动。\r\n\r\n```java\r\npublic String longestPalindrome(String s) {\r\n    if (s.length() < 2) {\r\n        return s;\r\n    }\r\n    int max = 0 , start = 0;\r\n    /*\r\n    * i 是移动的起始点\r\n    * 比如 s.length() == 8\r\n    * 现在max == 6\r\n    * i只需要到 (8 - 6 / 2 ) == 5 就可以，没必要继续向后扫描\r\n    */\r\n    for(int i = 0 ; i < s.length() - max / 2; i ++) {\r\n        int j = i;\r\n        int k = i;\r\n        // 跳过一定是回文的重复字符\r\n        while(k < s.length() - 1 && s.charAt(k) == s.charAt(k + 1)) {\r\n            k ++;\r\n        }\r\n        // 从重复序列的左右同时开始移动\r\n        while(j > 0  && k < s.length() - 1 && s.charAt(j - 1) == s.charAt(k + 1)) {\r\n            j --;\r\n            k ++;\r\n        }\r\n        int len = k - j + 1;\r\n        if (max <= len){\r\n            start = j;\r\n            max = len;\r\n        }\r\n    }\r\n    return s.substring(start, start + max);\r\n}\r\n```\r\n\r\n### 感想\r\n\r\n到现在也是做了好多的 `leetcode` 题目了，感觉对代码的细节控制更深入了。\r\n\r\n比如这个代码片段\r\n\r\n```java\r\nwhile(j > 0  && k < s.length() - 1 && s.charAt(j - 1) == s.charAt(k + 1)) {\r\n    j --;\r\n    k ++;\r\n}\r\n```\r\n\r\n如果按我之前的写法，我会写成下面这样\r\n\r\n```java\r\nwhile(j >= 0  && k < s.length() && s.charAt(j) == s.charAt(k)) {\r\n    j --;\r\n    k ++;\r\n}\r\n```\r\n\r\n看起来没什么问题，但 `j` 可能为 `-1`，而 `k` 可能为 `s.length()`，已经索引溢出了。\r\n\r\n为了解决这个问题，我会在后面加上更臃肿的代码\r\n\r\n```java\r\nif (j == -1) {\r\n  j ++;\r\n}\r\n\r\nif (k == s.length()) {\r\n  k --;\r\n}\r\n```\r\n\r\n算法题写多了，感觉自己更灵光了 :)"}}
{"actor":{"display_login":"iamwwc"}}