最近打算整理下排序算法，本来都不想刷题了，但是看群里狗群友一个比一个勤奋，所以今天的三道题还是刷了吧，这样睡觉也能安稳些。打个广告，130031711，java技术交流群，欢迎各位大佬萌新踊跃加入！
计算各个数位都不同的数字个数
题目：给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
示例:
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
思路：这个题我觉得不是用代码一个个去暴力解决的。其实是有一些规律的。我去找找规律
好了，回来了，用眼去看，用心去想。我直接贴代码再解释：
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if(n==0)
return 1;
int []dp=new int [n+1];
dp[0]=1;
dp[1]=10;
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1]+(dp[i-1]-dp[i-2])*(10-(i-1));
}
return dp[n];
}
}
各位数字都不同。首先加上一个位数的结果是正常的，因为100中各个数不同的肯定包含10中各个数不同的。所以这个很好理解。
而dp[i-1]-dp[i-2]的意思是我们上一次较上上一次多出来的各位不重复的数字。以n=3为例，n=2已经计算了0-99之间不重复的数字了，我们需要判断的是100-999之间不重复的数字，那也就只能用10-99之间的不重复的数去组成三位数，而不能使用0-9之间的不重复的数，因为他们也组成不了3位数。而10-99之间不重复的数等于dp[2]-dp[1]。
当i=2时，说明之前选取的数字只有1位，那么我们只要与这一位不重复即可，所以其实有9(10-1)种情况（比如1，后面可以跟0,2,3,4,5,6,7,8,9）。当i=3时，说明之前选取的数字有2位，那么我们需要与2位不重复，所以剩余的有8（10-2）种（比如12，后面可以跟0,3,4,5,6,7,8,9）。
然后这个dp 的公式就出来了。所以有了上面的代码。
这个题其实不是代码上的难度，单纯的就是找规律。没啥可说的，下一题吧。
水壶问题
题目：有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
思路：这个题，我觉得我遇到了瓶颈！！真的，这个我会，一看就会的会。以前做过这样一道数学题，是个拔高题我记得。然后能不能z这么多的水是可以判断的。我记得是两个桶的最大公约数能不能被z整除。能就可以，不能就fasle。大小什么的就不用说了！！但是问题来了，除了暴力遍历我不知道java代码怎么实现。。。真的是日狗了。。我去试试吧。这种思路一大堆下不了手的情况有点烦躁。
好了，虽然性能不咋地但是起码实现了，我去贴代码：
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if(x==z || y==z) return true;
if(x+y<z) return false;
if(x%2==0 && y%2==0 && z%2==1) return false;
int yue = x<y?x:y;
while(x%yue!= 0 || y%yue!=0 ){
yue--;
}
return z%yue == 0;
}
}
思路没问题，而且这个题真的我觉得是个数学题。然后求公约数这个，我可能是在这块浪费性能了，不过确实没思路，不知道有没有现成的api，我去看看性能排行第一的代码吧。
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (x == 0 && y == 0) return z == 0;
int a = x, b = y;
while (b != 0) {
a %= b;
a ^= b;
b ^= a;
a ^= b;
}
return z == 0 || (z % a == 0 && x + y >= z);
}
}
????分开每个字母我都认识！但是这个代码我是一点没明白，除了第一句！
这个比较无奈了，，感觉while操作最后实现的是a变成了最大公约数，但是怎么实现的完全看不懂。
这道题我还是笨办法做吧，下一题了。
最大整除子集
题目：给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:
输入: [1,2,4,8]
输出: [1,2,4,8]
思路：这个题怎么说呢，刚刚做了测试，1，4,2也是三个。又因为顺序是相互的，所以说其实这个顺序不重要。所以我目前的想法是先排序，在判断。而且可能有多个可选项，所以想要判断一个元素可以成为的最长串的数量，还需要去和前面所有的元素对比。打个比方，1,3,4,6,8,9,27如果是这样的例子。比如判断到9了，我们要去和8比，不是子集，继续和6比，不是子集，然后和4比，不是子集。然后和3比，是子集。这个时候其实3本身1,3.它的长度已经是2了，所以9的长度是3的长度2+1，也就是3。然后27继续去比较，因为直接是9的子集，所以是3+1也就是4.你以为这个就完事了？不是的，万一之前有更长的呢！所以还是要遍历一个遍。反正我觉得这个题就是双循环吧。我去敲代码试试。.
好了，写完了，兜兜转转，居然变成了二维dp，我直接贴代码：
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
LinkedList<Integer> res = new LinkedList<Integer>();
if(nums.length==0) return res;
Arrays.sort(nums);
//第一个存个数，第二个存上一个元素下标
int[][] dp = new int[nums.length][2];
//初始数是1，但是我看的赋值，所以统一从0开始。上一个下标是-1
dp[0][0] = 0;
dp[0][1] = -1;
//个数最大值
int max = -1;
//个数最大值的下标
int maxIdx = 0;
for(int i = 1;i<nums.length;i++){
//上一个统一为-1.如果有上一个了会被替换
dp[i][1] = -1;
for(int j = i-1;j>=0;j--){
if(nums[i]%nums[j]==0 && dp[i][0]<(dp[j][0]+1)){
dp[i][0] = dp[j][0]+1;
dp[i][1] = j;
if(max<dp[i][0]){
max = dp[i][0];
maxIdx = i;
}
}
}
}
while(maxIdx!=-1){
res.addFirst(nums[maxIdx]);
maxIdx = dp[maxIdx][1];
}
return res;
}
}
其实这个题用一个数据dp也可以实现，但是在找出最大的连续子集后还要重新遍历去一遍遍找元素，所以我这里用二维数据存上一个点的下标，将数组做成链表的形式。我觉得我思路没问题，但是性能告诉我不是这么回事。我也不知道为什么性能不咋地，反正就是这样了。只超过百分之七十五的人。我去看看性能排行第一的代码吧。
怎么说呢，大同小异，但是处理不同，我这里是二维数组，人家是两个数组。但是性能就不如人家的好，伐开森~~我直接贴代码：
class Solution {
public int max(int a,int b){
return a>b?a:b;
}
public List<Integer> largestDivisibleSubset(int[] nums) {
int n=nums.length;
if(n==0)
return new ArrayList();
int[] last=new int[n];
for(int i=0;i<n;i++)
last[i]=-1;
int[] dp=new int[n];
int ans=0;
Arrays.sort(nums);
for(int i=0;i<n;i++)
for(int j=0;j<i;j++){
if(nums[i]%nums[j]==0&&dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
if(dp[ans]<dp[i])
ans=i;
last[i]=j;
}
}
List<Integer> ansList=new ArrayList();
while(ans!=-1){
ansList.add(nums[ans]);
ans=last[ans];
}
return ansList;
}
}
然后其实我觉得这种题只能要看懂一种解，就都能看懂了，因为思路是差不多的。这个题也就这样了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利。生活健健康康！！打广告。java技术交流群，群号130031711，欢迎各位大佬萌新踊跃加入！
网友评论