1 两数之和
1. 两数之和 - 力扣(LeetCode)
和为目标值 target 就是在找 target - nums[i]
利用 哈希表 查找只需要 O(1)
class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Integer, Integer> hm = new HashMap<>();for (int i = 0; i < nums.length; i++) {if (hm.containsKey(target - nums[i])) {return new int[] { hm.get(target - nums[i]), i };}hm.put(nums[i], i);}return new int[0]; // 可以这样返回}
}
2 两数相加
2. 两数相加 - 力扣(LeetCode)
/*** 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 addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre = new ListNode(0); // 头指针boolean carry = false; // 进位ListNode cur = pre; // 当前指针while (l1 != null || l2 != null) {int sum = 0;if (carry) {// 如果l1 不等于null时,就取他的值,等于null时,就赋值0,保持两个链表具有相同的位数int x = l1 != null ? l1.val : 0;// 如果l1 不等于null时,就取他的值,等于null时,就赋值0,保持两个链表具有相同的位数int y = l2 != null ? l2.val : 0;sum = x + y + 1;carry = false;} else {// 如果l1 不等于null时,就取他的值,等于null时,就赋值0,保持两个链表具有相同的位数int x = l1 != null ? l1.val : 0;// 如果l1 不等于null时,就取他的值,等于null时,就赋值0,保持两个链表具有相同的位数int y = l2 != null ? l2.val : 0;sum = x + y;}if (sum >= 10) {sum %= 10;carry = true;}cur.next = new ListNode(sum);cur = cur.next;// 当链表l1不等于null的时候,将l1 的节点后移if (l1 != null) {l1 = l1.next;}// 当链表l2 不等于null的时候,将l2的节点后移if (l2 != null) {l2 = l2.next;}}if (carry) {cur.next = new ListNode(1);}return pre.next;}
}
3 无重复字符的最长子串
3. 无重复字符的最长子串 - 力扣(LeetCode)
4 寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数 - 力扣(LeetCode)
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 先合并再找中位数int len1 = nums1.length;int len2 = nums2.length;int len = len1 + len2;int merge[] = new int[len];int count = 0;// merge数组的元素个数int i = 0, j = 0;// 注意三个数组都需要各自独立的指针while (count != len1 + len2) {if (i == len1) {// nums1空了,nums2拼接过来// merge = IntStream.concat(// Arrays.stream(nums1),// Arrays.stream(nums2)).toArray();// 注意count要变化// count+=len2-j+1;while(j!=len2){merge[count++]=nums2[j++];}break;}if (j == len2) {// merge = IntStream.concat(// Arrays.stream(nums2),// Arrays.stream(nums1)).toArray();while(i!=len1){merge[count++]=nums1[i++];}break;}if (nums1[i] < nums2[j]) {merge[count++] = nums1[i++];} else {merge[count++] = nums2[j++];}}// {5,6,3}if (count % 2 == 0) {return (merge[len / 2 - 1] + merge[len / 2]) / 2.0;} else {return merge[len / 2];}}
}
5 最长回文子串
最长回文子串 - 力扣(LeetCode)
public class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;// dp[i][j] 表示 s[i..j] 是否是回文串boolean[][] dp = new boolean[len][len];// 初始化:所有长度为 1 的子串都是回文串for (int i = 0; i < len; i++) {dp[i][i] = true;}char[] charArray = s.toCharArray();// 递推开始// 先枚举子串长度for (int L = 2; L <= len; L++) {// 枚举左边界,左边界的上限设置可以宽松一些for (int i = 0; i < len; i++) {// 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得int j = L + i - 1;// 如果右边界越界,就可以退出当前循环if (j >= len) {break;}if (charArray[i] != charArray[j]) {dp[i][j] = false;} else {if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}// 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);}
}