二刷hot100,坚持每天打卡!!!
1. 两数之和
// 先求差,再查哈希表
public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i<nums.length;i++){int key = target - nums[i];if(map.containsKey(key)){return new int[]{map.get(key),i};}map.put(nums[i],i);}return new int[0];
}
2. 两数相加
// 对应位置相加,记录进位,然后链表尾插法即可public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int flag = 0,lv1,lv2;ListNode answer = null,target = null;while (l1 != null || l2 != null){lv1 = l1 == null ? 0:l1.val;lv2 = l2 == null ? 0:l2.val;l1 = l1 == null ? null:l1.next;l2 = l2 == null ? null:l2.next;int sum = lv1+lv2+flag;flag = sum / 10;ListNode listNode = new ListNode(sum % 10);if (target == null){target = listNode;answer = target;}else {target.next = listNode;target = target.next;}}if (flag >0){target.next = new ListNode(flag);}return answer;}
3. 无重复字符的最长字串
// 滑动窗口public int lengthOfLongestSubstring(String s){Set<Character> set = new HashSet<>();int start = 0,end = 0,answer=0;while (end < s.length()){if (set.contains(s.charAt(end))){set.remove(s.charAt(start++));}else {set.add(s.charAt(end++));answer = Math.max(answer,end - start);}}return answer;}
4. 最长回文子串
// 动态规划public String longestPalindrome(String s) {if (s == null || s.length() < 2) {return s;}int strLen = s.length();int maxStart = 0; //最长回文串的起点int maxEnd = 0; //最长回文串的终点int maxLen = 1; //最长回文串的长度boolean[][] dp = new boolean[strLen][strLen];for (int r = 1; r < strLen; r++) {for (int l = 0; l < r; l++) {if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {dp[l][r] = true;if (r - l + 1 > maxLen) {maxLen = r - l + 1;maxStart = l;maxEnd = r;}}}}return s.substring(maxStart, maxEnd + 1);}