分情况讨论 57. 数字序列中某一位的数字
- 确定当前数是第几位数i 复杂度
o(logn)
1位数字除了0之外有9个，2位数字有90个，3位数字有900….base: i位数的第一个数 （10，100，1000）
`num`:i位数有多少个数(9, 90, 900)`N`: 原数中的首位在第i位数中的位置
- 确定是几位数的第几个数k o(1)
base - 1是上一位数中的最后一个数`(9, 99, 999) `
[(剩下的数 + i - 1) / i] = 0代表k就是上一位数的最后一个数
第几个数k = base - 1 + [剩下的数 / 当前位数i]上取整 = base - 1 + [(剩下的数 + i - 1) / i]下取整
3. 确定是k的第m位 o(1)<br />
如果n % i == 0， 代表这是当前数的最后一位也就是第i位<br />
m = 剩下的数 % i == 0 ? i : 剩下的数 % i
class Solution {
public int digitAtIndex(int n) {
int i = 1;
long base = 1, num = 9;
//进行第一步，确定i
while (n > i * num){
n -= i++ * num;
num *= 10;
base *= 10;
}
//进行第二步
long k = (n + i - 1) / i + base - 1;
//第三步:确定是k的第m位
int m = n % i == 0 ? i : n % i;
//输出k的第m位
String sk = String.valueOf(k);
//在字符串中是第m - 1位
return Integer.parseInt(sk.substring(m - 1, m));
}
}
异或的使用 73. 数组中只出现一次的两个数字
把每个数都异或一边。
由于存在两个数只出现了一次，因此结果不为0.
最终异或的结果出现了1，因此能把两个不同的数按照这个1对应的位数上是0还是1进行划分成两个集合。
而这两个集合中，又只有这两个数出现了一次。
做法：
- 把每个数都异或一边。得到结果t
t相当于两个只出现一次的数异或的结果 - 找到t中为1的位数digit。
- 把digit上1的所有数字异或一遍，结果就是其中一个只出现一次的数。
- 将这个数和t异或，结果就是另一个数。
class Solution {
public int[] findNumsAppearOnce(int[] nums) {
//把所有数异或，扫描结果的数位，把值为1的数位保存下来。根据其筛选出两个集合。再分别把两个集合中所有数异或
//两个结果就是两个只出现了一次的数字。
int len = nums.length;
int r1 = 0;
//所有数异或
for (int i = 0; i < len; i ++){
r1 ^= nums[i];
}
//扫描位数
int k = 0;
for (int i = 0; r1 != 0; r1 >>= ++i){
//把值为1的数位保存下来。
if ((r1 & 1)!= 0){k = i; break;}
}
//根据其筛选出两个集合
List<Integer> c1 = new ArrayList<Integer>();
List<Integer> c2 = new ArrayList<Integer>();
for (int i = 0; i < len; i ++){
if ((nums[i] >> k & 1) == 1) c1.add(nums[i]);
else c2.add(nums[i]);
}
//再分别把两个集合中所有数异或
int r2 = 0, r3 = 0;
for (Integer e1 : c1) r2 ^= e1;
for (Integer e2 : c2) r3 ^= e2;
return new int[]{r2, r3};
}
}
一个数位实现轮3循环 74. 数组中唯一只出现一次的数字 - AcWing题库
方法1
%20%7D#card=math&code=%5Ccal%7BO%28nlogn%29%20%7D)对于每一位数位。
%20%20%3E%20o(logn)#card=math&code=o%2832%29%20%20%3E%20o%28logn%29)
从前向后循环，统计对应数位上的1的个数。 %7D#card=math&code=%5Ccal%7Bo%28n%29%7D)
如果 当前数位上的次数 % 3 = 1，代表对于只出现一次的数字，其数位上也对应1
如果 当前数位上的次数 % 3 = 0，代表对于只出现一次的数字，其数位上对应0
因此我们能直接求出对应的数字。
方法2
实际上这道题求的就是每个数位为1的次数cnt%3后结果
如果是1，代表出现了只出现了一次的数在该数位上是1；
如果是0，代表只出现了一次的数在该数位上是0
如果能求出每一位上的的值，就能求出最后的结果。
,实际上结果只能为1/0，每遇到三次1一个循环。
相当于数位遇到1的时候，
如何让每一位实现两位数的操作呢？
找规律，具体思路看题解
class Solution {
public int findNumberAppearingOnce(int[] nums) {
int one = 0, two = 0;
for (int i= 0 ; i < nums.length; i ++){
one = one ^ nums[i] & ~two;
two = two ^nums[i] & ~one;
}
return one;
}
}
数位运算剑指 Offer 65. 不用加减乘除做加法
规律：
不让使用加减号，因此要利用数位加法原理的规律。
例如：
num1 +num2 = num3 中
num1^num2= 没有进位的num3
num1&num2 << 1 = num3的进位carry
因此
num1 ^num2 + (num1 & num2) <<1 == num1 +num2
那怎么求左边等式的+?
num1 = num1 ^ num2
num2 = (num1 & num2) <<1
这样再对num1,num2进行同样的操作
递归的中止条件呢？
由于%20%3C%3C%201#card=math&code=nums2%20%3D%20%28num1%20%5C%20%5C%26%20%5C%20num2%29%20%3C%3C%201).
低位的0会不断增多，最终
当num2 = 0
`num1 = num1 ^ 0 = num1`
`num2 = (num1 & 0 << 1) = 0`
因此等式
num1 ^num2 + (num1 & num2) <<1 == num1' +num2' == …… = = num1'' + 0
最终答案就是当num2 = 0时的num1
class Solution {
public int add(int num1, int num2) {
while (num2 != 0){
int t1 = num1 ^ num2;
int t2 = (num1 & num2) << 1;
num1 = t1; num2 = t2;
}
return num1;
}
}
进制转换
对于二进制来说，求第i位上的1的公式a>>i&1
如果a是k进制，那么a&1 == a % k , 如果a % k == 1代表a的k进制最后一位是1
如果a % k > 1代表当前数不能用k进制来表示。
a>>i == for(i):a/=k
因此答案数组是数组中所有数的每一位为1的个数<2
要么选择其中一个元素 vpos，将其增加 ki。 代表 第i位是1
要么不选择任何元素，直接跳过此次操作。 代表第i位是0
import java.util.Scanner;
import java.io.*;
public class Main{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int T = s.nextInt();
while (T-- != 0){
int n = s.nextInt(), k = s.nextInt();
boolean wrong = false;//总数组是否符合条件
long[] f = new long[n];
for (int i = 0; i < n; i ++) f[i] = Long.parseLong(s.next());
for (int i = 0; i < 100 && !wrong; i ++){
//扫一遍数组，如果一个数有超过两次除不开k或者超过两个数除不开k，代表该数组没法转换、
//并且每一个数可以选择不除k^i，也可以除k^i
int num = 0;
for (int j = 0; j < n; j ++){
num += f[j] % k; f[j] /= k;
}
if (num >= 2 && !wrong) wrong = true;
}
if (!wrong) System.out.println("YES");
else System.out.println("NO");
}
}
}
若有收获，就点个赞吧
0 人点赞
