Braincao's Blog

心得目录

编号	题目
1	二分查找
2	矩阵原地转置
3	通过位运算符屏蔽其他位

算法心得

1.二分查找

• 有序数组考虑二分

• 二维矩阵中路径查找问题通常用回溯法。回溯法非常适合由多个步骤组成的问题，每个步骤都有多个选项。它从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案。

• 对int型整数，注意MIN越界问题

    MIN_VALUE取反还是MIN_VALUE
    MAX_VALUE+1=MIN_VALUE
    [−2^31,  2^31 − 1]

//二分查找
boolean find(int[] nums, int key){
    int left = 0;
    int right = nums.length-1;
    // 这里必须是<=
    while(left<=right){
        int mid = (left + right) / 2;
        if(key==nums[mid]){
            return true;
        }
        if(key<nums[mid]){
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }

    return false;
}

2.矩阵原地转置

#include <iostream>
using namespace std;

//二维数组原地转置   注意是原地转置
void zhuanzhi(int a[4][4])
{
    for(int i=0;i<4;i++)
    {
        for(int j=i+1;j<4;j++)
        {
            //交换两个数
            swap(a[i][j],a[j][i]);
        }
    }
}

int main()
{
    int test[4][4]={
        {1,2,3,4},
        {1,2,3,4},
        {5,6,7,8},
        {0,0,0,0}
    };
    zhuanzhi(test);

    //输出转置后的数组
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            cout<<test[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

3.通过位运算符屏蔽其他位

通过位运算符(&|~^)把其他位屏蔽掉

int result = (4&0b100)/0b100;
System.out.println(result);

result为1或0代表：数字保留下来的其中某一位，把其他位都屏蔽掉了

另外>>、<<运算符代表右移、左移。当需要建立位模式屏蔽某些位时，使用这两个运算符十分方便

int n = 0b1000; //n==8
int result = (n & (1<<3))>>3; 
System.out.println(result); //result==1

---

欢迎转载，欢迎错误指正与技术交流，欢迎交友谈心