花花酱 LeetCode 7. Reverse Integer

By zxi on September 12, 2018

Problem

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹− 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Solution: Simulation

Reverse digit by digit. Be careful about the overflow and negative numbers (especially in Python)

Time complexity: O(log(x)) ~ O(1)

Space complexity: O(log(x)) ~ O(1)

C++

// Author: Huahua

class Solution {

public:

int reverse(int x) {

int ans = 0;

while (x != 0) {

int r = x % 10;

if (ans > INT_MAX / 10 || ans < INT_MIN / 10) return 0;

ans = ans * 10 + r;

x /= 10;

}

return ans;

}

};

Java

class Solution {

public int reverse(int x) {

int ans = 0;

while (x != 0) {

int r = x % 10;

if (ans > Integer.MAX_VALUE / 10 || ans < Integer.MIN_VALUE / 10) return 0;

ans = ans * 10 + r;

x /= 10;

}

return ans;

}

Python3

class Solution:

def reverse(self, x):

min_val = -(2**31);

max_val = 2**31 - 1;

sign = -1 if x < 0 else 1

x = abs(x)

ans = 0

while x != 0:

ans = ans * 10 + (x % 10)

x //= 10

ans *= sign

if ans > max_val or ans < min_val: return 0

return ans

花花酱 LeetCode 189. Rotate Array

By zxi on August 6, 2018

Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3 
Output: [5,6,7,1,2,3,4]
Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] 
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input:[-1,-100,3,99] and k = 2 
Output: [3,99,-1,-100] 
Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Solution 1: Simulate rotation with three reverses.

If k >= n, rotating k times has the same effect as rotating k % n times.

[1,2,3,4,5,6,7], K = 3

[5,6,7,1,2,3,4]

We can simulate the rotation with three reverses.

reverse the whole array O(n) [7,6,5,4,3,2,1]
reverse the left part 0 ~ k – 1 O(k) [5,6,7,4,3,2,1]
reverse the right part k ~ n – 1 O(n-k) [5,6,7,1,2,3,4]

Time complexity: O(n)

Space complexity: O(1) in-place

C++

class Solution {

public:

void rotate(vector<int>& nums, int k) {

if (nums.empty()) return;

k %= nums.size();

if (k == 0) return;

reverse(begin(nums), end(nums));

reverse(begin(nums), begin(nums) + k);

reverse(begin(nums) + k, end(nums));

}

};

花花酱 LeetCode 345. Reverse Vowels of a String

By zxi on July 19, 2018

Problem

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

Solution

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string reverseVowels(string s) {

int i = 0;

int j = s.size() - 1;

while (i < j) {

while (!isVowel(s[i]) && i < j) ++i;

while (!isVowel(s[j]) && i < j) --j;

swap(s[i++], s[j--]);

}

return s;

}

private:

bool isVowel(char c) {

c = tolower(c);

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

}

};

花花酱 LeetCode 541. Reverse String II

By zxi on March 21, 2018

Problem

题目大意：把字符串分成块，每块长度2k，单独反转每一块的前k的字符。

https://leetcode.com/problems/reverse-string-ii/description/

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

Solution

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

string reverseStr(string s, int k) {

const int n = s.length();

for (int i = 0; i <= n / k; i += 2)

std::reverse(s.begin() + i * k, s.begin() + min(n, (i + 1) * k));

return s;

}

};

Posts tagged as “reverse”

花花酱 LeetCode 7. Reverse Integer

Problem

Solution: Simulation

C++

Java

Python3

花花酱 LeetCode 189. Rotate Array

Problem

Solution 1: Simulate rotation with three reverses.

花花酱 LeetCode 345. Reverse Vowels of a String

Problem

Solution

花花酱 LeetCode 541. Reverse String II

Problem

Solution

Related Problems

Posts tagged as “reverse”

花花酱 LeetCode 7. Reverse Integer

Problem

Solution: Simulation

C++

Java

Python3

花花酱 LeetCode 189. Rotate Array

Problem

Solution 1: Simulate rotation with three reverses.

花花酱 LeetCode 345. Reverse Vowels of a String

Problem

Solution

花花酱 LeetCode 541. Reverse String II

Problem

Solution

Related Problems

花花酱 LeetCode 206. Reverse Linked List