LeetCode每日十题---分治法

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=='*'; }

总结

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