目录
1. Two Sum (https://leetcode.com/problems/two-sum/)
2.Add Two Numbers (https://leetcode.com/problems/add-two-numbers/)
4.Maximum Subarray (https://leetcode.com/problems/maximum-subarray/)
5.Single Number (https://leetcode.com/problems/single-number/)
6.Path Sum(https://leetcode.com/problems/path-sum/)
leetcode题,每天刷一刷。当然更多的是抄袭原本答案,然后学习一下。
网址:https://leetcode.com/problemset/all/?page=1
Given an array of integers nums
and an integer target
, return indices of the two numbers such that they add up to target
.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
思路:
方法 1:暴力,复杂度 O(n 2 ),会超时
方法 2:hash。用一个哈希表,存储每个数对应的下标,复杂度 O(n).
方法 3:先排序,然后左右夹逼,排序 O(n log n),左右夹逼 O(n),最终 O(n log n)。但是注意, 这题需要返回的是下标,而不是数字本身,因此这个方法行不通。
答案:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> mapping;
vector<int> result;
for(int i = 0; i < nums.size(); i++){
mapping[nums[i]] = i;
}
for(int i = 0; i < nums.size(); i++){
int value = target - nums[i];
if(mapping.find(value) != mapping.end() && mapping[value] > i){
result.push_back(i);
result.push_back(mapping[value]);
break;
}
}
return result;
}
};
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
解析: 链表,类似于加法
代码:
/**
* 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 dummy(-1); //头节点
int carry = 0;
ListNode *pre=&dummy;
for(ListNode *pa = l1, *pb = l2;
pa != nullptr || pb != nullptr;
pa = pa == nullptr ? nullptr : pa->next,
pb = pb == nullptr ? nullptr : pb->next,
pre = pre->next){
const int ai = pa == nullptr ? 0 : pa->val;
const int bi = pb == nullptr ? 0 : pb->val;
const int value = (ai + bi + carry)%10;
carry = (ai + bi + carry)/10;
pre->next = new ListNode(value);
}
if(carry > 0){
pre->next = new ListNode(carry);
}
return dummy.next;
}
};
Given a string s
, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Example 4:
Input: s = "" Output: 0
分析:
代码:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int ASCII_MAX=26;
int last[ASCII_MAX]; //记录字符上次出现过的位置
int start = 0; //记录当前子串的起始位置
fill(last, last + ASCII_MAX, -1); //0也是有效位置,因此初始化为-1
int max_len = 0;
for(int i = 0; i < s.size(); i++) {
if(last[s[i] - 'a'] >= start) {
max_len = max(i - start, max_len);
start = last[s[i] - 'a'] +1;
}
last[s[i] - 'a'] = i;
}
return max((int)s.size() - start,max_len);
}
};
Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23
分析:
答案:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT_MIN, f=0;
for(int i = 0; i< nums.size(); i++){
f = max(f+nums[i],nums[i]);
result = max(f,result);
}
return result;
}
};
Given a non-empty array of integers nums
, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1] Output: 1
Example 2:
Input: nums = [4,1,2,1,2] Output: 4
Example 3:
Input: nums = [1] Output: 1
分析:按位异或运算符(^)
按位异或运算将两个运算分量的对应位按位遵照以下规则进行计算:
0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0
即相应位的值相同的,结果为 0,不相同的结果为 1。
代码:
class Solution {
public:
int singleNumber(vector<int>& nums) {
int x = 0;
for(int i = 0; i < nums.size(); i++){
x ^= nums[i];
}
return x;
}
};
Given the root
of a binary tree and an integer targetSum
, return true
if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum
.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true
Example 2:
Input: root = [1,2,3], targetSum = 5 Output: false
Example 3:
Input: root = [1,2], targetSum = 0 Output: false
分析:
代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr) return false;
if(root->left == nullptr && root->right == nullptr)
return targetSum == root->val;
return hasPathSum(root->left,targetSum - root->val) || hasPathSum(root->right,targetSum - root->val);
}
};
文章浏览阅读170次。2020/06/01 面向对象编程面向对象(object oriented programming,OOP)编程的思想主要是针对大型软件设计而来的。面向对象编程使程序的扩展性更强、可读性更好,使得编程可以像搭积木一样简单。Python中一切皆对象。Python支持面向过程、面向对象、函数式编程等多种编程范式。面向对象和面向过程的区别面向过程思维:更加关注的是“程序的逻辑流程”,是一种“执行者”思维,适合编写小规模的程序。面向对象思维:更加关注的是“软件中对象之间的关系”,是一种“设计者”思维_python从入门到入坟
文章浏览阅读4.1w次,点赞12次,收藏14次。案例:绘制多个同心圆代码如下:import turtlet = turtle.Pen()my_colors = ("red", "green", "yellow", "black")t.width(4)t.speed(1)for i in range(10): # 0 1 2 3 4 t.penup() t.goto(0, -i*10) # 0, -100,-2..._python利用负循环画10个同心圆
文章浏览阅读240次。精通PKI网络安全认证技术与编程实现从实战出发,介绍了PKI应用开发过程和细节。《精通PKI网络安全认证技术与编程实现》共32章,分6篇,主要内容包括PKI基础知识、OpenSSL开发、CrytoAPI开发、JavaSecurity开发、电子商务网站应用、PKI技术应用等,涉及C语言、Java语言、JSP、ASP/ASP.NET、PHP等开发语言。为了方便读者深入了解PKI,《精通PKI网络安全认..._api安全技术与实战pdf
文章浏览阅读644次。函数名: modf头文件:函数原型: double modf(double value, double *iptr);功 能: 求双精度数的小数部分参 数: double value 为要操作的双精度数 ,double *iptr 为要传回整数部分的变量指针返回值: 返回value的小数部分程序例: 分别求出双精度number的小数部分和整数部分,并将结果输出#include#includ..._c语言求一个双精度数的整数部分和小数部分
文章浏览阅读288次。最近在学习DDos相关知识,参考一些只是,做了摘要,供自己参考。 参考:http://blog.csdn.net/xlf13872135090/article/details/8059538SYN Flood 攻击原理 利用TCP协议缺陷,发送了大量伪造的TCP连接请求,使得被攻击方资源耗尽,无法及时回应或处理正常的服务请求。一个正常的TCP连接需要三次握手,首先客户端发送一个包含SYN标志的数_http存在synflood吗
文章浏览阅读775次。我们之前学习的都是针对一个表的操作。如果要进行多个表之间的操作,就要用到外键把他们关联起来。外键的作用:能够让多个表进行关联,使表与表之间有联系,实现共性抽取。如果数据项比较多的情况下,把所有数据都存放在一个表中,如果表太大,影响操作效率。解决办法就是把一个表拆分成多个表,并且用外键去关联。例子:如果要设计一个员工表1)员工表:编号、姓名、年龄、性别、所在分公司、所在部门2)部门表:编号、部门名称、部门经理、主要任务3)公司表:编号、分公司名,地址、电话、法人把公司和部门的数据抽取出来,形成_sql查询外键id的数据
文章浏览阅读220次。line-height: 设置元素当中的每行文本的行高(行间距) .test { width: 300px; height: 40px; margin-bottom: 20px; padding: 10px; background-color:..._段落元素设置样式
文章浏览阅读1.3k次。目标:使用OpenCV cv::inRange 函数进行基本的 阈值操作, 基于像素值在HSV色度空间的范围进行对象检测理论:前一篇文章中我们学习了如何使用cv::threshold 阈值函数进行阈值操作 本文我们将学习使用 cv::inRange 来进行处理 原理是一样的但是现在我们增加了一个我们所需要的 【像素值的范围】HSV色度空间 HSV colorspaceHSV ..._inrange和cv2.threshold一起使用
文章浏览阅读154次。 瑜伽培训课程层出不穷,但市面上都没有教授瑜伽老师们如何“教”的系统培训。瑜伽行业表面看似繁荣,但大多数老师缺失教学的“灵魂”。 为此,心合瑜伽学院王梓涵院长结合多年来积累的经验以及瑜伽老师的痛点,与心合教学团队不断打磨,开创瑜伽培训先河,首创贴合瑜伽老师的『瑜伽教学法』,教学法正是指导瑜伽老师们如何上课的法门! 不少老师们,有时会有这样的问题: “我把正确的口令讲出来了,但是会员好像不听我的口令,并没有按照口令去做,需要我不停地辅助和做示范才能完成...” 一个优秀的老师,总可以_会员病了无法来上瑜伽课怎么说
文章浏览阅读2.2w次,点赞12次,收藏113次。随机森林概述随机森林是集成学习方法bagging类中的翘楚。与集成学习boosting类的GBDT分庭抗礼。bagging类集成学习采用的方法是:用部分数据 or 部分特征 or 多个算法 训练一些模型;然后再组合这些模型,对于分类问题采用投票多数表决,回归问题采用求平均。各个模型训练之间互不影响,天生就适合并行化处理。在如今大数据时代背景下很有诱惑力。 主要效果:重点关注降低方差,..._随机森林及其调参
文章浏览阅读1.5k次,点赞2次,收藏2次。解决Exception: org.apache.hadoop.io.nativeio.NativeIO$Windows.access0(Ljava/lang/String;I)Z和Error: JAVA_HOME is incorrectly set.Please update D:\Software\hadoop260\conf\hadoop-env.cmd‘-Xmx512m’ 不是内部或外部命令,也不是可运行的程序或批处理文件。这个错误目前我知道的有以下几种解决办法:一、查看hadoop安装是_org.apache.hadoop.io.nativeio.nativeio$windows.access0(ljava/lang/string;i)z
文章浏览阅读2.6k次。我的是linux系统,那么要怎么样才能查看防火墙有没有开启呢?下面由学习啦小编给你做出详细的linux查看防火墙是否开启方法介绍!希望对你有帮助!linux查看防火墙是否开启方法一:service iptables status可以查看到iptables服务的当前状态。但是即使服务运行了,防火墙也不一定起作用,你还得看防火墙规则的设置 iptables -L在此说一下关于启动和关闭防火墙的命令:1..._linux防火墙服务找不到