Press "Enter" to skip to content

Posts tagged as “reverse”

花花酱 LeetCode 190. Reverse Bits

By zxi on September 30, 2019

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10101111110010110010011101101001.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Solution: Bit operation

Time complexity: O(1)
Space complexity: O(1)

C++

花花酱 LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

By zxi on September 15, 2019

Given a string s that consists of lower case English letters and brackets. 

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any bracket.

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"

Example 4:

Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"

Constraints:

  • 0 <= s.length <= 2000
  • s only contains lower case English characters and parentheses.
  • It’s guaranteed that all parentheses are balanced.

Solution: Stack

Use a stack of strings to track all the active strings.
Iterate over the input string:
1. Whenever there is a ‘(‘, push an empty string to the stack.
2. Whenever this is a ‘)’, pop the top string and append the reverse of it to the new stack top.
3. Otherwise, append the letter to the string on top the of stack.

Once done, the (only) string on the top of the stack is the answer.

Time complexity: O(n^2)
Space complexity: O(n)

C++

花花酱 LeetCode 92. Reverse Linked List II

By zxi on August 24, 2019

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Solution:

  1. Store the m – 1 and m-th item as prev and tail before reversing
  2. Reverse the m to n, return the head and tail->next of the reversed list
  3. Reconnect prev and head, tail and tail->next

Time complexity: O(n)
Space complexity: O(1)

C++

Python3

花花酱 LeetCode 917. Reverse Only Letters

By zxi on October 6, 2018

Problem

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

Input: "ab-cd"
Output: "dc-ba"

Example 2:

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Note:

  1. S.length <= 100
  2. 33 <= S[i].ASCIIcode <= 122
  3. S doesn’t contain \ or "

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1) – in place

C++/index

C++/iter

 

花花酱 LeetCode 31. Next Permutation

By zxi on October 2, 2018

Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution

Find the last acceding element x, swap with the smallest number y, y is after x that and y is greater than x.

Reverse the elements after x.

Time complexity: O(n)

Space complexity: O(1)

C++

Python3