目录
一.lc43 字符串相乘
二.lc338 比特位计数
三.lc461 汉明距离
lc43 字符串相乘
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 比特位计数
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);
}
}
