刷题记录

Problem: A string  S  of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts. Example 1: Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts. Note: S  will have length in range  [1, 500] . S  will consist of lowercase letters ( 'a'  to  'z' ) only. Analysis: Greedy. Use a map the store the last index of each char's appearance. what makes the partition successful is that the last appearance (end) stops to increment. It means no char from start to end appears after end. Solution: class Solution { ...

Problem: 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. Analysis: Two pass, init every child with 1 candy. 1. Scan from left to right, if ratings[i] < ratings[i + 1], set candies[i + 1] to candies[i] + 1. 2. Scan from right to left, if ratings[i] > ratings[i+1], get the larger one of candies[i] and candies[i + 1] + 1. If w...

Problem: Given  n  non-negative integers  a 1 ,  a 2 , ...,  a n , where each represents a point at coordinate ( i ,  a i ).  n  vertical lines are drawn such that the two endpoints of line  i  is at ( i ,  a i ) and ( i , 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and  n  is at least 2. Analysis: This problem uses greedy approach, I have no idea how the greedy approach can get the right result. The code is self explanatory.  class Solution { public int maxArea ( int [] height) { if (height == null || height . length == 0 ) return 0 ; int l = 0 , r = height . length - 1 , res = 0 ; while (l < r) { res = Math . max(res, Math . min(height[l], height[r]) * (r - l)); if (height[l] < height[r]) { ...