package y2019.Algorithm.array;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array

 * @ClassName: CanPlaceFlowers

 * @Author: xiaof

 * @Description: TODO 605. Can Place Flowers

 * Suppose you have a long flowerbed in which some of the plots are planted and some are not.

 * However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

 * Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty),

 * and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

 *

 * 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

 * 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

 * 来源：力扣（LeetCode）

 * 链接：https://leetcode-cn.com/problems/can-place-flowers

 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 *

 * Input: flowerbed = [1,0,0,0,1], n = 1

 * Output: True

 * @Date: 2019/7/12 8:55

 * @Version: 1.0

 */

public class CanPlaceFlowers {

    public boolean solution(int[] flowerbed, int n) {

        //判断每个花之间要有空格

        int count = 0;

        for(int i = 0; i < flowerbed.length && count < n; ++i) {

            //判断是否是空的

            if(flowerbed[i] == 0) {

                //判断左右是否间隔1一个空位

                int pre = i == 0 ? 0 : flowerbed[i - 1];

                int next = i < flowerbed.length - 1 ? flowerbed[i + 1] : 0;

                if(pre == 0 && next == 0) {

                    ++count;

                    flowerbed[i] = 1;

                }

            }

        }

        if(count == n) {

            return true;

        } else {

            return false;

        }

    }

    public static void main(String args[]) {

        String as[] = {"bella","label","roller"};

        int[] A = {1,0,0,0,1};

        int k = 1;

        CanPlaceFlowers fuc = new CanPlaceFlowers();

        System.out.println(fuc.solution(A, k));

    }

}

package y2019.Algorithm.array;

import java.util.HashMap;

import java.util.Map;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array

 * @ClassName: FindPairs

 * @Author: xiaof

 * @Description: 532. K-diff Pairs in an Array

 * Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array.

 * Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

 *

 * Input: [3, 1, 4, 1, 5], k = 2

 * Output: 2

 * Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).

 * Although we have two 1s in the input, we should only return the number of unique pairs.

 *

 * 给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j),

 * 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

 *

 * 来源：力扣（LeetCode）

 * 链接：https://leetcode-cn.com/problems/k-diff-pairs-in-an-array

 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 *

 * @Date: 2019/7/12 9:33

 * @Version: 1.0

 */

public class FindPairs {

    public int solution(int[] nums, int k) {

        if(k < 0) {

            return 0;

        }

        //这题用类似hash的方式

        Map<Integer, Integer> numMap = new HashMap();

        for(int t : nums) {

            if(!numMap.containsKey(t)) {

                numMap.put(t, 0);

            }

            //出现次数

            numMap.put(t, numMap.get(t) + 1);

        }

        //遍历查询缺失的一般

        int count = 0;

        //根据map中的数据进行判断，并且进行了去重

        for(Map.Entry entry : numMap.entrySet()) {

            //判断map中是否包含差值的数据，如果包含，还要避免是同同一对数据,剩余的个数要不能为0

            if(k == 0) {

                //特殊处理K为0的情况

                if((int) entry.getValue() >= 2) {

                    ++count;

                }

            } else if(numMap.containsKey((int) entry.getKey() + k)) {//因为是递增的，所以可以吧相同对排除掉

                ++count;

            }

        }

        return count;

    }

    public static void main(String args[]) {

        int[] A = {3,1,4,1,5};

        int[] B = {1,2,3,4,5};

        int k = -1;

        FindPairs fuc = new FindPairs();

        System.out.println(fuc.solution(A, k));

    }

}