您当前所在分类目录: 算法

[leetcode题解] 16. 3Sum Closest

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). Given an array nums of …

Continue reading

13. Roman to Integer

罗马数字包含以下七种字符:I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做&nb …

Continue reading

leetcode刷题汇总

leetcode题目不断刷新,大家也都一直在刷,本文记录作者刷题记录,一直更新,权当抛砖引玉,欢迎大家一块交流学习。如果各位leetcoder发现题解有问题,欢迎指正交流,也希望大家可以提出更新颖的解题方法。新建leetcode算法交流群259150720,欢迎leetcoder进群交流。 0001 Two Sum array Easy 0002 Add Two Numbers linked li …

Continue reading

[leetcod题解]684. 冗余连接

在本问题中, 树指的是一个连通且无环的无向图。 输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ,满足 u < v,表示连接顶点u 和v的无向图的边。 返回一条可以 …

Continue reading

[pat题解]1108.Finding Average

PAT1108题,本题要求输入N个字符串,然后判断这些字符串是否表示一个合法的数,将所有合法的数求和并计算其均值。对于不合法的数,对其进行输出。 合法规则:值必须在[-1000, 1000]范围内,并且精度不能超过小数点后两位。规则比较简单。 本题注意点: 1.要判断精度,比如1.000,精度为三位小数,不符合规则,则表示该数是非法的。 2.要判断该字符串能否表示一个数,比如aaa,显然不能表示一 …

Continue reading

[华为OJ题解]特殊要求字符串排序

本题是一个简单排序的题目,但是题目中对于不同字符给予不同的处理,稍微麻烦一点。主要涉及大小写忽略的稳定排序。输出的时候要固定非字母字符的位置等知识点。 题目要求如下: 规则1:英文字母从A到Z排列,不区分大小写。       如,输入:Type 输出:epTy 规则2:同一个英文字母的大小写同时存在时,按照输入顺序排列。     如,输入:BabA …

Continue reading

[华为OJ题解]求解最小公倍数

华为oj题解,给定两个数,求这两个数的最小公倍数。两个数的最小公倍数求法为两数的乘积除以两数的最大公约数,所以,本质上本题就是求解两个数的最大公约数问题。求解最大公约数直接使用辗转相除法进行求解即可。代码如下: #include <iostream> #include <string> using namespace std; int gcd(int a, int b) { …

Continue reading

[leetcode题解]215.Kth Largest Element in an Array(数组中找第k大数)

leetcode,215,Kth Largest Element in an Array,给定一个包括若干元素的数组以及一个k,要求在数组中找出第k大的数。 通常的思路是排序,然后可以快速找到第k大的数,时间复杂度o(nlogn)。比较好的方法是借助快排的思想,一次轴分,可以以o(n)的时间复杂度找到第k大数。 c++代码: class Solution { public: //author:凌风 …

Continue reading

[pat题解]1074.Reversing Linked List(25)

本题要求对一个链表进行分组逆置,给定K,每K个元素为一组,将组中元素逆置,如果最后一组元素不足K个,则不做处理。 本题个人做法为使用map来组织链表结构,可以方便的进行查询和处理。 c++代码如下:  #include <algorithm> #include <cstdio> #include <iostream> #include <vect …

Continue reading

[leetcode题解]143. Reorder List(链表重排序)

leetcode第143题,recorder list,属于linked-list相关的题目。 题目给定一个单链表,然后要求按给定的顺序重新排列所有元素,要求在原地做,而且不能修改节点中的值,只能修改节点的插入顺序。重排序的规则如下示例: L:a0->a1->a2->a3…..->an 将其修改为L:a0->an->a1->an-1->& …

Continue reading

[leetcode题解]2.Add Two Numbers

leetcode,2,Add Two Numbers,给定两个单链表,将两个单链表从左到右进行相加,题目中已知不会出现前导0。本题可以直接对两单链表同时进行遍历相加即可,保留一个进位,检测最后是否要进行正确进位,python和c++两种语言写,代码如下: python代码 class Solution(object): def addTwoNumbers(self, l1, l2): “”” :t …

Continue reading

[leetcode题解]19.Remove Nth Node From End of List(删除倒数N个元素)

leetcode,19,Remove Nth Node From End of List,给定一个单链表,删除倒数第N个元素,要求进行一遍遍历即可。思路是利用两个指针,一个提前走N步,然后另一个指针指向开头,两个指针同时走,当前面的指针到尾部时,后面的指针正好位于要删除的元素位置。为了得到要删除位置的前一个位置,可以加入一个预头,然后,前面的指针从头开始,后面的指针从预头开始。 c++代码: cl …

Continue reading

[leetcode题解]21.Merge two Sorted Lists(两排序链表合并)

leetcode,21,Merge Two Sorted Lists,单链表合并问题,合并两个已排序链表为一个完整的已排序链表。 直接使用两个指针依次比较其中值大小即可,小的插入,并且指针后移,最后不要忘记把剩下的非空链表加入链尾。 此题的升级版本为leetcode,23,Merge K Sorted Lists.  c++代码: class Solution { public: Lis …

Continue reading

[leetcode题解]23.Merge K Sorted Lists(多链表合并)

leetcode,23题,Merge K Sorted Lists,多排序链表合并为一个有序链表问题。可以直接使用priority_queue或者heap。 多个链表以vector形式组织,vector中可能含有空链表,所以建堆或者初始化优先队列之前先对vector进行过滤,将空链表过滤掉。 注意优先队列的写法,类型,底层容器,以及要用到的比较器,比较器是一个重载了括号操作符的普通类。 c++题解 …

Continue reading

[leetcode题解]24.Swap Nodes in Pairs(节点交换)

leetcode 第24题,将链表中相邻元素位置颠倒,题目要求不能改变元素节点中元素的值,只能改动节点位置。也就是要求在链表中删除插入。 python代码如下: # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = No …

Continue reading

[随手写]统计英文文本中每个单词出现的频率

给定一个文本文件,内部为纯英文文本即不会包含中文以及中文符号,要求统计出其中各不同单词的频率。 主要是过滤掉数字,英文标点符号,但是一个特例是类似can’t这类的上引号不能过滤掉,另外要注意单词间的分隔符可以为一个或者多个空白字符(空格、制表符、回车符),也可以为换行符或者标点符号。 主要步骤,第一步为从文件读取文本,然后全部转换为小写字母,然后将其中的所有数字和非单词的字符替换成空格 …

Continue reading

[leetcode题解]25.Reverse Nodes in k-Group(链表每k个元素逆置)

这个题很有意思,虽然标的难度为hard,但是其实就是链表相关知识点的一个小综合,比如尾插法,段遍历,双指针操作等。题目给定一个单链表和一个k值,要求将链表中的元素从表头开始每k个元素组成一个组,然后组内的元素进行逆置操作,如果最后一组不满k个元素,则该组中的元素顺序保持不变。特别的,题目中说操作过程中不能改变元素节点的值,只能对整个节点进行操作,这就要求我们要通过链表指针的操作来完成上述过程。 总 …

Continue reading

[leetcode题解]82.Remove Duplicates from Sorted List-II(排序链表保留唯一)

上一篇论文中写了一个排序链表去重的题目解法,那个题目要求对于重复的元素只保留一个,而本题给定一个排序链表,要求把重复的元素全部删除,所以与上个题目有点差异,但是解法可以基本一致,这里对每个元素,判断其是否唯一,如果不唯一就直接删除,如果唯一,那么就将这个唯一的元素拿出来插入新的链表中,最后将新的链表返回去即可。 题意演示 Given 1->2->3->3->4->4- …

Continue reading

[leetcode题解]61. Rotate List(链表旋转)

题目中给定一个单链表和一个数字k,要求将链表循环右移k次,每次将最右边的元素移动到最左边。最简单的思路先找到最后的k个元素的起始位置,然后把这k个元素直接搬到链表最前面并插入即可(可以使用尾插法,当然也可以把最后一个元素记录下来,然后直接将整段插入)。但是这里k的值可能非常大,是链表长度的好几倍,我们要先处理下k值,我们需要的k值是对链表长度取余得到的值,所以这里先写一个方法求得链表的长度,然后k …

Continue reading

[leetcode题解]83.Remove Duplicates from Sorted List(排序链表去重)

题目给定一个单链表,该单链表已排序,要求删除所有重复值的节点。因为链表已排序,所以相同的值的节点都相邻,所以本题是相邻节点去重问题,可以直接两个指针操作即可。比较简单的排序链表去重问题。一种逐个去重,一种把所有重复的找出来,直接去除所有重复元素,两种方法分别是python实现和c++实现。 python代码: class Solution(object): def deleteDuplicates …

Continue reading

[leetcode题解]86.Partition List(链表分割)

leetcode第86题,partition-list,是一个关于链表分割的题目。题目给定一个单链表和一个数x,要求链表中节点val小于x的节点全部在左边,而大于等于x的节点全部在右边,而且左右两边中的元素分别保持在原链表中的相对位置。总体来说就类似于快排中的partition部分。所以这个的实现可以直接使用快排的中partition方法直接在单链表上更换节点的值就好。 这里使用最原始的思路,就是 …

Continue reading