- 博客(60)
- 收藏
- 关注
RSS订阅原创 【LeetCode】24.两两交换链表中的节点(python 版)
题目描述：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例:给定 1->2->3->4, 你应该返回 2->1->4->3.思路：方法一：迭代方法：基础的三指针法，分别指向需要交换的两个节点和它们的前一个节点，注意节点交换时各个链的连接顺序。因为头结点会与下一个节点...
2020-05-13 20:53:56
428
原创 【LeetCode】23.合并 K 个排序链表(python版)
题目描述：合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->6思路：这个题是简单难度的《合并两个排序链表》的加强版。方法一：一个很容易想的思路是：先合并前两个链...
2020-02-09 16:14:46
237
原创 【LeetCode】14.最长公共前缀(python版)
题目描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。示例 1:输入: ["flower","flow","flight"]输出: "fl"示例 2:输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。说明:所有输入只包含小写字母 a-z 。思路：本题虽然只是“容易”等级的题目，但是...
2020-01-21 14:43:19
559
1
原创 【LeetCode】22.括号生成(Python 版)
题目描述：给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。例如，给出 n = 3，生成结果为：[ "((()))", "(()())", "(())()", "()(())", "()()()"]思路：方法一：暴力法：枚举出所有的括号组合，再判断其是否有效class Solution: def generateP...
2020-01-20 15:16:46
1509
原创 【LeetCode】19. 删除链表的倒数第N个节点(python 版)
题目描述：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。示例：给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：给定的 n 保证是有效的。进阶：你能尝试使用一趟扫描实现吗？思路：# Definition for singly-linked...
2020-01-20 09:45:47
389
原创 【LeetCode】17.电话号码的字母组合(python版)
题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例:输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].说明:尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。思路：回溯法(穷举法)...
2020-01-19 15:33:44
1207
原创 【LeetCode】6.Z字形变换(python版)
题目描述：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：L C I RE T O E S I I GE D H N之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。请你实现这个将字符串进行指定行数变换...
2020-01-19 10:42:14
340
原创 【LeetCode】11.盛最多水的容器(python版)
题目描述：给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水...
2020-01-17 10:41:56
470
原创 【LeetCode】788.旋转数字(python版)
题目描述：我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。现在我们有一个正整数 N, 计...
2020-01-16 11:34:20
300
原创 【LeetCode】5.最长回文子串(python版)
题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例 2：输入: "cbbd"输出: "bb"思路：暴力算法：遍历字符串，以每个字符作为中心词，往两边延伸判断是否左右两边字符是否相等。每次只需要维护延伸得到的最长回文子串。暴力算法的时...
2020-01-16 11:19:06
535
原创 【LeetCode】442.数组中重复的数据(python版)
题目描述：给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。你可以不用到任何额外空间并在O(n)O(n)O(n)时间复杂度内解决这个问题吗？示例：输入:[4,3,2,7,8,2,3,1]输出:[2,3]...
2020-01-08 11:21:19
936
1
原创 【LeetCode】无重复字符的最长子串(python版)
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke...
2019-12-25 16:41:44
242
原创 【总结篇】求众数
np.bincount()解释：简易版：对于数组[11, 4, 4, 11, 3, 9, 8]，看做是编号分别为11, 4, 4, 11, 3, 9, 8的7个小球。为了将小球归置整齐，需要放到对应编号的桶中，所以需要11+1=12个桶，同样编号从0-11。最后按照桶编号依次输出桶中包含的小球个数(整个过程其实就是计数排序)。很显然编号必须是非负整数。详细版参考这里，...
2019-12-25 14:19:09
397
原创 【每日一练】最长斐波那契子序列
题目描述：给定一个数组，找出其中最长的子序列，满足该子序列是斐波那契子序列注： 如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：n >= 3对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}思路：本题一开始想岔了，一直以为Fibonacci数列必须是严格按照{1，1，2，3，5，8……}的...
2019-10-25 16:04:50
604
原创 【LeetCode】【137. Single Number II】(python版)
Description：Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.Note:Your algorithm should have a linear runti...
2019-08-21 16:18:32
170
原创 【LeetCode】【18.4sum】（python版）
Describe：Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the...
2019-06-14 21:18:03
166
原创 《剑指offer》【最小的k个数】（python版）
问题描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。思路：这个算是面试中常见题了，这里总结一下解决方法(注意判断k的合法性)：1、全部升序排序，输出前k个数字，最小时间复杂度为2、由于不要求最小的k个数按序输出，参考快排中partition函数思想：每轮排序之后枢轴左边数字都比它小，右边数字都比它大...
2018-10-23 17:18:54
5141
2
原创 【LeetCode】【136. Single Number】(python版)
Description：Given a non-empty array of integers, every element appears twice except for one. Find that single one.Note:Your algorithm should have a linear runtime complexity. Could you implement...
2018-09-02 14:56:30
238
原创 《剑指offer》【出现次数超过一半的数】(python版)
问题描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。思路： 1、排序，计算其中位数的出现次数，如果超过一半那么即为该数，否则不存在。2、借鉴快排思想，如果一个数出现超过一半，那么如果以该数为枢轴，进行一次快排，那么这个...
2018-09-02 11:09:52
466
原创 基础算法之排序算法总结(python版)
常见排序算法包括有：冒泡，简单选择，直接插入，快排，归并排序，堆排序，希尔排序目录冒泡排序思想：复杂度分析： 选择排序思想：复杂度分析直接插入排序思想：复杂度分析希尔排序思想复杂度分析快速排序思想：复杂度分析 快排优化 归并排序思想复杂度分析归并优化堆排序思想复杂度分析 总结冒泡排序思想：...
2018-09-02 10:49:53
303
原创 【每日一练】区间最大乘积
问题描述：给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:[6] = 6 * 6 = 36; [2] = 2 * 2 = 4; [1] = 1 * 1 = 1; [...
2018-09-02 10:46:24
1875
原创 【LeetCode】【220. Contains Duplicate III】(python版)
Description： Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolu...
2018-09-01 20:41:17
1934
原创 【LeetCode】【84. Largest Rectangle in Histogram】(python版)
Description：Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.Above is a histogram where ...
2018-08-22 11:40:35
282
原创 【LeetCode】【395. Longest Substring with At Least K Repeating Characters】(python版)
Description： Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.Example 1:Input:s = "aa...
2018-08-21 20:43:06
631
原创 【LeetCode】【3. Longest Substring Without Repeating Characters】(python版)
Description： Given a string, find the length of the longest substring without repeating characters.Example 1:Input: "abcabcbb"Output: 3 Explanation: The answer is "abc", which the length is 3....
2018-08-21 19:09:55
587
原创 【每日一题】【暴力求解】最大点集合
问题描述：P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。输入描述:第一行输入点集的个数 N，...
2018-08-11 20:11:21
4229
原创 【每日一练】【暴力求解】堆棋子
问题描述：小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.输入描述:输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数第二行为n个...
2018-08-11 14:22:53
437
原创 【每日一练】【贪心策略】疯狂队列
题目描述： 小易老师是非常严厉的,它会要求所有学生在进入教室前都排成一列,并且他要求学生按照身高不递减的顺序排列。有一次,n个学生在列队的时候,小易老师正好去卫生间了。学生们终于有机会反击了,于是学生们决定来一次疯狂的队列,他们定义一个队列的疯狂值为每对相邻排列学生身高差的绝对值总和。由于按照身高顺序排列的队列的疯狂值是最小的,他们当然决定按照疯狂值最大的顺序来进行列队。现在给出n个学生的身高,...
2018-08-11 10:13:07
206
原创 【每日一练】【动态规划】合唱
问题描述： 小Q和牛博士合唱一首歌曲,这首歌曲由n个音调组成,每个音调由一个正整数表示。 对于每个音调要么由小Q演唱要么由牛博士演唱,对于一系列音调演唱的难度等于所有相邻音调变化幅度之和, 例如一个音调序列是8, 8, 13, 12, 那么它的难度等于|8 - 8| + |13 - 8| + |12 - 13| = 6(其中||表示绝对值)。现在要对把这n个音调分配给小Q或牛博士,让他们演...
2018-08-10 20:46:45
549
原创 【LeetCode】【322. Coin Change】(python版)
Description： You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that am...
2018-07-28 19:08:11
2019
原创 【LeetCode】【837. New 21 Game】(python版)
Description： Alice plays the following game, loosely based on the card game “21”.Alice starts with 0 points, and draws numbers while she has less than K points. During each draw, she gains an inte...
2018-07-28 18:16:21
1467
原创 【LeetCode】【5. Longest Palindromic Substring】(python版)
Description： Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.Example 1：Input: "babad"Output: "bab"Note: &a
2018-07-28 15:38:25
346
原创 《剑指offer》【把字符串转换成整数】（python版）
题目描述： 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。 输入描述： 输入一个字符串,包括数字字母符号,可以为空 输出描述： 如果是合法的数值表达则返回该数字，否则返回0 示例1输入+21474836471a33...
2018-07-18 22:07:59
1454
原创 《剑指offer》【扑克牌的顺子】（python版）
题目描述： 从扑克牌中随机抽5张牌，判断是不是一个顺子， 即这5张牌是不是连续的。2～10为数字本身， A为1。 J为11、Q为12、 K为13。大、小王可以看成任意数字。(为了方便，输入数组中0代表大小王)思路： 本题思路很好想，相信玩过QQ斗地主的人都知道什么叫赖子牌，本题实际是一个意思。所谓顺子只需要判断两点：1、五张牌没有重复 2、王牌个数等于顺子中空缺的位置。class So...
2018-07-18 21:47:17
1992
原创 《剑指offer》【调整数组顺序使奇数位于偶数前面】（python版）
题目描述： 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分思路： 我认真看了一下，题目应该是要求在原地调整，所以这里不能再开辟一个数组 第一种：从头往尾扫描数组，遇到一个偶数就把它提出来，依次把其后的数字前移一格，最后将偶数插入末尾的空位。时间复杂度为O(n2)O(n2)O(n^2) 第二种：采用两指针分别从首...
2018-07-18 21:36:42
2679
2
原创 《剑指offer》【第一次只出现一次的字符】（python版）
题目描述： 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1.思路： 第一种：扫描字符串，将每个字符与其它所有字符进行比较，如果没有相同，说明他就是第一个只出现一次的字符。算法时间复杂为O(n2)O(n2)O(n^2)第二种：采用hash表，一次扫描字符串记录字符出现的次数数，第二次扫描字符串...
2018-07-18 20:44:11
874
原创 《剑指offer》【滑动窗口的最大值】（python版）
题目描述： 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2...
2018-07-17 21:52:46
4148
1
原创 《剑指offer》【二叉搜索树的后序遍历序列】（python版）
题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。# -*- coding:utf-8 -*-class Solution: def VerifySquenceOfBST(self, sequence): # write code here if len...
2018-07-17 20:18:57
1601
原创 《剑指offer》【树的子结构】（python版）
题目描述： 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）思路： 本题可以分为两步，第一步：找到A中与B的根结点值相等的结点R，第二步：判断以R为根结点的子树是否包含B一样的结构。本题思路不难，但是需要格外注意对指针空值的判断。# -*- coding:utf-8 -*-# class TreeNode:# def __init_...
2018-07-16 16:25:40
979
原创 《剑指offer》【机器人的运动范围】（python版）
题目描述： 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？思路： 本题与 def m...
2018-07-16 16:14:34
2283
4
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人