【LEETCODE】54、数组分类，简单级别，题目：605、532

小鱼儿 2021-09-30 02:18 207阅读 0赞

数组类，简单级别完结。。。。

不容易啊，基本都是靠百度答案。。。。

希望做过之后后面可以自己复习，自己学会这个解法

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

转载于:https://www.cnblogs.com/cutter-point/p/11174484.html