ARTS 第38周

发表于

ARTS （第38周）

Algorithm 算法

二维数组中的查找

https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路1：

想着先按行进行二分查找，然后再按列进行二分查找，

结果发现是错误的。因为从行的关系里无法确定出列的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public boolean Find(int target, int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        //比最小值都小 直接结束
        if (target < array[0][0]) {
            return false;
        }
        // 二分查找
        // 在第一行找到 小于该值的最大数
        int l = 0;
        int r = array[0].length - 1;
        int m = l + ((r - l) >> 1);// 等价 l + ((r - l) / 2);
        while (l <= r) {
            if (target == array[0][m]) {
                return true;
            } else if (target < array[0][m]) {
                r = m - 1;
            } else if (target > array[0][m]) {
                if (m == array[0].length - 1 || target < array[0][m + 1]) {
                    System.out.println("break" + m);
                    r = m;
                    break;
                }
                l = m + 1;
            }
            m = l + ((r - l) >> 1);
        }
        //System.out.println("->" + r);
 
        // 行
        int c = r;
        // 在指定列 二分查找
        l = 0;
        r = array.length - 1;
        m = l + ((r - l) >> 1);
 
        while (l <= r) {
            if (target > array[m][c]) {
                l = m + 1;
            } else if (target < array[m][c]) {
                r = m - 1;
            } else {
                // (target == array[m][c])
                return true;
            }
            m = l + ((r - l) >> 1);
        }
        return false;
    }

思路2：按行进行二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 题目描述
    // 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
    public boolean Find(int target, int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        int l = 0, r = 0, m = 0;
        for (int i = 0; i < array.length; i++) {
            // 二分查找
            // 在第一行找到 小于该值的最大数
            l = 0;
            r = array[i].length - 1;
            m = l + ((r - l) >> 1);// 等价 l + ((r - l) / 2);
            while (l <= r) {
                if (target == array[i][m]) {
                    return true;
                } else if (target < array[i][m]) {
                    r = m - 1;
                } else if (target > array[i][m]) {
                    l = m + 1;
                }
                m = l + ((r - l) >> 1);
            }
        }
        return false;
    }

Review 英文文章

https://vuejs.org/v2/guide/index.html

vue的简易使用入门

Tip 技巧

1、java 的<<、 >> 、>>>位运算的掩码

If the promoted type of the left-hand operand is int, then only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.

如果左侧操作数的提升类型为int，则仅使用右侧操作数的五个最低阶位作为移位距离。就好像右边的操作数受到了一个位逻辑与运算符&（§15.22.1），掩码值为0x1f（0b11111）。因此，实际使用的移位距离始终在0到31之间（包括0到31）。

2、IEEE754标准

这是是一种浮点数表示标准
一般分为单、双精度两种
单精度是32位的二进制数，双精度是64位的二进制数
一个浮点数的组成分为三个部分
第1位是数符s s=1表示负数 s=0表示正数
第2-9位为阶码E （双精度为2-12位）
第10-32位为尾数M （双精度为13-64位）
转换大致过程如下：
将十进制数转为二进制数 用类似于科学计数法的形式表示成
V=(-1)^s（1+M）2^(E-127)（单精度）
V=(-1)^s（1+M）2^(E-1023)（双精度）
然后将每部分算出的数值按顺序排列
例如：
-0.0625=-1.0*2^(-4)
s=1，M=1-1=0,E=-4 +127=123=0111 1011 ，E（双精度）=-4 +1023=1019 =0111 1111 011
单精度:1011 1101 1000 0000 0000 0000 0000 0000
双精度:1011 1111 1011 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

https://zhidao.baidu.com/question/188228095.html用户 leeesoooleon

Share 分享

https://blog.csdn.net/u013094181/article/details/21863491 负数取余运算

https://blog.csdn.net/m0_37482190/article/details/86544398 64位 32位的系统区别