什么是动态规划? 动态规划,英文名称:Dynamic Programming,简称DP。 如果某一问题有很多重叠子问题,使用动态规划是最有效的。 动态规划中的每一个状态一定由上一个状态推导而出,这一点...
代码随想录10:贪心算法
什么是贪心算法 贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 贪心的解题步骤 将问题分解为若干子问题 找出适合的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解 分发饼干 假...
代码随想录09:回溯算法
什么是回溯法? 回溯法:回溯搜索法,是一种搜索方法,回溯是递归的副产品,只要有递归就会有回溯。 回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案 回溯法解决的问题 组合问题:N个数里面按一定规则...
代码随想录08:二叉树
理论基础 种类: 满二叉树 完全二叉树 二叉搜索树 平衡二叉搜索树 存储: 链式存储(指针) 顺序存储(数组) 遍历方式: 深度优先遍历(DFS) 前序遍历(中左右) 中序遍历(左中右) 后续遍历(左...
代码随想录07:栈与队列
栈与队列 栈:先进后出 队列:先进先出 栈用于处理匹配问题 有效的括号 问题描述:给定一个只包含 '('、')'、'['、']'、'{'、'}' 的字符串,判断是否有效 左括号必须和右括号匹配 左括号...
代码随想录06:双指针法
双指针法在数组、链表的操作中是非常常见的,很多考察数组、链表、字符串等操作的面试题都会使用双指针法。 常见的题目类型: 移除元素 反转字符串 替换空格 反转字符串中的单词 反转链表 删除链表中倒数第N...
代码随想录05:字符串
反转字符串 输入:hello 输出:olleh 思路:双指针法,头尾双指针,互相交换,然后向中间平移,当头尾指针相交时结束 def reverse(s): first = 0 end = len(s)...
代码随想录04:哈希表
什么是哈希表? 英文名 Hash Table,中文名 散列表。 官方解释:哈希表是根据关键码的值而直接进行访问的数据结构。 举例:数组是哈希表,关键码是 0、1、2...,值是 array[0]、ar...
代码随想录03:链表
理论基础 单链表:一个数据域 + 一个指针域(指向下个节点),最后一个节点指向空。 双链表:一个数据域 + 两个指针域(一个指向上个节点,一个指向下个节点)。 循环链表:链表首位相连。 链表定义 st...
代码随想录02:数组
理论基础 数组是存放在连续内存空间上的相同类型数据的集合。 数组下标从0开始。 数组内存空间的地址是连续的。 二分查找 问题:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 tar...