Q1.
There is a board with 2 rows and N columns, represented by a matrix M . Rows are numbered from 0 to 1 from top to bottom and columns are numbered from 0 to N-1 from left to right. Each cell contains either a 0 or a 1. You know that:
- the sum of integers in the 0-th (upper) row is equal to U,
- the sum of integers in the 1-st (lower) row is equal to L,
- the sum of integers in the K-th column is equal to C[K].
Your job is to recover M based on this information.
Write a function: function solution(U, L, C); that, given two integers U, L and an array C of N integers, as described above, returns a string describing the matrix M in the following format. The first part of the string should be the description of the upper row ( N characters: 0 or 1), then there should be comma (,) , and finally there should be the description of the lower row (N characters: 0 or 1.)
The output string should not contain any whitespace. If there exist multiple valid Ms, your function may return any one of them. If no valid M exists, your function should return the word IMPOSSIBLE.
Examples: 1. Given U = 3, L = 2, C = [2, 1, 1, 0, 1] , your function may, for example, return 11001,10100 which describes the following board:
Q2.
/*
- Date: 8-Oct-2019
- Description:
- John was sitting near to a fireplace in his house, trying to get some warmth
- from the fire. Fighting his cold at the end of a freezing, Short, dark winter
- day, he started wondering why it always had to be so cold during this season.
- That was when he came up with an idea.
- John stated that winter is the initial pan of the year in which it is always
- colder than in the remaining part. This latter part is called ‘summer’.Then
- he assumed that summer is always warmer than winter; that is, any temperature
- measured in winter is colder than every temperature measured in summer.
- Then he searched the Internet and found the previous years meteorological
- data, which contained the years temperature measurements. He began to wonder
- if it might be possible to divide the year into winter and summer so that
- winter comes before summer and each winter’s temperature measurement is
- smaller than any temperature measured in summer. In case there are many such
- possible partitions, find the one in which the winter period is as short as
- possible. (It is quite cold now; there is really no reason for winter to be
- longer than necessary…)
- Write a function that, given a sequence T of temperature measurements
- (specified as integer numbers), finds the partition of the year into winter
- and summer that meets the conditions above and makes winter as short as
- possible, then returns the length of the winter. Both winter and summer have
- to be at least one day long. You can assume that there exists at least one
- partition that satisfies this condition.
- For example, given: T = [5, -2, 3, 8, 6]
- the function should return 3, as after partitioning the year into
- winter: [5, -2, 3] and summer: [8, 6], each winter’s measurement is smaller
- than each summer’s temperature.
- On the other hand, for the following array: T = [-5, -5, -42, 6, 12]
- the function should return 4. The partition that minimizes the length of the
- winter is [-5, -5, -5, -42] and [6, 12]. Winter could also have length 5,
- but the function should return the shortest possible winter.
- Assume that:
- N is an integer within the range [2…300,000];
- each element of array T is an integer within the range
- There will be at least one correct way to divide the year into winter and
- summer.
- Complexity:
- expected worst-case time complexity is O(N)
- In programming words:
- Write a program to divide an array in such a way that all left side
- elements are smaller than any right side element .i.e.
- max of left sub-array < min of right sub-array.
- Output should be the count of number of elements in left sub-array.
- Implementation:
- Keep track of max number while moving from left to right, increment
- right-sub-array-count if new number is greater than max otherwise set counter
- to 0 and update max.
*/
第一道题很难，不知道大家有没有答案