Given a number num, two adjacent digits can be swapped if their parity is the same, that is, both are odd or both are even. For example, (5,9) have the same parity, but (6,9) do not.
Find the largest number that can be created. The swap operation can be applied any number of times.
Function Description
Complete the function getLargestNumber in the editor.
getLargestNumber has the following parameter:
string num: a string of digits Returns string: the largest number that can be created
Constraints
- 1 ≤ length of
num≤ 10⁵ numconsists of digits 0-9 only.
Example 1
Input:
num = "7596801"
Output:
"9758601"
Explanation: Let num = "7596801".
- Swap 5 and 9 -> "7956801"
- Swap 7 and 9 -> "9756801"
- Swap 6 and 8 -> "9758601" It can be proven that the largest value possible is "9758601".
Example 2
Input:
num = "0082663"
Output:
"8662003"
Explanation: Zero is even parity, so swaps can be made until the digits are arranged as shown.
解法
同奇偶可任意排序,所以分别提取奇数位、偶数位,并按降序填回原本属于该奇偶性的位置。时间复杂度 O(n log n)。
def getLargestNumber(num: str) -> str:
odd = sorted([c for c in num if int(c) % 2 == 1], reverse=True)
even = sorted([c for c in num if int(c) % 2 == 0], reverse=True)
oi = ei = 0
res = []
for c in num:
if int(c) % 2 == 1: res.append(odd[oi]); oi += 1
else: res.append(even[ei]); ei += 1
return ''.join(res)class Solution {
String getLargestNumber(String num) {
List<Character> odd = new ArrayList<>(), even = new ArrayList<>();
for (char c : num.toCharArray()) {
if ((c - '0') % 2 == 1) odd.add(c); else even.add(c);
}
odd.sort(Comparator.reverseOrder());
even.sort(Comparator.reverseOrder());
StringBuilder sb = new StringBuilder();
int oi = 0, ei = 0;
for (char c : num.toCharArray()) {
if ((c - '0') % 2 == 1) sb.append(odd.get(oi++));
else sb.append(even.get(ei++));
}
return sb.toString();
}
}class Solution {
public:
string getLargestNumber(string num) {
vector<char> odd, even;
for (char c : num) (c - '0') % 2 ? odd.push_back(c) : even.push_back(c);
sort(odd.rbegin(), odd.rend());
sort(even.rbegin(), even.rend());
string res;
int oi = 0, ei = 0;
for (char c : num) res += (c - '0') % 2 ? odd[oi++] : even[ei++];
return res;
}
};Given a country name and a phone number, query the API at
https://jsonmock.hackerrank.com/api/countries?name=country to get the country's
calling codes. Prepend the calling code to the phone number and return the string. If the data
array is empty, return the string '-1'. If there are multiple calling codes, use the one at the
highest index. The format of the number should be:
<Calling Code><space><Phone Number>
Example:
+1 7653555443
The response is a JSON object with 5 fields. The essential field is data:
data: Either an empty array or an array with a single object that contains the country's record.
In the data array, the country has the following schema:
name: The name of the country (String)
- callingCodes: An array of the country's calling codes (String Array)
- A number of fields that are not of interest.
page, per_page, total, total_pages, etc. are not required for this task.
If the country is found, the data array contains exactly 1 element. If not, it is empty and the function should return '-1'.
Function Description
Complete the
getPhoneNumbersfunction in the editor.getPhoneNumbershas the following parameters: - string country: the country to query
- string phoneNumber: the phone number Returns string: the completed phone number or -1
Constraints
- The returned JSON object contains either 0 or 1 record in data.
- he country name may contain uppercase and lowercase English letters and <space> (ascii 32)
Example 1
Input:
country = "Afghanistan"
phoneNumber = "6564454455"
Output:
"+93 6564454455"
Explanation:
A call is made to API https://jsonmock.hackerrank.com/api/countries?name=Afghanistan.
The calling codes array contains 1 entry, '93'.
Example 2
Input:
country = "Puerto Rico"
phoneNumber = "564539386"
Output:
"+1939 564539386"
Explanation: A call is made to the API to fetch the record for Puerto Rico. The returned callingCodes = ['1787', '1939']. Use the higher index code, callingCodes[1].
Example 3
Input:
country = "Oceania"
phoneNumber = "987574876"
Output:
"-1"
Explanation: The API call return has an empty data array.
解法
HTTP GET 调用 API,解析 JSON 获取 data[0].callingCodes;若为空数组返回 "-1";否则取最后一个 calling code 加 + 拼接。
import urllib.request
import json
def getPhoneNumbers(country: str, phoneNumber: str) -> str:
url = "https://jsonmock.hackerrank.com/api/countries?name=" + urllib.parse.quote(country)
with urllib.request.urlopen(url) as resp:
body = json.loads(resp.read())
if not body.get("data"):
return "-1"
codes = body["data"][0].get("callingCodes", [])
if not codes:
return "-1"
return "+" + codes[-1] + " " + phoneNumberimport java.net.URI;
import java.net.http.*;
import java.util.regex.*;
class Solution {
String getPhoneNumbers(String country, String phoneNumber) throws Exception {
String url = "https://jsonmock.hackerrank.com/api/countries?name=" + java.net.URLEncoder.encode(country, "UTF-8");
HttpClient client = HttpClient.newHttpClient();
HttpRequest req = HttpRequest.newBuilder().uri(URI.create(url)).build();
String body = client.send(req, HttpResponse.BodyHandlers.ofString()).body();
Matcher m = Pattern.compile("\"callingCodes\":\\[(.*?)\\]").matcher(body);
if (!m.find()) return "-1";
String inner = m.group(1).trim();
if (inner.isEmpty()) return "-1";
String[] codes = inner.replaceAll("\"", "").split(",");
return "+" + codes[codes.length - 1].trim() + " " + phoneNumber;
}
}// C++ HTTP requires an external library (libcurl etc.). Pseudocode equivalent:
// fetch URL, JSON-parse "data[0].callingCodes", pick last entry, format result.
class Solution {
public:
string getPhoneNumbers(string country, string phoneNumber) {
// Use libcurl or other HTTP client to fetch the JSON; parse callingCodes; return.
return "-1"; // placeholder; implement HTTP fetch with libcurl in production
}
};For each word in a list of words, if any two adjacent characters are equal, change one of them. Determine the minimum number of substitutions so the final string contains no adjacent equal characters.
Function Description
Complete the function minimalOperations in the editor below.
minimalOperations has the following parameter(s):
string words[n]: an array of strings Returnsint[n]: each element is the minimum substitutions for words[x]
Constraints
1 ≤ n ≤ 1002 ≤ length of words[x] ≤ 10⁵
Example 1
Input:
words = ["add", "boook", "break"]
Output:
[1, 1, 0]
Explanation:
- add: change one d (1 change)
- boook: change the middle o (1 change)
- break: no changes are necessary (0 changes) The return array is [1, 1, 0]
解法
扫描每个字符串找连续相同字符的极长块,长度为 L 的块需要 L // 2 次替换。把所有块的贡献加和。时间复杂度 O(总字符数)。
from typing import List
def minimalOperations(words: List[str]) -> List[int]:
res = []
for w in words:
cnt = 0; i = 0
while i < len(w):
j = i
while j < len(w) and w[j] == w[i]: j += 1
cnt += (j - i) // 2
i = j
res.append(cnt)
return resclass Solution {
int[] minimalOperations(String[] words) {
int[] res = new int[words.length];
for (int k = 0; k < words.length; k++) {
String w = words[k];
int cnt = 0, i = 0;
while (i < w.length()) {
int j = i;
while (j < w.length() && w.charAt(j) == w.charAt(i)) j++;
cnt += (j - i) / 2;
i = j;
}
res[k] = cnt;
}
return res;
}
}class Solution {
public:
vector<int> minimalOperations(vector<string>& words) {
vector<int> res;
for (auto& w : words) {
int cnt = 0, i = 0;
while (i < (int)w.size()) {
int j = i;
while (j < (int)w.size() && w[j] == w[i]) j++;
cnt += (j - i) / 2;
i = j;
}
res.push_back(cnt);
}
return res;
}
};