LeetCode 热题 Hot 100

• 744. 寻找比目标字母大的最小字母

class Solution {   /     * 方法1: 直接遍历     */    public char nextGreatestLetter1(char[] letters, char target) { for (char letter : letters) {     if (letter > target) return letter; } return letters[0];    } /     * 方法2: 已知有序,我们就可以采用二分查找来求值     */    public char nextGreatestLetter2(char[] letters, char target) { int L = 0, R = letters.length - 1; while (L <= R) {     // 中间位置     int mid = L + ((R - L) >>> 1);     if (letters[mid] <= target) {  L = mid + 1;     } else {  R = mid - 1;     } } // 结束条件就是R在L的左边一位,所以第一个大于目标值的位置应该为L的位置 // 但是如果L一直走到了列表结尾也没有找到大于target的最小字母,那就返回第一个字符就行 return L < letters.length ? letters[L] : letters[0];    }}

• 1.两数之和

class Solution {   /     * 方法1: 暴力枚举     */    public int[] twoSum1(int[] nums, int target) { int n = nums.length; // 保证一个不动 另外一个移动 for (int i = 0; i < n; i++) {     int l = nums[i];     for (int j = i + 1; j < n; j++) {  int r = nums[j];  if (l + r == target) {      return new int[]{i, j};  }     } } return new int[]{};    } /     * 方法2: 哈希表     * 思路: key: nums[i]     * value: i     */    public int[] twoSum2(int[] nums, int target) { Map<Integer, Integer> hash = new HashMap<>(); int n = nums.length; for (int i = 0; i < n; i++) {     // 如果能找到另外一个target-nums[i]的值 就代表找到了     if (hash.containsKey(target - nums[i])) {  return new int[]{i, hash.get(target - nums[i])};     } else {  hash.put(nums[i], i);     } } return new int[]{};    }}

• 2.两数相加

/ * 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 resultHead = new ListNode(-1); // 最终结果的尾指针,默认指向结果的头节点 ListNode resultTail = resultHead; // 每位数字相加的进位,默认为0 int carry = 0; while (l1 != null || l2 != null) {     int n1 = l1 != null ? l1.val : 0;     int n2 = l2 != null ? l2.val : 0;     // 求和     int sum = n1 + n2 + carry;     // 得到当前位并且组装节点     resultTail.next = new ListNode(sum % 10);     // 尾节点后移继续下次组装     resultTail = resultTail.next;     // 记录本次进位     carry = sum / 10;     // 继续下次移动     if (l1 != null) {  l1 = l1.next;     }     if (l2 != null) {  l2 = l2.next;     } } // 循环结束后考虑最后一次是否有进位 if (carry > 0) {     resultTail.next = new ListNode(carry); } return resultHead.next;    }}

• 3.无重复字符的最长子串

class Solution {    public int lengthOfLongestSubstring(String s) {// 定义窗口的左边界和有边界 int l = 0, r = 0; // 保存最大窗口的长度 int maxWindow = 0; // 每次循环窗口里面的内容有没有重复来进行左边界和右边界来移动 Set<Character> windowSet = new HashSet<>(); // 不超过字符串长度 while (l < s.length() && r < s.length()) {     // 判断当前扩张边界的字符已经出现在之前的set里面了     if (windowSet.contains(s.charAt(r))) {  // 将l出现的字符移除掉  windowSet.remove(s.charAt(l));  // 缩小窗口  l++;     } else {  windowSet.add(s.charAt(r));  r++;  maxWindow = Math.max(r - l, maxWindow);     } } return maxWindow;    }}

• 4.寻找两个正序数组的中位数

class Solution {    /     * 算法的时间复杂度应该为 O(log (m+n))     */    public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n = nums1.length + nums2.length; // 为偶数 if (n % 2 == 0) {     // 中间的左侧数字     int l = findKth(nums1, 0, nums2, 0, n >>> 1);     int r = findKth(nums1, 0, nums2, 0, (n >>> 1) + 1);     return (l + r) / 2.0; } else {     // 直接返回中间的数字     return findKth(nums1, 0, nums2, 0, (n >>> 1) + 1); }    }    /     * 找到两个数组中第K大的元素     * i: nums1的起始位置     * j: nums2的起始位置     */    public int findKth(int[] nums1, int i, int[] nums2, int j, int k) { // 保证nums1的长度不超过nums2的长度 if (nums1.length - i > nums2.length - j) {     return findKth(nums2, j, nums1, i, k); } // 返回第k个元素 if (nums1.length == i) {     return nums2[j + k - 1]; } if (k == 1) return Math.min(nums1[i], nums2[j]); int idx1 = Math.min(nums1.length, i + (k >>> 1)); int idx2 = j + k - (k >>> 1); if (nums1[idx1 - 1] < nums2[idx2 - 1]) {     return findKth(nums1, idx1, nums2, j, k - (idx1 - i)); } else {     return findKth(nums1, i, nums2, idx2, k - (idx2 - j)); }    }    }

• 10.正则表达式匹配

暂时不写

• 11.盛最多水的容器

class Solution {    /     * 方法1     */    public int maxArea1(int[] height) { int res = 0; int n = height.length; for (int i = 0; i < n; i++) {     for (int j = i + 1; j < n; j++) {  // 面积 = (j - i) * 较小的高度  int area = (j - i) * Math.min(height[i], height[j]);  res = Math.max(res, area);     } } return res;    } /     * 方法2: 双指针方法     */    public int maxArea2(int[] height) { int n = height.length; int res = 0; int l = 0, r = n - 1; while (l < r) {     // 面积 = (r-l) * 较小的高度     int area = (r - l) * Math.min(height[l], height[r]);     res = Math.max(res, area);     // 左边高于右边,l++     if (height[l] < height[r]) {  l++;     } else {  r--;     } } return res;    }}

• 15.三数之和

    /     * b + c = -a     */    public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; if (n < 3) return res; Arrays.sort(nums); // 固定好一个数字 至少长度为3所以遍历到n-2就行 for (int i = 0; i < n - 2; i++) {     // 右边的不能和左边的重复 用过了     if (i > 0 && nums[i - 1] == nums[i]) continue;     //  得到两数之和     int twoSum = -nums[i];     int l = i + 1, r = n - 1;     while (l < r) {  // 当前和  int currentSum = nums[l] + nums[r];  if (currentSum > twoSum) {      r--;  } else if (currentSum < twoSum) {      l++;  } else {      res.add(Arrays.asList(nums[i], nums[l], nums[r]));      l++;      // 和左边的不能重复      while (l < r && nums[l - 1] == nums[l]) {   l++;      }      r--;      // 和右边的不能重复      while (l < r && nums[r] == nums[r + 1]) {   r--;      }  }     } } return res;    }

• 17.电话号码的字母组合

class Solution {    /     * 初始化对应所有的数字,为了直接对应2-9,新增了两个无效的字符串     */    private String[] lettersOnDigit = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};    /     * 设置全局列表存储最后的结果     */    private List<String> pathList = new LinkedList<>();    /     * 深度优先遍历     */    public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) return pathList; dfs(new StringBuilder(), digits); return pathList;    }    /     * path: 已经经历过了哪些字母     */    private void dfs(StringBuilder path, String digits) { // 判断是否走到了叶子节点->判断path的长度是否和digits的长度一样 if (path.length() == digits.length()) {     pathList.add(path.toString());     return; } // 当前数字是几 int currentDigit = digits.charAt(path.length()) - '0'; // 当前数字对应的字符串 String currentLetters = lettersOnDigit[currentDigit]; // 遍历字符串 for (char c : currentLetters.toCharArray()) {     // 加入当前的path     path.append(c);     // 参数传入dfs进行递归调用     dfs(path, digits);     // 比如a->d->p     // 此时d下面还有qrs所以我们得将path回退到d然后把qrs这一轮的dfs完,所以我们需要删除末尾的继续去尝试     // 当从递归中走出来时,删除末尾的继续尝试     // 当从递归中走出来时,删除末尾的继续尝试     path.deleteCharAt(path.length() - 1); }    }}

• 19.删除链表的倒数第N个节点

/ * 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 {   /     * 方法1     */    public ListNode removeNthFromEnd(ListNode head, int n) { // 暂存节点 ListNode dummy = new ListNode(-1, head); int len = getLength(head); // 定义的临时节点 ListNode tmp = dummy; // 要删除倒数第N个,正数是len - n -1,我们从1开始因为第一个节点是-1,我们定位到需要被删除节点的前驱节点 for (int i = 1; i <= (len - n); i++) {     // 需要被删除节点的前驱节点     tmp = tmp.next; } // 删除需要被删除的节点 tmp.next = tmp.next.next; return dummy.next;    }    /     * 获取链表长度     */    private int getLength(ListNode node) { int len = 0; // 遍历得到链表的长度 while (node != null) {     len++;     node = node.next; } return len;    }}

哈尔滨保险