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

 

package y2019.Algorithm.array.medium;

/**
 * @ProjectName: cutter-point
 * @Package: y2019.Algorithm.array.medium
 * @ClassName: FindDuplicate
 * @Author: xiaof
 * @Description: TODO 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
 * @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;

    }

}