回顾前面刷过的算法（8）
最近几天回顾了一下一下几道算法题目
//最长回文子串//思路： 中心扩散，先以一个元素为中心进行扩散，再以两个元素为中心进行扩散//维护两个变量，maxLength记录最长回文子串长度，maxStart记录子串的开始位置，便于截取public String longestPalindrome(String s) {int maxLength = 0, maxStart = 0;for (int j = 0; j < 2; j++) {for (int i = 0; i < s.length(); i++) {int left = i;int right = i + j;while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}left++;right--;if (maxLength < right - left + 1) {maxLength = right - left + 1;maxStart = left;}}}return s.substring(maxStart, maxLength + maxStart);}//合并两个有序链表//思路：创建一个新头结点，再定义两个指针分别去遍历两条有序链表，进行比较，//然后拼接到新头结点上public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode newHead = new ListNode(0);ListNode tail = newHead;ListNode p = l1, q = l2;while (p != null && q != null) {if (p.val >= q.val) {tail.next = q;q = q.next;} else {tail.next = p;p = p.next;}tail = tail.next;}if (p != null) {tail.next = p;} else if (q != null) {tail.next = q;}return newHead.next;}//有效括号public boolean isValid(String s) {if (s.isEmpty()) return false;Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(') {stack.push(')');} else if (c == '{') {stack.push('}');} else if (c == '[') {stack.push(']');} else if (stack.isEmpty() || c != stack.pop()) {return false;}}if (stack.isEmpty()) return true;return false;}//无重复字符的最长子串//思路：定义两个变量left和right，用于指向字符串数组，每次right++//然后检查set中是否存在当前right指向的字符，存在则remove所有并且left++//接着将其add到set中去，然后维护一个res变量记录left与right指向的子串最大长度//left和right的移动类似一个滑动窗口public int lengthOfLongestSubstring(String s) {char[] ss = s.toCharArray();Set<Character> set = new HashSet<>();int res = 0;for (int left = 0, right = 0; right < s.length(); right++) {char ch = ss[right];while (set.contains(ch)) {set.remove(ss[left]);left++;}set.add(ss[right]);res = Math.max(res, right - left + 1);}return res;}//两数相加//利用map存储元素，数组值当作key，索引当作value//在遍历数组的同时判断map中是否存在目标和与当前元素的差//存在则返回两个元素的下标public int[] twoSum(int[] nums, int target) {HashMap<Integer, Integer> map = new HashMap();for (int i = 0; i < nums.length; i++) {if (map.containsKey(target - nums[i])) {return new int[] { map.getOrDefault(target - nums[i], 0), i};}map.put(nums[i], i);}return null;}