花花酱 LeetCode 405. Convert a Number to Hexadecimal

By zxi on December 7, 2019

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase.
The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.
The given number is guaranteed to fit within the range of a 32-bit signed integer.
You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:

Input:
26

Output:
“1a”
Example 2:

Input:
-1

Output:
“ffffffff”

Solution: Simulation

if input is negative, add 2^32 to it (e.g. set the highest bit to 1)
while num is non zero, mod it by 16 and prepend the remainder to ans string, then divide num by 16.

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

constexpr char kHex[] = "0123456789abcdef";

class Solution {

public:

string toHex(int num) {

if (num == 0) return "0";

long t = num < 0 ? (1LL << 32) + num : num;

string ans;

while (t) {

ans = kHex[t % 16] + ans;

t /= 16;

}

return ans;

}

};

花花酱 LeetCode 1271. Hexspeak

By zxi on November 30, 2019

A decimal number can be converted to its Hexspeak representation by first converting it to an uppercase hexadecimal string, then replacing all occurrences of the digit 0 with the letter O, and the digit 1 with the letter I. Such a representation is valid if and only if it consists only of the letters in the set {"A", "B", "C", "D", "E", "F", "I", "O"}.

Given a string num representing a decimal integer N, return the Hexspeak representation of N if it is valid, otherwise return "ERROR".

Example 1:

Input: num = "257"
Output: "IOI"
Explanation:  257 is 101 in hexadecimal.

Example 2:

Input: num = "3"
Output: "ERROR"

Constraints:

1 <= N <= 10^12
There are no leading zeros in the given string.
All answers must be in uppercase letters.

Solution: Simulation

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

string toHexspeak(string num) {

long n = stol(num);

string ans;

while (n) {

int r = n % 16;

char c;

if (r == 0) c = 'O';

else if (r == 1) c = 'I';

else if (r >= 10 && r <= 15) c = 'A' + r - 10;

else return "ERROR";

ans += c;

n >>= 4;

}

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 LeetCode 800. Simple RGB Color

By zxi on March 17, 2018

Problem

In the following, every capital letter represents some hexadecimal digit from 0 to f.

The red-green-blue color "#AABBCC" can be written as "#ABC" in shorthand. For example, "#15c" is shorthand for the color "#1155cc".

Now, say the similarity between two colors "#ABCDEF" and "#UVWXYZ" is -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2.

Given the color "#ABCDEF", return a 7 character color that is most similar to #ABCDEF, and has a shorthand (that is, it can be represented as some "#XYZ"

Example 1:
Input: color = "#09f166"
Output: "#11ee66"
Explanation:  
The similarity is -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
This is the highest among any shorthand color.

Note:

color is a string of length 7.
color is a valid RGB color: for i > 0, color[i] is a hexadecimal digit from 0 to f
Any answer which has the same (highest) similarity as the best answer will be accepted.
All inputs and outputs should use lowercase letters, and the output is 7 characters.

Solution: Brute Force

R, G, B are independent, find the closest color for each channel separately.

Time complexity: O(3 * 16)

Space complexity: O(1)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

string similarRGB(string color) {

const string hex{"0123456789abcdef"};

vector<int> rgb(3, 0);

for (int i = 0; i < 3; ++i)

rgb[i] = hex.find(color[2 * i + 1]) * 16 + hex.find(color[2 * i + 2]);

string ans(7, '#');

for (int i = 0; i < 3; ++i) {

int best = INT_MAX;

for (int j = 0; j < 16; ++j) {

int diff = abs(j * 16 + j - rgb[i]);

if (diff >= best) continue;

best = diff;

ans[2 * i + 1] = ans[2 * i + 2] = hex[j];

}

return ans;

}

};

[ZOJ] 3713: In 7-bit

By zxi on March 12, 2017

// 3934609 2017-03-13 08:38:54 Accepted 3713 C++0x 290 6428 xxfflower

#include <iostream>

#include <string>

#include <iomanip>

using namespace std;

void put_hex(int byte) {

cout << hex << uppercase << setfill('0') << setw(2) << byte;

}

void put_str(const string& s) {

for(char c : s)

put_hex(c);

}

void put_len(int length) {

while(length>=128) {

put_hex(length % 128 + 128);

length >>= 7;

}

put_hex(length);

}

int main(int argc, char const *argv[])

{

int n;

cin>>n;

string s;

getline(cin, s);

while(n--) {

getline(cin, s);

put_len(s.length());

put_str(s);

cout<<endl;

}

return 0;

}

Posts tagged as “hex”

花花酱 LeetCode 405. Convert a Number to Hexadecimal

Solution: Simulation

C++

花花酱 LeetCode 1271. Hexspeak

Solution: Simulation

C++

花花酱 LeetCode 800. Simple RGB Color

Problem

Note:

Solution: Brute Force

[ZOJ] 3713: In 7-bit