6 a546167160

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 9w+

求连续子数组和等于给定目标值的区间--面试题

题目给定n个数和一个target,输出连续区间和为target的所有区间写代码的时候遇到的问题保存区间内元素和,区间变化加减操作即可,而不是每次对区间求和,这样时间复杂度就是O(n)了,否则是O(n^2),因为还要遍历区间内部元素如果初始化元素和为0,样例,arr = [4] ,target = 4,应该返回[0,0],出错。因此,初始化为数组第一个元素j循环向后加时,防止越界;当区间...

2019-07-02 16:16:27

两个有序数组中第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

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

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

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

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

LeetCode 股票买卖系列问题

121 买卖一次记录遍历到当前为止的最小值,每次拿当前价格减去最小值,得到可能的收益,更新最大收益值,遍历一次数组。class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 minprice = float("...

2019-05-05 10:29:44

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

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

LeetCode 22. Generate Parentheses

题目思路对2n个格子填上左或者右括号,有2^(2n)种可能,再依据不合法情况进行剪枝,先有左括号,再有右括号。写代码时,left,right表示还有多少个括号可以用,递归结束条件是,都用完了;递归时,如果左括号还没用完就加上,加右括号时,多一个条件,左括号剩下的个数要少于右括号剩下的个数,即左括号使用的个数要多于右括号使用的个数,这样才是合法的。代码class Solution(obje...

2019-05-02 20:02:27

带重复元素的二分查找

循环条件,等于号要有,否则从[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

动态规划原理及例题

什么是动态规划斐波那契数列额外空间,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

回溯算法思路总结

注意点定义清楚递归函数函数的作用,及需要的参数,参数一般有(要搜索的对象,当前访问位置index,当前已有的一个中间结果,总的结果res,访问标记变量visited)递归调用函数后,记得回退,把当前值从当前结果中弹出,把参数重新置为未访问。递归函数的结束条件是,当前结果的长度等于要求的长度,或当前访问位置等于遍历对象的长度(其实就是越界一位,说明遍历完成),把当前结果加入总结果列表后返回。...

2019-04-18 22:05:17

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

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

LeetCode 79. Word Search

题目思路主函数内,两重循环遍历二维数组,调用回溯的递归函数,选择每个元素作为匹配的起始位置,一旦找到就返回true。递归函数的作用从当前位置开始board[startx][starty]寻找word[index,:],结束条件是index取到最后一位时,当前位置的值等于要找的字母,返回true;递归过程要先判断当前位置的值是否等于要找的index位置的值,如果是再递归调用上下左右寻找下...

2019-04-18 15:58:20

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

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

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

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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。