# leetcode - firmware

191. Number of 1 Bits
計算數值n總共有幾個1 bit

int hammingWeight(uint32_t n) {
    int count = 0;
    while(n){
        if(n&1)
            count++;
        n >>= 1;
    }
    return count;
}

231. Power of Two
判斷數值n是不是2的冪次。
n = 2^4 (10000)

10000 AND 1111(=10000-1) => 0

bool isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return (n & (n - 1)) == 0;
}

233. Reverse Bits
Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    for(int i =0;i<32;i++){
        res <<= 1; //res先移動(歸零)
        res |= (n & 1);
        n >>= 1;
    }
    return res;
}

136. Single Number

對於任何數字 a，a XOR a 等於 0。
對於任何數字 a，a XOR 0 等於 a。

int singleNumber(int* nums, int numsSize) {
    int result = 0;
    for (int i = 0; i < numsSize; i++) {
        result ^= nums[i];
    }
    return result;
}

27. Remove Element

int removeElement(int* nums, int numsSize, int val) {
    int count = 0;
    for(int i =0;i<numsSize;i++){
        if(nums[i] == val)
            count++;
        else
            nums[i-count] = nums[i];
    }
    return (numsSize - count);
}

189. Rotate Array
13. Roman to Integer

int romanToInt(char* s) {
    int romanValues[26] = {0}; // 映射表，用於將羅馬字符映射為整數
    romanValues['I' - 'A'] = 1;
    romanValues['V' - 'A'] = 5;
    romanValues['X' - 'A'] = 10;
    romanValues['L' - 'A'] = 50;
    romanValues['C' - 'A'] = 100;
    romanValues['D' - 'A'] = 500;
    romanValues['M' - 'A'] = 1000;

    int result = 0;
    int prevValue = 0; // 上一個羅馬字符的整數值
    while (*s) {
        int curValue = romanValues[*s - 'A'];
        result += curValue;
        // 如果當前字符的整數值大於前一個字符的整數值，則減去前一個字符的值兩倍（因為前一個字符已經被加過了）
        if (curValue > prevValue) {
            result -= 2 * prevValue;
        }
        prevValue = curValue;
        s++;
    }
    return result;
}

392. Is Subsequence
s = "abc", t = "ahbgdc"
Return true.

bool isSubsequence(char* s, char* t) {
    while (*s && *t) {
        if (*s == *t)
            s++;
        t++;
    }
    return !(*s);
}

一段數字累加

int sumOfDigits(int num) {
    int sum = 0;
    
    while (num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

二進制轉成十進制

int binaryToDecimal(int n) {
    int decimal = 0;
    int base = 1;
    
    while (n != 0) {
        int remainder = n % 10;
        decimal += remainder * base;
        n = n / 10;
        base *= 2;
    }
    
    return decimal;
}

十進制轉成二進制

void decimalToBinary(int n) {
    int binary[32];
    
    int i = 0;
    
    if (n == 0) {
        return;
    }
    
    while (n > 0) {
        binary[i] = n % 2;
        n = n / 2;
        i++;
    }
    
    for (int j = i - 1; j >= 0; j--) {
        printf("%d", binary[j]);
    }
    printf("\n");
}