package y2019.Algorithm.array.medium; import java.util.Arrays; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.array.medium * @ClassName: ProductExceptSelf * @Author: xiaof * @Description: TODo 238. Product of Array Except Self * Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all * the elements of nums except nums[i]. * Input: [1,2,3,4] * Output: [24,12,8,6] * * 给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 * 来源：力扣（LeetCode） * 链接：https://leetcode-cn.com/problems/product-of-array-except-self * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 * * @Date: 2019/7/17 9:31 * @Version: 1.0 */ public class ProductExceptSelf { public int[] solution(int[] nums) { //直接对所有数据求乘积,然后每个数据遍历的时候，求除数 int[] res = new int[nums.length]; int allX = 1, zeroNum = 0; for(int i = 0; i < nums.length; ++i) { if(nums[i] != 0) { allX *= nums[i]; } else { ++zeroNum; } } //求各个位置的值 if(zeroNum <= 1) { for(int i = 0; i < res.length; ++i) { if(nums[i] == 0 && zeroNum == 1) { res[i] = allX; } else if (zeroNum == 0) { res[i] = allX / nums[i]; } } } return res; } public static void main(String[] args) { int data[] = {1,0}; ProductExceptSelf fuc = new ProductExceptSelf(); System.out.println(fuc.solution(data)); System.out.println(); } }
package y2019.Algorithm.array.medium; import java.io.*; import java.util.*; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.array.medium * @ClassName: Subsets * @Author: xiaof * @Description: TODO 78. Subsets * Given a set of distinct integers, nums, return all possible subsets (the power set). * Note: The solution set must not contain duplicate subsets. * * Input: nums = [1,2,3] * Output: * [ * [3], * [1], * [2], * [1,2,3], * [1,3], * [2,3], * [1,2], * [] * ] * * * * @Date: 2019/7/17 10:49 * @Version: 1.0 */ public class Subsets { public List<List<Integer>> solution(int[] nums) { //输出所有可能组合，因为涉及到长度的变化，这里考虑用递归 List<List<Integer>> res = new ArrayList<>(); res.add(new ArrayList<>()); //每次递归深度加一，相当于去探索，长度不能超过总长，每次递归都是前面一次的集合加上下一次的集合 //那就要对位置做标记，但是长度又是不固定的并且不重复，那么考虑用set做标记 Set mark = new HashSet(); Arrays.sort(nums); //这里还涉及一个问题，那就是可能有重复的组合，顺序不一样而已，那么为了排除掉乱序的，我们对数组拍个顺，然后每次只看后面的数据 allZhuHe(new ArrayList<>(), mark, res, 1, nums, 0); return res; } public void allZhuHe(List<Integer> curList, Set marks, List<List<Integer>> res, int len, int[] nums, int startIndex) { if(len > nums.length) { return; } //如果再合理范围内，那么我们取不在集合中的数据 // Set tempSet = new HashSet(marks); for(int i = startIndex; i < nums.length; ++i) { if(!marks.contains(nums[i])) { //如果不包含 List<Integer> tempList = new ArrayList<>(curList); tempList.add(nums[i]); res.add(tempList); marks.add(nums[i]); allZhuHe(tempList, marks, res, len + 1, nums, i); marks.remove(nums[i]); } } } // public List deepClone(List<Integer> curList) throws IOException, ClassNotFoundException { // //直接拷贝对象 // ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream(); // ObjectOutputStream objectOutputStream = new ObjectOutputStream(byteArrayOutputStream); // objectOutputStream.writeObject(curList); // // ByteArrayInputStream byteIn = new ByteArrayInputStream(byteArrayOutputStream.toByteArray()); // ObjectInputStream in = new ObjectInputStream(byteIn); // @SuppressWarnings("unchecked") // List dest = (List) in.readObject(); // return dest; // // } public static void main(String[] args) { int data[] = {1,2,3}; Subsets fuc = new Subsets(); System.out.println(fuc.solution(data)); System.out.println(); } }
第287题，这个题联系到了快慢指针，惊艳到我了
package array.medium; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.array.medium * @ClassName: FindDuplicate * @Author: xiaof * @Description: 287. Find the Duplicate Number * Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), * prove that at least one duplicate number must exist. Assume that there is only one duplicate number, * find the duplicate one. * * Input: [1,3,4,2,2] * Output: 2 * * 不能更改原数组（假设数组是只读的）。 * 只能使用额外的 O(1) 的空间。 * 时间复杂度小于 O(n2) 。 * 数组中只有一个重复的数字，但它可能不止重复出现一次。 * * @Date: 2019/7/17 11:29 2019年9月5日10:04:13 2020年4月21日10:01:47 * @Version: 1.0 */ public class FindDuplicate { public int solution(int[] nums) { //明显就是hash了，但是不能修改原数组，因为数组再1~n之间，对于这种有范围的数组，直接hash不用想了 int[] hashNum = new int[nums.length]; for(int i = 0; i < nums.length; ++i) { if(hashNum[nums[i]] == 0) { hashNum[nums[i]]++; } else { return nums[i]; } } return -1; } //因为数据范围是1~n，所以肯定是hash，但是又因为只能使用O(1)的空间 //参考：https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation. //这里用链表来做，吧数组中的每一个位置的数据当初指向下一个链表的对象 //比如：1,3,4,2,2转换成链表就是没个位置数据指向下一个链表对象 //(0,1)->(1,3)->(3,2)->(2,4)<->(4,2) public int solution2(int[] nums) { if (nums.length > 1) { //大于1个数据才可以有可能重复 int slow = nums[0]; int fast = nums[nums[0]]; //指向第二个节点位置 while (slow != fast) { //因为存在一个指向重复的节点，所以必定有环 slow = nums[slow]; //指向下一个位置 fast = nums[nums[fast]]; //移动2次 } //当我们slow和fast相遇之后，参考142. Linked List Cycle II的结论可知，从开头的位置到slow走向成环节点，和meet位置走向这个位置的距离是一样的,或者环的n倍 //这里需要计算的是-------参考 y2019.Algorithm.LinkedList.medium.DetectCycle //2*s(走了s步) = s + n*r (环链表总长) //s = n*r => //a(链表开始到环链开始节点距离) + x(链表开始循环到相遇节点距离) = n*r //a(链表开始到环链开始节点距离) + x(链表开始循环到相遇节点距离) = (n - 1)*r + r //a(链表开始到环链开始节点距离) = (n - 1)*r + r - x(链表开始循环到相遇节点距离) //a(链表开始到环链开始节点距离) = (r - x) + (n - 1) * r //a = h(相遇的节点到链表开始的节点) + (n-1) * r //因为r是环形链表的长度，所以只要走a步，环形链表的位置不论循环多久，最后回到相遇的节点，然后会向前走h步，也就是到相遇的节点位置 fast = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } return -1; } }