发表于 |

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

SOL1

由于两个数列都是有序的，直接merge两个数组再求中间值，复杂度O（n）。

  • 注意最后返回值做除法时，不能直接写/2，会自动进行转换变成int，提醒是要注意返回值的格式
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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0;
        int j = 0;
        int k = 0;
        int[] array = new int[nums1.length+nums2.length];
        while(i<nums1.length && j<nums2.length){
            if(nums1[i]<nums2[j]){
                array[k]=nums1[i];
                k++;
                i++;
            } else {
                array[k]=nums2[j];
                k++;
                j++;
            }
        }
        while(i<nums1.length){
            array[k]=nums1[i];
            k++;
            i++;
        }
        while(j<nums2.length){
            array[k]=nums2[j];
            k++;
            j++;
        }
        //compute median
        if(array.length%2 ==1){
            return array[(int)(array.length/2)];
        } else {
            return (array[(array.length/2)]+array[(array.length/2)-1])/2.0; //！！！这里一定不能写/2，会自动变成int！！！
        }
        
    }
}

SOL2

题目要求里面是需要log(m+n)

log复杂度, 参考水中的鱼blog的思路, 使用二分法. 其实看到log复杂度应该能直接想到二分的思路.
脑死,好难,我再想想,思路想出来了竟然不会写我屮艸芔茻

我再想想!!!!

发表于 |

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.

SOL

看到题想到用map来实现, 具体思路还是参考了网路上这张图↓
hint
以及网路上的讲解:

假设子串里含有重复字符,则父串一定含有重复字符,单个子问题就可以决定父问题,因此可 以用贪心法。跟动规不同,动规里,单个子问题只能影响父问题,不足以决定父问题。
从左往右扫描,当遇到重复字母时,以上一个重复字母的index+1作为新的搜索起始位置, 直到最后一个字母,复杂度是 O(n)。

但是在实现的时候还是结果有错, 仔细看了下发现是没有考虑多个重复字符的计算问题(eg: abcdba…), 于是在重复字符出现的判定那里又加上了新的变量j用于标示上一个滑动窗口(好名字)的起点,从而把map中前一个窗口的键值都清除.

*

  • map的用法，map在处理字符串的时候感觉很常用
  • 字符串的用法
  • 这题没什么太大难度，把背后的逻辑想明白就能得出很好的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int start = 0;
        int length = 0;
        for(int i = 0,j=0; i<s.length(); i++){
            if(map.containsKey(s.charAt(i))){
                //if occur repeat?
                length = Math.max(length, i-start);
                start = map.get(s.charAt(i))+1;
                for(int k=j; k<start;k++){
                    map.remove(s.charAt(k));
                }
                j=start;
            }
            map.put(s.charAt(i), i);
        }
        length = Math.max(length, s.length()-start);
        return length;
    }
}

写到一半IntelliJ竟然挂了……

发表于 |

539. Minimum Time Difference 数列内最小时间差

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

1
2
Input: ["23:59","00:00"]
Output: 1

Note:
The number of time points in the given list is at least 2 and won’t exceed 20000.
The input time is legal and ranges from 00:00 to 23:59.

SOL

没看到note里面就开始想题,还以为是只有两个值的我写到一半发现写错,简直崩溃……(所以一定要认 真 审 题

解法1

复杂度: nlog(n) 主要是sort的复杂度

思路：

  • 提取出时间后直接变成分钟数，分钟差>1260时直接给小时间+2460，再做大时间-小时间的减法
  • 只需要对两个相邻时间进行减法，因为需要的是最短时间=！=，这个trick我竟然是看了答案才想到，还以为要分类计算啥的，说明有时候想的太复杂了(或者就是傻

总结:

  • 认真审题
  • 时间(list)向数字的转换
  • 集合(各种list)的使用还是要加强，不能每个方法都要现搜

一些小的注意点:

  1. 在生成ArrayList的时候，ArrayList是错误的, https://goo.gl/g9vo6m 指出应使用这种格式
1
List<Integer> xxx = new ArrayList<Integer>();

(注意左侧是list,<>里面是Integer,右边的可写可不写

  1. 分割String时使用的split()方法
  2. arrayList获取数组长度时用的是size（）非length（）; 获取arraylist元素使用.get（）
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
class Solution {
    public int findMinDifference(List<String> timePoints) {
        List<Integer> timeList = new ArrayList<>(); //<-创建集合存放所有时间 
        int time, timeDiff=12*60+1;
        String[] splitedTime;
        //读取所有时间->int arraylist中
        for (String s: timePoints){
            splitedTime = s.split(":"); //<-split函数
            time = (Integer.parseInt(splitedTime[0]))*60+Integer.parseInt(splitedTime[1]); //<-String to Int
            timeList.add(time);
        }
        Collections.sort(timeList);
        for(int i=0;i<timeList.size()-1;i++){ //<-注意arrayList用的是size（）非length（）
            int diff = Math.abs(timeList.get(i)-timeList.get(i+1));//获取arraylist中数使用.get（）
            if (diff<timeDiff){
                timeDiff = diff;
            }
        }
        int a=Math.abs(timeList.get(0)+24*60-timeList.get(timeList.size()-1));
        if(a<timeDiff){
        timeDiff = a;
        }
        return timeDiff;
    }
}

解法2

解法2 (https://goo.gl/ptB4F9 )就更简洁一些了. 因为时间数值只有24*60即1440个, 所以建立一个1440的boolean数组来标示是否出现各个时间点即可 (斯国一.jpg

复杂度: O(n)

注意:

  • 别忘了处理重复值的情况！！！(眼神放空
  • 比较大小用Math.min/max更配哦(((
  • length: array用(int[], string[]);
    length(): String相关Obj用(String, StringBuilder, etc);
    size(): Collection Obj用(ArrayList, Set, etc) via https://goo.gl/arGP91
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
47
class Solution {
    public int findMinDifference(List<String> timePoints) {
        boolean[] array = new boolean[24*60];
        int pre = Integer.MAX_VALUE;
        int first = Integer.MAX_VALUE;
        int last = Integer.MIN_VALUE;
        int timeDiff = Integer.MAX_VALUE;
        //time String to array
        for(String s: timePoints){
            String[] time = s.split(":");
            int hour = Integer.parseInt(time[0])*60;
            int minute = Integer.parseInt(time[1]);
            //!!!!!!!!!!!!!!!!!!!!!!!!!别忘了处理重复值的情况！！！（苦痛脸
            if (array[hour + minute]){
                return 0;
            }
            array[hour + minute] = true;
        }
        
        //compare
        for(int i=0;i<array.length;i++){ 
            if(array[i]){
                if(pre<Integer.MAX_VALUE){
                   //if(timeDiff>(i-pre)){
                   //    timeDiff = i-pre;
                   //}//用Math.min更简洁！
                    timeDiff = Math.min(timeDiff, i-pre);
                }
                pre = i;
                first = Math.min(first, i);
                last = Math.max(last, i);
                //if(i<first){//同上
                //    first = i;
                //}
                //if(i>last){//同上
                //    last = i;
                //}
            }
        }
        int gap = first + 24*60 - last;
        //if(gap<timeDiff){
        //    timeDiff = gap;
        //}
        timeDiff = Math.min(gap, timeDiff);
        return timeDiff;
    }
}

发表于 |

2. 链表两数相加

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.

1
2
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

SOL

直接对两个链表进行遍历(或者说对节点直接进行遍历操作而非单纯的从链表进行),复杂度是O(n)

难点在于

  • 链表的使用
  • 结构体中值和方法的调用
  • 对于加法各种情况的处理
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
/**
 * Definition for singly-linked list.
 * public class ListNode { <-注意这里是list node而非linked list
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode resultList = new ListNode(0);//由于不能new空node，所以任意赋值，返回时从下一个节点返回值即可
        ListNode t1 = l1;
        ListNode t2 = l2; 
        //ListNode t1 = l1, t2 = l2; 
        ListNode t3 = resultList;
        int digitSum = 0;
        while(t1 != null || t2 !=null){
            if (t1!=null){
                digitSum =digitSum + t1.val; //digitSum += t1.val
                t1=t1.next;//错误写法：t1=t1.next()
            }
            if(t2!=null){//注意t2和t1不要写成嵌套，是错误的逻辑
                    digitSum += t2.val;
                    t2=t2.next;
            } 
            t3.next = new ListNode(digitSum % 10);//这里要记得取余 注意这句是赋值给.next，且new了一个新node并赋值
            t3 = t3.next;
            digitSum = digitSum / 10; //传到下一位的进位，取商 digitSum/=10;
        }
        //别忘了最后一位carry上1的情况！
        if (digitSum == 1){
            t3.next = new ListNode(1);
        }
        return resultList.next;//这里直接把被copy的resultList.next返回，实际在队列中运算的是t3
    }
}

做这道题的时候还注意了一下java for each的用法:
在Java核心技术I-79页提出for each循环的语句格式为:

1
for (variable : collection) statement

定义一个变量用于暂存集合中的每一个元素,并执行相应的语句(或语句块).
Collection这一集合表达式必须是一个数组或者是一个实现了Iterable接口的类对象(例如ArrayList)

发表于 |

1. 两数求和问题

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

SOL

先实现了第一种最简单的解法, 整体遍历, 复杂度O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] sol = new int[2];
        for (int i = 0; i<nums.length; i++){
            for (int j = i+1; j<nums.length;j++){
                if (target == nums[i] + nums[j]){
                    sol[0] = i;
                    sol[1] = j;
                }
            }
        }
    return sol;
    } 
}

剩下的hashmap方法晚上再研究一下

发表于 |

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment