刷题打卡，第二天
一、（简单）1281. 整数的各位积和之差
二、215. (中等)数组中的第K个最大元素
三、670. （中等）最大交换
一、（简单）1281. 整数的各位积和之差
原题链接：1281. 整数的各位积和之差
题目描述：
给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
/
示例 1：
输入：n = 234
输出：15
解释：
各位数之积 = 2 * 3 * 4 = 24
各位数之和 = 2 + 3 + 4 = 9
结果 = 24 - 9 =15
/
示例 2：
输入：n = 4421
输出：21
解释：
各位数之积 = 4 * 4 * 2 * 1 = 32
各位数之和 = 4 + 4 +2 + 1 = 11
结果 = 32 - 11 = 21
题目很简单，每个循环中：
各位数之和 += n的最后一位数
各位数之积 *= n的最后一位数
当轮循环结束前，将n去除最后一位数。
n为0结束循环时返回积 - 和即可。
class Solution { public int subtractProductAndSum(int n) { int plus = 0;//和 int x = 1;//积 while(n!=0){ x *= n%10; plus += n%10; n /= 10; } return x-plus; } }
提交结果：
二、215. (中等)数组中的第K个最大元素
原题链接：(中等)数组中的第K个最大元素
题目描述：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
/
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
/
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
解题思路:
题目要求数组中第k大的数，只要把数组所有元素放入优先队列（最大堆）中排序，从中取出的数都是从大到小的，所以取出的第k个数就是第k大的数。因为Java有PriorityQueue()方法，所以写起来最简单。
class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a,Integer b){ return b-a; } });//创建优先队列，重写比较器，设定为最大堆。 for(int i = 0;i < nums.length;++i){//将数组元素放入堆中 que.offer(nums[i]); } int out = 0; for(int i = 0;i < k;++i){//依次取出堆中元素，直到第k个 out = (int)que.poll(); } return out;//返回第k大的数 } }
提交结果：
内存和用时都很多，哈哈
三、670. （中等）最大交换
原题链接：（中等）最大交换
题目描述：
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
/
示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。
/
示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。
解题思路：
可以将这个整数拆分成各个数位的数字（个位上的数、十位上的数、百位…），存放在有序可重复的List集合中，同时存放到最大堆中，方便获取最大的数位。
若堆中取出值最大数位与集合中的最高数位比较，相等就比较次大的数位，若一直相等，代表值已经最大，不用交换；
若不相等，找出当前对比不相等的最大值在集合中的位置，将其值放到不相等情况下最高的位级中，原本位置则放入交换的数，从而实现单次交换最大。
解题代码：
class Solution { public int maximumSwap(int num) { List list = new ArrayList();//创建有序可重复集合list int sum = 0; //用来记录非负整数有多少位数 int temp = num; //复制一个非负整数 PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a,Integer b){ return b-a; } });//创建优先队列，重写比较器，设置成最大堆。 while(temp != 0){//从个位数开始，将各个数位上的数放入集合与最大堆 list.add(temp%10); que.offer(temp%10); temp /= 10; sum++;//记录数位的多寡 } int i = 1,big,curr;//big表示堆中取出的最大值，curr表示集合中的位数大小 while(i<=sum){ big = (int)que.poll();//取出堆中的最大值 curr = (int)list.get(sum-i);//取出最高数位的数 if(curr == big){//比较，相等就比较下一数位 i++; continue; }else{//不等 int index = list.indexOf(big);//获取比较不相等的最大值在集合中的位置 //交换位置，让更大的数到更高的数位中，从而得到最大值 list.set(index,curr);//下标index位置的值改为curr list.set(sum-i++,big);//下标sum-i的位置的值改为big break; } } //以下操作是将分开储存的位数重新加起来，得到完整的非负整数 int ten = 1; int out = 0; for(int j = 0;j< sum;++j){ out += ((int)list.get(j)*ten); ten *= 10; } return out; } }
提交结果：
贵在坚持：
