目錄
一.lc43 字符串相乘
二.lc338 比特位計數(shù)
三.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相乘的結(jié)果)
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 翻轉(zhuǎn)
String reverseStr = tmpRes.reverse().toString();
// 2.4 最終結(jié)果補零
// 第一個數(shù)補零個數(shù) = 3 - 1 - 0 = 2
for (int j = 0; j < num2.length() - 1 - i; j++) {
reverseStr += "0";
}
// 2.5 和當(dāng)前結(jié)果str進行相加得到新結(jié)果
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 比特位計數(shù)
338. 比特位計數(shù) - 力扣（LeetCode）
package com.fong.lc338;
import org.junit.Test;
/**
* 1.題目:
* 給你一個整數(shù) n 浅侨，對于 0 <= i <= n 中的每個 i 溃列，計算其二進制表示中 1 的個數(shù) ，返回一個長度為 n + 1 的數(shù)組 ans 作為答案。
*
* 輸入：n = 2
* 輸出：[0,1,1]
* 解釋：
* 0 --> 0
* 1 --> 1
* 2 --> 10
*
* 思想: 超時
*/
public class Solution2 {
/**
思想: dp + 奇偶規(guī)律
(1)只有奇數(shù)和偶數(shù)兩種
(2)奇數(shù): dp[i] = dp[i-1] + 1
i是奇數(shù), i-1為偶數(shù), 那么1的數(shù)量則為上一個偶數(shù)的基礎(chǔ)上+1
(3)偶數(shù): dp[i] = dp[i / 2];
i / 2, 相當(dāng)于右移了一位, 1的數(shù)量是不變的
*/
public int[] countBits(int n) {
int[] dp = new int[n+1];
// base case dp[0] = 0
for (int i = 1; i <= n; i++) {
// 1.偶數(shù)
if (i % 2 == 0) dp[i] = dp[i / 2];
// 2.奇數(shù)
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;
/**
* 題目:
* 兩個整數(shù)之間的 漢明距離 指的是這兩個數(shù)字對應(yīng)二進制位不同的位置的數(shù)目敬鬓。
* 給你兩個整數(shù) x 和 y，計算并返回它們之間的漢明距離蘸劈。
*
* 輸入：x = 1, y = 4
* 輸出：2
* 解釋：
* 1 (0 0 0 1)
* 4 (0 1 0 0)
* ↑ ↑
* 上面的箭頭指出了對應(yīng)二進制位不同的位置月弛。
*
* 時間復(fù)雜度：OO(logC)，其中 C 是元素的數(shù)據(jù)范圍芋浮，在本題中 logC = log2^31 = 31
* 空間復(fù)雜度：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號位, 不一樣的統(tǒng)計
if ((x & 1) != (y & 1)) cnt++;
// 2.統(tǒng)計下一位
x /= 2;
y /= 2;
}
return cnt;
}
@Test
public void test1() {
int x = 1, y = 4;
int i = hammingDistance(x, y);
System.out.println(i);
}
}
