java常见算法
1.
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 1：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
示例 2：
输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
示例 3：
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
class Solution { public int massage(int[] nums) { int len = nums.length; if (len == 0) return 0; if (len == 1) return nums[0]; int[] dp = new int[len]; dp[0] = nums[0]; dp[1] = Math.max(nums[0],nums[1]); for (int i = 2; i < len; i++) { dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]); } return dp[len - 1]; }}2.回溯+深度
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
class Solution { public List<List> permute(int[] nums) { int len = nums.length; ArrayList<List> lists = new ArrayList(); List list = new LinkedList(); boolean[] isVisited = new boolean[len]; dfs(nums,isVisited,lists,list); return lists; } public void dfs(int[] nums,boolean[] isVisited,ArrayList<List> lists,List list) { if (list.size() == nums.length) { lists.add(new LinkedList(list)); return; } for (int i = 0; i < nums.length; i++) { if (isVisited[i]) continue; isVisited[i] = true; list.add(nums[i]); dfs(nums,isVisited,lists,list); isVisited[i] = false; list.remove(list.size() - 1); } }}3.
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5
示例 2：
输入：[3,2]
输出：-1
示例 3：
输入：[2,2,1,1,1,2,2]
输出：2
class Solution { public int majorityElement(int[] nums) { HashMap map = new HashMap(); int len = nums.length; if (len == 0) return -1; for (int i = 0; i < len; i++) { if (map.containsKey(nums[i])) { int a = map.get(nums[i]); a++; map.put(nums[i],a); }else { map.put(nums[i],1); } } for (int i = 0; i len / 2) return nums[i]; } return -1; }}