行业门户网站制作,四川省住房和城乡建设厅官网下载,家具设计软件下载,建设工程施工合同管辖1262. 可被三整除的最大和 原题链接#xff1a;完成情况#xff1a;解题思路#xff1a;方法一#xff1a;贪心 正向思维方法二#xff1a;贪心 逆向思维 参考代码#xff1a;方法一#xff1a;贪心 正向思维方法二#xff1a;贪心 逆向思维 原题链接#xff1a;… 1262. 可被三整除的最大和 原题链接完成情况解题思路方法一贪心 正向思维方法二贪心 逆向思维 参考代码方法一贪心 正向思维方法二贪心 逆向思维 原题链接
1262. 可被三整除的最大和
https://leetcode.cn/problems/greatest-sum-divisible-by-three/description/
完成情况 解题思路
方法一贪心 正向思维 方法二贪心 逆向思维 参考代码
方法一贪心 正向思维
package LeetCode中等题;import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;public class __1262可被三整除的最大和__贪心_余数分组配对 {public static void main(String[] args) {int nums[] {3,6,5,1,8};maxSumDivThree(nums);}/**** param nums* return*/public static int maxSumDivThree(int[] nums) {//用v_remind[i]来表示余数ListInteger v_remind [] new List[3];for (int i0;i3;i){v_remind[i] new ArrayListInteger();}//按余数值进行分组for (int num : nums){v_remind[num % 3].add(num);}Collections.sort(v_remind[1],(a,b)- b-a); //自定义Collecctions类的v_remind[1]排序规则Collections.sort(v_remind[2],(a,b)- b-a); //自定义Collecctions类的v_remind[2]排序规则int ans 0;int lb v_remind[1].size(),lc v_remind[2].size();//每一个v_remind[1]和一个v_remind[2]都可以进行匹配为一组//因此我应该是放任所有的v_remind[0]不去管//然后大小排序好1,2.。。。。。。。//然后每一组1,2就从大到小区合并//同时不能让他们某一组多余值大于%3的余数因为任何数得余数都一个除以3for(int countB lb-2;countB lb;countB){if (countB 0){for (int countC lc-2;countC lc;countC){if (countC 0 (countB - countC)%3 0){ans Math.max(ans,getSum(v_remind[1],0,countB)getSum(v_remind[2],0,countC));}}}}return ansgetSum(v_remind[0],0,v_remind[0].size());}/**** param listRemind* param start* param end* return*/private static int getSum(ListInteger listRemind, int start, int end) {int sum 0;for (int i start;iend;i){sum listRemind.get(i);}return sum;}
}
方法二贪心 逆向思维
package LeetCode中等题;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class __1262可被三整除的最大和__贪心_先取所有的数再按余数对应去除 {/**** param nums* return*/public int maxSumDivThree(int[] nums) {//用v_remind[i]来表示余数// 使用 v[0], v[1], v[2] 分别表示 a, b, cListInteger v_remind[] new List[3];for (int i0;i3;i){v_remind[i] new ArrayListInteger();}//按余数值进行分组for (int num : nums){v_remind[num % 3].add(num);}Collections.sort(v_remind[1],(a, b)- b-a); //自定义Collecctions类的v_remind[1]排序规则Collections.sort(v_remind[2],(a,b)- b-a); //自定义Collecctions类的v_remind[2]排序规则int total Arrays.stream(nums).sum();int remove Integer.MAX_VALUE;if (total % 3 0){remove 0;} else if (total % 3 1) {if (v_remind[1].size() 1){remove Math.min(remove,v_remind[1].get(v_remind[1].size() - 1));}if (v_remind[2].size() 2){remove Math.min(remove,v_remind[2].get(v_remind[2].size() - 2) v_remind[2].get(v_remind[2].size() - 1) );}}else {if (v_remind[1].size() 2){remove Math.min(remove,v_remind[1].get(v_remind[1].size() - 2)v_remind[1].get(v_remind[1].size() - 1));}if (v_remind[2].size() 1){remove Math.min(remove,v_remind[2].get(v_remind[2].size() - 1));}}return total - remove;}
}
