daipi

算法精讲

bigdata(1) git(1) JAVA基础(2) Java开发(2) python(6) 操作系统(12) 数据库(5) 数据结构(1) 机器学习(1) 测试基础知识(6) 笔试(1) 统计基础(1) 计算机网络(5) 论文(1) 软件操作(1) 面试复盘(1)

/ 注册

全部文章 / 算法精讲（共10篇）

回溯法之有效括号

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。说明：解集不能包含重复的子集。例如，给出 n = 3，生成结果为： [ "((()))", "(()())", "(())()", "()((...

八皇后回溯法

2020-05-11

0 584

动态规划之上楼梯

案例一：有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。为了防止溢出，请将结果Mod 1000000007 给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。测试样例：1返回：1 暴力搜索法code # -*- coding:utf-8 -...

动态规划上楼梯

2020-03-16

0 655

动态规划之找零钱问题

案例一：有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成ai...

动态规划找零钱

2020-03-15

0 1233

平衡二叉树判断

平衡二叉树（AVL树） 1.空树是平衡二叉树。2.如果一棵树不为空，并且其中所有的字数都满足各自的左子树和右子树高度差不超过1. 判断是否为平衡二叉树思路：需要辅助函数来求出树的深度。遍历每一个节点，同时判断每一个节点的左右子树的深度差即可完成平衡二叉树的判别。（考点：树的遍历，树的深度） #求树...

平衡二叉树

2020-03-10

0 601

二叉树的四种遍历

二叉树三种遍历的非递归实现利用栈来实现存储树的结构方式。先序遍历实现步骤： 1.初始化一个栈，将头节点压入栈中。2.弹出栈顶元素并将该点记为cur，打印该点，判断该点的右节点是否为空，不为空则入栈，判断该节点的左节点是否为空，不为空则入栈。3.重复二步骤，直到栈中为空，遍历结束。 d...

二叉树遍历递归循环

2020-03-10

0 590

二分搜索

二分搜索提醒：取得中点写法：常规写法：mid=(left+right)/2 由于上述写法可能造成溢出，更安全的写法：mid=left+(right-left)/2 案例一：对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。给定一个数组arr及...

二分搜索

2020-03-10

0 599

链表判环练习

案例一：如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。给定一个单链表的头结点head（注意另一个参数adjust为加密后的数据调整参数，方便数据设置，与本题求解无关)，请返回所求值。思路...

链表有环链表

2020-03-09

0 620

链表回文判断

链表类型题目注意事项：需要注意一个节点和空链表的特殊情况。需要考虑链表中特殊位置的存在的处理方式（tail 和head）注意循环中使用next时需要判断该节点本身是否存在，如果不存在则不能使用next。链表类型的题在其他其他数据结构的辅助下进行解题，空间复杂度提高，但是解题会更加的简单。 ...

链表回文栈

2020-03-07

0 620

排序算法

一.按时间复杂度划分时间复杂度为o(n^2) 冒泡排序：从第一个数与后面数对比，比后一位数大则调换位置，小于等于不用换位置。选择排序：从所有数中选出最小的数放在头部置上，再从剩余数选出最小放在开头位置。插入排序（老是忘记）：前面数比后面数小则与后面数换位置。时间复杂度为o(...

排序

2020-03-07

0 659

队列和栈基础与算法讲解

队列和栈队列的基本操作 1.队列：先进先出，与栈操作不同，push操作为在队头加入元素，而pop操作是从队尾弹出一个元素。栈和队列的基本操作都是时间复杂度为O(1)的操作队列可以理解为一条直线，操作在两端执行，而栈理解为一条射线，只在一端操作。案例一：编写一个类,只能用两个栈结构实现队列,...

python 队列和栈数据结构

2020-03-04

0 972