Chapter 3: Collections

Ruby SDE-Foundations

0 概述

Collection 包括String, Array, Hash

0.1 如果String没有对应的函数，那么除非有in-place处理的要求，总是可以用str.chars或者str.split("")把String的问题转化成Array的问题

e.g.
def caesar_cipher(message, n)
  alphabet = ("a".."z").to_a
  new_message = ""
  new_chars = message.chars.map do |char|
    old_index = alphabet.index(char)    
    new_char = (old_index != nil ? alphabet[(old_index + n)%26] : char)
    new_char
  end
  return new_chars.join("")
end

1 处理Sentence的问题

sentence中包含多个词，用空格隔开，处理每个词

处理这样的string, 总是通过str.split(" ")把问题转换成array问题 (array of strings), 然后对array进行遍历 (arr.each/ arr.each_with_index / arr.map) 处理每个分隔开的word.

1.1 sentence中包含多个词，用空格隔开，转换成另一句sentence

通过str.split(" ")把问题转换成array问题 (array of strings), 然后把array用array.map变换成新array new_arr, 最后再用new_arr.join(" ")转回为string

words = str.split(" ")
# 把parts按照题意转换成目标array
new_words = words.map do |part|
  new_word = ...
  new_word
end
return new_Words.join(" ")

2 Collection的聚合类问题，输入输出是n => 1的结构

2.1 由一组元素得出一个非boolean的结果

给定一组元素，得出一个非boolean的结果(boolean见2.2)，通常是array元素同样的类型, 用array.inject 由acc和ele得到new_acc再结算

e.g. Write a method matrix_addition_reloaded that accepts any number of matrices as arguments. The method should return a new matrix representing the sum of the arguments. Matrix addition can only be performed on matrices of similar dimensions, so if all of the given matrices do not have the same "height" and "width", then return nil.

def matrix_addition_reloaded(*matrices)
    return matrices.inject() do |acc, m|
        return nil if acc.length != m.length || acc[0].length != m[0].length
        matrix_addition(acc, m)
    end
end

2.2 对一组元素做一个判断(boolean) 的问题

给定一组元素, 对某个事实做true or false判断的问题,可以认为是inject的特殊情况, 用:

全都是 / 只存在 => array.all? or (0..num).all

# Write a method, `only_vowels?(str)`, that accepts a string as an arg.
# The method should return true if the string contains only vowels.
# The method should return false otherwise.
def only_vowels?(str)
    vowels = "aeiou"
    str.split("").all? { |char| vowels.include?(char) }
end

def is_sorted(arr)
    (0...arr.length - 1).all? { |i| arr[i] <= arr[i + 1] }
end

有没有 / 至少有一个 => array.any? or (0..num).any

# Write a method, adult_in_group?(people), that accepts an array containing people.
# The method should return true if there is at least 1 person with an age of 18 or greater.
# The method should return false otherwise.
def adult_in_group?(people)
    people.any? { |person| person[:age] >= 18 }
end

完全没有 / 除去某个就没有了 => array.none? or (0..num).none

Write a method, coprime?(num_1, num_2), that accepts two numbers as args.The method should return true if the only common divisor between the two numbers is 1. The method should return false otherwise. For example coprime?(25, 12) is true because 1 is the only number that divides both 25 and 12.

def coprime?(num_1, num_2)
    (2..num_1).none? { |factor| num_1 % factor == 0 && num_2 % factor == 0}
end

3. 在Collection中处理相邻的元素关系的问题

对于需要比较或者交换前后元素的情况，用(0...arr.length-1)配合arr[idx]比直接用arr.each.with_index更好, 因为有时候我们需要去掉头尾的部分. 如果头尾具有特殊性，则对头尾和中间元素 ((1...arr.length-1))分开处理.

def peak_finder(arr)
    peaks = []
    return [] if arr.length == 0
    if arr.length > 0 && arr[0] > arr[1]
        peaks << arr[0]
    end
    (1...arr.length-1).each do |idx|
        if arr[idx] > arr[idx-1] && arr[idx] > arr[idx+1]
            peaks << arr[idx]
        end
    end
    if arr.length > 0 && arr[-1] > arr[-2]
        peaks << arr[-1]
    end
    return peaks
end

3.1 分段处理的问题

1. 先处理collection为空的情况;
2. 用一个变量来记录当前段的状态，然后当arr[idx] != arr[idx+1]时清算之前段，并且reset这个变量。注意变量的初始值应该把每段的第1个元素考虑在内，即count = 1。
3. 处理好最后一个idx，即idx == nums.length-1

e.g. #  p compress_str("aaabbc")        # => "3a2bc"
def compress_str(str)
    return str if str.empty?
    count = 1
    new_str = ""
    (0...str.length).each do |idx|
        if idx != str.length - 1 && str[idx] == str[idx+1]
            count += 1
        else
            new_str += count == 1 ? str[idx] : count.to_s + str[idx]
            count = 1
        end
    end
    return new_str
end

# 674. Longest Continuous Increasing Subsequence
def find_length_of_lcis(nums)
    return 0 if nums.empty?
    max_count, count = 1, 1
    (0...nums.length).each do |idx|
        # 可以认为越界元素一定不会满足条件
        if idx != nums.length-1 && nums[idx] < nums[idx+1]
            count += 1
        else
            max_count = count if count > max_count
            count = 1
        end
    end
    return max_count
end

4. 对Collection进行反复操作直到满足条件的问题

可以用一个变量completed = false, 然后用completed这个boolean变量去记录每一轮的情况，直到completed为true

completed = false
until completed
    completed = true                    # 默认这一轮completed为true
    (0...arr.length).each do |idx|
        # 处理每一个arr[idx]  
        if condition 满足一定条件下
            # 修改arr[idx]
            completed = false
        end
    end
end
return arr

e.g. bubble sort
def bubble_sort(array)
    sorted = false
    until sorted
        sorted = true
        (0...array.length - 1).each do |i|
            if array[i] > array[i + 1]
                array[i], array[i + 1] = array[i + 1], array[i]
                sorted = false
            end
        end
    end
    return array
end

5. 在Collection中查找的问题

5.1 查找所有满足条件的元素（的数量）

用array.select，block里输出需要满足的条件。如果只需要元素的数量，则可以用arr.count

5.2 查找第一个/最后一个满足条件的元素

这类问题适合单独用一个函数实现(因为找到后可能需要立即退出查找)，用变量idx = 0或idx = arr.length-1, 用while循环找到，即返回.

def hipsterfy(word)
  vowels = "aeiou"
  i = word.length - 1
  while i >= 0
    if vowels.include?(word[i])
      return word[0...i] + word[i+1..-1]
    end
    i -= 1
  end
  word
end

5.3 已知range查找的问题

例如找因子, 找公因子, 找质数, 这类问题等同于在collection中查找的问题。

5.3.1 知道算子的范围，用range (1..num).each来逐个检查

def is_prime?(num) # 实际上是查找因子
    return false if num <= 1
    (2..num).each do |n|
        return false if num % n == 0
    end
    return true
end

5.3.2 知道结果的范围，用while result <= num和i += 1来逐个检查

def perfect_square?(num)
    i = 1
    square = nil
    while square <= num
        square = i * i
        return true if square == num
        i += 1
    end
    return false
end

def power_of_two?(num)
    return true if num == 1
    result = 1
    while result <= num
      result = result * 2
      return true if result == num
    end
    return false
end

5.4 查找第n个或者前n个满足条件的元素

通常这类问题都不能用select因为我们并不知道元素所处的范围

从idx = 0开始，
查找第n个元素，用一个count = 0来记录元素的数量，until count == n
查找前n个元素，用一个array = []来记录所有元素，until array.length == n
在循环内，idx递增，每次找到都记录给count或者array

def nth_prime(n)
  count = 0
  num = 1
  until count == n
    num += 1
    if is_prime?(num)
        count += 1
    end
  end
  num
end

6 对称和反转

检查一个Collection是否对称，或者对一个Collection进行反转，用头尾i = 0, j = arr.length - 1两个marker，以及while i < j相向而行。然后每次都对arr[i]和arr[j]进行比较或者交换。

e.g.
def palindrome?(string)
  i, j = 0, string.length - 1
  while i < j
    return false if string[i] != string[j]
    i += 1
    j -= 1
  end
  return true
end

7 求collection内元素的两两组合

arr.each_with_index do |ele1, idx1|
  arr.each_with_index do |ele2, idx2|
    if idx2 > idx1
      # do something about ele1 and ele2

e.g.
def substrings(string)
  subs = []
  (0...string.length).each do |start_idx|
    (0...string.length).each do |end_idx|
      subs << string[start_idx..end_idx] if start_idx <= end_idx
    end
  end
  subs
end

8 Collection内统计所有元素的问题

例如是否unique，是否duplicate，两个collection元素是否相同，一般可以新建一个Hash.new作为counter，然后对collection进行循环的同时，检查 counter内已有的记录，并且记录新的元素。

def unique_chars?(string)
    hash = Hash.new(0)
    string.each_char do |char|
        return false if hash.has_key?(char)
        hash[char] += 1
    end
    true
end