方法二：中心扩展算法
每一个长度为1的子串都是回文子串，向外扩展即可
我们仔细观察一下方法一中的状态转移方程：
P(i,i)=true
P(i,i+1)=(S i ==S i+1 )
P(i,j)=P(i+1,j−1)∧(S i ==S j )
找出其中的状态转移链：
P(i,j)←P(i+1,j−1)←P(i+2,j−2)←⋯←某一边界情况
可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。
边界情况即为子串长度为 1 或 2 的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展，例如从P(i+1,j−1) 扩展到 P(i,j)；如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。
聪明的读者此时应该可以发现，「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。
class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) { return ""; } int start=0; int end=0; //对于每一个回文中心 for(int i=0;i<s.length();i++){ //长度为1的回文中心 int len1=expand(s,i,i); //长度为2的回文中心 int len2=expand(s,i,i+1); int len=Math.max(len1,len2); //更新最长 if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } //扩展 public int expand(String s,int left,int right){ while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){ left--; right++; } return right-left-1; } }
15. 三数之和【中等】
中等
5.4K
相关企业
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。 示例 2： 输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。 示例 3： 输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
排序+双指针
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans=new ArrayList<>(); int n=nums.length; Arrays.sort(nums); //枚举a for (int first = 0; first <n; first++){ //去重上次 if(first>0&&nums[first]==nums[first-1]){ continue; } //枚举c int third=n-1; int target=-nums[first]; //枚举b for (int second = first+1; second <n ; second++) { //去重上次 if(second > first+1&&nums[second]==nums[second-1]){ continue; } //需要保证c在b的右侧 while (second<third&&nums[second]+nums[third]>target){ third--; } // 如果指针重合，随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if (second == third) { break; } if (nums[second] + nums[third] == target) { List<Integer> list = new ArrayList<Integer>(); list.add(nums[first]); list.add(nums[second]); list.add(nums[third]); ans.add(list); } } } return ans; } }
17. 电话号码的字母组合【中等】
中等
2.2K
相关企业
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1： 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2： 输入：digits = "" 输出：[] 示例 3： 输入：digits = "2" 输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
自己
笛卡尔积
class Solution { public List<String> letterCombinations(String digits) { List<String> res=new ArrayList<>(); String[] strs={ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; char [] ds=digits.toCharArray(); String[] es=new String[]{}; for(int i=0;i<ds.length;i++){ es=dikaerji(es,strs[ds[i]-'0']); } for(String s:es){ res.add(s); } return res; } public String[] dikaerji(String[] a,String b){ if(a.length==0&&b.length()==0){ return new String[]{}; } if(a.length==0){ return b.split(""); } if(b.length()==0){ return a; } String[] ss=new String[a.length*b.length()]; char [] bs=b.toCharArray(); int c=0; for(int i=0;i<a.length;i++){ String es; for(int j=0;j<bs.length;j++){ es=""+a[i]+bs[j]; ss[c++]=es; } } return ss; } }
19. 删除链表的倒数第 N 个结点【中等】
19.删除链表的倒数第 N 个结点
提示
中等
2.6K
相关企业
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2： 输入：head = [1], n = 1 输出：[] 示例 3： 输入：head = [1,2], n = 1 输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
快慢指针
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode first = head; ListNode second = dummy; for (int i = 0; i < n; ++i) { first = first.next; } while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; ListNode ans = dummy.next; return ans; } }
20. 有效的括号【简单】
简单
3.6K
相关企业
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1： 输入：s = "()" 输出：true 示例 2： 输入：s = "()[]{}" 输出：true 示例 3： 输入：s = "(]" 输出：false
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
栈
class Solution { public boolean isValid(String s) { int n=s.length(); if(n%2!=0){ return false; } Stack<Character> stack=new Stack(); HashMap<Character,Character> map=new HashMap<>(); map.put(')','('); map.put(']','['); map.put('}','{'); for(int i=0;i<n;i++){ Character c= s.charAt(i); if(map.containsKey(c)){ if(stack.isEmpty()||stack.peek()!=map.get(c)){ return false; } stack.pop(); }else{ stack.push(c); } } return stack.isEmpty(); } }
括号生成
最长有效括号
删除无效的括号
21. 合并两个有序链表【简单】
21.合并两个有序链表
简单
3.1K
相关企业
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例 2： 输入：l1 = [], l2 = [] 输出：[] 示例 3： 输入：l1 = [], l2 = [0] 输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead = new ListNode(-1); ListNode prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev.next = l1 == null ? l2 : l1; return prehead.next; } }
22. 括号生成
- 括号生成
中等
3.3K
相关企业
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1： 输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"] 示例 2： 输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
回溯
class Solution { public List<String> generateParenthesis(int n) { List<String> ans=new ArrayList<String>(); backtrack(ans,new StringBuilder(),0,0,n); return ans; } public void backtrack(List<String> ans,StringBuilder cur,int open,int close,int max){ if(cur.length()==max*2){ ans.add(cur.toString()); return; } if(open<max){ cur.append('('); backtrack(ans,cur,open+1,close,max); cur.deleteCharAt(cur.length()-1); } if(close<open){ cur.append(')'); backtrack(ans,cur,open,close+1,max); cur.deleteCharAt(cur.length()-1); } } }
23. 合并 K 个升序链表【困难】
23.合并 K 个升序链表
困难
2.5K
相关企业
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2： 输入：lists = [] 输出：[] 示例 3： 输入：lists = [[]] 输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
顺序合并
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode res=null; for(ListNode l:lists){ res=mergeTwoLists(res,l); } return res; } public ListNode mergeTwoLists(ListNode a,ListNode b){ if(a==null||b==null){ return a!=null?a:b; } ListNode head=new ListNode(0); ListNode tail=head,head1=a,head2=b; while(head1!=null&&head2!=null){ if(head1.val<=head2.val){ tail.next=head1; head1=head1.next; }else{ tail.next=head2; head2=head2.next; } tail=tail.next; } tail.next=(head1!=null)?head1:head2; return head.next; } }
31. 下一个排列【中等】
31.下一个排列
中等
2.2K
相关企业
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1： 输入：nums = [1,2,3] 输出：[1,3,2] 示例 2： 输入：nums = [3,2,1] 输出：[1,2,3] 示例 3： 输入：nums = [1,1,5] 输出：[1,5,1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
官方
class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { int j = nums.length - 1; while (j >= 0 && nums[i] >= nums[j]) { j--; } swap(nums, i, j); } reverse(nums, i + 1); } public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } public void reverse(int[] nums, int start) { int left = start, right = nums.length - 1; while (left < right) { swap(nums, left, right); left++; right--; } } }
