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;
    }
};