- 博客(20)
- 收藏
- 关注
RSS订阅原创 二分查找 概念以及一些例题
一、什么二分查找？二分查找，每次查找时，通过将待查找区间分成两部分，并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为 O(n)的数组，二分查找的时间复杂度为O(logn)。举例来说，给定一个排好序的数组 {3,4,5,6,7}，我们希望查找 4 在不在这个数组内。第一次，折半时考虑中位数5，因为5大于4,所以如果4存在于这个数组，那么其必定存在于5左边这一 半。于是我们的查找区间变成了 {3,4,5}。（注意，根据具体情况和您的刷题习惯，这里的 5 可以 保留也可以不保留，并不影响时间复杂
2020-10-17 11:21:02
366
转载 回溯法——关于n皇后的一些例题
昨天写了一篇博客：回溯法——从八皇后问题讲起现在来看一下几道Leetcode上面的例题：[版权声明] 本文部分内容转载自：1、回溯算法详解 作者：labuladong2、「手画图解」从N皇后问题看回溯算法 作者：笨猪爆破组一、解题思路回溯算法有固定的框架框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：1、路径：也就是已经做出的选择。2、选择列表：也就是你当前可以做的选择。3、结束条件：也就是到达决策树底层，无法再做选择的条件。再看两张4皇后的图：（因
2020-10-09 23:19:06
306
转载 回溯法——从八皇后问题讲起
本文部分内容转载自：八皇后问题（递归回溯算法详解+C代码）作者：苍之羽 仅作个人学习使用一、什么是回溯法？按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术就叫回溯法。二、回溯法和递归的联系：我们在回溯法中可以看到有递归的身影，但是两者是 完全不同、却有着联系 的两个概念。回溯法从问题本身出发，寻找可能实现的所有情况。和穷举法的思想相近，不同在于穷举法是将所有的情况都列举出来以后再一一筛选，而回溯法在列举过程如果发
2020-10-09 15:41:44
212
原创 递归和分治 Leetcode刷题集合
分治问题，由**“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子问题**，再将子问题进行处理合并，从而实现对原问题的求解。归并排序就是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为 1 的子数组；“治”即为把已经排好序的两个小数组合成为一个排好序的大数组，从长度为 1 的子数组开始，最终合成一个大数组。一、50. Pow(x, n)原题链接：https://leetcode-cn.com/problems/powx-n/
2020-10-06 23:46:47
307
原创 深度优先算法(二) 一些例题加深对DFS的理解
我在三天前写了一篇文章：深度优先算法入门(超级简单的例题入门)当然只理解概念是不行的，我们就做几道相似的题目来加深一下对DFS的理解吧。一、46. Permutations给定一个 没有重复 数字的序列，返回其所有可能的全排列。示例:输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], ...
2020-10-03 21:46:22
168
原创 深度优先算法DFS入门 (超级简单的例题入门)
参考文章：1、Leetcode Subset I & II 作者：算法鱼 （里面是java版本的代码）一、什么是 DFS？图的深度优先搜索（Depth First Search），和树的先序遍历比较类似。具体做法是：假设初始状态是图中所有顶点均未被访问，则从某个顶点V出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V有路径相通的顶点都被...
2020-10-02 23:05:19
1105
转载 动态规划 第6讲： 01背包问题&空间简化（322. 零钱兑换）
之前关于01背包问题和空间简化的博客：1、动态规划 第4讲： 01背包问题&空间简化 (基础入门篇)2、动态规划 第5讲： 01背包问题&空间简化 (LeetCode刷题1: 降维、二维、三维)本文部分内容转载于：1、Leetcode 官方题解 作者：Leetcode官方（LeetCode-Solution）2、The Change Making Problem - Fewest Coins To Make Change Dynamic Programming 作者：Back
2020-08-12 23:15:39
181
原创 动态规划 第5讲： 01背包问题&空间简化 (LeetCode刷题1: 降维、二维、三维)
前两天，写了一篇文章：动态规划 第4讲： 01背包问题&空间简化 (基础入门篇)，作为初步了解，接下来做几道题来巩固一下，每道题都有最初版和空间优化版的代码。一、416. 分割等和子集 （难易程度：medium）原题链接：https://leetcode-cn.com/problems/partition-equal-subset-sum给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。注意:每个数组中的元素不会超过 100数组的大小不会超过 2
2020-08-10 23:39:43
341
转载 动态规划 第4讲： 01背包问题&空间简化 (基础入门篇)
本文部分内容引用于：1、动态规划解决01背包问题 作者：Christal_R2、01背包理解及空间优化（动态规划） 作者：有理想的小树为了看懂这个01背包问题，还有空间简化（二维变成一维 or 三维变成二维），我足足花了一周的时间，看了无数篇博客和题解，终于大致明白了。一、什么是01背包问题？（1）问题描述：有N个物品，该物品有两个属性，重量w[i]，价值v[i]，有背包一个，承重为W；现在要求从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。每件物品都只有一件，
2020-08-08 00:27:53
445
原创 动态规划 第3讲： 子序列问题
最近在复习期末考试，又有点懒，更新博客的效率也下降了。话不多说，我们来刷一遍子序列问题，用动态规划的方法。一、300. 最长上升子序列 (难易程度：medium)原题链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/给定一个无序的整数数组，找到其中最长上升子序列的长度。示例:输入: [10,9,2,5,3,7,101,18]输出: 4解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说
2020-08-02 00:07:40
138
原创 动态规划 第2讲： 二维动态规划
写完一维动态规划的博客之后，我就开始做比较基础的二维动态规划的leetcode题目。不过因为太懒了，所以博客就推迟了好几天才写。好，我们开始吧！一、64. 最小路径和 （难易程度： medium）原题链接：https://leetcode-cn.com/problems/minimum-path-sum/给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例:输入:[[1,3,1],[1,5,1],
2020-07-21 23:16:33
1818
1
原创 动态规划 第1讲： 一维动态规划
这篇文章参考了以下博客或者公众号：1、动态规划图解 作者：NFGC(Leetcode题解)之前 我写了一篇博客：动态规划 第0讲：基础入门课对动态规划算法进行了大致的讲解。接下来两周，我们将会一步一步、由浅到深来分析各个类型的题目。首先，当然是最简单的一维动态规划算法了。一、70. 爬楼梯 （难易程度：easy）原题链接：https://leetcode-cn.com/problems/climbing-stairs/假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2
2020-07-10 20:58:32
1641
原创 贪心算法 第2讲： 区间问题
区间问题是贪心算法常见题目，其类型通常是N×2或者N×Mi的数组，进行一些合并，删除等操作。一、区间问题分成两类：（1）合并区间：(i. 合并区间(ii. 先统计，再合并区间（2）计算不重叠区间：(i. 不重叠区间个数(ii. 相邻区间视为重叠区间上面这四种情况，我们用四道题目来解释二、56. 合并区间 （难度：中等）原题链接：https://leetcode-cn.com/problems/merge-intervals/给出一个区间的集合，请合并所有重叠的区间。示例 1:输
2020-06-27 15:34:56
815
原创 贪心算法 第1讲： 分配问题
一、什么是贪心算法？贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。举一个
2020-06-24 12:07:57
3356
1
原创 SCAU-ACM 18250 寻找SCAU
时间限制:1000MS 内存限制:65535K 题型: 编程题 语言: G++;GCCDescription我们知道华农校园里很多地方都有SCAU（South China Agricultural University）的标志，如五山一条街旁边的草坪就有一个绿绿的"SCAU"。小To今年刚考进了华农，他来到学校寻找着校园内SCAU的标志。现在小To得到了一个字符串，他想知道这个字符...
2018-12-02 10:46:36
1549
原创 SCAU 菱形打印全集
初级版：Description由键盘输入正数n（n<30），要求输出如下2n+1行的菱形图案。（例.输入2）+++++++++++++思路分析：我们需要将整个菱形分成四块来考虑，从上到下空格的个数先从n/2递减到0后递增到n/2，而行循环因子i又从0递增到n，故自然可联想到用i与n/2来表示空格个数。因为空格个数是非负数，所以我们引进绝对值|n/2-i|表示空格个数。打完空...
2018-11-04 00:35:22
2143
原创 SCAU 暴力法求最近点对
由键盘输入n(n<50)个点的坐标x,y(x,y<1000,浮点数)，计算出最近两个点的距离。（保留三位小数）#include <stdio.h>#include <stdlib.h>#include<math.h>double distance(double x1, double y1, double x2, double
2018-11-03 19:20:51
1381
原创 SCAU 计算高精度加法(C Programming)
Description由键盘输入两个位数很长的整数（一行一个，最多不超过80位），试计算并输出这两个数的和。#include <stdio.h>#include <string.h>int main(){ char m[80],n[80]; /*后面如果用到strlen，一定要用char，因为strlen只能用于计算字符串的长度*/ in...
2018-10-22 17:42:58
2221
原创 SCAU 找矩阵中的鞍点(C Programming)
Description由键盘输入一个3＊4（3行4列）的矩阵，输出矩阵中的鞍点（即在矩阵行中最大，列中最小的数）。若没有鞍点，输出“NO”字样。#include<stdio.h> int main() { int i,j,k,max,min; int col=0,row=0;/*鞍点的行、列*/ int a[3][4]; for(i=0; i<
2018-10-20 18:01:35
2957
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人