七夕了,男朋友说他想学学算法~

最近公共祖先

https://www.nowcoder.com/questionTerminal/70e00e490b454006976c1fdf47f155d9

---

---

高端解法：

本来父亲节点和孩子节点的关系为 : parent = (child-1)/2 ->根节点的编号从0开始

由于现在根节点的编号从1开始,所以父亲节点和孩子节点的关系为:parent = child/2

---

我们只要让大的编号的那个孩子除2 (到达父亲位置）然后和另一个进行比较即可,当二者相等时,就是最近的公共祖先

class LCA {
public:
    int getLCA(int a, int b) {
        // write code here
        //结束条件:二者编号相同
        while(a!=b)
        {
            //大的编号的那个孩子除2 
            a>b?a/=2:b/=2;
        }
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

---

求最大连续bit数

https://www.nowcoder.com/questionTerminal/4b1658fd8ffb4217bc3b7e85a38cfaf2?commentTags=Java

---

方法1:求得n的每一个比特位的情况,放到容器中,然后遍历容器看有多少个比特位1是连续的

#include
#include
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> v;//存放n的32位比特位
	v.resize(32);
	for (int i = 0; i < 32; i++)
	{
		//n的第i位是1还是0
		if (((1 << i) & n) != 0)
		{
			v[i] = 1;
		}
	}
	int max = 0;
	//遍历查找多少个1连续
	for (int i = 0; i < 32; i++)
	{
		//注意:tmp的初始化要放在for循环内部
		//如果放在外部每一次进入while循环就是累加
		//而我们需要的每次进入whil循环是从0开始
		int tmp = 0;
		//看有多少个连续的bit是1
		while (i < 32 && v[i] == 1)
		{
			tmp++;
			i++;
		}
		//更新最大的连续的bit数
		max = max > tmp ? max : tmp	;
	}
	cout << max << endl;
	return 0;
}
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

---

不需要保存到容器的方法

#include
#include
using namespace std;
int main()
{
    int n;
    cin>>n;
    int count = 0;
    int max_count = 0;
    for(int i = 0;i<32;i++)
    {
        //判断n的每一个比特位是1还是0
        if(n&1 == 1)
        {
            count++;
        }
        else
        {
            max_count = max_count>count?max_count:count;//更新max_count
            count = 0;//注意:count要重新置0
        }
        n>>=1;
    }
    //注意:最后一轮,max_count和count并没有比较,所以出了for循环之后,还需要进行比较
    max_count = max_count > count ? max_count : count;
    cout<<max_count<<endl;
    return 0;
}
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

注意:如果n为负数,由于是有符号右移 -> 正数:补0,负数:补1,

所以,如果n为负数,会陷入死循环

---

方法2:

通过/2 %2的方法

#include
#include
using namespace std;
int main()
{
    int n;
    cin>>n;
    int count = 0;
    int max_count = 0;
    while(n)
    {
        if(n%2 == 1)
        {
            count++;
        }
        else
        {
            //更新max_count的值,然后把count置0
            max_count = max_count>count?max_count:count;
            count = 0;
        }
        n/=2;
    }
    //注意:最后一轮,max_count和count并没有比较,所以出了while循环之后,还需要进行比较
    max_count = max_count > count ? max_count : count;
    cout<<max_count<<endl;
    return 0;
}
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

---

如果不想在跳出循环还比较:可以把更新max_count的情况写在if内

while(n)
{
    if(n%2 == 1)	//相当于n&1
    {
        count++;
        //更新max_count的值
        max_count = max_count>count?max_count:count;
    }
    else
    {
        count = 0;
    }
    n/=2;	//相当于:n>>=1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

注意:上面的情况,并不针对负数,牛客网的测试用例不完全！

---

针对负数也能满足的情况:

让n带符号右移,将n强转为(unsigned int 类型)

#include
#include
using namespace std;
int main()
{
    int n;
    cin>>n;
    int count = 0;
    int max_count = 0;
    for(int i = 0;i<32;i++)
    {
        //判断n的每一个比特位
        if(n&1)
        {
            count++;
        }
        else
        {
            max_count = max_count>count?max_count:count;
            count = 0;
        }
        n = (unsigned int)n>>1;//防止n为负数
    }
    //注意:最后一轮,max_count和count并没有比较,所以出了for循环之后,还需要进行比较
    max_count = max_count > count ? max_count : count;
    cout<<max_count<<endl;
    return 0;
}
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

---

或者不是右移num的每一位进行判断,而是将1进行左移判断

因为对num右移,当num位负数可能存在死循环情况

#include
using namespace std;
int main()
{
    int num;
    //多组输入
    while(cin>>num)
    {
        int count = 0;
        int max_count = 0;
        for(int i = 0;i<32;i++)
        {
            //判断num的每一位是不是1,用1左移进行判断!
            if(num&(1<<i))
            {
                count++;
                max_count = max(max_count,count);//更新max_count
            }
            else
            {
                count = 0;    
            }
        }
        cout<<max_count<<endl;
    }
    return 0;
}
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

---