LeetCode每日十题---分治法

    科技2025-05-25  89

    1.题目描述

    1.1笔者解答

    class Solution { public int majorityElement(int[] nums) { Map<Integer,Integer> map=new HashMap<Integer,Integer>(); for(int i=0;i<nums.length;i++){ map.put(nums[i],map.getOrDefault(nums[i],0)+1); } for(Integer num:map.keySet()){ if(map.get(num)>nums.length/2){ return num; } } return 0; } }

    1.2笔者分析

    学了一个新的算法:摩尔投票法。 核心就是对拼消耗。玩一个诸侯争霸的游戏,假设你方人口超过总人数一半以上,并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗,最差所有人都联合起来对付你(对应你每次选择作为计数器的数都是众数),或者其他国家也会相互攻击(会选择其他数作为计数器的数),但是只要你们不要内斗,最后肯定你赢,最后能剩下的必定是自己人。

    public int majorityElement(int[] nums){ int count=1; int maj=nums[0]; for(int i=1;i<nums.length;i++){ if(maj==nums[i]) count++; else{ count--; if(count==0) maj=nums[i+1]; } } return maj; }

    2.题目描述

    2.1笔者分析

    解题思路:对于一个形如 x op y (op为运算符,x和y为数)的算式而言,它的结果组合取决于x和y的结果组合树,而x和y又可以下城形如x op y的算式。因此该问题的子问题就是x op y中的x 和 y :以运算符分隔的左右两侧算式解。 然后我们进行分治算法三步走: 1.分解:按运算符分成左右两部分,分别求解。 2.解决:实现一个递归函数,输入算式,返回算式解。 3.合并:根据运算符合并左右两部分的解,得出最终解。

    public List<Integer> diffWaysToCompute(String input){ if(input.length()==0){ return new ArrayList<>(); } List<Integer> result=new ArrayList<>(); int num=0; //考虑全是数字的情况 int index=0; while(index<input.length()&&!isOperation(input.charAt(index))){ num=num*10+input.charAt(index)-'0'; index++; } //将全数字的情况直接返回 if(index==input.length()){ result.add(num); return result; } for(int i=0;i<input.length();i++){ if(isOperation(input.charAt(i))){ List<Integer> result1=diffWaysToCompute(input.substring(0,i)); List<Integer> result2=diffWaysToCompute(input.substring(i+1)); //将两个结果依次运算 for(int j=0;j<result1.size();j++){ for(int k=0;k<result2.size();k++){ char op=input.charAt(i); result.add(caculate(result1.get(j),op,result2.get(k))); } } } } return result; } private int caculate(int num1,char c,int num2){ switch(c){ case '+': return num1+num2; case '-': return num1-num2; case '*'; return num1*num2; } return -1; } private boolean isOperation(char c){ return c=='+'||c=='-'||c=='*'; }

    总结

    摩尔投票法还是挺秀的,分治法也挺牛,每日打卡三十二天,以下图为证

    Processed: 0.014, SQL: 8