Determine the integer floor of the sum of two floating point numbers. The floor is the largest integer ≤ a + b.

Constraints

• 0.1 < a, b < 10⁶
• a and b have at most 8 places after the decimal

Example 1

Input:

a = 1.1
b = 3.89

Output:

4

Explanation: floor(1.1 + 3.89) = floor(4.99) = 4.

解法

取 floor(a + b)。O(1)。

import math

def add_numbers(a: float, b: float) -> int:
    return math.floor(a + b)

class Solution {
    public long addNumbers(double a, double b) { return (long) Math.floor(a + b); }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long addNumbers(double a, double b) { return (long long) floor(a + b); }
};

Given a string that consists of left and right parentheses, '(' and ')', balance the parentheses by inserting parentheses as necessary. Determine the minimum number of characters that must be inserted. Function Description Complete the function balanceParentheses in the editor. balanceParentheses has the following parameter:

• String s: a string of parentheses Returns int: the minimum number of insertions needed

Constraints

1 ≤ length of s ≤ 10⁵

Example 1

Input:

s = "()))"

Output:

2

Explanation: Insert a '(' 2 times at the beginning of the string to make it valid: '((()))'

Example 2

Input:

s = "))(("

Output:

4

Explanation: Insert 2 left parentheses at the start and 2 right parentheses at the end of the string to get "(()))(())" after 4 insertions.

Example 3

Input:

s = "(()))"

Output:

1

Explanation: Insert 1 left paranthesis at the left end of the string to get '((()))'. The string is balanced after 1 insertion.

Example 4

Input:

s = "()()"

Output:

0

Explanation: The sequence is already valid.

解法

扫描，用 open 计未配对左括号。遇 ')' 若 open > 0 则配掉，否则需 +1 个 '('。最后剩余 open 个未配的左括号也要补 ')'。总插入 = unmatched_right + open。O(N)。

def balance_parentheses(s: str) -> int:
    open_cnt = 0
    insert = 0
    for c in s:
        if c == '(':
            open_cnt += 1
        else:
            if open_cnt > 0:
                open_cnt -= 1
            else:
                insert += 1
    return insert + open_cnt

class Solution {
    public int balanceParentheses(String s) {
        int open = 0, insert = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') open++;
            else if (open > 0) open--;
            else insert++;
        }
        return insert + open;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int balanceParentheses(string s) {
        int open = 0, insert = 0;
        for (char c : s) {
            if (c == '(') open++;
            else if (open > 0) open--;
            else insert++;
        }
        return insert + open;
    }
};

The binary cardinality of a number is the total number of 1's it contains in its binary representation. For example, the decimal integer 20 corresponds to the binary number 10100₂. There are 2 1's in the binary representation so its binary cardinality is 2. Given an array of decimal integers, sort it ascending first by binary cardinality, then by decimal value. Return the resulting array. Function Description Complete the function cardinalitySort in the editor. cardinalitySort has the following parameter(s):

• int nums[n]: an array of decimal integers Returns int[n]: the integer array nums sorted first by ascending binary cardinality, then by decimal value

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁶

Example 1

Input:

nums = [31, 15, 7, 3, 2]

Output:

[2, 3, 7, 15, 31]

Explanation: 31₁₀ → 11111₂ so its binary cardinality is 5. 15₁₀ → 1111₂ so its binary cardinality is 4. 7₁₀ → 111₂ so its binary cardinality is 3. 3₁₀ → 11₂ so its binary cardinality is 2. 2₁₀ → 10₂ so its binary cardinality is 1.

Example 2

Input:

nums = [1, 2, 3, 4, 5]

Output:

[1, 2, 4, 3, 5]

Explanation: The sorted elements with binary cardinality of 1 are [1, 2, 4]. The array to return is [1, 2, 4, 3, 5].

Example 3

Input:

nums = [3]

Output:

[3]

Explanation: Not privided for now.

Example 4

Input:

nums = [1, 2, 3, 4, 5]

Output:

[1, 2, 4, 3, 5]

Explanation: Not privided for now.

解法

按 (popcount, value) 升序排序。时间 O(n log n)。

from typing import List

def cardinality_sort(nums: List[int]) -> List[int]:
    return sorted(nums, key=lambda x: (bin(x).count('1'), x))

import java.util.*;

class Solution {
    public int[] cardinalitySort(int[] nums) {
        Integer[] arr = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) arr[i] = nums[i];
        Arrays.sort(arr, (a, b) -> {
            int pa = Integer.bitCount(a), pb = Integer.bitCount(b);
            return pa != pb ? pa - pb : a - b;
        });
        int[] out = new int[nums.length];
        for (int i = 0; i < nums.length; i++) out[i] = arr[i];
        return out;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> cardinalitySort(vector<int>& nums) {
        vector<int> a = nums;
        sort(a.begin(), a.end(), [](int x, int y) {
            int px = __builtin_popcount(x), py = __builtin_popcount(y);
            return px != py ? px < py : x < y;
        });
        return a;
    }
};

Given an undirected connected graph of g_nodes and M connections, traverse all nodes at least once, and store the order of traversal in A. Now create the lexicographically largest array B which is a permutation of A. Function Description Complete the function createLexicographicallyLargestPermutation in the editor. createLexicographicallyLargestPermutation has the following parameters:

• int g_from[]: an array of integers representing the starting nodes
• int g_to[]: an array of integers representing the ending nodes Returns int[]: the lexicographically largest permutation array B

Example 1

Input:

g_from = [4, 5, 1, 4, 3]
g_to = [5, 1, 4, 3, 2]

Output:

[5, 4, 3, 2, 1]

Explanation: This and the following 2 explanations are not from the official, so be careful when reading them :) The order of traversal A is [5, 4, 3, 2, 3, 4, 1]. The lexicographically largest permutation B is [5, 4, 3, 2, 1].

Example 2

Input:

g_from = [3, 3]
g_to = [1, 2]

Output:

[3, 2, 1]

Explanation: The order of traversal A can be [3, 1, 3, 2] or any other traversal that visits all nodes at least once. The lexicographically largest permutation B is [3, 2, 1].

Example 3

Input:

g_from = [1, 2, 3, 2, 1]
g_to = [2, 3, 4, 4, 4]

Output:

[4, 3, 2, 1]

Explanation: The order of traversal A can be [1, 2, 3, 4, 2, 1, 4, 4] or any other traversal that visits all nodes at least once. The lexicographically largest permutation B is [4, 3, 2, 1].

As new students begin to arrive at college, each receives a unique ID number, 1 to n. Initially, the students do not know one another, and each has a different circle of friends. As the semester progresses, other groups of friends begin to form randomly. There will be three arrays, each aligned by an index. The first array will contain a querytype which will be either Friend or Total. The next two arrays, student1 and student2, will each contain a student ID. If the query type is Friend, the two students become friends. If the query type is Total, report the sum of the sizes of each group of friends for the two students. Function Description Complete the function findCircleNum in the editor. findCircleNum has the following parameters:

• 1. String[] queryType: an array of strings representing the type of query
• 2. int[] student1: an array of integers representing the first student IDs
• 3. int[] student2: an array of integers representing the second student IDs Returns int: the sum of the sizes of each group of friends for the two students in a Total query

Constraints

૮ ․ ․ ྀིა

Example 1

Input:

queryType = ["Friend", "Friend", "Total"]
student1 = [1, 2, 1]
student2 = [2, 3, 4]

Output:

4

Explanation: The queries are assembled, aligned by index: Index queryType student1 student2 0 Friend 1 2 1 Friend 2 3 2 Total 1 4 Students will start as discrete groups (1), (2), (3) and (4). Students 1 and 2 become friends with the first query, as well as students 2 and 3 in the second. The new groups are (1, 2), (2, 3) and (4) which simplifies to {1, 2, 3} and (4). In the third query, the number of friends for student 1 = 3 and student 4 = 1 for a Total = 4. Notice that student 2 is indirectly part of the circle of friends of student 1.

Given a barcode, query the API at https://jsonmock.hackerrank.com/api/inventory?barcode=barcode and return the item's discounted price. 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 item's record. In the data array, the item has the following schema: barcode: the barcode for the product (String) price: the gross selling price (Number) discount: the discount percent to apply (Number). Some fields that are not of interest. page, per_page, total, total_pages, etc. are not required for this task. If the barcode is found, the data array contains exactly 1 element. If not, it is empty and the function should return '-1'. Use the "discount" and the "price" properties to calculate the discounted price rounded to the nearest integer. discountedPrice = price - ((discount / 100) * price) Function Description Complete the function getDiscountedPrice in the editor. getDiscountedPrice has the following parameters:

• string barcode: the item to query Returns int: the discounted price rounded to the nearest integer or -1 Constraints
• There will be either 1 or 0 records in data.

Constraints

There will be either 1 or 0 records in data

Example 1

Input:

barcode = "74002314"

Output:

2964

Explanation: First, a call is made to API https://jsonmock.hackerrank.com/api/inventory?barcode=74002314. The price = 3705 and discount = 20.

Given an array of integers, determine whether each is a power of 2, where powers of 2 are [1, 2, 4, 8, 16, 32, 64...]. For each integer evaluated, append to an array a value of 1 if the number is a power of 2 or 0 otherwise. Function Description Complete the function isPower in the editor below. isPower has the following parameter(s):

• int arr[n]: an array of integers Returns int[n]: array of binary integers where each index i contains a 1 if arr[i] is a power of 2 or a 0 if it is not

Constraints

• 1 ≤ n ≤ 100
• 0 ≤ arr[i] ≤ 5 x 10⁷

Example 1

Input:

arr = [1, 3, 8, 12, 16]

Output:

[1, 0, 1, 0, 1]

Explanation: 1 = 2⁰, 8 = 2³ and 16 = 2⁴. The return array is [1, 0, 1, 0, 1].

Given a string, create a new string made up of its last two letters, reversed

Constraints

2 ≤ length of word ≤ 100

Example 1

Input:

word = "APPLE"

Output:

"E L"

Explanation: The last letter in 'APPLE' is E and the second-to-last letter is L, so return E L.

Example 2

Input:

word = "bat"

Output:

"t a"

Explanation: Just an example provided by Oracle with no explanation

Given two sorted arrays, merge them to form a single, sorted array with all items in non-decreasing order. Function Description Complete the function mergeArrays in the editor below. mergeArrays has the following parameter(s):

• int a[n]: a sorted array of integers
• int b[n]: a sorted array of integers Returns int[n]: an array of all the elements from both input arrays in non-decreasing order

Constraints

• 1 < n ≤ 10⁵
• 0 ≤ a[i], b[i] ≤ 10⁹ where 0 ≤ i < n

Example 1

Input:

a = [1, 2, 3]
b = [2, 5, 5]

Output:

[1, 2, 2, 3, 5, 5]

Explanation: Merge the arrays to create array c as follows: a[0] c = [a[0]] = [1] a[1] c = [a[0], b[0]] = [1, 2] a[1] c = [a[0], b[0], a[1]] = [1, 2, 2] a[2] c = [a[0], b[0], a[1], a[2]] = [1, 2, 2, 3] No more elements in a → c = [a[0], b[0], a[1], a[2], b[1], b[2]] = [1, 2, 2, 3, 5, 5] Elements were alternately taken from the arrays in the order given, maintaining precedence.

Given an array of n integers, rearrange them so that the sum of the absolute differences of all adjacent elements is minimized. Then, compute the sum of those absolute differences. Function Description Complete the function minDiff in the editor. minDiff has the following parameter:

• int arr[]: an integer array Returns int: the sum of the absolute differences of adjacent elements

Constraints

• 2 ≤ n ≤ 10⁵
• 0 ≤ arr[i] ≤ 10⁹, where 0 ≤ i

Example 1

Input:

arr = [1, 3, 3, 2, 4]

Output:

3

Explanation: If the list is rearranged as arr' = [1, 2, 3, 3, 4], the absolute differences are |1 - 2| = 1, |2 - 3| = 1, |3 - 3| = 0, |3 - 4| = 1. The sum of those differences is 1 + 1 + 0 + 1 = 3.

There is an array of n integers called num[]. The array can be reduced by 1 element by performing a move. Each move consists of the following three steps:

• Pick two different elements num[i] and num[j], i ≠ j.
• Remove the two selected elements from the array.
• Add the sum of the two selected elements to the end of the array. Each move has a cost associated with it: the sum of the two elements removed from the array during the move. Calculate the minimum total cost of reducing the array to one element. Function Description Complete the function reductionCost in the editor below. reductionCost has the following parameter(s):
• int num[n]: an array of integers Returns int: the minimum total cost of reducing the input array to one element

Constraints

• 2 ≤ n ≤ 10⁴
• 0 ≤ num[i] ≤ 10⁵

Example 1

Input:

num = [4, 6, 8]

Output:

28

Explanation: Remove 4 and 6 in the first move at a cost of 4 + 6 = 10, and the resultant array is num' = [8,10]. Remove 8 and 10 in the second move at a cost of 8 + 10 = 18, and the resultant array is num'' = [18]. The total cost of reducing this array to one element using this sequence of moves is 10 + 18 = 28. This is just one set of possible moves. For instance, one could have started with 4 and 8. Then 4 + 8 = 12, num' = [6,12] 6 + 12 = 18, num'' = [18], cost 12 + 18 = 30.

Example 2

Input:

num = [1, 2, 3]

Output:

9

Explanation: Make the following moves to reduce the array num = [1, 2, 3]:

• Remove 1 and 2 at cost; 1 + 2 = 3, resulting in num' = [3, 3]
• Remove 3 and 3 at cost; 3 + 3 = 6, resulting in num'' = [6]. Sum up the cost of each reduction to get 3 + 6 = 9.