day7 8-牛客67道剑指offer-JZ74、57、58、73、61、62、64、65、把字符串转换成整数、数组中重复的数字

文章目录

  • 1. JZ74 和为S的连续正数序列
    • 暴力解法
    • 滑动窗口（双指针）
  • 2. JZ57 和为S的两个数字
  • 3. JZ58 左旋转字符串
  • 4. JZ73 翻转单词序列
  • 5. JZ61 扑克牌顺子
  • 6. JZ62 孩子们的游戏(圆圈中最后剩下的数)
    • 迭代 模拟
    • 递归 约瑟夫环问题 找规律
  • 7. JZ64 求1+2+3+...+n
  • 8. JZ65 不用加减乘除做加法
  • 9. 把字符串转换成整数
  • 10. 数组中重复的数字
    • 哈希表
    • 原地解法

1. JZ74 和为S的连续正数序列

在这里插入图片描述

暴力解法

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        if(sum == 0) return vector<vector<int>>{};
        for(int i=1; i<sum; i++)
        {
            int temp = 0;
            path.clear();
            for(int j=i; j<sum; j++)
            {
                path.push_back(j);
                temp += j;
                if(temp == sum) result.push_back(path);
                if(temp > sum) break;
            }
            //result.push_back(path);
        }
        return result;
    }
    vector<int> path;
    vector<vector<int> > result;
};

至少是两个数，优化遍历的次数，数学公式计算
在这里插入图片描述

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        //暴力解法 写法2
        for (int n = sqrt(2 * sum); n >= 2; --n) 
        {
            if (((n & 1) == 1 && sum % n == 0) || (sum % n * 2 == n)) 
            {
                vector<int> res;
                //j用于计数，k用于遍历求值
                for (int j = 0, k = sum / n - (n - 1) / 2; j < n; j++, k++)//注意看k的求法
                    res.push_back(k);
                result.push_back(res);
                }
        }
        return result;
    }
    vector<int> path;
    vector<vector<int> > result;
};

滑动窗口（双指针）

在这里插入图片描述在这里插入图片描述

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        //滑动窗口
        int left = 1, right = 2, tempsum = 3;
        while(left < right)
        {
            if(tempsum == sum)//保存结果
            {
                path.clear();
                for(int i=left; i<=right; i++)
                    path.push_back(i);
                result.push_back(path);
            }
            if(tempsum < sum)//窗口右边界外扩 右移
            {
                right++;tempsum += right;
            }
            else //tempsum > sum 窗口左边界右移；tempsum = sum 窗口左边界右移 开始下一轮子结果
            {
                tempsum -= left;//新的边界值
                left++;
            }
        }
        return result;

    }
    vector<int> path;
    vector<vector<int> > result;
};

2. JZ57 和为S的两个数字

在这里插入图片描述

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        if(array.size() == 0) return vector<int>{};
        // 滑动窗口 双指针 写法1
        /*
        int left = 0, right = array.size()-1;
        while(left < right)
        {
            if(sum - array[left] == array[right])
            {
                result.push_back(array[left]);
                result.push_back(array[right]);
                break;
            }
            if(sum - array[left] < array[right]) right--;
            else left++;
        }
        */
        // 滑动窗口 双指针 写法2
        int left = 0, right = array.size()-1, tempsum = 0;
        while(left < right)
        {
            tempsum = array[left] + array[right];
            if(tempsum == sum)
            {
                result.push_back(array[left]);
                result.push_back(array[right]);
                return result;
            }
            else if(tempsum > sum) right--;
            else left++;
        }
        return result;
    }
    vector<int> result;
};

3. JZ58 左旋转字符串

在这里插入图片描述
先局部反转 cbafedZYX，然后整体反转XYZdefabc

#include <algorithm>
#include <type_traits>
class Solution {
public:
    string LeftRotateString(string str, int n) {
        int len = str.size();
        if(len <= 1) return str;
        else if(len < n) n %= len;
        reverse(str, 0, n-1);
        reverse(str, n, len-1);
        reverse(str, 0, len-1);
        return str;
    }
    void reverse(string& str, int start, int end)
    {
        for(int i=start, j=end; i<j; i++, j--)
        {
            swap(str[i], str[j]);
        }
    }
};

4. JZ73 翻转单词序列

在这里插入图片描述

class Solution {
public:
    string ReverseSentence(string str) {
        if(str.size() <= 1) return str;
        string result = "", temp = "";
        for(int i=0; i<str.size(); ++i)
        {
            if(str[i] == ' ')//遇到空格 把temp和之前的结果拼接
            {
                result = ' ' + temp + result;//倒序拼接
                temp = "";//更新 存下一个单词
            }
            else temp += str[i];//没有遇到空格 把整个字符串都存在temp中
        }
        if(temp.size()) // 如果temp还剩有单词 没有这一步的话示例1会返回" am a nowcoder."
            result = temp + result;
        return result;
    }
};

5. JZ61 扑克牌顺子

在这里插入图片描述

  • 排序，统计0的个数，统计所有相邻数字间隔总数。
  • 如果0的个数 = 相邻数字间隔总数，就是顺子；如果出现对子，则不是顺子。
  • 统计所有相邻数字间隔总数时，如果两个数字间隔为1，不计数。
class Solution {
public:
    bool IsContinuous(vector<int>& numbers) {
        if(numbers.size() < 5) return false;
        sort(numbers.begin(), numbers.end());
        int numOfZero = 0, numOfInner = 0;
        //如果是连续的数 排序后 两两之间间隔为1
        //比较0的个数 是否等于 统计的间隔长度 若相邻/间隔为1 视间隔长度为0
        for(int i=0; i<numbers.size() - 1; i++)
        {
            if(numbers[i] == 0) numOfZero++;
            else if(numbers[i] == numbers[i+1]) return false;//对子 不可能是顺子
            else
            {
                numOfInner += numbers[i+1] - numbers[i] - 1;//相邻数的间隔长度为0 间隔长度累加
                //numOfInner += numbers[i+1] - numbers[i] -1;//这里千万注意要减去1
            }
        }
        if(numOfZero >= numOfInner) return true;
        return false;

    }
};

6. JZ62 孩子们的游戏(圆圈中最后剩下的数)

在这里插入图片描述

迭代 模拟

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(n < 1 || m < 1) return -1;
        vector<int> numbers(n,0);//标记哪个小朋友拿过礼物
        int index = -1,step = 0, count = n;
        while (count > 0) 
        {
            index++;
            if(index >= n) index = 0;//模拟环 从第一个小朋友开始
            if(numbers[index] == -1) continue;
            step++;//报数
            if(step == m)
            {
                numbers[index] = -1;
                step = 0;//下一个小朋友从头开始报数
                count--;//已经有一个小朋友拿过礼物了 环中小朋友数量-1
            }
        }
        return index;
    }
};

递归 约瑟夫环问题 找规律

在这里插入图片描述
也就是说，从f(n-1, m)当前位置来看，f(n, m)在f(n-1, m)的后m个位置。n个数字中最后剩下的数字，即去掉的数字为(m-1)%n，下一次报数是从第 m%n 个数字开始。因此，f(n-1) 和 f(n)的关系如下：

f(n-1)f(n)
0m%n
1(m+1)%n
……
n-2(m-2)%n

两种写法

#include <any>
class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        //递归 约瑟夫环问题 写法1
        if(n <= 0) return -1;
        return (LastRemaining_Solution(n-1, m) + m) % n;

        //递归 约瑟夫环问题 写法2
        /*
        if(n <= 0 || m < 0) return -1;
        int result = 0;
        for(int i=2; i<=n; ++i)
        {
            result = (result + m) % i;
        }
        return result;
        */
    }
};

7. JZ64 求1+2+3+…+n

在这里插入图片描述
不能用if、switch、？：等操作时，利用逻辑与的短路特性实现递归终止，也就是通过判断n是否为0来控制递归是否终止。
n递减，并且通过递归实现倒序累加和。当n = 0时，递归结束；n > 0时，递归，倒序累加求和。因此判断条件是 (n > 0) && ((result += Sum_Solution(n-1)) > 0);

class Solution {
public:
    int Sum_Solution(int n) {
        int result = n;
        (n > 0) && ((result += Sum_Solution(n-1)) > 0);
        return result;
    }
};

8. JZ65 不用加减乘除做加法

在这里插入图片描述
在这里插入图片描述
两个数异或：相当于每一位相加，而不考虑进位，产生非进位的加和结果；
两个数相与，并左移一位：相当于求得进位；
将上述两步的结果相加，什么时候进位制为0也就说明两个数相加到了最终点，也就计算结束了。

5-101，7-111
第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。

class Solution {
public:
    int Add(int num1, int num2) {
        //位运算 迭代
        int add = num2;// add表示进位值
        int sum = num1; // sum表示总和 
        while(add != 0)
        {
            int temp = sum ^ add;// 将每轮的无进位和与进位值做异或求和
            add = (sum & add) << 1;// 进位值是用与运算产生的
            sum = temp;// 更新sum为新的和
        }
        return sum;
    }
};

9. 把字符串转换成整数

在这里插入图片描述
要注意的两点，1.越界处理，2.正负号个数处理，越界处理用下面这种写法的时候，怎么改都只能通过95.5%的用例，最后还有两组用例没过。换成练习模式才知道原来是过不了“±5”这种例子，真的无语，加了一个统计正负号个数的判断。

#include <climits>
class Solution {
public:
    int StrToInt(string s) {
        int result = 0;
        int index = 0;
        int len = s.size();//下标索引 字符串长度
        
        //1.剔除特殊情况
        if(len == 0) return 0;

        //2.如果有前导空格就去掉，让指针往后偏移到非空格处
        while(index < len)
        {
            if(s[index] == ' ') index++;
            else break;
        }
        //如果全是空格，直接返回
        if(index >= len) return 0;

        //3.处理正负号
        int flag = 1;//正负号标志位 正数1 负数-1
        int flagnum = 0;
        //如果第一个符号是正负号的情况
        if(s[index] == '+')
        {
            index++;
            flagnum++;
        }
        if(s[index] == '-')
        {
            index++;
            flag = -1;
            flagnum++;
        }
        //最多有一个正 / 负号
        if(flagnum > 1) return 0;

        //4.有效数字部分
        while(index < len)
        {
            char c = s[index];
            //后续非法字符，截断
            if(c < '0' || c > '9') break;

            //处理越界 这种写法是结果和当前遍历的数字都进行越界处理
            if(result > INT_MAX / 10 || (result == INT_MAX / 10 && (c - '0') > INT_MAX % 10)) return INT_MAX;
            if(result < INT_MIN / 10 || (result == INT_MIN / 10 && (c - '0') > -(INT_MIN % 10))) return INT_MIN;

            result = result * 10 + flag * (c - '0');
           /*
            cout << s[index] - '0'<<endl;
            cout << flag * (s[index] - '0') <<endl;
            cout << "result:" << result <<endl;
           */
            index++;
        }
        return result;
    }
};

10. 数组中重复的数字

在这里插入图片描述

哈希表

使用了循环，循环次数为数组大小，时间复杂度为O(N)。引入额外的集合空间，空间复杂度为O(N)，最坏的情况是数组中的元素都不重复。

  • 用map
#include <string>
#include <unordered_map>
class Solution {
  public:
    int duplicate(vector<int>& numbers) {
        unordered_map<int, int> m;
        for(int i=0; i<numbers.size(); i++)
        {
            m[numbers[i]]++;
            if(m[numbers[i]] >= 2) return numbers[i];            
        }
        return -1;
    }
};
  • 用vector，降低内存复杂度
#include <string>
#include <unordered_map>
class Solution {
  public:
    int duplicate(vector<int>& numbers) {
    	//哈希表 数组 直接统计频率 降低内存复杂度
        vector<int> result(numbers.size(), 0);
        for(int i=0; i<numbers.size(); i++)
        {
            result[numbers[i]]++;
            if(result[numbers[i]] >= 2) return numbers[i];
        }
        return -1;
    }
};

原地解法

在这里插入图片描述

  • 如果numbers[index] = index，第index个位置的元素也可以用numbers[numbers[index]]来表示
  • 使用了循环，循环次数为数组大小，时间复杂度为O(N)。没有引入额外的集合空间，空间复杂度为O(1)
#include <string>
#include <unordered_map>
class Solution {
  public:
    int duplicate(vector<int>& numbers) {
        //原地解法
        int index = 0;
        while (index < numbers.size()) 
        {
            if(numbers[index] == index)//第index个位置的元素=index
            {
                index++;
                continue;
            }
            else //第index个位置的元素≠index
            {
                //如果第index个位置的元素numbers[index] = index 说明元素重复
                if(numbers[index] == numbers[numbers[index]]) return numbers[index];//重复元素 返回
                else swap(numbers[index], numbers[numbers[index]]);//交换位置
            }
        }
        return -1;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/68130.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

0基础学C#笔记08：插入排序法

0基础学C#笔记08：插入排序法

文章目录 前言一、过程简单描述&#xff1a;二、代码总结 前言 我们在玩打牌的时候&#xff0c;你是怎么整理那些牌的呢&#xff1f;一种简单的方法就是一张一张的来&#xff0c;将每一张牌插入到其他已经有序的牌中的适当位置。当我们给无序数组做排序的时候&#xff0c;为了…
阅读更多...
SpringBoot 该如何预防 XSS 攻击

SpringBoot 该如何预防 XSS 攻击

XSS 漏洞到底是什么&#xff0c;说实话我讲不太清楚。但是可以通过遇到的现象了解一下。在前端Form表单的输入框中&#xff0c;用户没有正常输入&#xff0c;而是输入了一段代码&#xff1a;</input><img src1 onerroralert1> 这个正常保存没有问题。问题出在了列表…
阅读更多...
竞赛项目 深度学习疲劳驾驶检测 opencv python

竞赛项目 深度学习疲劳驾驶检测 opencv python

文章目录 0 前言1 课题背景2 实现目标3 当前市面上疲劳驾驶检测的方法4 相关数据集5 基于头部姿态的驾驶疲劳检测5.1 如何确定疲劳状态5.2 算法步骤5.3 打瞌睡判断 6 基于CNN与SVM的疲劳检测方法6.1 网络结构6.2 疲劳图像分类训练6.3 训练结果 7 最后 0 前言 &#x1f525; 优…
阅读更多...
HCIP-linux和kvm（ks配置文件自动化安装及console连虚拟机有问题）

HCIP-linux和kvm（ks配置文件自动化安装及console连虚拟机有问题）

1、linux linux安装教程参考&#xff0c;https://blog.51cto.com/cloudcs/5245337 yum源配置 本地yum源配置&#xff1a; 8版本配置&#xff1a;将光盘iso挂载到某个目录&#xff0c;/dev/cdrom是/dev/sr0软链接&#xff0c;# mount /dev/cdrom /mnt&#xff0c;# ls /mnt Ap…
阅读更多...
.NET6使用SqlSugar操作数据库

.NET6使用SqlSugar操作数据库

1.//首先引入SqlSugarCore包 2.//新建SqlsugarSetup类 public static class SqlsugarSetup{public static void AddSqlsugarSetup(this IServiceCollection services, IConfiguration configuration,string dbName "ConnectString"){SqlSugarScope sqlSugar new Sq…
阅读更多...
手动创建一个DOCKER镜像

手动创建一个DOCKER镜像

1. 我们先使用C语言写一个hello-world程序 vim hello.c # include <stdio.h>int main() {print("hello docker\n"); } 2. 将hello.c文件编译成二进制文件, 需要安装工具 yum install gcc yum install glibc-static 开始编译 gcc -static hello.c -o hello 编译…
阅读更多...
Mybatis Plus条件构造器LambdaQueryWrapper

Mybatis Plus条件构造器LambdaQueryWrapper

官网地址 Mybatis Plus条件构造器LambdaQueryWrapper 目前数据库数据情况&#xff0c;User表 iduser_namebirthdaysexaddress1张12023-08-10男123163.com2李12023-08-10女222163.com3张22023-08-10女999163.com4张32023-08-10男9994qq.com ## 简单介绍 如何使用各种场景 方法…
阅读更多...
基于Promise.resolve实现Koa请求队列中间件

基于Promise.resolve实现Koa请求队列中间件

本文作者为360奇舞团前端工程师 前言 最近在做一个 AIGC 项目&#xff0c;后端基于 Koa2 实现。其中有一个需求就是调用兄弟业务线服务端 AIGC 能力生成图片。但由于目前兄弟业务线的 AIGC 项目也是处于测试阶段&#xff0c;能够提供的服务器资源有限&#xff0c;当并发请求资源…
阅读更多...
Java算法_ LRU 缓存(LeetCode_Hot100)

Java算法_ LRU 缓存(LeetCode_Hot100)

题目描述&#xff1a;请你设计并实现一个满足 LRU &#xff08;最近最少使用&#xff09; 缓存 约束的数据结构。 获得更多&#xff1f;算法思路:代码文档&#xff0c;算法解析的私得。 运行效果 完整代码 import java.util.HashMap; import java.util.Map;/*** 2 * Author: L…
阅读更多...
微信小程序备案流程

微信小程序备案流程

微信小程序备案流程 &#x1f4d4; 千寻简笔记介绍 千寻简笔记已开源&#xff0c;Gitee与GitHub搜索chihiro-notes&#xff0c;包含笔记源文件.md&#xff0c;以及PDF版本方便阅读&#xff0c;且是用了精美主题&#xff0c;阅读体验更佳&#xff0c;如果文章对你有帮助请帮我…
阅读更多...
Oracle database Linux自建环境备份至远端服务器自定义保留天数

Oracle database Linux自建环境备份至远端服务器自定义保留天数

环境准备 linux下安装oracle 请看 oracle12c单节点部署 系统版本: CentOS 7 软件版本&#xff1a; Oracle12c 备份策略与实现方法 此次备份依赖Oracle自带命令exp与linux下crontab命令&#xff08;定时任务&#xff09; exp Oracle中exp命令是一个用于导出数据库数据和对象的…
阅读更多...
算法竞赛入门【码蹄集新手村600题】(MT1140-1160）C语言

算法竞赛入门【码蹄集新手村600题】(MT1140-1160）C语言

算法竞赛入门【码蹄集新手村600题】(MT1140-1160&#xff09;C语言 目录MT1141 数字3MT1142 整除的总数MT1143 沙哈德数MT1144 整除MT1145 全部整除MT1146 孙子歌诀MT1147 古人的剩余定理MT1148 隐晦余8MT1149 余数MT1150 战死四五百MT1151 韩信生气MT1152 韩信又生气了MT1153 …
阅读更多...
UML类图

UML类图

UML类图 类与类之间的关系 类与类之间的关系 依赖 一个类的对象,作为另一个类的局部变量, 虚线加箭头表示继承 实线三角实现 虚线三角关联 一个类的对象,作为一个类的字段 实线箭头 a. 组合 实心菱形实线箭头 b. 聚合 空心菱形实线箭头
阅读更多...
甄品焕新｜燕千云服务请求预警功能上线，燕小千AIGC能力再升级

甄品焕新｜燕千云服务请求预警功能上线，燕小千AIGC能力再升级

​ 燕千云数智化业务服务平台发布了1.23.0版本&#xff0c;此次版本上线了服务请求预警功能&#xff0c;增加呼叫中心服务场景中的通话质检功能&#xff0c;提高了企业IT服务效率。此次还升级了燕小千AIGC能力&#xff0c;不仅可以实时预估文档学习时间&#xff0c;还可以一键分…
阅读更多...
MySQL 存储过程、函数、触发器、事件

MySQL 存储过程、函数、触发器、事件

​ 目录 存储过程 创建存储过程 调用存储过程 查看存储过程 删除存储过程 进阶 变量 if条件判断 传递参数 case结构 while循环 repeat结构 loop语句 leave语句 游标/光标 存储函数 触发器 创建触发器 删除触发器 查看触发器 事件 查看事件调度器是否开启…
阅读更多...
Nginx负载均衡（重点）

Nginx负载均衡（重点）

正向代理 部署正向代理 server { listen 80; server_name localhost; #charset koi8-r; #access_log logs/host.access.log main; location / { root html; index index.html index.htm; proxy_pass http://20.0.0.60:80…
阅读更多...
新手如何快速学习单片机？

新手如何快速学习单片机？

初步确定学习目标&#xff1a;是学习简单便宜的51呢&#xff0c;还是学习简单但是性价比已经不算太高的&#xff0c;但是功能强大稳定可靠的avr&#xff0c;还是物美价廉的stm32&#xff0c;或者ARM9&#xff08;可以跑系统了&#xff09;&#xff0c;再往上x86什么的如果是学8…
阅读更多...
【Linux】UDP协议——传输层

【Linux】UDP协议——传输层

目录 传输层 再谈端口号 端口号范围划分 认识知名端口号 两个问题 netstat与iostat pidof UDP协议 UDP协议格式 UDP协议的特点 面向数据报 UDP的缓冲区 UDP使用注意事项 基于UDP的应用层协议 传输层 在学习HTTP等应用层协议时&#xff0c;为了便于理解&#xff…
阅读更多...
Word转PDF在线转换如何操作？分享转换技巧

Word转PDF在线转换如何操作？分享转换技巧

现如今&#xff0c;pdf转换器已成为大家日常办公学习必不可少的工具&#xff0c;市场上的pdf转换器主要有两种类型&#xff0c;一种是需要下载安装的&#xff0c;另一种是网页版&#xff0c;打开就可以使用的&#xff0c;今天小编给大家推荐一个非常好用的网页版pdf转换器&…
阅读更多...
json-server的入门

json-server的入门

由于前端开发的时候&#xff0c;需要向后端请求数据&#xff0c;有的时候后端还没有准备好&#xff0c;所以需要使用一些简单的静态数据&#xff0c;但是我们更加希望能够模拟请求以及请求回来的过程&#xff0c;这个时候就需要使用json-server Json-Server的介绍 json-server…
阅读更多...
最新文章

Copyright @ 2022~2023