LeetCode-时间复杂度简记

这到好。刚做到第四题。就来个难题,搞不下去了。

两个排序数组的中位数。

想想很简单。两个数组合起来排个序不就行了?
那这么简单。。后面还有一句话时间复杂度必须在O(log(m+n))。。也就是没那么简单了。。

先整理复习下时间复杂度的概念,再来做题吧。

时间复杂度

在计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。

定义总是难以理解。

通俗理解

下面是通俗的理解,不一定严谨但就那意思:

执行一行最简单的代码,需要单位时间1。记做O(1)。
执行二行最简单的代码,需要单位时间1*2。记做O(2)。
...
执行n行最简单的代码,需要单位时间1*n。记做O(n)。

可以看到随着n越大需要的时间是越多。
这就是时间复杂度。
O(1)O(2)...因为是常数级次数,一般都直接记做O(1)

时间复杂的计算

时间复杂度怎么计算呢?
其实就是计算代码执行的总的时间。也就是执行了多少行代码*单位时间。
算法无非就是一行一行代码、循环、递归组成。
那么一行代码是1。

  1. 循环递归则是根据循环递归次数来计算,比如N次循环那么O(n)。
  2. 如果是循环套循环就是n*n次,O(n^2)。
  3. 再比如O(logn),怎么来的呢?典型的就是二分查找。
    二分查找的执行次数其实就是每次减半,直至K次后只有1个元素,换句话说就是减半的次数即为代码执行的次数,那么公式为:

n/2^k=1
2^k=n
k=log(n) //log的底不写一般为2
因此时间复杂度为O(logn)

O(log(m+n))意味着什么

我们可以反过来推。
还是设次数为k,k=log(m+n),那么(m+n)/ 2^k=1 -> m/2^k + n/2^k=1。
意味着需要一个很小的执行次数来完成此算法,感觉像2个二分查找~~

LeetCode-无重复字符的最长子串

题目

给定一个字符串,找出不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc",其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b",其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke",其长度为 3。

 请注意,答案必须是一个子串,"pwke" 是一个子序列 而不是子串。

思路

从字符串中找出最长的子串。
首先分析得,子串肯定是连续的,那么可以定义一个滑动的窗口。
这个窗口保存的是当前没有重复字母的子串,一旦出现重复,则将窗口向前移动,也就是把从(包括)重复的那个字母前面的字符删除除。看上去就像一个窗口向前移动。最后记录下最大的不重复的长度即是结果。

答案

class Solution {
    public int lengthOfLongestSubstring(String str) {
        if(str.length() == 0){
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        StringBuilder window = new StringBuilder();
        int maxLen = -1;
        for (int i = 0; i < str.length(); i++){
            Character character = str.charAt(i);
            if(map.containsKey(character)){
                if (window.length() > maxLen){
                    maxLen = window.length();
                }
                int index = map.get(character);
                window.replace(0, index + 1, "");
                window.append(character);
                map.clear();
                for (int j = 0; j < window.length(); j++){
                    map.put(window.charAt(j), j);
                }
                continue;
            }
            window.append(character);
            map.put(character, window.length() - 1);
        }
        if (window.length() > maxLen){
            maxLen = window.length();
        }
        return maxLen;  
    }
}

哎代码太复杂,其实不需要弄个真正的字符串来充当window。只需要用一个index来表示即可。下面是优化过的代码时间复杂度为O(n):

class Solution {
    public int lengthOfLongestSubstring(String str) {
        HashMap<Character, Integer> map = new HashMap<>();
        int count = str.length();
        int len = 0;
        int startIndex = 0;
        for (int i = 0; i < count; i++){
            Character character = str.charAt(i);
            if(map.containsKey(character)){
                int index = map.get(character);
                if (index >= startIndex){
                    len = Math.max(i - startIndex, len);
                    startIndex = index + 1;
                }
            }
            map.put(character, i);
        }
        return Math.max(count - startIndex, len);
    }
}

LeetCode

这又扯淡了。
没事刷刷LeetCode。对自己面试也有帮助。

LeetCode-两数相加

题目

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

思路

1.两个链表每次同时取一个item相加
2.记录进位的情况,在下一次相加时加上进位
3.考虑两个链表长度不一的情况
4.最后一个如果进位记得加一个node

答案

答案比较丑。看了官方答案写的挺简洁··

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l11, ListNode l22) {
        ListNode l1 = l11;
        ListNode l2 = l22;
            
        ListNode l3 = null;
        ListNode l4 = null;
        int tmp = 0;
        boolean end = false;
        while(true){
            int l1Val = 0;
            int l2Val = 0;
            if(l1 != null){
                l1Val = l1.val;
            }
            if(l2 != null){
                l2Val = l2.val;
            }
            int val = l1Val + l2Val + tmp;
            if(val >= 10){
                tmp = 1;
                val = val % 10;
            }else {
                tmp = 0;
            }
            if(l3 == null){
                l3 = new ListNode(val);
                l4 = l3;
            }else {
                ListNode tmpNode = new ListNode(val);
                l4.next = tmpNode;
                l4 = tmpNode;
            }
            
            if((l1 == null || l1.next == null) && (l2 == null || l2.next == null)){
                if(tmp == 1){
                    l4.next = new ListNode(1);
                }
                break;
            }
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
          
        }
       
        return l3;
    }
}