栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

搜索算法、回溯算法、位运算、二分查找 6/9 46-50

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

搜索算法、回溯算法、位运算、二分查找 6/9 46-50

1.有效三角形的个数( LeetCode 611 )

方法一:暴力解法 888ms

   class Solution {
        public int triangleNumber(int[] nums) {
            int ans = 0;
            Arrays.sort(nums);
            
            for (int i = 0; i < nums.length; i++) {
                for (int k = nums.length - 1; k - i > 1 ; k--) {
                    for (int j = i + 1; j < k; j++) {
                        if (nums[i] + nums[j] > nums[k]){
                            ans += k - j;
                            break;
                        }
                    }
                }
            }
            return ans;
        }
    }

方法二:排序 + 二分查找 288ms

class Solution {
    public int triangleNumber(int[] nums) {
            int ans = 0;
            Arrays.sort(nums);
            
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    int left = j + 1;
                    int right = nums.length - 1;
                    int k = j;
                    //找到最大的k满足条件 i + j > k
                    while (left <= right){
                        int mid = (left + right) / 2;
                        if (nums[i] + nums[j] > nums[mid]){
                            k = mid;
                            left = mid + 1;
                        }else {
                            right = mid - 1;                            
                        }
                    }
                    ans += k - j;
                }
            }
            return ans;
        }
}

方法三:排序 + 双指针
在方法二的基础上改进

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int k = i;
            for (int j = i + 1; j < n; ++j) {
                while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
                    ++k;
                }
                //k - j可能小于0,ans要加一个正数
                ans += Math.max(k - j, 0);
            }
        }
        return ans;
    }
}
2.剑指 Offer 53 – II. 0~n-1中缺失的数字 ⭐⭐⭐⭐⭐

二分法
排序数组中的搜索问题,首先想到 二分法 解决

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

3.剑指 Offer 53 – I. 在排序数组中查找数字 I

普通的二分查找
查找等于目标值的所有位置

class Solution {
    public int search(int[] nums, int target) {
            int l = 0;
            int r = nums.length - 1;
            int ans = 0;

            while (l <= r){
                int mid = (l + r) / 2;
                if (target > nums[mid]){
                    l = mid + 1;
                }else if (target < nums[mid]){
                    r = mid - 1;
                }else {
                    ans++;
                    for (int i = mid - 1; i >= 0; i--) {
                        if (nums[i] == target)ans++;
                        else break;
                    }
                    for (int i = mid + 1; i < nums.length; i++) {
                        if (nums[i] == target)ans++;
                        else break;
                    }
                    break;
                }
            }

            return ans;
        }
}
4.剑指 Offer 51. 数组中的逆序对

二分 + 分治思想

    class Solution {
        int ans = 0;
        public int reversePairs(int[] nums) {
            split(nums,0,nums.length - 1);
            return ans;
        }
        //分
        public void split(int[] nums,int l,int r){
            if (l >= r)return;
            int mid = (l + r) / 2;
            split(nums,l,mid);
            split(nums,mid + 1,r);
            merge(nums,l,mid,r);
        }
        //合
        private void merge(int[] nums, int l, int mid, int r) {
            int left = l;
            int right = mid + 1;
            List list = new ArrayList<>();
            while (left <= mid && right <= r){
                if (nums[right] < nums[left]){
                    list.add(nums[right]);
                    right++;
                }else {
                    ans += right - mid - 1;
                    list.add(nums[left]);
                    left++;
                }
            }
            while (left <= mid){
                ans += right - mid - 1;
                list.add(nums[left]);
                left++;
            }
            while (right <= r){
                list.add(nums[right]);
                right++;
            }
            for (int i = 0; i < list.size(); i++) {
                nums[l++] = list.get(i);
            }
        }
    }
5.寻找峰值( LeetCode 162 )

方法一:寻找最大值
由于题目保证了 nums[i] ≠ [i+1] ,那…么数组 nums中最大值两侧的元素一定严格小于最大值本身。因此,最大值所在的位置就是一个可行的峰值位置。

class Solution {
    public int findPeakElement(int[] nums) {
        int idx = 0;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > nums[idx]) {
                idx = i;
            }
        }
        return idx;
    }
}

方法二:迭代爬坡
我们总是往高处走总能找到山峰

class Solution {
        public int findPeakElement(int[] nums) {
            int idx = 0;
            while (!(compare(nums,idx - 1,idx) < 0 && compare(nums,idx,idx + 1) > 0)){
                //如果右侧高则向右侧移动
                if(compare(nums,idx,idx + 1) < 0){
                    idx++;
                }else {//否则向左侧移动
                    idx--;
                }
            }
            return idx;
        }
        //比较nums中两个位置的大小
        public int compare(int[] nums,int l,int r){
            if (l == -1)return -1;
            if (r == nums.length)return 1;
            return nums[l] - nums[r];
        }
    }

方法三:方法二的二分实现
在上述算法中,如果我们固定选取 i 为 [l,r] 的中点,那么每次可行的下标范围会减少一半,成为一个类似二分查找的方法,时间复杂度为O(logn)。

class Solution {
        public int findPeakElement(int[] nums) {
            int idx = 0;
            int left = 0;
            int right = nums.length - 1;
            while (left <= right){
                int mid = (left + right) / 2;
                if (compare(nums,mid - 1,mid) < 0 && compare(nums,mid,mid + 1) > 0){
                    idx = mid;
                    break;
                }
                if(compare(nums,mid,mid + 1) < 0){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
            return idx;
        }
        public int compare(int[] nums,int l,int r){
            if (l == -1)return -1;
            if (r == nums.length)return 1;
            return nums[l] - nums[r];
        }
    }
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/962630.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号