ARTS - Week 2

ARTS - Week 2

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 239 - Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Difficulty: Hard

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 

Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7

Solution

第一种解法:优先队列

使用优先队列中最大堆的数据结构,将数组中每 k 个值放入最大堆中,取出堆顶元素即为当前 window 中所需最大值。之后按需循环移动 window,每次更新堆中的数据,得到所有的最大值数组。

PS:由于 Ruby 和 Python 中没有现成的 PriorityQueue 数据结构,所以此种解法使用 Java 完成。

# Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] result = new int[len - k + 1];
        if(len == 0) return new int[0];
        Queue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
            @Override
            public int compare(Integer i1, Integer i2){
                return Integer.compare(i2, i1);
            }
        });

        for(int i = 0; i < k; i++){
            queue.add(nums[i]);
        }

        result[0] = queue.peek();

        for(int i = k; i < len; i++){
            queue.remove(nums[i - k]);
            queue.add(nums[i]);
            result[i - k + 1] = queue.peek();
        }

        return result;
    }
}

复杂度

  • Time complexity: O(nlogn);
  • Space complexity: O(1);

运行结果

Runtime: 51 ms.
Your runtime beats 21.41 % of java submissions.

第二种解法:双向队列

在一个双向队列中,维护队列里面最前面元素是最大的。每次循环到新的元素时,就从队列最后一个元素依次和这个新的元素进行比较。把所有小于新元素的队列元素都清除出队列。因为小于新元素的元素肯定不是当前最大值,是无效的。维持队列中从大到小排列的顺序。

Python 中的列表和 Ruby 中的数组都可以当作双向队列使用。

# Python

class Solution:
    def maxSlidingWindow(self, nums, k):
        if not nums: return []
        window, res = [], []
        for i, x in enumerate(nums):
            if i >= k and window[0] <= i - k:
                window.pop(0)
            while window and nums[window[-1]] <= x:
                window.pop()
            window.append(i)
            if i >= k - 1:
                res.append(nums[window[0]])

        return res
# Ruby
def max_sliding_window(nums, k)
  return [] if k < 1 || k > nums.size || nums.empty?

  window, res = [], []
  nums.each_with_index do |num, index|
    window.shift if index >= k && window[0] <= index - k

    while !window.empty? && nums[window[-1]] <= num
      window.pop
    end

    window.push(index)

    res.push(nums[window[0]]) if index >= k - 1
  end

  return res
end

复杂度

  • Time complexity: O(n)。双向队列的插入和删除均为 O(1);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 136 ms.
Your runtime beats 55.02 % of python3 submissions.

Ruby:
Runtime: 92 ms.
Your runtime beats 100.00 % of ruby submissions.

相较 Java 的解法,Python 和 Ruby 的方式中时间复杂度均有优化,但运行时间却反而增加了,难道语言间效能差这么多?😂

一种算法比另外一种在当前环境下更优,一定是有地方解决了那种算法哪里做的无用功。在这道题里堆维护了 window 里 k 个元素的大小顺序,而双向队列只是记录了最大值,从而优化了性能。

LeetCode Problems 242 - Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Difficulty: Easy
Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Solution

第一种解法:字符串排序后比较

对字符串排序后比较是否一致,简单粗暴。

# Python

class Solution:
    def isAnagram(self, s, t):
        return sorted(s) == sorted(t)
# Ruby

def is_anagram(s, t)
  return s.chars.sort == t.chars.sort
end

复杂度

  • Time complexity: O(nlogn);快速排序的时间复杂度为 O(nlogn);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 132 ms.
Your runtime beats 5.71 % of python3 submissions.

Ruby:
Runtime: 116 ms.
Your runtime beats 61.11 % of ruby submissions.

第二种解法:哈希表

使用哈希表统计每个字符出现的次数。

# Python

class Solution:
    def isAnagram(self, s, t):
        dic1, dic2 = {}, {}
        for item in s:
            dic1[item] = dic1.get(item, 0) + 1
        for item in t:
            dic2[item] = dic2.get(item, 0) + 1
        return dic1 == dic2
# Ruby

def is_anagram(s, t)
  hash1, hash2 = {}, {}
  s.split('').each {|char| hash1[char] = hash1[char].to_i + 1}
  t.split('').each {|char| hash2[char] = hash2[char].to_i + 1}

  return hash1 == hash2
end

复杂度

  • Time complexity: O(n);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 60 ms.
Your runtime beats 67.67 % of python3 submissions.

Ruby:
Runtime: 172 ms.
Your runtime beats 14.44 % of ruby submissions.


Review

Understanding How Python is Used in Data Science

Why Python is the Right Programming Language for Data Science

Python 发展成为数据科学最火爆的语言,有以下几点原因:

  • 语法简单,易于学习入门,这使得数据科学家容易上手使用;
  • 已有大量的类库可以用于数据分析,很方便的将数据可视化;

之前我以为只有 Python 才能做那些数据分析的工作。但今天通过检索,发现 Ruby 可以做一样的事情。只不过 Python 发展出了大量可用于数据科学的类库,使数据科学家处理数据的效率越来越高,也就促使越来越多的人使用,形成了正向循环,现在成为了数据科学中最热门的语言。


Tip

本周学习了 Python 的语法,并使用 matplitlib 和 Pygal 将批量数据可视化,以分析数据进而找到期望中的规律。Python 作为瑞士军刀一般的存在,用于快速的做一些小工具还是蛮有意思的。


Share

作为脚本语言,PHP、Ruby、Python 等语言的本质区别是什么?每一种语言肯定是解决了之前语言存在的某种问题而被发明并广泛使用。

为何 PHP 被吐槽不够优雅,Ruby Python 会一直被诟病性能问题。也许把所有这些都放进整个编程语言的发展历史中去看,会找到每种语言那样去设计的原因。

# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×