笔试题练习(八)

简介:
1,不使用中间变量实现strlen
复制代码
int strlen_p(const char *p)
{
    if (*p == '\0')
        return 0; 
    else
        return strlen_p(++p)+1;
}
复制代码
2,统计32位整数二进制表示1的个数
复制代码
bool isPowOf2(int n)
{//是否是2的幂
    return (n & (n-1)) ? false : true;
}
int countOnes(int n)
{//统计二进制表示中1的个数
    int count = 0;
    while (n != 0)
    {
        n = n & (n-1);
        ++count;
    }
    return count;
}
int countZeros(int n)
{//统计二进制表示中0的个数
    n = ~n;
    return countOnes(n);
}
复制代码
3,题目: 有一个数组t[100],存放了1~99之间的数字,用效率较高的代码把重复数字去掉。例如数组{1,2,2,2,3,5,6,6}变成{1,2,3,5,6}。
复制代码
bool flag[100] = {false};//flag[1]flag[99],flag[0]不用

int removeRedundant(int t[],int size)
{
    int i,end = 0;
    for (i = 0; i < size; ++i)
    {
        if (flag[t[i]] == false)
        {
            flag[t[i]] = true;
        }
    }
    for (i = 1; i < size; ++i)
    {
        if (flag[i] == true)
        {    
            t[end++] = i;
        }
    }
    return end;
}
复制代码
 
4,写一个程序, 要求功能:求出用1,2,5这三个数不同个数组合的和为100的组合个数。如:100个1是一个组合,5个1加19个5是一个组合。

因为x+2y+5z=100

所以x+2y=100-5z,且z<=20 x<=100 y<=50

所以(x+2y)<=100,且(x+5z)是偶数

对z作循环,求x的可能值如下(x的取值种数就代表了最终解的个数,对于某个z,x定了后y自动确定):

z=0, x=100, 98, 96, ... 0

z=1, x=95, 93, ..., 1

z=2, x=90, 88, ..., 0

z=3, x=85, 83, ...,

z=4, x=80, 78, ..., 0

......

z=19, x=5, 3, 1

z=20, x=0

因此,组合总数为100以内的偶数+95以内的奇数+90以内的偶数+...+5以内的奇数+1,即为:

(51+48)+(46+43)+(41+38)+(36+33)+(31+28)+(26+23)+(21+18)+(16+13)+(11+8)+(6+3)+1

某个偶数m以内的偶数个数(包括0)可以表示为m/2+1=(m+2)/2

某个奇数m以内的奇数个数也可以表示为(m+2)/2

所以,求总的组合次数可以编程为:

int  number=0;
for (int m=0;m<=100;m+=5)
{
number+=(m+2)/2;
}
cout<<number<<endl;
 这个程序,只需要循环21次, 两个变量,就可以得到答案,比最常见的那个穷举法要高效的多
 
5,通过一次遍历找到单链表中倒数第n个节点,链表可能相当大,可使用辅助空间,但是辅助空间的数目必须固定,不能和n有关。

复制代码
struct Node
{
    int value;
    struct Node* next;
};

Node* findLastNth(Node* head, int n)
{//找到倒数第n个节点
    assert(head != NULL && n>0);
    Node *p1,*p2;
    p1 = head;
    p2 = head;
    int i = 1;
    while (i < n && p2->next != NULL) 
    {//间隔n-1
        p2 = p2->next;
        ++i;
    }
    if (i < n)
    {//没有倒数第n个
        return NULL;
    }
    else if(p2->next == NULL)
    {//恰好链表头就是
        return p1;
    }
    while (p2->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}
复制代码
 6,有1,2,....一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数.
复制代码
void sortOnorder(int array[], int len)
{
    int temp;
    for(int i = 0; i < len; )
    {
        if ( array[i] != i + 1)//下标和值不满足对应关系
        {
            temp = array[array[i] - 1];        //不相等的话就把array[i]交换到与索引相应的位置
            array[array[i] - 1] = array[i];
            array[i] = temp;
        }
        else
            i++; // 保存,以后此值不会再动了
    }
}



本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2009/06/02/1494419.html,如需转载请自行联系原作者
目录
相关文章
|
弹性计算 Linux 数据安全/隐私保护
幻兽帕鲁Palworld服务器部署保姆级教程(Palworld私服)
幻兽帕鲁Palworld服务器部署保姆级教程(Palworld私服)幻兽帕鲁Palworld多人游戏专用服务器一键部署教程,阿里云推出新手0基础一键部署幻兽帕鲁服务器教程,傻瓜式一键部署,3分钟即可成功创建一台Palworld专属服务器,成本仅需26元,阿里云百科分享2024年新版基于阿里云搭建幻兽帕鲁服务器教程
249 1
|
机器学习/深度学习 传感器 编解码
CV学习笔记-立体视觉(点云模型、Spin image、三维重建)
CV学习笔记-立体视觉(点云模型、Spin image、三维重建)
1923 0
CV学习笔记-立体视觉(点云模型、Spin image、三维重建)
|
存储 Oracle 关系型数据库
ORACLE ASM 存储磁盘管理
-- ORACLE ASM 自动存储管理 -- 1、磁盘组的创建与删除 sqlplus / as sysasm create diskgroup data normal redundancy failgroup f1 disk '/dev/data1', '/dev/data2', failgroup f2 disk '/dev/data3', '/dev/data4'; 删除磁盘组: alter drop diskgroup data dismount; drop diskgroup data; 如果磁盘组中还包含文件,那么上述命令将执行失效。
2020 0
|
6天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
16天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1317 7
|
4天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
285 128
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
3天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
15天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1376 87