首页 > 代码库 > leetcode 1 - 5 解题思路
leetcode 1 - 5 解题思路
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
求数组中两个数相加的和等于target,且答案只有一个。
1、用map实现,注意一次就可以通过,不需要把先把所有数据加到map中,边加边寻找。
2、其次,如果遍历两次的话,需要注意同一个数不能用两次,但是如果这个数出现了两次,是可以使用的。
3、可以排序。
public class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; Map<Integer, Integer> map = new HashMap(); for (int i = 0; i < nums.length; i++){ if (map.containsKey(target - nums[i])){ result[0] = map.get(target - nums[i]); result[1] = i; break; } map.put(nums[i], i); } return result; } }
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
两个非空链表相加
注意进位
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int flag = 0; ListNode head = new ListNode(0); ListNode result = head; while (l1 != null || l2 != null || flag != 0){ int num = flag; if (l1 != null){ num += l1.val; l1 = l1.next; } if (l2 != null){ num += l2.val; l2 = l2.next; } head.next = new ListNode(num % 10); flag = num / 10; head = head.next; } return result.next; } }
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb"
, the answer is "abc"
, which the length is 3.
Given "bbbbb"
, the answer is "b"
, with the length of 1.
Given "pwwkew"
, the answer is "wke"
, with the length of 3. Note that the answer must be a substring, "pwke"
is a subsequence and not a substring.
求一个字符串中不出现重复数字的最大长度。
很多种做法:
1、暴力枚举
2、使用窗口发(set、map都可以)
3、使用ASCII码(数组)
public class Solution { public int lengthOfLongestSubstring(String s) { if (s.length() == 0){ return 0; } int[] pos = new int[256]; char[] word = s.toCharArray(); int maxLen = 1; int start = 0; for (int i = 0; i < 256; i++){ pos[i] = -1; } for (int i = 0; i < word.length; i++){ int num = (int) (word[i]); if (pos[num] != -1){ maxLen = Math.max(maxLen, i - start); int begin = pos[num] + 1; for (int j = start; j < pos[num]; j++){ pos[(int) (word[j])] = -1; } pos[num] = i; start = begin; } else { pos[num] = i; } } maxLen = Math.max(maxLen, word.length - start); return maxLen; } }
public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; int[] index = new int[128]; // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { i = Math.max(index[s.charAt(j)], i); ans = Math.max(ans, j - i + 1); index[s.charAt(j)] = j + 1; } return ans; } }
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
求连个数组的中位数,如果是偶数个,那么取平均值。并且要求时间复杂度是O(log (m+n))
1、暴力做法的负载度是O(m + n)不符合题意。
2、使用二分法的想法:如果A的中点大于B的中点,那么所求中点应该在A的左边和B的右边,复杂度是O(log (m+n))
public class Solution { public double findMedianSortedArrays(int[] A, int[] B) { int m = A.length, n = B.length; int l = (m + n + 1) / 2; int r = (m + n + 2) / 2; return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0; } public double getkth(int[] A, int aStart, int[] B, int bStart, int k) { if (aStart > A.length - 1) return B[bStart + k - 1]; if (bStart > B.length - 1) return A[aStart + k - 1]; if (k == 1) return Math.min(A[aStart], B[bStart]); int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE; if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1]; if (aMid < bMid) return getkth(A, aStart + k/2, B, bStart, k - k/2);// Check: aRight + bLeft else return getkth(A, aStart, B, bStart + k/2, k - k/2);// Check: bRight + aLeft } }
5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example:
Input: "cbbd" Output: "bb"
寻找最长回文子串
1、以每个字母以及两个字母中间为中心(后者在字母中间添加一个#之类的标记),构造回文串,然后看长度。
2、Manacher’s Algorithm
leetcode 1 - 5 解题思路