lib.rs

struct Solution {}

impl Solution {
  // 理解起来应该很容易，但是时间复杂度有点大，可以用hashMap来优化查找时间，由于主要目的是为了熟悉Rust语法这里就沿用这个答案
  pub fn lemonade_change(bills: Vec<i32>) -> bool {
    let mut dp = vec![0; bills.len()];
    let mut i = 0;
    let mut res = true;
    while i < bills.len() {
      if bills[i] == 5 {
        dp[i] = bills[i]
      } else {
        let mut temp = bills[i];
        while temp != 5 {
          let max = get_max(&mut dp, temp); // 找到dp数组中小于当前顾客给的金额的最大值
          if max == 0 {
            res = false;
            break;
          }
          temp = temp - max; // 减去找到的金额大小，如果不满足5，则继续找，例如20-10-5=5
        }
        if res == false {
          break;
        }
        dp[i] = bills[i];
      }
      i += 1;
    }
    res
  }
}

fn get_max(dp: &mut Vec<i32>, current: i32) -> i32 {
  let mut max = 0;
  let mut index = 0;
  let mut i = 0;
  while i < dp.len() {
    let val = dp[i];
    if val > max && val < current {
      max = val;
      index = i;
    }
    i += 1;
  }

  dp[index] = 0; // 找到金额后置为0代表已经找零给顾客了
  max
}
#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn tests() {
    let coins: Vec<i32> = vec![
      5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5,
      20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5,
      10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5,
      20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5,
      10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5,
      20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5,
      10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5,
      20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5,
      10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5,
      20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5,
      10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5,
      20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5,
      10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5,
      20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5,
      10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5, 20, 5, 10, 5,
      20, 5, 10, 5, 20, 5, 10, 5, 20,
    ];
    Solution::lemonade_change(coins);
  }
}