文章目录

• • 240.搜索二维矩阵II
  • 496.下一个更大元素
  • 869.重新排列得到2的幂

240.搜索二维矩阵II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

思路：由于每行都是有序的，所以可以对每行进行二分查找

import java.util.Arrays;

public class Solution240 {
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int i = 0;i < matrix.length;i++){
            int index = Arrays.binarySearch(matrix[i],target);
            if(index >= 0){
                return true;
            }
        }
        return false;
    }
}

496.下一个更大元素

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

思路：暴力枚举

public class Solution496 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int []nextGreaterIndex = new int[nums1.length];
        for(int i = 0;i < nums1.length;i++){
            int j = 0;
            while (j < nums2.length && nums1[i] != nums2[j]){
                j++;
            }
            nextGreaterIndex[i] = -1;
            for(j = j + 1;j < nums2.length;j++){
                if(nums1[i] < nums2[j]){
                    nextGreaterIndex[i] = nums2[j];
                    break;
                }
            }
        }
        return nextGreaterIndex;
    }
}

869.重新排列得到2的幂

给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

import java.util.ArrayList;

public class Solution869 {
    //先进行全排列获得n的所有可能，但排列后n的位数不能变，否则舍弃
    public boolean reorderedPowerOf2(int n) {
        //将n分割成个位数
        int []arr = split(n);
        //进行排列出所有可能
        ArrayList<Integer> arrList = new ArrayList<>(); //用来存储结果
        int len = arr.length;
        boolean []isUsed = new boolean[len];
        DFS(len,arr,arrList,isUsed,new StringBuilder());
        for(int i = arrList.size() - 1;i >= 0;i--){
            //判断这个数是否是2的幂
            if(String.valueOf(arrList.get(i)).length() != len){
                continue;       //如果存在前导零则长度不会等于源长度，舍弃
            }
            if(judge(arrList.get(i))){
                return true;
            }
        }
        return false;

    }

    boolean judge(int n){
        while (n != 1){
            if(n % 2 == 0){
                n = n >> 1;
            }else {
                return false;
            }
        }
        return true;
    }

    /**
     *
     * @param len   表示每个元素的长度
     * @param arr   源数组
     * @param arrList  存储数组
     * @param isUsed    标记数组
     */
    private void DFS(int len, int []arr, ArrayList<Integer> arrList, boolean []isUsed,StringBuilder sb){

        if(len <= 0){
            arrList.add(Integer.parseInt(sb.toString()));
            return;
        }

        for(int i = 0;i < arr.length;i++){
            if(isUsed[i]){  //如果已经被使用则跳过
                continue;
            }
            sb.append(arr[i]);
            isUsed[i] = true;
            DFS(len - 1,arr,arrList,isUsed,sb);
            sb.deleteCharAt(sb.length() - 1);
            isUsed[i] = false;
        }

    }

    private int []split(int n){
        int []arr = new int[String.valueOf(n).length()];
        int i = 0;
        while (n != 0){
            arr[i++] = n % 10;
            n = n / 10;
        }
        return arr;
    }
}