- 博客(90)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 排序算法总结（附动图和python实现）
冒泡排序冒泡排序要对一个列表多次重复遍历。它要比较相邻的两项，并且交换顺序排错的项。每对 列表实行一次遍历，就有一个最大项排在了正确的位置。大体上讲，列表的每一个数据项都会在 其相应的位置 “冒泡”。如果列表有 n 项，第一次遍历就要比较 n-1 对数据。需要注意，一旦列表中最大(按照规定的原则定义大小)的数据是所比较的数据对中的一个，它就会沿着列表一直后移，直到这次遍历结束。# 冒泡排序...
2019-02-17 10:10:05
688
原创 求连续子数组和等于给定目标值的区间--面试题
题目给定n个数和一个target，输出连续区间和为target的所有区间写代码的时候遇到的问题保存区间内元素和，区间变化加减操作即可，而不是每次对区间求和，这样时间复杂度就是O(n)了，否则是O(n^2)，因为还要遍历区间内部元素如果初始化元素和为0，样例，arr = [4] ，target = 4，应该返回[0,0]，出错。因此，初始化为数组第一个元素j循环向后加时，防止越界；当区间...
2019-07-02 16:16:27
5043
3
原创 两个有序数组中第k小的数
题目给定两个已经排序好的数组，找到两者所有元素中第k大的元素思路方法一：归并排序，设立两个指针，依次向后遍历比较大小，时间复杂度O(m+n)，即两个数组长度之和方法二：二分查找，充分利用有序信息，递归终止条件:如果一个序列为空，那么第k个元素就是另一个序列的第k个元素；如果k = 1，那么直接返回min(A[0],B[0]) ；如果A[p - 1] == B[q - 1]，则...
2019-05-24 10:30:31
3275
1
原创 leetcode 72. Edit Distance
题目求两个词的编辑距离，可以进行 插入，删除，替换三种操作。思路动态规划状态定义：dp[i][j]表示从word1[0:i-1]变换到word2[0:j-1]的最小编辑距离状态初始化：第一行和第一列都好解释，因为两个字符串都可以删除至空值“”，然后相等状态转移：注意，更新dp[i][j]时，判断的是word1[i-1] 和 word2[j-1]代码class Solutio...
2019-05-23 20:54:49
201
原创 189 旋转数组
两种思路第一个，开辟一个数组，i下标存储原数组中 i+k mod n下标的元素，再依次赋值给原数组。空间复杂度O(n)第二个，三次逆序数组定义 reverse 逆转方法：将数组元素反转，比如 [1,2,3,4] 逆转后变成 [4,3,2,1]对前 n - k 个元素 [1,2,3,4] 进行逆转后得到 [4,3,2,1]对后k个元素 [5,6,7] 进行逆转后得到 [7,6,5]将前...
2019-05-19 23:42:10
189
原创 329. Longest Increasing Path in a Matrix
题目二维数组（矩阵）中的最长递增路径长度思路动态规划状态 ： dp[ i ] [ j ]表示以当前位置为结尾的最长递增路径长度，状态转移， 从上下左右走一步到当前位置，上下左右最大的加一。代码class Solution: def inarea(self, x, y, m, n): if 0 <= x < m and 0 <= y < ...
2019-05-08 15:35:14
102
原创 LeetCode 300. Longest Increasing Subsequence
题目求最长上升子序列（不要求连续）思路动态规划状态：取第 i 个元素的条件下，得到的最长上升子序列长度状态转移：dp[i] = max(dp[0]…dp[j]…dp[i-1]) + 1 且满足 nums[j] < nums[i]两重循环，遍历数组，遍历当前元素之前的所有dp值初始化为1，因为如果是递减序列，结果是1返回值是所有dp值里最大的代码class Sol...
2019-05-05 10:55:30
86
原创 LeetCode 股票买卖系列问题
121 买卖一次记录遍历到当前为止的最小值，每次拿当前价格减去最小值，得到可能的收益，更新最大收益值，遍历一次数组。class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 minprice = float("...
2019-05-05 10:29:44
445
原创 LeetCode 152. Maximum Product Subarray
题目求最大乘积子数组思路因为正负数的关系，不能只用一个数组来存，需要存最大最小值状态定义：取 i 元素，能得到的最大/小乘积值状态转移：dp[i][0/1] = dp[i-1][0/1]*nums[i] 更新化简，用x, y 取奇偶来降低空间复杂度，使用两个长度为2的列表即可。代码class Solution: def maxProduct(self, nums: List...
2019-05-04 22:57:51
81
原创 LeetCode 120. Triangle
题目三角形数组的最小路径和思路自底向上的动态规划状态定义为：从最后一行开始走到第i，j位置的最小路径和状态转移方程：(i, j)值为：正下值(i+1, j)，和右下值(i+1, j+1)较小的，加上当前值初始化最后一行为本身，因为没有下一行。代码简化二维数组到一维，因为一次更新上一行的值只需要用到下一行的值class Solution(object): def mini...
2019-05-04 22:05:15
80
原创 LeetCode 22. Generate Parentheses
题目思路对2n个格子填上左或者右括号，有2^(2n)种可能，再依据不合法情况进行剪枝，先有左括号，再有右括号。写代码时，left，right表示还有多少个括号可以用，递归结束条件是，都用完了；递归时，如果左括号还没用完就加上，加右括号时，多一个条件，左括号剩下的个数要少于右括号剩下的个数，即左括号使用的个数要多于右括号使用的个数，这样才是合法的。代码class Solution(obje...
2019-05-02 20:02:27
91
原创 带重复元素的二分查找
循环条件，等于号要有，否则从[1]找1，就不进循环里了带重复元素，返回数组中第一个出现的index如果找到一个元素后，用while递归向前，要记得判断边界index会不会减到小于0，例如[-1,-1,-1,2,3,5]；当所有元素相同时，时间复杂度又退回O(n)最好的方法是，找到一个之后，判断是否与前一个数相同，如果相同则继续二分def find(nums,k): if len(nu...
2019-04-24 14:53:32
2434
原创 动态规划原理及例题
什么是动态规划斐波那契数列额外空间，n+1长度数组（0，1，…，n）自顶向下if n == 0: memo[0] = 0if n == 1: memo[1] = 1if memo[n] == [0]: meno[n] = memo[n-1] + memo[n-2]return memo[n]自底向上memo[0] = 0memo[1] = 1for i in ra...
2019-04-20 17:34:02
539
原创 回溯算法思路总结
注意点定义清楚递归函数函数的作用，及需要的参数，参数一般有（要搜索的对象，当前访问位置index，当前已有的一个中间结果，总的结果res，访问标记变量visited）递归调用函数后，记得回退，把当前值从当前结果中弹出，把参数重新置为未访问。递归函数的结束条件是，当前结果的长度等于要求的长度，或当前访问位置等于遍历对象的长度（其实就是越界一位，说明遍历完成），把当前结果加入总结果列表后返回。...
2019-04-18 22:05:17
1251
原创 LeetCode 51. N-Queens
题目思路对角线1，同一条对角线上坐标相加和相等对角线2，同一条对角线上坐标相减差相等各有2n-1条对角线代码class Solution: def solveNQueens(self, n): res = [] row = [] col = [0 for i in range(n)] diag1 = [0 f...
2019-04-18 20:50:15
114
原创 LeetCode 200. Number of Islands
题目思路回溯，递归函数的作用是把和当前陆地相邻的陆地都标为false。代码class Solution: def numIslands(self, grid: List[List[str]]) -> int: m = len(grid) if m == 0: return 0 n = len(grid...
2019-04-18 19:23:11
129
原创 LeetCode 79. Word Search
题目思路主函数内，两重循环遍历二维数组，调用回溯的递归函数，选择每个元素作为匹配的起始位置，一旦找到就返回true。递归函数的作用从当前位置开始board[startx][starty]寻找word[index,:]，结束条件是index取到最后一位时，当前位置的值等于要找的字母，返回true；递归过程要先判断当前位置的值是否等于要找的index位置的值，如果是再递归调用上下左右寻找下...
2019-04-18 15:58:20
107
原创 LeetCode 77. Combinations
题目组合，从数组中取k个数，返回所有可能的组合.思路定义一个start变量，每次从start往后取数字，不会重复取前面的数字，因为是组合，不考虑顺序。代码class Solution: def combine(self, n: int, k: int) -> List[List[int]]: res = [] if n<=0 or k...
2019-04-18 10:18:25
117
原创 LeetCode 46.Permutations
题目求数组全排列思路代码为了避免重复取出元素，设置used数组来标识是否用过这个数字。class Solution: def permute(self, nums): res = [] used = [0]*len(nums) if len(nums)==0: return res re...
2019-04-17 20:39:45
104
原创 LeetCode 17. Letter Combinations of a Phone Number
题目思路递归思路，从头开始遍历字符串，结果是，当前字符串能表示的字母 加上 后续所有字符能表示的字母串。代码class Solution: def letterCombinations(self, digits: str) -> List[str]: res = [] if digits == '': # 注意判断输入字符串为空的情况 ...
2019-04-17 18:50:06
85
原创 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree
题目思路两个值都小于根节点值，则在左子树中递归找公共根节点两个值都大于根节点值，则值右子树中递归找公共根节点一个大于等于根节点值，一个小于等于根节点值，则公共根节点为root本身。代码class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') ...
2019-04-17 18:17:08
111
原创 LeetCode 437. Path Sum III
题目思路先递归找包含根节点的路径数，再在左右子树中找不包含根节点（体现在sum不减root的值）的路径数。代码class Solution: def pathSum(self, root: TreeNode, sum: int) -> int: if root == None: return 0 res = 0 ...
2019-04-16 17:52:26
96
原创 LeetCode 257. Binary Tree Paths
题目思路递归终止条件：叶子节点，返回节点值过程：对每个左右子树的子路径，加上根节点的值代码class Solution: def binaryTreePaths(self, root: TreeNode) -> List[str]: res = [] if root == None: return res ...
2019-04-16 16:49:31
93
原创 LeetCode 112. Path Sum
题目思路递归实现，注意递归的终止条件，不是root==None，而是要到达根节点，即root.left == None and root.right == None。代码class Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if root == None: ...
2019-04-16 15:56:48
101
原创 LeetCode 347. Top K Frequent Elements
题目思路The first step is to build a hash map. Python provides us both a dictionary structure for the hash map and a method Counter in the collections library to build the hash map we need.This step ...
2019-04-15 15:28:40
129
原创 LeetCode 279 Perfect Squares
题目思路从大的数指向小的数，最短路径问题可以使用层序遍历的推广，广度优先遍历实现。代码def numSquares(n): if n <= 0: return 0 stack = [(n,0)] visited = [0]*(n+1) # 避免重复推入元素 visited[n]= 1 while stack !=[]: ...
2019-04-15 10:57:31
102
原创 二叉树的层序遍历
使用队列，队列中存储节点时，多用一个变量来存储节点所在的层数，也就是在队列中存n个包含两个元素的列表，[[node1,level1],[node2,level2],[node3,level2]]，当队列不为空时，先取出队列头，如果结果列表的长度等于当前节点对应的层数，那么就是该层的第一个节点，那么就加上一个空列表用于装新层的节点（例如level=0，len(res)=0;level=0; 就加上一...
2019-04-15 00:36:53
111
原创 LeetCode 二叉树最大最小深度
二叉树最大深度递归左右子树，返回较大的深度，结束条件是遍历到叶子节点的左右孩子为空，返回0；最后加上根节点的值.leetcode 104class Solution: def maxDepth(self, root: TreeNode) -> int: if root == None: return 0 return 1 ...
2019-04-13 22:40:07
141
原创 非递归遍历二叉树
递归遍历二叉树很简单，这里以 后续遍历为例子。def postorderTraversal(self, root: TreeNode) -> List[int]: ans = [] if root != None: ans.extend(self.postorderTraversal(root.left)) ans.extend(self....
2019-04-13 10:47:10
337
原创 LeetCode 2sum/3sum/4sum
题目nSUM问题是指，在一个数组中，找出n个数相加和等于给定的数，返回数的下标列表。2sum字典法建立 {元素：下标} 字典，遍历数组，判断target-x是否在字典里，如果在则返回结果，如果不在字典里就把当前元素加入字典。不在一开始遍历数组建字典，为了避免重复元素抵消下标，比如[2,2]，只能存一个下标。时间复杂度为O(n)class Solution: def twoSum...
2019-04-11 21:45:05
99
转载 4.11 村庄买卖酒
题目直线上有n（2<=n<=100000)个等距的村庄，每个村庄要么买酒，要么卖酒。设第i个村庄对酒的需求为ai(-1000<=ai<=1000),其中ai>0表示买酒，ai<0表示卖酒。所有村庄供需平衡，即所有ai之和等于0。把k个单位的酒从一个村庄运到相邻村庄需要k个单位的劳动力。计算最少需要多少劳动力可以满足所有村庄的需求（使得数组中所有数为0的最少移...
2019-04-11 20:58:40
125
原创 01背包 动态规划 python
题目给定一组物品大小及其对应的价值，求背包大小固定的小偷能获得的最大收益是多少思路贪心不能保证收益最大动态规划递推式：c[i, w]表示到第i个物品为止，在总空间为w的情况下，能得到的最优解（选或者不选第i个物品）创建二维数组来表示c[i,w]，其中i最大值为物品个数，w最大值为背包总大小，起始值为0，因此是一个(n+1)*(w+1)的二维数组。代码def packege(v,w...
2019-04-06 21:58:43
456
1
原创 4.2 LeetCode 从排序数组中删除重复元素
题目思路用number标记最后一位已经存好的不同的数在数组中的位置，遍历数组，遇到和number位不同的数，先把number加一，然后把第i个数赋值给number位置，number初始化为0，所以第一位一定相等，因此最后返回长度要加一。代码if not nums: print(0) number = 0for i in nums: if i != nums[numbe...
2019-04-02 09:32:32
85
原创 3.28 剑指offer 扑克牌顺子
题目从扑克牌中随机抽5张牌，判断是不是顺子，即这5张牌是不是连续的。2～10为数字，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。牛客网直接输入转换过的数字数组，王取为0。思路方法一先统计王的数量，再把牌排序，如果后面一个数比前面一个数大于1以上，那么中间的差值就必须用王来补了。看王的数量够不够，如果够就返回true，否则返回false。tips：排序的数组，可以通过...
2019-03-28 20:56:38
72
原创 3.22 剑指offer 数组中只出现一次的数字
题目一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。思路要求空间复杂度为O(1)，时间复杂度为O(n)。简化问题，如果只有一个数只出现一次，其他数字都出现两次，那么利用异或运算的性质。对数组中每个元素异或，相同的两个数异或为0，剩下的就是出现1次的数字。但是现在有两个只出现1次的数字，我们把所有数字异或，得到结果肯定不为0；找到某一位不为0，...
2019-03-22 23:09:23
73
原创 3.21 LeetCode 使用dic解决问题
1. Two Sum从无序数组中，找到两个数求和为target，返回下标。字典，数值：索引避免重复数字被覆盖，先从字典里查找target - nums[i]，如果找到则返回，没找到就加入字典。 def twoSum(self, nums: List[int], target: int) -> List[int]: dic = {} for i i...
2019-03-21 21:04:06
164
原创 3.21 剑指offer 平衡二叉树
题目一棵树的任意节点，左右子树的深度差值不大于1，为平衡二叉树。判断是否是平衡二叉树。思路如果对每个节点的左右子树都调用获取深度的递归子函数，再判断差值，这样，计算到上层节点时，会重复计算下层节点的深度。改进的方法是，一次后序遍历整个二叉树，递归从下到上返回左右子树的深度时，判断差值，如果大于1直接返回-1。因此在获得深度时，如果等于-1说明已经不平衡了，就返回-1给上层函数。 如果不大于...
2019-03-21 17:04:05
92
原创 3.21 剑指offer 数字在排序数组中出现的次数
题目在排好序的数组中，统计数k出现的次数思路思路一使用二分查找，如果在中间出现，循环判断前一个数是否一样，后一个数是否一样，直到找到不一样的为止思路二先找到第一个k，再找最后一个k，下标相减得到计数都使用二分查找，第一个k，如果k和中间值相等，那么要判断k是不是第一个，前一个值是否是k，如果不是，那中间值就是第一个k；如果是k，那么去前半段找第一个k最后一个同理注意二分查找中...
2019-03-21 11:28:18
59
原创 3.15 剑指offer 按之字形顺序打印二叉树
题目请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。思路层序遍历的进阶每行的节点的访问顺序是相反的，我们可以用两个栈来隔行存储，一个栈中根据另一个栈的栈顶元素的“左结点->右结点”的顺序存储节点，而另一个栈根据另一个栈的栈顶元素的“右子树->左子树”的顺序存储节点，直到两个栈都为空。...
2019-03-16 00:11:58
96
原创 3.15 剑指offer 滑动窗口的最大值
题目给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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,5,1...
2019-03-15 16:02:19
92
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人