当前位置: 首页 > news >正文

算法知识点————数论和链表

1、n数和

2数和

  • 有序(递增):头尾相加,和目标值比较
  • 无序:哈希表(target - cur)

多数和:
​ 先排序
拿一个数(检测 i 和i-1 重复的不选择)
​ 2数和问题 (检测 去重)

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int len = nums.size();vector<vector<int>> res; //结果是一个二元组 ,每个里面是个vectorint i,j,k;sort(nums.begin(),nums.end());//先排序for(i = 0;i<len -2;i++){ //先取一个数if( i > 0 && nums[i] == nums[i-1]) continue;//去重,重复元素就不取了int temp = 0 - nums[i]; //temp记录剩下两个数和的负值int l = i+1,r = nums.size()-1;//左右指针寻找值while( l < r){int sum = nums[l] + nums[r] ;if(sum == temp)//找到了{res.push_back({nums[i],nums[l],nums[r]}); //存到结果res中while(l < r && nums[l] == nums[++l]);//去重 l向后面移动while(l < r && nums[r] == nums[--r]);}else if (sum < temp){//和不够l++;}else {r--;}}}return res;}
};

2、回文数121 回文串abcba

  • 负数不是回文数字
  • 个位数都是回文数
  • 0结尾的数不是回文数
  • 从后往前取数 %10 然后和原来的数比较
  • 跳出while循环要么是num == x 要么是不等于(大于和小于)
  • 最后的可能是12和1或者12和12 或者1和12都算
class Solution {
public:bool isPalindrome(int x) {if(x < 0) return false;if(x < 10) return true;if(x%10 == 0) return false;int num = 0;while(num < x){//121num = num*10 + x%10;//当前值 12x/=10;//1}if(x == num || num == x/10 || x == num/10) return true;//else return false;}
};

3、两个链表对应两个数组然后相加,结果在链表中
1->5->8 对应851
1->6->3->9 对应9361

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2,int carry =0) {if(l1 == nullptr && l2 == nullptr){return carry ? new ListNode(carry) : nullptr;//如果有进位,创建节点}if(l1 == nullptr) swap(l1,l2);//如果l1 是空的,l2一定不是空的 ,交换l1和l2保证l1非空int sum = carry+l1->val+(l2 ? l2->val :0);l1->val = sum%10;//节点保存数位l1->next = addTwoNumbers(l1->next,(l2 ? l2->next : nullptr),sum / 10);return l1;}
};

升级版本:两次反转链表,然后相加,结果返回反转

1->5->8 对应158
1->6->3->9 对应1639

class Solution {
public:ListNode* reverseList(ListNode* head){if(head == nullptr || head->next == nullptr) return head;auto newNode = reverseList(head->next);head->next->next = head;head->next = nullptr;return newNode;}ListNode *addTwo(ListNode* l1,ListNode* l2 ,int carry = 0){if(l1 == nullptr && l2 == nullptr){return carry ? new ListNode(carry) :nullptr;}if(l1 == nullptr) swap(l1,l2);carry += l1->val + (l2 ? l2->val : 0);l1->val = carry %10;l1->next = addTwo(l1->next ,(l2 ? l2->next : nullptr),carry/10);return l1;}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//两次反转链表,然后相加,结果返回反转l1 = reverseList(l1);l2 = reverseList(l2);auto l3 = addTwo(l1,l2);return reverseList(l3);}
};
http://www.lryc.cn/news/451483.html

相关文章:

  • NASA:ATLAS/ICESat-2 L3B 每日和每月网格极地海面高度异常 V003
  • Java类设计模式
  • Valhalla实现 使用Docker部署利用OSM(Mapbox)地图实现路径规划详细步骤
  • blender解决缩放到某个距离就不能继续缩放
  • 2022浙江省赛G I M
  • 数据链路层 ——MAC
  • 在java中都是如何实现这些锁的?或者说都有哪些具体的结构实现
  • 用CSS创造三角形案例
  • matlab-对比两张图片的Ycbcr分量的差值并形成直方图
  • Chromium 使用安全 DNS功能源码分析c++
  • 10.1 刷题
  • 车辆重识别(2021ICML改进的去噪扩散概率模型)论文阅读2024/9/29
  • 828华为云征文|针对Flexus X实例云服务器的CPU和内存性能测评
  • Python知识点:如何使用Google Cloud IoT与Python进行边缘计算
  • 力扣 最小覆盖子串
  • python的内存管理机制
  • 阿布量化:基于 Python 的量化交易框架
  • 计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-28
  • 【tower-boot 系列】开源RocketMQ和阿里云rockerMq 4.x和5.x集成 (一)
  • Pikachu-Cross-Site Scripting-反射型xss(post)
  • Vue3 工具函数(总结)
  • (undone) MIT6.824 Lab1
  • SpringMVC——REST
  • 【牛客网刷题记录】【java】二叉树
  • 一文讲透大语言模型构建流程
  • VR视频怎样进行加密和一机一码的使用?--加密(一)
  • Ubuntu启动后第一次需要很久才能启动GTK应用问题
  • 栏目二:Echart绘制动态折线图+柱状图
  • Gromacs——使用过程中暴露问题分析及学习
  • Webpack模式-Resolve-本地服务器