1、整数向负数进制转换

除对应进制数取余(绝对值),(被除数-余数的绝对值)/进制数作为新的被除数,直到被除数为0.注:原数为0的情况。

public static String baseNeg2(int N) {
	StringBuffer sb=new StringBuffer();
	int temp=-1;
	while(N!=0||temp==-1) {
		temp=Math.abs(N%-2);
		sb.append(temp);
		N=(N-temp)/-2;
	}
	return sb.reverse().toString();
}

2、数组中出现次数超过一半的数字

1.排序后,中位数就是出现次数超过一半的数字。时间复杂度O(nlogn)。
2.受快速排序算法的启发:如果按照基准进行一次快速排序后,基准的位置刚好是n/2,那么这个数就是数组的中位数;如果它的下标大于n/2,那么中位数位于它的左边,在左边部分继续查找;如果它的下标小于n/2,那么中位数位于它的右边,在右边部分继续查找。时间复杂度O(nlogn)。
3.遍历数组,保存2个值:数组中的一个数字,对应数字的次数。遍历下一个数字时,如果和当前保存的数字相等,次数加1,否则,次数减1;次数为0时,保存下一个值与次数。最后一次把次数设为1的数字就是出现次数超过一半的数字。时间复杂度O(n)。

3、二进制中1的个数

/**
* 按位进行与运算,long类型需要64次运算。
* @param n
* @return
*/
public static int solve1(long n){
	int count=0;
	long flag=1;
	while(flag!=0){
		if((n&flag)!=0){
			++count;
		}
		flag=flag<<1;
	}
	return count;
}

/**
* 如果一个整数非0,那么其二进制至少有一个1;
* 对于一个非0整数减去1,等价于把其二进制最右边的1变为0,其左边的所有位保持不变,其右边所有的0变为1:1100(2)减1后变为1011;
* 让n&(n-1)相当于把n的二进制表示中的最右边的一个1变为0,做几次这样的运算n变为0就说明n的二进制中有多少个1.可以减少计算次数。
* @param n
* @return
*/
public static int solve2(long n){
	int count=0;
	while(n!=0){
		++count;
		n=n&(n-1);
	}
	return count;
}

4、构造数组的MaxTree(来源:牛客网

对于一个没有重复元素的整数数组,请用其中元素构造一棵MaxTree,MaxTree定义为一棵二叉树,其中的节点与数组元素一一对应,同时对于MaxTree的每棵子树,它的根的元素值为子树的最大值。现有一建树方法:对于数组中的每个元素,其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数,那么它就是树根。(大顶堆也是一种MaxTree

//先找左边第一个比自己大的,再找右边第一个比自己大的,保留其中较小的
public static int[] buildMaxTree(int[] A, int n) {
	// write code here
	int[] index = new int[A.length];
	int[] stack = new int[A.length];
	int len = 0;
	//找到左边第一个比自己大的值的索引
	for (int i = 0; i < A.length; ++i) {
		if (len == 0) {
			stack[len++] = i;//保留左边第一个比自己大的值的索引
			index[i] = -1;//表示左边没有比它大的
		} else {
			if (A[i] < A[stack[len - 1]]) {
				index[i] = stack[len - 1];
				stack[len++] = i;
			} else {
				while (len > 0 && A[stack[len - 1]] < A[i]) {
					--len;
				}
				if (len == 0) {
					index[i] = -1;
				} else {
					index[i] = stack[len - 1];
				}
				stack[len++] = i;
			}
		}
	}
	len = 0;
	//找到右边第一个比自己大的值的索引
	for (int i = A.length - 1; i >= 0; --i) {
		if (len == 0) {
			stack[len++] = i;//保留右边第一个比自己大的值的索引
		} else {
			if (A[i] < A[stack[len - 1]]) {
				if (index[i] == -1 || A[stack[len - 1]] < A[index[i]]) {
					index[i] = stack[len - 1];
				}
				stack[len++] = i;
			} else {
				while (len > 0 && A[stack[len - 1]] < A[i]) {
					--len;
				}
				if (len > 0) {
					if (index[i] == -1 || A[stack[len - 1]] < A[index[i]]) {
						index[i] = stack[len - 1];
					}
				}
				stack[len++] = i;
			}
		}
	}
	return index;
}
//在找左边第一个比自己大的同时,遇到右边第一个比自己大的也比较一下并保留较小的
public static int[] buildMaxTree2(int[] A, int n) {
	// write code here
	int[] index = new int[A.length];
	int[] stack = new int[A.length];
	int len = 0;
	for (int i = 0; i < A.length; ++i) {
		if (len == 0) {
			stack[len++] = i;//保留左边第一个比自己大的值的索引
			index[i] = -1;//表示左边没有比它大的
		} else {
			if (A[i] < A[stack[len - 1]]) {
				index[i] = stack[len - 1];
				stack[len++] = i;
			} else {
				//遇到右边第一个比自己大的:保留左右第一比自己大的中的较小的那个值的索引
				while (len > 0 && A[stack[len - 1]] < A[i]) {
					if (index[stack[--len]] == -1 || A[i] < A[index[stack[len]]]) {
						index[stack[len]] = i;
					}
				}
				if (len == 0) {
					index[i] = -1;
				} else {
					index[i] = stack[len - 1];
				}
				stack[len++] = i;
			}
		}
	}
	return index;
}

5、计算斐波拉契序列(O(logn))

/*
* f(n)   f(n-1)         1   1
*                 =             的n-1次方,n>=2.
* f(n-1) f(n-2)         1   0
* */
public class 斐波拉契 {
    public static void main(String[] args) {
        System.out.println(getNthNumber(88488994));
    }

    public static int getNthNumber(int n) {
        // write code here
        if (n < 2) {
            return 1;
        }
        long[][] fib = {{1, 1}, {1, 0}};
        long[][] temp = {{1, 1}, {1, 0}};
        solve(temp, fib, n);
        return (int) temp[0][0];
    }

    public static void solve(long[][] temp, long[][] fib, int n) {
        if (n == 2) {
            long[][] ttemp = new long[2][2];
            for (int i = 0; i < 2; ++i) {
                ttemp[i][0] = (temp[i][0] * fib[0][0] % 1000000007 + temp[i][1] * fib[1][0] % 1000000007) % 1000000007;
                ttemp[i][1] = (temp[i][0] * fib[0][1] % 1000000007 + temp[i][1] * fib[1][1] % 1000000007) % 1000000007;
            }
            for (int i = 0; i < temp.length; ++i) {
                temp[i][0] = ttemp[i][0];
                temp[i][1] = ttemp[i][1];
            }
            return;
        }
        if (n % 2 == 0) {
            solve(temp, fib, n / 2);
            solve(temp, temp, 2);
            return;
        }
        solve(temp, fib, n - 1);
        solve(temp, fib, 2);
    }
}

6、子集

public class 子集 {
    public static void main(String[] args) {
        int[]arr={1,2,3};
        System.out.println(Arrays.toString(subsets(arr).toArray()));
    }

    /**
     * 作用:计算一个数组的所有子集
     * 思路:
     * n个数的数组共有2的n次方个子集,这些子集可以看成是n个数中每个数有或没有组成的。
     * 比如:1 2 3,000表示空集[],100表示[1]
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets(int[] nums) {
        ArrayList<List<Integer>> list = new ArrayList<>();
        int len=1<<nums.length;
        for (int i=0;i<len;++i) {
            List<Integer> llist=new ArrayList<>();
            int flag=1;
            int index=0;
            while(index<nums.length){
                if((flag&i)>0){
                    llist.add(nums[nums.length-index-1]);
                }
                ++index;
                flag=flag<<1;
            }
            list.add(llist);
        }
        return list;
    }
}

7、取石子游戏(来源:HDOJ

import java.util.Scanner;
/**
 * 思路:
 * 1、如果n为斐波拉契数的话,先者必输。
 * 2、n不是斐波拉契数的话,可以分为多个不连续的斐波拉契数的和。比如:f(n)=fib(a)+fib(b)+fib(c),a>b>c。有fib(a)>2*fib(b);fib(b)>2*fib(c)。只要先者先拿fib(c),那么后者不可能拿到fib(b),也就相当于后者先拿斐波拉契数,所以先者必赢。
 */
public class 取石子游戏 {
    public static void main(String[] args){
        int n;
        Scanner in=new Scanner(System.in);
        n=in.nextInt();
        while(n!=0){
            System.out.println((notFib(n)?"First":"Second")+" win");
            n=in.nextInt();
        }
    }
    public static boolean notFib(int n){
        int a=1;
        int b=2;
        if(n<=2){
            return false;
        }
        while(b<n){
            int t=b;
            b+=a;
            a=t;
        }
        if(b==n){
            return false;
        }
        return true;
    }
}

8、从N个无序数中寻找Top-k个最大/小数( 经典海量数据 )?

  • 在可以改变原数组且内存够用的情况下
    • 1.使用普通排序算法排序后取前k个数。时间复杂度O(nlogn)。
    • 2.基于快速排序:如果按照基准进行一次快速排序后,基准的位置刚好是k-1(从0开始),那么前k个数就是topK个数(不保证有序)。
    • 3.基于堆排序:
      • 1.(数据量大到内存放不下时)先取序列中K个数构建大顶堆/小顶堆O(K),然后从剩下的序列中每次取一个数,替换堆中元素/丢弃O(logK*(n-K))。时间复杂度为O(NlogK)。
      • 2.(内存足够大时)把N个数据构建一个大顶堆/小顶堆O(logN),做k此排序即可。时间复杂度为O(KlogN)。
    • 4.使用TreeSet
private static void getMinK(int[] arr, int n, int k) {
	TreeSet<Integer>set=new TreeSet<>();
	for(int i:arr){
		//前K个数直接加入集合中
		if(set.size()<k){
			set.add(i);
		}else{
			//降序遍历
			Iterator<Integer> iterator=set.descendingIterator();
			if(i<iterator.next()){
			//小的替代最大的,TreeSet会自动调整顺序
				iterator.remove();
				set.add(i);
			}
		}
	}
	System.out.println(set.toString());
}

9、抽屉原理(原理:我的牛客博客

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,至少会有一个抽屉里面放两个苹果,这一现象称为“抽屉原理”。如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。

寻找重复数(来源:LeetCode

 public static int findDuplicate(int[] nums) {
	 // 快慢指针从起点开始,快指针每次走2步,慢指针每次走1步,找到在环中相遇位置
	 int tortoise = nums[0];
	 int hare = nums[0];
	 do {
		 tortoise = nums[tortoise];
		 hare = nums[nums[hare]];
	 }
	 while (tortoise != hare);

	 // 慢指针从相遇位置继续走,再加一个慢指针从起点开始,两个慢指针相遇的位置就是环的入口
	 int ptr1 = nums[0];
	 int ptr2 = tortoise;
	 while (ptr1 != ptr2) {
		 ptr1 = nums[ptr1];
		 ptr2 = nums[ptr2];
	 }
	 return ptr1;
 }

10、计算N!的十进制中末尾0的个数

/**
* 计算N!十进制表示中末尾0的个数
* 思路:2*5有1个0,2的个数大于或等于5的个数,所以计算5的个数即可。
* n/5+n/25+n/125+...+n/5^k,直到n>5^k。
* @param n
* @return
*/
private static int getZeroCount(int n) {
	int count=0;
	while(n>0){
		count+=n/5;
		n/=5;
	}
	return count;
}

举一反三

计算1~n之间有多少个因子m的方法:n/m+n/m^2+...+n/m^k,直到n>m^k。

11、计算N!的2进制中末尾0的个数

/**
* 计算N!的2进制中末尾0的个数
* 思路:2进制中末尾有K个0,表示这个数是m*2^(k-1),这个m最后一位是1,即是一个奇数,所以等价于计算有多少个2相乘。
* n/2+n/4+n/8+...+n/2^k,直到n>2^k。
* @param n
* @return
*/
private static int getZeroCount(int n) {
	int count=0;
	while(n>0){
		count+=n/2;
		n/=2;
	}
	return count;
}

12、数论分块

给定一个N,计算i*n%i,i从1到N的和。

1、i*n%i=i*(n-i*[n/i])=i*n-i^2*[n/i]。//[n/i]表示取整
2、i从1到N对上述公式求和=n^2*(n+1)/2-i^2*[n/i],i从1到N。
3、i^2*[n/i],i从1到N,假设N=10,i从1到10,n/i结果为:10,5,3,2,2,1,1,1,1,1。可以看出有重复的部分,按照相同数字分块。每一块的结果为:假设某一块的左右端点为left,right。n/left*(从left^2一直加到right^2),公式为:(right*(right+1)*(2*right+1)/6-(left-1)*(left)*(2*left-1)/6)*n/left。
4、块的左右端点left、right之间的关系:right=n/(n/left);

13、差分数组(来源:航班预订统计

//题目
这里有 n 个航班,它们分别从 1 到 n 进行编号。
我们这儿有一份航班预订表,表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。
请你返回一个长度为 n 的数组 answer,按航班编号顺序返回每个航班上预订的座位数。

//思路:查分数组,统计每个航班与前一个航班的预订的座位数的差。比如:数组balance[i]表示第i个航班与第i-1个航班的差。那么第i个航班预订的座位数res[i]=res[i-1]+balance[i]。

//代码
public int[] corpFlightBookings(int[][] bookings, int n) {
	int[] res=new int[n];
	int[] balance=new int[n+1];
	for(int i=0;i<bookings.length;++i){
		balance[bookings[i][0]]+=bookings[i][2];
		balance[bookings[i][1]+1]-=bookings[i][2];
	}
	for(int i=0;i<n;++i){
		if(i==0){
			res[i]=balance[i];
		}else{
		res[i]=balance[i-1]+balance[i+1];
		}
	}
	return res;
}

14、最大子矩阵的大小(来源:LeetCode

//思路:
1、因为矩阵中必须全是1,所以只要遇到0,这一列的高度就为0。
2、计算以每一行为低能得到的最大矩阵:统计每一列全1的个数,只要当前行的某一列为0,那么这一列的高度就为0,否则,为上一行高度+1.统计完高度后计算当前最大矩阵。
3、当前最大矩阵的计算:max{某个区间*该区间高度最小值}。使用栈进行如下操作:
	1.如果栈为空/当前值大于栈顶坐标对应的值,坐标入栈;否则,一直出栈,直到满足入栈条件。
	2.在每次出栈后,计算以栈顶值对应的列向左右扩展能得到的最大矩阵:因为栈中元素是递增的,所以最左到达当前栈顶坐标+1的位置,最右到达当前元素-1的位置。然后记录最大值。
4、遍历完一行后,栈肯定是不空的,进行如下操作:出栈,每次出栈后计算以栈顶值对应列向左右扩展能得到的最大矩阵:这时还在栈中,所以其右边所有元素都>=它,因为如果其右边有比它小的元素,它就被pop了,所以最右可以到达最右边的列,最左到达当前栈顶值+1的位置。然后记录最大值。
//举一反三
1、对于连续的数字问题,可以尝试保留坐标。
2、在连续数组问题中以最小值为基准的时候,可以尝试使用递增栈。

public static int maximalRectangle(char[][] matrix) {
	int max = Integer.MIN_VALUE;
	int[] arr = new int[matrix[0].length];
	for (int i = 0; i < matrix.length; ++i) {
		for (int j = 0; j < matrix[i].length; ++j) {
			arr[j] = matrix[i][j] == &#39;0&#39; ? 0 : arr[j] + 1;
		}
		Stack<Integer> stack = new Stack<>();
		for (int k = 0; k < arr.length; ++k) {
			while (!stack.isEmpty() && arr[stack.peek()] >= arr[k]) {
		/*
		* 以栈顶高度能分割的最大矩阵面积,因为栈是单增的,且存储的是坐标,所以以栈顶为中心向左右扩展,最左到达栈顶下一个
		* 坐标+1位置,最右到达k-1位置。
		* */
				int temp = stack.pop();
				int start = stack.isEmpty() ? -1 : stack.peek();
				max = Math.max(arr[temp] * (k - start - 1), max);
			}
			stack.push(k);
		}
		while (!stack.isEmpty()) {
/*
* 最右存在栈中元素的右边肯定都是>=自己的,否则就被pop了。
* */
			int index = stack.pop();
			int start = stack.isEmpty() ? -1 : stack.peek();
			int temp = Math.max(arr[index] * (arr.length - start-1), arr[index]);
			if (max < temp) {
				max = temp;
			}
		}
	}
	return max;
}

15、全排列

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class 全排列 {
    public static void main(String[] args){
    }
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        ArrayList<Integer> list=new ArrayList<>();
        for(int i:nums){
            list.add(i);
        }
        backtrack(0,list,nums.length-1,res);
        return res;
    }
    private static void backtrack(int first,ArrayList<Integer> nums,int n,List<List<Integer>> list){
		//当到达最后一个元素,说明此次排列到头了,加入结果集中
        if(first==n){
            list.add(new ArrayList<Integer>(nums));
        }
		//从first位置开始遍历,交换2个元素,然后递归以下一个位置为首位置
        for(int i=first;i<=n;++i){
            Collections.swap(nums,first,i);
            backtrack(first+1,nums,n,list);
            Collections.swap(nums,first,i);//回溯
        }
    }
}

16、布隆过滤器

可以精确判断某一元素是否在此集合中,精确程度由用户的具体设计决定,想做到100%的精确是不可能的。

  • 优势:利用很少的空间可以做到较高的精确率。

1、元素

  • bitarray,值为0、1
  • K个哈希函数
  • N个目标数据

2、步骤

  • 把每个数据通过K个哈希函数散列得到K个值,将bitarray中[K个值%bitarray大小]对应位置置为1.
  • 在判断一个数据是否包含在N个数据中时,通过K个哈希函数散列得到K个值,判断bitarray中[K个值%bitarray大小]对应位置是否都是1:如果不是则肯定不包含;如果是则表示包含,但是存在错误率:(1-e^(-(nk)/m))k。

3、数值

  • 单个数据大小不影响布隆过滤器大小,只影响哈希函数的实现细节。
  • p表示失误率。
  • bitarray大小m=-n*lnp/(ln2)^2。
  • 哈希函数个数K=ln2*m/n。

17、卡特兰数

C(2n,n)/(n+1)。

结果为卡特兰数的一些题目

  • n个数进出栈的顺序种数。
  • 2n个人排队买票,n个人拿5块钱,n个人拿10块钱,票价是5块钱1张,每个人买一张票,售票员手里没有零钱,让售票员可以顺利卖票的排队种数。
  • n个左括号,n个右括号,有效排列种数。
  • n个无差别节点构成的二叉树种数。
  • 2n个人分2队,第二队的人比第一队的对应位置的人高:把2n个人从矮到高排序,假设第一队的记为0,第二队的记为1。有:000 111满足要求,001 110不满足要求;也就是说每个1前面要有一个0和它对应。所以结果为卡特兰数。

18、约瑟夫问题

  • 题目描述:由n个人坐成一圈,按顺时针由1开始给他们编号。然后由第一个人开始报数,数到m的人出局。现在需要求的是最后一个出局的人的编号。给定两个int n和m,代表游戏的人数。请返回最后一个出局的人的编号。
  • 思路:
    • 每次出局一个人后,假设剩下k个人,这k个人从1~k编号.
    • 最后剩1个人时,就是最后一个出局的人,其编号为1,记为getResult(1)=1.
    • 剩2个人时,假设最后一个出局的人在此时的编号为getResult(2).
    • 。。。
    • 剩n个人时,假设最后一个出局的人在此时的编号为getResult(n).
    • 剩k个人时,编号为1-k,这时出局一个编号为m的人,那么从m+1重新开始编号1~k-1,得出k个人时编号为old的人在k-1个人时对应编号new之间的关系:old=(new+m-1)%k+1.
  • 代码
public int getResult(int n, int m) {
	if(n==1){
		return 1;
	}
	return (getResult(n-1,m)+m-1)%n+1;
}

19、最大公约数

  • 解法一:辗转相除法。
  • 解法二:x和y的公约数与x-y和y的公约数相同,最大公约数自然也是相同的。
  • 解法三
    • 对于x和y来说,如果y=ky1,x=kx1,那么f(y,x)=k*f(y1,x1)。
    • 如果x=px2,且p是素数,同时y%p!=0,那么f(y,x)=f(y,px2)=f(y,x2)。
    • 取p=2。
      • 若x,y均为偶数,f(x,y)=2f(x/2,y/2)=2f(x>>1,y>>1)。
      • 若x为偶数,y为奇数,f(x,y)=f(x/2,y)。
      • 若x为奇数,y为偶数,f(x,y)=f(x,y/2)。
      • 若x,y均为奇数,f(x,y)=f(x-y,y)。(大的减小的)。

20、最小覆盖子串(来源:LeetCode

import java.util.HashMap;
import java.util.Scanner;

/**
 * 滑动窗口:字符串S的所有子串中包含字符串T中所有字符的子串称为窗口。
 * 1、left、right两个指针,表示窗口的左右边界。
 * 2、right指针向右滑动,找到一个满足要求的窗口后,下一步。
 * 3、left指针向右滑动,找到下一个不满足要求的窗口,下一步。
 * 4、重复2、3直到S尾。
 *
 * 5、如何判断窗口是否满足要求?
 *      1、把T中的字符与其个数作为键值对存入map中。
 *      2、right指针向右滑动时,将对应字符在map中的值-1。
 *      3、left指针向右滑动时,将对应字符在map中的值+1。
 *      4、如果map中所有值都小于等于0,说明当前窗口满足要求;否则不满足。
 */
public class 最小覆盖子串 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String t = in.nextLine();
        System.out.println(minWindow(s, t));
    }

    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();//s的子串需要对应字符个数。
        char[] chars_t = t.toCharArray();
        for (char ch : chars_t) {
            int count = need.getOrDefault(ch, 0);//如果key存在,则拿到value;否则拿到给定的默认值。
            need.put(ch, count + 1);
        }

        int left = 0;
        int right = 0;
        int min = Integer.MAX_VALUE;
        int res_left = 0;
        int res_right = 0;
        char[] chars_s = s.toCharArray();
        while (right < s.length()) {
            while (right < s.length() && !isOk(need)) {//right指针向右滑动
                int count = need.getOrDefault(chars_s[right], 0);
                need.put(chars_s[right], count - 1);
            }
            if (isOk(need)) {//如果当前窗口满足要求,则left指针向右滑动
                while (left <= right && isOk(need)) {
                    need.put(chars_s[left], need.get(chars_s[left++]) + 1);
                }
                if (min > right - left + 1) {
                    min = right - left + 1;
                    res_left = left - 1;
                    res_right = right;
                }
            } else {
                break;
            }
        }
        return new String(s.toCharArray(), res_left, res_right - res_left);
    }

    /**
     * 是否包含T中所有字母
     *
     * @param need
     * @return
     */
    private static boolean isOk(HashMap<Character, Integer> need) {

        for (Character ch : need.keySet()) {
            if (need.get(ch) > 0) {
                return false;
            }
        }
        return true;
    }
}

21、删除链表中重复的结点(来源:NowCoder

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode head=new ListNode(0);//头结点
        head.next=pHead;
        ListNode pre=head;//pre指向最后一个没有重复的结点
        ListNode last=pre.next;
        while(last!=null){
		//遇到重复结点时,找到下一个不同的结点,这个结点不一定不与后面的结点重复
		if(last!=null&&last.next!=null&&last.val==last.next.val){
                while(last.next!=null&&last.val==last.next.val){
                    last=last.next;
                }
                pre.next=last.next;//下一个结点只是与当前重复的结点不同,后面可能有重复结点
            }else{
                pre=last;//两个结点不同时,前一个结点肯定无重复
            }
            last=last.next;
        }
        return head.next;
    }
}

22、100亿手机号码去重

  • bitmap:用位数组存储,数组对应位置为1表示索引值代表的值存在、0表示索引值代表的值不存在。
  • 手机号码一般11位,第一位目前都是1,所以可以只看后面10位。用一个999999999(10个9)长度的位数组存储。需要内存:999999999/8/1024/1024=1192MB。
  • 分治:按照第二、第三位把手机号码分到不同文件中,使用99999999(8个9)长度的位数组分别存储。需要内存:9999999/8/1024/1024=11.92MB。
  • 手机号码还原:
    • 对于不足8位的值前面补0。
    • 然后加上1+文件前缀。

23、乘法表中第K小的数(来源:LeeTCode

/*
二分查找
	二分查找一般是在有序的数组中查找一个数是否存在,这里通过计算一个数在序列中的位置找出第K小的数:通过二分计算这个基准值——当<=x-1的个数小于k,<=x的个数大于等于k时,这个x就是第K小的数。
*/
class Solution {
    public int findKthNumber(int m, int n, int k) {
        int left=1;
        int right=n*m+1;
        int mid=0;
        while(left<right){
            mid=left+(right-left)/2;
            int count=0;
            for(int i=1;i<=m;++i){
                count+=mid/i>n?n:mid/i;
            }
            if(count>=k){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}