2859. Sum of Values at Indices With K Set Bits

tags: Easy、Bitwise

You are given a 0-indexed integer array nums and an integer k.
Return an integer that denotes the sum of elements in nums whose corresponding indices have exactly k set bits in their binary representation.
The set bits in an integer are the 1's present when it is written in binary.
For example, the binary representation of 21 is 10101, which has 3 set bits.

解法:

int sumIndicesWithKSetBits(int* nums, int numsSize, int k){
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        int n = __builtin_popcount(i);
        if (n == k) {
            count += nums[i];
        }
    }
    return count;
}

3226. Number of Bit Changes to Make Two Integers Equal

tags: Easy、Bitwise

You are given two positive integers n and k.
You can choose any bit in the binary representation of n that is equal to 1 and change it to 0.
Return the number of changes needed to make n equal to k. If it is impossible, return -1.

解法1:

int minChanges(int n, int k) {
    if (n == k) {return 0;}
    int count = 0;

    while ((n != 0) | (k != 0)) {
        if (n & 1) {
            if (!(k & 1)) {
                count++;
            }
        } else {
            if (k & 1) {
                count = -1;
                break;
            }
        }
        n >>= 1;
        k >>= 1; 
    }
    return count;
}

解法2:

int minChanges(int n, int k)
{
        return (__builtin_popcount(n^k)==__builtin_popcount((n^k)&n))?__builtin_popcount((n^k)):-1;
}

947. Most Stones Removed with Same Row or Column

tags: Volatile、Medium

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.
A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.
Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.

解法:

void dfs (int** stones, int stonesSize, int* visited, int index) {
    visited[index] = 1;
    for (int i = 0; i < stonesSize; i++) {
        if (!visited[i] && (stones[i][0] == stones[index][0] || stones[i][1] == stones[index][1])) {
            dfs(stones, stonesSize, visited, i);
        }
    }
}


int removeStones(int** stones, int stonesSize, int* stonesColSize) {
    int* array = (int*)calloc(stonesSize, sizeof(int)); //儲存是否訪問過
    int count = 0;
    for (int i = 0; i < stonesSize; i++) {
        if(!array[i]) {
            dfs(stones, stonesSize, array, i);
            count++;
        }
    }
    *stonesColSize = (stonesSize - count);
    return (stonesSize - count);
}

calloc 會分配 num 個元素，每個元素的大小為 size 字節，並將這塊記憶體初始化為全零。calloc 返回的記憶體塊大小為 num * size 字節。 -> 分配速度較malloc慢