通过移除给定字符串中存在的十六进制表示中的字符来修改数组
我们给定了一个正整数数组,需要修改数组的每个元素,方法是从当前元素的十六进制表示中移除给定字符串 'hex' 中的字符。
为了解决这个问题,我们可以将当前数字转换为十六进制数。然后,我们可以移除十六进制字符串中与 'hex' 和当前十六进制字符串共有的字符。修改十六进制字符串后,我们可以将其转换回十进制。
问题陈述 – 我们给定一个包含正整数的数组,数组长度为 N。此外,我们还给定了包含 0 到 9 的数字以及 'A' 到 'F' 字符的字符串 'hex'。我们需要将每个数组值转换为十六进制,移除 'hex' 字符串中存在的数字十六进制表示中的字符,然后将其再次转换回十进制数。
示例
输入 – array[] = {92, 90, 75, 129}, hex = '1BC'
输出 – [5, 90, 4, 8]
解释 –
92 的十六进制表示为 '5C'。由于 'C' 出现在 'hex' 字符串中,因此我们必须将其移除。因此,结果字符串将为 '5';将其转换为十进制后,我们得到 5。
90 的十六进制值为 '5A'。由于 '5' 或 'A' 不在 'hex' 字符串中,因此它将保持不变。
75 的十六进制表示为 '4B',移除 'B' 后,字符串变为 '4'。当我们将 '4' 转换为十进制时,我们得到 4。
129 的十六进制值为 '81'。移除 '1' 后,修改后的十六进制字符串为 '8',其十进制表示为 8。
输入 – array[] = {54, 43, 56, 9999, 1234, 32}, hex = "1BCFE234"
输出 – [6, 0, 8, 112, 13, 0]
解释
实际数字 -> 十六进制 -> 修改后的十六进制 -> 最终十进制
54 -> 36 -> 6 -> 6
43 -> 2B -> 0 -> 0
56 -> 38 -> 8 -> 8
9999 -> 270F -> 70 -> 112
1234 -> 4D2 -> D -> 13
32 -> 20 -> 0 -> 0
方法 1
在这种方法中,我们将首先将十进制值转换为十六进制值。然后,我们将修改十六进制值。接下来,我们将修改后的十六进制值转换为十进制,并用结果值替换数组元素。此外,我们将使用不同的方法从十六进制字符串中移除字符,将十进制转换为十六进制,以及将十六进制转换为十进制数字。
算法
在 changeArr() 函数中开始遍历每个字符串字符。
使用 decimalToHexa() 函数将数组值转换为十六进制值,并将结果存储在字符串变量 'hexa' 中。
在 decimalToHexa() 函数中,如果数字为 0,则返回 0。
定义数组 alpha[] 并存储字符。另外,定义字符串 'hexa'。
进行迭代,直到数字大于零。
如果 num % 16 <10 为真,则将 num % 16 附加到字符串 'hexa'。否则,将 alpha[num % 16 - 10] 附加到字符串 'hexa',因为我们需要为 11 到 16 的值附加字符。
将 num 除以 16。
当 while 循环迭代完成后,使用 reverse() 方法反转字符串 'hexa' 并返回其值。
现在,使用 removeChars() 函数移除字符串 'hexa' 中的字符,这些字符在 'hexa' 和给定的字符串 'hex' 之间是共有的。
在 removeChars() 函数中,定义名为 'charSet' 的集合,并将字符串 'hex' 的所有字符插入其中。
现在,遍历字符串 'hexVal'。如果字符串 'hexVal' 的当前字符存在于 charset 中,则继续迭代。否则,将当前字符附加到临时字符串 'res'。
返回字符串 'res'。
现在,使用 decimalToHexa() 函数将修改后的十六进制字符串转换为十进制。
在 decimalToHexa() 函数中,定义数组 'mp',其中包含从 10 到 15 的数字。
反转十六进制字符串。
遍历十六进制字符串。将字符值乘以 16pos,并将其添加到值 'res' 中。
– 将值 'pos' 加 1。
用值 'dec' 替换数组元素。
示例
#include <bits/stdc++.h> using namespace std; string decimalToHexa(int num){ if (num == 0) { return "0"; } // char array to store hexadecimal number char alpha[] = {'A', 'B', 'C', 'D', 'E', 'F'}; string Hexa; // Traverse the number until it becomes zero while (num > 0) { // if the remainder is less than 10, store it as it is if (num % 16 < 10) { Hexa += to_string(num % 16); } else { // else store the character Hexa += alpha[num % 16 - 10]; } // divide the number by 16 num /= 16; } // reverse the string reverse(Hexa.begin(), Hexa.end()); return Hexa; } int hexaToDecimal(string modifiedHex) { // stores hexadecimal to decimal char mp[] = {10, 11, 12, 13, 14, 15}; // Stores result int res = 0; int pos = 0; // reverse the string reverse(modifiedHex.begin(), modifiedHex.end()); // Traverse the string for (char ch : modifiedHex) { // If a digit, multiply it with 16^pos if (isdigit(ch)) { res += ((int)pow(16, pos)) * (ch - '0'); } // If character, multiply it with 16^pos else { res += ((int)pow(16, pos)) * mp[ch - 'A']; } // Increment the position pos += 1; } // Return the answer return res; } string removeChars(string hexaVal, string hex) { // set to store the characters of the given string set<char> charSet; // insert the characters of the given string in the set for (char ch : hex) { charSet.insert(ch); } // string to store the final hexadecimal number string res = ""; // traverse the hexadecimal number string for (char ch : hexaVal) { // if the character is present in the set, then continue if (charSet.find(ch) != charSet.end()) { continue; } // else add the character to the final string res += ch; } // return the final string return res; } // function to modify the array as per the given condition void changeArr(int array[], int N, string hex) { // Traverse the array for (int i = 0; i < N; i++) { // covnert the number to hexadecimal string hexa = decimalToHexa(array[i]); // remove the characters from the hexadecimal number string which are present in the given string string modifiedHex = removeChars(hexa, hex); // change the hexadecimal number to decimal int decVal = hexaToDecimal(modifiedHex); // replace the number with the new decimal value array[i] = decVal; } cout << "The final array after converting a number to hexadecimal, removing characters which are present in the string, and converting back to decimal is " << endl; // Print the modified array for (int i = 0; i < N; i++) { cout << array[i] << " "; } } int main() { // Given array int array[] = {54, 43,56,9999,1234, 32}; int N = sizeof(array) / sizeof(array[0]); // Given string string hex = "1BCFE234"; changeArr(array, N, hex); return 0; }
输出
The final array after converting a number to hexadecimal, removing characters which are present in the string, and converting back to decimal is 6 0 8 112 13 0
时间复杂度 – O(N*S),其中 N 是数组长度,S 是字符串长度。
空间复杂度 – O(S),因为我们需要存储修改后的字符串。