2022.02.05 DAY2
2022/2/5 23:44:43
本文主要是介绍2022.02.05 DAY2,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
今天陪老姐送对象去安庆了,上午还去了西风禅寺求了个签,第一次拿到中评签,看来今年还需要继续努力哈哈哈。一直到晚上才有时间去做点题目,今天依旧是leetcode。
题目
leetcode 1 两数之和
题目
(两数之和)[https://leetcode-cn.com/problems/two-sum/]
思路
还是一样,我们先考虑一下朴素做法,显然是双重遍历,时间复杂度是O(N^2^)
,显然在1e5
的情况下是过不掉的,所以我们选择优化到O(N)
。由于我们只需要找到一个符合题意得解即可,我们可以利用哈希表的特点边遍历边读入,这样的时间复杂度是最小的。
代码
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> hash; int len = nums.size(); for(int i = 0; i < len; ++ i){ int t = target - nums[i]; if(hash.count(t)) return {hash[t], i}; hash[nums[i]] = i; } return {}; } };
2. leetcode 2 两数相加
题目
(两数相加)[https://leetcode-cn.com/problems/add-two-numbers/]
思路
其实就是链表的模拟题。
代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* res = new ListNode(-1); ListNode* temp = new ListNode; res = temp; int carry = 0; while(l1 || l2){ int n1 = l1 ? l1->val : 0; int n2 = l2 ? l2->val : 0; int sum = n1 + n2 + carry; carry = sum / 10; temp->next = new ListNode(sum % 10); temp = temp->next; if(l1) l1 = l1->next; if(l2) l2 = l2->next; } if(carry) temp->next = new ListNode(1); return res->next; } };
Acwing 第37场周赛 B题 4297 截断数组
题目
(截断数组)[https://www.acwing.com/problem/content/4300/]
思路
用一个前缀数组一个后缀数组来维护值就行了,需要注意的是题目要求从中间切开所以中间的数组长度绝对不为0,所以双指针的l
与r
不能相碰。
代码
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int arr[N]; long long pre[N], last[N];//预加载前后缀和数组 int main(){ int n; cin.tie(0); ios::sync_with_stdio(false); cin >> n; for(int i = 0;i < n; ++i){ cin >> arr[i]; } for(int i = 1; i <= n; ++ i){ pre[i] = pre[i - 1] + arr[i - 1]; } for(int i = n; i >= 1; -- i){ last[i] = last[i + 1] + arr[i - 1]; } int l = 1, r = n; long long res = 0; while(l < r){ if(pre[l] > last[r]){ r--; }else if(pre[l] < last[r]) { l++; }else{ res = max(res, pre[l]); l++; } } cout << res; }
这篇关于2022.02.05 DAY2的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性