算法成长之路leetcode1-4

算法成长之路leetcode1-4

1.Two Sum

desc

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:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

solution

s.eg1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//24 ms	38 MB s.O(n^2) k.O(1)
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result =new int[2];
for(int i = 0;i<nums.length-1;i++){
for(int j = i+1;j<nums.length;j++){
if(nums[i]+nums[j] == target){
result[0] = i;
result[1] = j;
return new int[]{i,j};
}
}
}
return new int[0];
}
}

eg2.

1
2
3
4
5
6
7
8
9
10
11
12
13
// 3 ms	37.2 MB s.O(n) k.O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> cache = new HashMap();
for(int i = 0;i<nums.length;i++){
if(cache.get(nums[i]) != null){
return new int[]{cache.get(nums[i]),i};
}
cache.put(target-nums[i],i);
}
return new int[0];
}
}

2.Add Two Numbers

des

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.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

solution

eg1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 2 ms	44.7 MB
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0; // 进位
ListNode head = new ListNode(0);
ListNode cur = head; // 一定要用两个链表,不能用一个操作
while(l1 != null ||l2 != null|| carry != 0){ // lastSum当最后一位刚好进1的时候,需要在循环

int l1v = l1 == null?0:l1.val;
int l2v = l2 == null?0:l2.val;
int temp =l1v+l2v+carry;
ListNode node;
if(temp>=10){
node = new ListNode(temp-10);
lastSum = 1;
}else{
node = new ListNode(temp);
lastSum = 0;
}

if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;

cur.next = node;
cur = node;
}
return head.next;
}
}

3.Longest Substring Without Repeating Characters

desc

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: 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.

solution

eg1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//2 ms 24.05% 36.9 MB 95.35%
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> strSet = new HashSet();
int maxLen = 0;
if(s != null && s.length() >0){
char ss[] = s.toCharArray(); //利用toCharArray方法转换
for (int i = 0; i < ss.length-1; i++) {
strSet.add(ss[i]);
for(int j = i+1; j<ss.length; j++){
int oL = strSet.size();
strSet.add(ss[j]);
int cL = strSet.size();
if(oL != cL){ // 不相等时记下个数
if(cL > maxLen){
maxLen = cL;
}
}else{ // 相等时 跳出此次循环 清空set
strSet.clear();
break;
}
}
}
if(maxLen == 0){ // 全相等时
maxLen = 1;
}
}
return maxLen;
}
}

eg2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 2 ms	37.3 MB
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
char[] chars = s.toCharArray();
int leftIndex = 0;//记录最左边相等时的值,然后向右滑动窗口
for (int j = 0; j < chars.length; j++) {
for (int innerIndex = leftIndex; innerIndex < j; innerIndex++) {
if (chars[innerIndex] == chars[j]) {
maxLength = Math.max(maxLength, j - leftIndex);
leftIndex = innerIndex + 1;
break;
}
}
}
return Math.max(chars.length - leftIndex, maxLength);
}
}

4.Median of Two Sorted Arrays

desc

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)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:

1
2
3
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

solution

eg1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 20 ms  10.07%
// 2.2 MB 99.84%
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int maxL = 0;
if (nums1.length >= nums2.length) {
maxL = nums1.length;
} else {
maxL = nums2.length;
}
List<Integer> newList = new ArrayList(maxL);
for (int i = 0; i < maxL; i++) {
if (i < nums1.length) {
newList.add(nums1[i]);
}
if (i < nums2.length) {
newList.add(nums2[i]);
}
}

int size = newList.size();
int index = size / 2;
newList.sort(Comparator.comparing(Integer::valueOf));
if (size % 2 == 0) {
return (newList.get(index) + newList.get(index - 1)) / 2d;
} else {
return newList.get(index);
}
}
}

eg2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;
double res = 0.0;
if (n <= 0) {
return res;
}
if ((n & 1) == 0) {
res = (findKth(nums1, nums2, 0, 0, n / 2) + findKth(nums1, nums2, 0, 0, n / 2 + 1)) / 2.0;
}
else {
res = findKth(nums1, nums2, 0, 0, n / 2 + 1);
}
return res;
}
private int findKth(int[] nums1, int[] nums2, int start1, int start2, int k) {
if (start1 >= nums1.length) {
return nums2[start2 + k - 1];
}
if (start2 >= nums2.length) {
return nums1[start1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
int left = start1 + k / 2 - 1 >= nums1.length ? Integer.MAX_VALUE : nums1[start1 + k / 2 - 1];
int right = start2 + k / 2 - 1 >= nums2.length ? Integer.MAX_VALUE : nums2[start2 + k / 2 - 1];
if (left < right) {
return findKth(nums1, nums2, start1 + k / 2, start2, k - k / 2);
}
return findKth(nums1, nums2, start1, start2 + k / 2, k - k / 2);
}
}

eg3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 二分查找、分治算法
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
//m:A数组的长度
int m = A.length;
//n:B数组的长度

int n = B.length;
//如果A的长度大于B
if (m > n) { // to ensure m<=n
//交换AB数组,确保m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
//设置两个指针,iMin为头指针,IMAX为尾指针,halfLen为中位数指针
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
//如果头指针走向不大于尾指针,进行循环
while (iMin <= iMax) {
//i为中位数
int i = (iMin + iMax) / 2;
//j为
int j = halfLen - i;
if (i < iMax && B[j - 1] > A[i]){
iMin = i + 1; // i is too small
}
else if (i > iMin && A[i - 1] > B[j]) {
iMax = i - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i - 1]; }
else { maxLeft = Math.max(A[i - 1], B[j - 1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }

int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }

return (maxLeft + minRight) / 2.0;
}
}
return 0d;
}
}
作者

byte4sec

发布于

2019-11-05

更新于

2020-12-31

许可协议

评论