leetcode 剑指offer刷题归类之四经典算法题

约瑟夫环问题

/**
 * https://blog.csdn.net/weixin_38214171/article/details/80352921
 */

public class JosephCircle {


    public static void main(String[] args) {
        System.out.println(joseph(5,3));
        System.out.println(LastRemaining_Solution(5,3));
    }

    public static int joseph(int count,int doom){

        int alive = count; //幸存人数
        int number = 0;   //计数，number==dom时，淘汰这个人
        int index = 0;    //下标，为总人数-1

        //0表示这个人在约瑟夫环内，1表示这个人在约瑟夫环外
        int[] circle = new int[count];
        //只要幸存人数>0,则一直进行
        while (alive>0){
            number += 1-circle[index];
            if(number == doom){   //当number==dom时，就要淘汰这个人
                /**
                 * 淘汰一个人分四步
                 * 1.输出这个人的位置
                 * 2.把这个人的状态从圈内0，改为状态1
                 * 3.幸存人数alive--；
                 * 4.计数number归零
                 */
                System.out.println(index+1);
                circle[index] = 1;
                alive--;
                number = 0;
            }

            //与总人数count取余，则可以使index在0~count-1之间 一直循环，达到循环数组的目的
            index = (index+1)%count;
            System.out.println("index="+index);
        }

        if(index == 0){
            return count;
        }
        return index;
    }


    /**
     * 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。
     * HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:
     * 首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。
     * 每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,
     * 从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,
     * 可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。
     * 请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
     * @param n   小朋友的个数
     * @param m    报数
     * @return
     */
    public static int LastRemaining_Solution(int n, int m) {
        int alive = n;

        int[] help = new int[n];

        int index = 0;

        int cur = -1;

        while (alive>0){

            cur+= 1-help[index];

            if(cur == m-1){

                help[index] = 1;
                alive--;
                cur = -1;

            }
            index = (index+1)%n;

        }
        if(index == 0){
            return n-1;
        }
        return index-1;
    }
}

寻找第k小的数

1.用大根堆此方法时间复杂度为O(N*logk)，因为二叉堆的插入和删除操作都是logk的时间复杂度。不详细说明

2.借助快排的思想

/**
 * 时间复杂度为O(n)
 * 复杂度：平均情况下，遍历一次数组找到哨兵是n，下一次就是n/2，最后到1，中间最多需要k次（k=lg2n）
 * 等比数列求和：n+n/2+n/4+n/8+…+1 = 2n
 */

public class FindkthInArray {

    public static void main(String[] args) {
        int[] array =  {92, 5, 88, 13, 80,7};
        System.out.println(findKthLargest(array,5));
    }

    public static int findKthLargest(int[] nums,int k){
        return findK(nums,k,0,nums.length-1);
    }

    private static int findK(int[] nums, int k, int start, int end) {

        int low = start;
        int high = end;
        int key = nums[low];
        while (low<high){

            while (low<high&&nums[high]>=key){
                high --;
            }
            nums[low] = nums[high];
            while (low<high &&nums[low]<=key){
                low++;
            }
            nums[high] = nums[low];
        }

        nums[low] = key;
        if(low == k-1){
            return key;
        }else if(low>k-1){
            return findK(nums, k, start, low-1);
        }else {
            return findK(nums, k, low+1, end);
        }

    }

}

2sum 3sum问题

2sum问题比较简单。不再赘述，直接借用set数组能解决

3sum问题有两种思路。

思路一：先排序。然后转化为先固定a。排序好的b+c=0的问题。b的坐标从a的坐标+1开始，c从最右边开始。b和c相中家夹逼。

时间复杂度。排序O(NlgN),后面的过程为O(n^2).所以总的时间复杂度为O(n^2)

public class Sum3 {

    public static void main(String[] args) {

        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(nums));

    }

    public static List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length<3){
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2;) {
            int j = i+1;
            int k = nums.length-1;
            while (j<k){
                if(nums[j]+nums[k]+nums[i] == 0){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    result.add(list);
                    j++;
                    k--;
                    // 从左向右找第一个与之前处理的数不同的数的下标,去除重复元素
                    while (j<k&&nums[j]==nums[j-1]){
                        j++;
                    }
                    // 从右向左找第一个与之前处理的数不同的数的下标
                    while (j<k&&nums[k]==nums[k+1]){
                        k--;

                    }

                }else {
                    if(nums[j]+nums[k]+nums[i] < 0){
                        j++;
                        // 从左向右找第一个与之前处理的数不同的数的下标
                        while (j<k&&nums[j]==nums[j-1]){
                            j++;
                        }
                    }else {
                        k--;
                        // 从右向左找第一个与之前处理的数不同的数的下标
                        while (j<k&&nums[k]==nums[k+1]){
                            k--;

                        }
                    }

                }

            }
            // 指向下一个要处理的数
            i++;
            // 从左向右找第一个与之前处理的数不同的数的下标
            while (i < nums.length - 2 && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return result;
    }
}

数组中超过一半或者超过1/3的数

 /**
     * 超过一半
     *
     * @param nums
     * @return
     */
    public static int moreThanHalf(int[] nums) {
        int a = nums[0];
        int cnta = 0;
        for (int num : nums) {
            //如果是a的话，计数+1
            if (num == a) {
                cnta++;
                continue;
            }
            //如果不是a，且计数不为0，将其赋值给a
            if (cnta == 0) {
                a = num;
                cnta = 1;
                continue;
            }
            //如果不是a，且a的计数不为0，那么就都删除，表现为a的数量减1
            cnta--;
        }
        cnta = 0;

        for (int num : nums) {
            if (num == a) {
                cnta++;
            }
        }
        if (cnta <= nums.length / 2) {
            return 0;
        }

        return a;
    }


    /**
     * 超过1/3
     *
     * @param nums
     * @return
     */

    public static List<Integer> majorityElement(int[] nums) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        int a = nums[0];
        int cnta = 0;
        int b = nums[0];
        int cntb = 0;
        for (int num : nums) {
            //num = a或者num = b，计数+1
            if (num == a) {
                cnta++;
                continue;
            }
            if (num == b) {
                cntb++;
                continue;
            }
            //如果既不是a，也不是b，a或者b的个数为0，那么将这个值付给a或者b
            if (cnta == 0) {
                a = num;
                cnta = 1;
                continue;
            }
            if (cntb == 0) {
                b = num;
                cntb = 1;
                continue;

            }
            //有三个不一样的数就将他们都删除
            cnta--;
            cntb--;
        }

        for (int num : nums) {
            if (num == a) {
                cnta++;
            } else {
                if (num == b) {
                    cntb++;
                }
            }
        }
        if (cnta > nums.length / 3) {
            ans.add(a);
        }
        if (cntb > nums.length / 3) {
            ans.add(b);
        }
        return ans;

    }

leetcode 剑指offer刷题归类之 四 经典算法题

约瑟夫环问题

寻找第k小的数

2sum 3sum问题

数组中超过一半或者超过1/3的数

leetcode 剑指offer刷题归类之四经典算法题