solve #136

aylei · aylei · commit 948f712b9df2 · 2019-02-23T00:07:32.000+08:00
diff --git a/src/lib.rs b/src/lib.rs
@@ -131,3 +131,6 @@ mod n0129_sum_root_to_leaf_numbers;
 mod n0130_surrounded_regions;
 mod n0131_palindrome_partitioning;
 mod n0132_palindrome_partitioning_ii;
+mod n0134_gas_station;
+mod n0135_candy;
+mod n0136_single_number;
diff --git a/src/n0134_gas_station.rs b/src/n0134_gas_station.rs
@@ -0,0 +1,75 @@
+/**
+ * [134] Gas Station
+ *
+ * There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
+ * 
+ * You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
+ * 
+ * Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
+ * 
+ * Note:
+ * 
+ * 
+ * 	If there exists a solution, it is guaranteed to be unique.
+ * 	Both input arrays are non-empty and have the same length.
+ * 	Each element in the input arrays is a non-negative integer.
+ * 
+ * 
+ * Example 1:
+ * 
+ * 
+ * Input: 
+ * gas  = [1,2,3,4,5]
+ * cost = [3,4,5,1,2]
+ * 
+ * Output: 3
+ * 
+ * Explanation:
+ * Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
+ * Travel to station 4. Your tank = 4 - 1 + 5 = 8
+ * Travel to station 0. Your tank = 8 - 2 + 1 = 7
+ * Travel to station 1. Your tank = 7 - 3 + 2 = 6
+ * Travel to station 2. Your tank = 6 - 4 + 3 = 5
+ * Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
+ * Therefore, return 3 as the starting index.
+ * 
+ * 
+ * Example 2:
+ * 
+ * 
+ * Input: 
+ * gas  = [2,3,4]
+ * cost = [3,4,3]
+ * 
+ * Output: -1
+ * 
+ * Explanation:
+ * You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
+ * Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
+ * Travel to station 0. Your tank = 4 - 3 + 2 = 3
+ * Travel to station 1. Your tank = 3 - 3 + 3 = 3
+ * You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
+ * Therefore, you can't travel around the circuit once no matter where you start.
+ * 
+ * 
+ */
+pub struct Solution {}
+
+// submission codes start here
+
+impl Solution {
+    pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
+        0
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_134() {
+    }
+}
diff --git a/src/n0135_candy.rs b/src/n0135_candy.rs
@@ -0,0 +1,81 @@
+/**
+ * [135] Candy
+ *
+ * There are N children standing in a line. Each child is assigned a rating value.
+ * 
+ * You are giving candies to these children subjected to the following requirements:
+ * 
+ * 
+ * 	Each child must have at least one candy.
+ * 	Children with a higher rating get more candies than their neighbors.
+ * 
+ * 
+ * What is the minimum candies you must give?
+ * 
+ * Example 1:
+ * 
+ * 
+ * Input: [1,0,2]
+ * Output: 5
+ * Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
+ * 
+ * 
+ * Example 2:
+ * 
+ * 
+ * Input: [1,2,2]
+ * Output: 4
+ * Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
+ *              The third child gets 1 candy because it satisfies the above two conditions.
+ * 
+ * 
+ */
+pub struct Solution {}
+
+// submission codes start here
+
+impl Solution {
+    pub fn candy(ratings: Vec<i32>) -> i32 {
+        let mut from = 0;
+        let mut n = 1;
+        let mut last = 1;
+        let mut ascending = false;
+        for i in 1..ratings.len() {
+            if ratings[i] == ratings[i-1] {
+                n += 1;
+                from = i;
+                ascending = false;
+            } else if ratings[i] >= ratings[i-1] {
+                from = i;
+                ascending = true;
+                last += 1;
+                n += last;
+            } else {
+                if ascending {
+                    last = 1;
+                    from = i;
+                    ascending = false;
+                }
+                n += (i - from + 1) as i32;
+            }
+        }
+        n
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_135() {
+        assert_eq!(Solution::candy(vec![3,2,1,2,3]), 11);
+        assert_eq!(Solution::candy(vec![2,2,1,2,2]), 7);
+        assert_eq!(Solution::candy(vec![1,0,2]), 5);
+        assert_eq!(Solution::candy(vec![1,2,2]), 4);
+        assert_eq!(Solution::candy(vec![1,1,1,1,1,1]), 6);
+        assert_eq!(Solution::candy(vec![1,2,2,2,2,2,2,0]), 10);
+    }
+}
diff --git a/src/n0136_single_number.rs b/src/n0136_single_number.rs
@@ -0,0 +1,45 @@
+/**
+ * [136] Single Number
+ *
+ * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
+ * 
+ * Note:
+ * 
+ * Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
+ * 
+ * Example 1:
+ * 
+ * 
+ * Input: [2,2,1]
+ * Output: 1
+ * 
+ * 
+ * Example 2:
+ * 
+ * 
+ * Input: [4,1,2,1,2]
+ * Output: 4
+ * 
+ * 
+ */
+pub struct Solution {}
+
+// submission codes start here
+impl Solution {
+    pub fn single_number(nums: Vec<i32>) -> i32 {
+        nums.iter().fold(0, |acc, &num| { acc ^ num })
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_136() {
+        assert_eq!(Solution::single_number(vec![2,2,1]), 1);
+        assert_eq!(Solution::single_number(vec![4,1,2,1,2]), 4);
+    }
+}
