LeetCode Weekly Contest 100

https://leetcode.com/contest/weekly-contest-100

Monotonic Array

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

Note:

1. 1 <= A.length <= 50000
2. -100000 <= A[i] <= 100000

Increasing Order Search Tree

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1:

Note:

1. The number of nodes in the given tree will be between 1 and 100.
2. Each node will have a unique integer value from 0 to 1000.

Bitwise ORs of Subarrays

We have an array A of non-negative integers.

For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].

Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)

Example 1:

Example 2:

Example 3:

Note:

1. 1 <= A.length <= 50000
2. 0 <= A[i] <= 10^9

Orderly Queue

A string S of lowercase letters is given. Then, we may make any number of moves.

In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.

Return the lexicographically smallest string we could have after any number of moves.

Example 1:

Example 2:

Note:

1. 1 <= K <= S.length <= 1000
2. S consists of lowercase letters only.

K>1时，相邻元素S[i]S[i+1]可以在调到首尾后通过两次操作交换相对位置，即有一字符串xxxx[ab]xxx可以通过如下几步改变为xxxx[ba]xxx:

• xxxx[ab]xxx
• [ab]xxxxxxx 不断把第一位调换到末尾
• [a]xxxxxxx[b] 把第二位调换到末尾
• xxxxxxx[ba] 把第一位调换到末尾
• xxxx[ba]xxx 不断把第一位调换到末尾

K=1时，对于每个i考虑S[i:]+S[:i]即当S[i]作为第一个字符的情况即可。