算法基础八

2023-12-13 17:43:54

Pow(x,n)

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。

示例 1:
输入:x = 2.00000, n = 10 输出:1024.00000
示例 2:
输入:x = 2.10000, n = 3 输出:9.26100

解题思路:用递归的方式,将n 二分下去,注意n的正负和奇偶。

 public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1] 输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23

解题思路:动态规划

 public int maxSubArray(int[] nums) {
        int pre = 0;
        int maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

跳跃游戏

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。

示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ,所以永远不可能到达最后一个下标。


public boolean canJump(int[] nums) {
        int len = nums.length;
        int rightmost = 0;
        for(int i = 0; i < len; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= len - 1) {
                    return true;
                }
            }
        }
        return false;
    }

合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]] 输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路:先按照区间起点排序,然后从起点小的开始遍历,依次合并每个有重叠的区间。

  public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

插入区间

给你一个 无重叠的 ,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 1:
输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]
示例 2:
输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
示例 3:
输入:intervals = [], newInterval = [5,7]
输出:[[5,7]]
示例 4:
输入:intervals = [[1,5]], newInterval = [2,3]
输出:[[1,5]]
示例 5:
输入:intervals = [[1,5]], newInterval = [2,7]
输出:[[1,7]]

解题思路:可以分三段处理,先添加原来的区间,即在给的 newInterval 之前的区间,然后添加 newInterval ,这里可能需要合并多个区间。最后把剩下的部分添加到最终结果里。


 public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;

        List<int[]> ansLsit = new ArrayList<>();

        for(int[] interval : intervals) {
            if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if(!placed) {
                    ansLsit.add(new int[]{left, right});
                    placed = true;
                }
                ansLsit.add(interval);
            } else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ansLsit.add(interval);
            } else {
                // 与插入区间有交集,计算他们的并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }

        if (!placed) {
            ansLsit.add(new int[]{left, right});
        }

        int[][] ans = new int[ansLsit.size()][2];
        for (int i = 0; i < ansLsit.size(); ++i) {
            ans[i] = ansLsit.get(i);
        }

        return ans;
    }

文章来源:https://blog.csdn.net/javaJasonjava/article/details/134893523
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。