LeetCode刷题笔记_02

algorithm
算法
发布日期:   2022-05-11
更新日期:   2022-05-11
文章字数:   2k
阅读时长:   9 分
阅读次数:  

算法实现

package xyz.standalon.opt;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-11 16:00
 * @desc:  一个数组中出现了奇数次,其他数都出现了偶数次,怎么找到打印这个数字？
 *
 * 提示：
 *  1. hashmap 记录出现的次数,找打出现奇数次的数字
 *  2. 异或运算的使用
 *      2.1 一个数字和本身做异或运算结果为0
 *      2.2 一个数字和0 做异或运算等于本身
 */
public class ExclusiveOR {
    //一个数字在数组中出现次数为奇数次
    public static int printOddTimesNum1(int[] nums){
        //定义一个变量eor,和数组中每个元素做异或运算
        int eor = 0;
        for (int i = 0;i < nums.length;i++){
            //做异或运算并赋值给eor
            eor ^= nums[i];
        }
        return eor;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,1,3,4,5,4,5,6};
        int ans = printOddTimesNum1(nums);
        System.out.println(ans);
    }

}

package xyz.standalon.opt;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-11 22:09
 * @desc:
 */
public class SwapTwoNumber {
    public static void swap(int[] arr,int i,int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void main(String[] args) {
        int[] arr = {10,-56,2};
        System.out.println(arr[0]);
        System.out.println(arr[1]);
        swap(arr,0,1);
        System.out.println(arr[0]);
        System.out.println(arr[1]);
    }
}
package xyz.standalon.opt;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-11 16:40
 * @desc:   异或运算应用2.0
 *      1.怎么将一个int数的最右侧的1提取出来
 *      2.一个数组中有两种数出现奇数次,其他数字都出现了偶数次,怎么找到并打印这两种数
 */
public class UsedExclusiveOR2 {

    //怎么将一个int数的最右侧的1提取出来
    //注意次数使用的运算符号为 & 符号
    public static int getRightOne(int key){
        //方式一
        int rightOne = key & (- key);
        //方式二
        int rightOne2 = key & ((~key) + 1);
        return rightOne;
    }
    public static int[] printOddTimesNum2(int[] nums){

        //定义一个变量eor,获取两个奇数字的异或结果并保存到eor中
        int eor = 0;
        for (int i = 0;i < nums.length;i++){
            //做异或运算并赋值给eor
            eor ^= nums[i];
        }
        //循环执行后,此时eor等于 a ^ b的结果
        //提取eor数字二进制中最右侧的1
        int rightOne = eor & (-eor);
        // 求出数组中的元素与rightOne的右侧1的位置相同的数字,即右侧位置为1的所有数字
        // 定义一个变量用于保存 onlyone和每个右侧位置为1的数字异或运算后的结果
        int onlyOne = 0; //eor'
        for (int i = 0;i < nums.length;i++){
            if ((nums[i] & rightOne) != 0){
                onlyOne ^= nums[i];
            }
        }
        //此时onlyOne 的结果等于两数之一的数字a
        //求出另外一个数字b : b = eor ^ eor'
        int second = eor ^ onlyOne;
        return new int[]{onlyOne,second};
    }

    public static void main(String[] args) {
        int[] nums = {1,1,2,2,2,4,4,4,4,10,10,10};
       int[] Numbers =  printOddTimesNum2(nums);
       for (int i = 0 ; i < Numbers.length;i++){
           System.out.println(Numbers[i]);
       }

    }
}
package xyz.standalon.opt;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-11 19:16
 * @desc: 一个数组中有一种数字出现K次, 其他数字都出现M次,`M > 1`,`K < M`.找到出现K次的数字.要求: 额外空间复杂度为`O(1)`,时间复杂度为`O(n)`
 * 分析：
 * 1.构建一个int整型数组t,长度为32位.
 * 2.将t[i]记录 i位置出现1的次数,t[i]的值暂时记作count
 * 2.1 如果 m % count == 0 当前位置只会存在出现m次数字,反之该位置存在出现k次的数字
 * 2.2 如果 m % count != 0 当前位置有出现k次的数字
 * 3.
 */
public class UsedExclusiveOR3 {
    //常规写法 额外空间复杂度为O(n) 不符合题意O(1)的要求
    public static int test(int[] arr, int k, int m) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        int ans = 0;
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                ans = num;
                break;
            }
        }
        return ans;
    }

    public static HashMap<Integer, Integer> map = new HashMap<>();

    public static int getOnlyKTimesNum(int[] arr, int k, int m) {
        if (map.size() == 0) {
            createMap(map);
        }
        int[] t = new int[32];
        for (int num : arr) {
            while (num != 0) {
                int rightOne = num & (-num);
                t[map.get(rightOne)]++;
                num ^= rightOne;
            }
        }
        int ans = 0;

        for (int i = 0; i < 32; i++) {
            if (t[i] % m != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }

    private static void createMap(HashMap<Integer, Integer> map) {
        int value = 1;
        for (int i = 0; i < 32; i++) {
            map.put(value, i);
            value <<= 1;
        }
    }

    //优化后的写法
    public static int km(int[] arr, int k, int m) {
        int[] support = new int[32];
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                support[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < support.length; i++) {
            if (support[i] % m != 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int kinds = 5;
        int range = 100;
        int testTime = 100000;
        int max = 9;
        System.out.println("test is running ...");
        for (int i = 0; i < testTime;i++) {
            int a = (int)(Math.random() * max) + 1; // 1 ~ 9
            int b = (int)(Math.random() * max) + 1;
            int k = Math.min(a,b);
            int m = Math.max(a,b);
            // 严格控制 k < m
            if (k == m) {
                m++;
            }
            //构建数组
            int[] arr = randomArray(kinds,range,k,m);
            int ans1 = test(arr,k,m);
            int ans2 = getOnlyKTimesNum(arr,k,m);
            int ans3 = km(arr,k,m);
            if (ans1 != ans2 || ans1 != ans3){
                System.out.println("ans1: " + ans1);
                System.out.println("ans2: " + ans2);
                System.out.println("ans3: " + ans3);
                System.out.println("Occured a mistake in you program!");
            }
        }
        System.out.println("test is over ...");
    }
    //对数器
    private static int[] randomArray(int kinds, int range, int k, int m) {
        int appearKTimeNum =  randomNumber(range);
        // 出现k次的数字
        int times = k;
        // 数字种类最少为两种
        int numKinds = (int)(Math.random() * kinds) + 2; // 其他数字种类为[2,kinds + 1]
        //数组长度为出现k次的数字个数 + 出现m次数字的个数即：1 * k + (numKinds - 1) * m
        int[] arr = new int[times + (numKinds - 1) * m];
        int index = 0;
        for (; index < times;index++){
            arr[index] = appearKTimeNum;
        }
        HashSet<Integer> set = new HashSet<>();
        set.add(appearKTimeNum);
        // 出现k次的数字已经生成,接下来生成出现m次的数字
        numKinds--;
        while (numKinds != 0){
            int currentNum = 0;
            do {
                currentNum = randomNumber(range);
            }while (set.contains(currentNum));
            set.add(currentNum);
            numKinds--;
            for (int i = 0; i < m ;i++){
                arr[index++] = currentNum;
            }
        }
        //数组创建和元素添加完成
        //给数组元素重新排序
        for (int i = 0;i < arr.length;i++){
            // i位置的数,和j位置元素进行交换
            int j =(int) (Math.random() * arr.length); // j的取值范围是 [0,n - 1]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        return arr;
    }

    private static int randomNumber(int range) {
        return (int) (Math.random() * (range + 1))
                - (int)(Math.random() * (range + 1));
    }
}

异或运算在算法中的应用

运算符介绍

  • 异或运算
    • 无进位相加
    • 相同为0,不同为1
    • 满足交换律和结合律
    • 任何数和自身做异或运算,结果为0
    • 任何数与0做异或运算还是等于数字本身
    • 应用
      • 两数交换
a = a ^ b;
b = a ^ b;
a = a ^ b;
  • 应用异或运算

  1. 一个数组中出现了奇数次,其他数都出现了偶数次,怎么找到打印这个数字？

  2. 怎么将一个int数的最右侧的1提取出来

  3. 一个数组中有两种数出现奇数次,其他数字都出现了偶数次,怎么找到并打印这两种数

  4. 一个数组中有一种数字出现K次,其他数字都出现M次,M > 1,K < M.找到出现K次的数字.要求: 额外空间复杂度为O(1),时间复杂度为O(n)

运算符

操作符 描述 示例
＆ 如果相对应位都是1，则结果为1，否则为0 （A＆B），得到12，即0000 1100
| 如果相对应位都是 0，则结果为 0，否则为 1 （A | B）得到61，即 0011 1101
^ 如果相对应位值相同，则结果为0，否则为1 （A ^ B）得到49，即 0011 0001
〜 按位取反运算符翻转操作数的每一位，即0变成1，1变成0。 （〜A）得到-61，即1100 0011
<< 按位左移运算符。左操作数按位左移右操作数指定的位数。 A << 2得到240，即 1111 0000
>> 按位右移运算符。左操作数按位右移右操作数指定的位数。 A >> 2得到15即 1111
>>> 按位右移补零操作符。左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。 A>>>2得到15即0000 1111
文章作者: rudy
文章链接: https://FacturyValue.github.io/2022/05/11/algorithm/LeetCode%E5%88%B7%E9%A2%98%E7%AC%94%E8%AE%B0_02/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 rudy !
algorithm
赏
  目录