文档章节

牛客网刷题笔记(四)在线编程

o
 osc_n6euf5h6
发布于 2019/03/19 23:22
字数 1141
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目一:整数转化

题目描述:

编写一个函数,确定需要改变几个位,才能将整数A转变成整数B。

给定两个整数int A,int B。请返回需要改变的数位个数。

解题思路:

用异或,相同为0,不同为1;

程序代码:

class Transform {
public:
   int calcCost(int A, int B) {
       // write code here
       int amount = A^B;
       int count = 0;
       while(amount){
           count ++;
           amount = amount & (amount - 1);
      }
       return count++;
  }
};

题目二:奇偶位交换

题目描述:

请编写程序交换一个数的二进制的奇数位和偶数位。(使用越少的指令越好)

给定一个int x,请返回交换后的数int。

解题思路:

用0xAAAAAAAA与x相与求的奇数位上数字(偶数位上数字为0)

用0x 55555555 与x相与求的偶数位上数字(奇数位上数字为0)

oddVal右移一位 even左移一位 。

程序代码:

class Exchange {
public:
   int exchangeOddEven(int x) {
       // write code here
       int odd = x & (0x55555555);
       int even = x & (0xaaaaaaaa);
       return (odd << 1) | ((even >> 1)&0x7fffffff);// 无符号右移,高位补0
  }
};

 

题目三:碰撞的蚂蚁

题目描述:

在n个顶点的多边形上有n只蚂蚁,这些蚂蚁同时开始沿着多边形的边爬行,请求出这些蚂蚁相撞的概率。(这里的相撞是指存在任意两只蚂蚁会相撞)

给定一个int n(3<=n<=10000),代表n边形和n只蚂蚁,请返回一个double,为相撞的概率。

解题思路:

考虑不相撞的概率,只有当所有的蚂蚁都朝一个方向(顺时针或者逆时针)爬行时才不会相撞,所以不相撞的概率为:2/2^n.

程序代码:

class Ants {
public:
   double antsCollision(int n) {
       // write code here
       double rat;
       rat = 1.0 - pow(0.5,n - 1);
       return rat;
  }
};

 

题目四:另类加法

题目描述:

请编写一个函数,将两个数字相加。不得使用+或其他算数运算符。

给定两个int AB。请返回A+B的值

解题思路:

用位的异或实现加法;

程序代码:

class UnusualAdd {
public:
   int addAB(int A, int B) {
       // write code here
       int Xor, And;
       while(B != 0){
           Xor = A^B;
           And = (A&B)<<1;
           A = Xor;
           B = And;
      }
       return A;
  }
};

 

题目五:最近公共祖先

题目描述:

有一棵无穷大的满二叉树,其结点按根结点一层一层地从左往右依次编号,根结点编号为1。现在有两个结点a,b。请设计一个算法,求出a和b点的最近公共祖先的编号。

给定两个int a,b。为给定结点的编号。请返回ab的最近公共祖先的编号。注意这里结点本身也可认为是其祖先。

解题思路:

满二叉树的父节点是子节点除以2取整的结果,利用这一点找出父节点。如果a != b,就让其中的较大数除以2, 如此循环知道a == b,即可得到原来两个数的最近公共祖先。

程序代码:

class LCA {
public:
   int getLCA(int a, int b) {
       // write code here
       while(a != b){
           if(a > b)
               a /= 2;
           else
               b /= 2;
      }
       return a;
  }
};

 

题目六:二叉树的最大深度

题目描述:

给定一个二叉树,找到最大深度,即找出从根节点到叶节点的最大路径长度。

解题思路:

递归找出二叉树的最大深度;

程序代码:

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
   int maxDepth(TreeNode *root) {
       if(root == NULL )
           return 0;
       return 1 + max(maxDepth(root ->left), maxDepth(root -> right));
  }
};

 

题目七:词频统计

题目描述:

请设计一个高效的方法,找出任意指定单词在一篇文章中的出现频数。

给定一个string数组article和数组大小n及一个待统计单词word,请返回该单词在文章中的出现频数。保证文章的词数小于等于1000。

解题思路:

利用 .count()函数统计在数组中某个值出现的次数;

程序代码:

class Frequency:
   def getFrequency(self, article, n, word):
       # write code here
       return article.count(word)

 

题目八:abc

题目描述:

设a、b、c均是0到9之间的数字,abc、bcc是两个三位数,且有:abc+bcc=532。求满足条件的所有a、b、c的值。

解题思路:

利用数字的含义,例如:524 = 5100 + 210 +4*1;

程序代码:

#include <iostream>
using namespace std;
int main(){
   for (int i = 0;i <= 9;i++){
       for (int j = 0; j <= 9;j++){
           for (int k = 0;k <= 9;k++){
               if (i*100 + j*10 + k + j*100 + k*11 == 532)
                   cout<<i<<" "<<j<<" "<<k<<endl;
          }
      }
  }
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
剑指Offer-003:从尾到头打印链表

一、前言 本系列文章为《剑指Offer》刷题笔记。 刷题平台:牛客网 二、题目 输入一个链表,返回一个反序的链表。 1、思路 可以直接使用列表的插入手法,每次插入数据,只插入在首位。 2、编程...

骑着螞蟻流浪
04/22
0
0
剑指Offer-002:替换空格

一、前言 本系列文章为《剑指Offer》刷题笔记。 刷题平台:牛客网 二、题目 请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为W...

骑着螞蟻流浪
04/22
0
0
【机器学习】【深度学习】【人工智能】【算法工程师】面试问题汇总(持续更新)

1. 算法 【1】动态规划经典题目总结 2. 数据结构 2.1 数组和字符串 【1】【算法】删除一个数组中为0的元素 【2】牛客网在线编程专题《剑指offer-面试题34》丑数 【3】牛客网在线编程专题《剑...

Microstrong0305
03/31
0
0
分享一些程序员必备网站

本人呢是个收藏狂,看到过很多很好的学习和工具网站,挑选出一些分享给大家。有些已经很出名的我就不再分享出来了。 1. 中文在线教程书籍 free-programming-books-zh_CN 这是github上的一个开...

osc_u4dvv5qa
2019/04/11
2
0
PAT甲级终结——心得总结

首先报喜一波 第一次考,满分,4道题总共花了2个小时做完,一部分是题简单的原因,一部分也是自己三刷了PAT的心血吧。 刷PAT的经验 神指导: 胡凡-《算法笔记》神助攻:柳婼的博客,百度即可...

osc_h9x23mw1
2019/12/08
4
0

没有更多内容

加载失败,请刷新页面

加载更多

浅谈对python pandas中 inplace 参数的理解

这篇文章主要介绍了对python pandas中 inplace 参数的理解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 pandas 中 inplace 参数在很多函数中都会有,它的作用是:是否...

Linux就该这么学
26分钟前
13
0
C++ 从基本数据类型说起

前言 int 在32位和64位操作系统,都是四个字节长度。为了能编写一个在32位和64位操作系统都能稳定运行的程序,建议采用std::int32_t 或者std::int64_t指定数据类型。*与long随操作系统子长变...

osc_sxdofc9c
26分钟前
9
0
游戏音乐的作用以及起源

游戏音乐是由特殊的音乐、语言符号、美学符号组成,在电子游戏的发展下,游戏音乐越来越成熟,游戏音乐与美术相融合,能够带给玩家视觉与声音的感官冲击,形成游戏音乐所具有的独特的审美效果...

奇亿音乐
27分钟前
10
0
2020,最新Model的设计-APP重构之路

很多的app使用MVC设计模式来将“用户交互”与“数据和逻辑”分开,而model其中一个重要作用就是持久化。下文中设计的Model可能不是一个完美的,扩展性强的model范例,但在我需要重构的app中,...

osc_mfzkzkxi
27分钟前
4
0
面对职业瓶颈,iOS 开发人员应该如何突破?

我们经常看到 iOS 开发人员(各种能力水平都有)的一些问题,咨询有关专业和财务发展方面的建议。 这些问题有一个共同点:前面都会说“我现在遇到了职业困境”,然后会问一些诸如“我是否应该...

osc_gfpedeca
28分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部