目录
一.lc43 字符串相乘
二.lc338 比特位计数
三.lc461 汉明距离

lc43 字符串相乘

43. 字符串相乘 - 力扣（LeetCode）

package com.fong.lc43;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


public class Solution1 {
    /**
     num1
     * num2
     ---------
     result
     */
    public String multiply(String num1, String num2) {
        // 1.特殊判断
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }

        // 2.num2逐位和num1相乘 并 累加
        String res = "";
        for (int i = num2.length() - 1; i >= 0; i--) {
            // 2.1 相乘(num2第i个 和 num1相乘的结果)
            int carry = 0;
            StringBuilder tmpRes = new StringBuilder();
            int n2 = num2.charAt(i) - '0';

            // 2.2 累加
            for (int j = num1.length() - 1; j >= 0 || carry != 0; j--) {
                int n1 = (j < 0) ? 0 : num1.charAt(j) - '0';
                int product = (n1 * n2 + carry);
                tmpRes.append(product % 10);
                carry = product / 10;
            }
            // 2.3 翻转
            String reverseStr = tmpRes.reverse().toString();
            // 2.4 最终结果补零
            // 第一个数补零个数 = 3 - 1 - 0 = 2
            for (int j = 0; j < num2.length() - 1 - i; j++) {
                reverseStr += "0";
            }
            // 2.5 和当前结果str进行相加得到新结果
            res = addStr(res, reverseStr);
        }
        return res;
    }

    public String addStr(String str1, String str2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for (int i = str1.length()-1, j = str2.length()-1; i >= 0 || j >= 0 || carry != 0; i--, j--) {
            int n1 = (i < 0) ? 0 : str1.charAt(i) - '0';
            int n2 = (j < 0) ? 0 : str2.charAt(j) - '0';
            int sum = n1 + n2 + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }

    @Test
    public void test1() {
        String s1 = "789";
        String s2 = "101";
        String multiply = multiply(s1, s2);
        System.out.println(multiply);
    }
}

lc338 比特位计数

338. 比特位计数 - 力扣（LeetCode）

package com.fong.lc338;

import org.junit.Test;

/**
 * 1.题目:
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 *
 * 输入：n = 2
 * 输出：[0,1,1]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 *
 * 思想: 超时
 */
public class Solution2 {
    /**
     思想: dp + 奇偶规律
     (1)只有奇数和偶数两种
     (2)奇数: dp[i] = dp[i-1] + 1
     i是奇数, i-1为偶数, 那么1的数量则为上一个偶数的基础上+1
     (3)偶数: dp[i] = dp[i / 2];
     i / 2, 相当于右移了一位, 1的数量是不变的

     */
    public int[] countBits(int n) {
        int[] dp = new int[n+1];
        // base case dp[0] = 0
        for (int i = 1; i <= n; i++) {
            // 1.偶数
            if (i % 2 == 0) dp[i] = dp[i / 2];
                // 2.奇数
            else dp[i] = dp[i-1] + 1;
        }
        return dp;
    }
    @Test
    public void test() {
        int n = 5;
        int[] ints = countBits(n);
        for (int i : ints) {
            System.out.println(i);
        }
    }
}

lc461 汉明距离

Loading Question... - 力扣（LeetCode）

package com.fong.lc461;

import org.junit.Test;

/**
 * 题目:
 * 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
 * 给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
 *
 * 输入：x = 1, y = 4
 * 输出：2
 * 解释：
 * 1   (0 0 0 1)
 * 4   (0 1 0 0)
 *        ↑   ↑
 * 上面的箭头指出了对应二进制位不同的位置。
 *
 * 时间复杂度：OO(logC)，其中 C 是元素的数据范围，在本题中 logC = log2^31 = 31  
 * 空间复杂度：O(1)。
 */
public class Solution1 {
    public int hammingDistance(int x, int y) {
        int cnt = 0;
        while (x != 0 || y != 0) {
            // 1.提取x的0号位, y的0号位, 不一样的统计
            if ((x & 1) != (y & 1)) cnt++;
            // 2.统计下一位
            x /= 2;
            y /= 2;
        }
        return cnt;
    }

    @Test
    public void test1() {
        int x = 1, y = 4;
        int i = hammingDistance(x, y);
        System.out.println(i);
    }
}