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; } }