java常见算法
题目————回溯
给你一个整数数组 digits ,其中每个元素是一个数字(0 - 9)。数组中可能存在重复元素。
你需要找出 所有 满足下述条件且 互不相同 的整数:
该整数由 digits 中的三个元素按 任意 顺序 依次连接 组成。
该整数不含 前导零
该整数是一个 偶数
例如,给定的 digits 是 [1, 2, 3] ,整数 132 和 312 满足上面列出的全部条件。
将找出的所有互不相同的整数按 递增顺序 排列,并以数组形式返回。
示例 1:
输入:digits = [2,1,3,0]
输出:[102,120,130,132,210,230,302,310,312,320]
解释:
所有满足题目条件的整数都在输出数组中列出。
注意,答案数组中不含有 奇数 或带 前导零 的整数。
import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;import java.util.List;class Solution { List res=new ArrayList(); LinkedList path=new LinkedList(); boolean[] used; public int[] findEvenNumbers(int[] digits) { used=new boolean[digits.length]; Arrays.sort(digits); backtracking(digits); int[] result=new int[res.size()]; for(int i=0; i<result.length; i++){ result[i]=res.get(i); } return result; } private void backtracking(int[] digits){ if(path.size()==3){ int sum=0; for(int i=0; i<path.size(); i++){ sum=sum*10+path.get(i); } if(valid(sum)){ res.add(sum); } return; } for(int i=0; i0&&digits[i]==digits[i-1]&&used[i-1]==false){ continue; } used[i]=true; path.add(digits[i]); backtracking(digits); //回溯———— used[i]=false; //将加上的最后一个去掉 path.removeLast(); } } private boolean valid(int sum){ if(sum%2!=0){ return false; } if(sum<=99){ return false; } return true; }}
2.题目——哈希表
给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
import java.util.Arrays;import java.util.HashMap;import java.util.Map;class p { public int[] intersect(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) { return intersect(nums2, nums1); } Map map = new HashMap(); for (int num : nums1) { int count = map.getOrDefault(num, 0) + 1; map.put(num, count); } int[] intersection = new int[nums1.length]; int index = 0; for (int num : nums2) { int count = map.getOrDefault(num, 0); //重复的-- if (count > 0) { intersection[index++] = num; count--; if (count > 0) { map.put(num, count); } else { map.remove(num); } } } return Arrays.copyOfRange(intersection, 0, index); }}