花花酱 LeetCode 899. Orderly Queue

By zxi on September 1, 2018

Problem

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:

Input: S = "cba", K = 1
Output: "acb"
Explanation: 
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".

Example 2:

Input: S = "baaca", K = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1st character ("b") to the end, obtaining the string "aacab".
In the second move, we move the 3rd character ("c") to the end, obtaining the final result "aaabc".

Note:

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

Solution: Rotation or Sort?

if \(k =1\), we can only rotate the string.

if \(k > 1\), we can bubble sort the string.

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string orderlyQueue(string S, int K) {

if (K > 1) {

sort(begin(S), end(S));

return S;

}

string ans = S;

for (int i = 1; i < S.size(); ++i)

ans = min(ans, S.substr(i) + S.substr(0, i));

return ans;

}

};

Java

// Author: Huahua

class Solution {

public String orderlyQueue(String S, int K) {

if (K > 1) {

char[] chars = S.toCharArray();

Arrays.sort(chars);

return new String(chars);

}

String ans = S;

for (int i = 1; i < S.length(); ++i) {

String tmp = S.substring(i) + S.substring(0, i);

if (tmp.compareTo(ans) < 0) ans = tmp;

}

return ans;

}

Python3 SC O(n^2)

# Author: Huahua 48 ms

class Solution:

def orderlyQueue(self, S, K):

if K > 1: return ''.join(sorted(S))

return min([S[i:] + S[0:i] for i in range(0, len(S))])

Python3 SC O(n)

# Author: Huahua 36 ms

class Solution:

def orderlyQueue(self, S, K):

if K > 1: return ''.join(sorted(S))

ans = S

for i in range(0, len(S)):

ans = min(ans, S[i:] + S[0:i])

return ans

花花酱 LeetCode 897. Increasing Order Search Tree

By zxi on September 1, 2018

Problem

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:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9

Note:

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

Solution: In-order traversal

root = 5

inorder(root.left) 之后

self.prev = 4

（1-4）已经处理完了，这时候的树是很奇怪的一个形状，3即是2的右子树，又是5的左子树。

2 5

\ / \

3 6

\ \

prev -> 4 8

/ \

7 9

—————————

5.left = None # 把5->3的链接断开

/ \

7 9

—————————–

self.prev.right = root <=> 4.right = 5

把5接到4的右子树

5 <– prev

/ \

7 9

self.prev = root <=> prev = 5

inorder(5.right) <=> inorder(6) 然后再去递归处理6（及其子树）即可。

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 64 ms

class Solution {

public:

TreeNode* increasingBST(TreeNode* root) {

TreeNode dummy(0);

prev_ = &dummy;

inorder(root);

return dummy.right;

}

private:

TreeNode* prev_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

prev_->right = root;

prev_ = root;

prev_->left = nullptr;

inorder(root->right);

}

};

Java

class Solution {

private TreeNode prev;

public TreeNode increasingBST(TreeNode root) {

TreeNode dummy = new TreeNode(0);

this.prev = dummy;

inorder(root);

return dummy.right;

}

private void inorder(TreeNode root) {

if (root == null) return;

inorder(root.left);

this.prev.right = root;

this.prev = root;

this.prev.left = null;

inorder(root.right);

}

Python3

class Solution:

def increasingBST(self, root):

dummy = TreeNode(0)

self.prev = dummy

def inorder(root):

if not root: return None

inorder(root.left)

root.left = None

self.prev.right = root

self.prev = root

inorder(root.right)

inorder(root)

return dummy.right

花花酱 LeetCode 896. Monotonic Array

By zxi on September 1, 2018

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.

Solution:

C++

// Author: Huahua

class Solution {

public:

bool isMonotonic(vector<int>& A) {

bool inc = true;

bool dec = true;

for (int i = 1; i < A.size(); ++i) {

inc &= A[i] >= A[i - 1];

dec &= A[i] <= A[i - 1];

}

return inc || dec;

}

};

Java

class Solution {

public boolean isMonotonic(int[] A) {

boolean inc = true;

boolean dec = true;

for (int i = 1; i < A.length; ++i) {

inc &= A[i] >= A[i - 1];

dec &= A[i] <= A[i - 1];

}

return inc || dec;

}

Python

# Author: Huahua

class Solution:

def isMonotonic(self, A):

inc = True;

dec = True;

for i in range(1, len(A)):

inc = inc and A[i] >= A[i - 1]

dec = dec and A[i] <= A[i - 1]

return inc or dec;

Posts published in September 2018

花花酱 LeetCode 899. Orderly Queue

Problem

Solution: Rotation or Sort?

C++

Java

Python3 SC O(n^2)

Python3 SC O(n)

花花酱 LeetCode 897. Increasing Order Search Tree

Problem

Solution: In-order traversal

C++

Java

Python3

花花酱 LeetCode 896. Monotonic Array

Solution:

C++

Java

Python