- 博客(28)
- 收藏
- 关注
RSS订阅原创 leetcode-152成绩最大子数组（优化）
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。示例 1:输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。//第一种思路：动态规划，用两个dp数组dp_max[i], dp_min[j]，分别记录到第i个元素时的最大和最小连续乘积dp_max[i] = max(dp_max[
2020-05-18 21:07:46
231
原创 bfs-dfs-回溯-递归总结
参考http://chen-tao.github.io/2017/01/25/about-bfs/BFS常用于计算图的连通性，单源最短路径，计算最小操作次数···public class GraphNode{int val;List neighbors;}public void BFS(GraphNode start){LinkedList q = new LinkedList();HasheSet visited = new HasheSet();q.push(start);vi
2020-05-13 10:56:51
273
原创 c++迭代器失效问题探究
迭代器失效：该迭代器不再表示任何元素，即该迭代器已经不表示任何元素。何时发生：处理vector，string，deque时，如果进行添加和删除操作就会导致迭代器失效。《C++ Primer》中总结如下：（1）添加元素后：容器是vector或string时，如果存储空间重新分配，之前指向容器的迭代器、指针和引用都会失效；如果没有重新分配，插入位置之前的迭代器、指针和引用都有效，插入位置之后的失效容器是deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效；在首尾添加，则迭代器失效
2020-05-09 16:40:44
190
原创 stl-vector源码注解
#include<iostream>#include<algorithm>#include<string>namespace ve { template<typename T> class Vector { public: typedef T value_type; typedef value_type* iteartor...
2020-05-08 18:19:36
144
原创 type traits小总结
主要是阅读了侯捷老师的《stl源码剖析》的迭代器部分的内容，进行的一点总结：type traits是什么？字面翻译，就是类型特点，顾名思义，就是某个类本身的特质。在下图中，迭代器是容器和算法之间的桥梁，而算法在调用使用数据的过程中，也需要知道这个数据或者说容器本身的性质。迭代器中的type traits有哪些？template <class I>struct itera...
2020-05-08 17:01:57
429
原创 stl五个内存基本处理工具
stl定义的五个全局函数，作用于未初始化空间，便于容器的实现。包括contruct(), destroy()和uninitialized_copy(), uninitialized_fill(), uninitialized_fill_n，后面三个分别对应于高层次函数copy(), fill(),fill_n()，都是stl算法。1. construct(),属于<stl_construc...
2020-05-08 15:08:42
171
原创 trivial/nontrival函数
这里想谈一下，关于c++中的trivial和nontrivai的成员函数，主要对应于以下几个函数：默认构造函数（default constructor）拷贝构造函数（copy constructor）拷贝赋值操作符（copy assignment operator）析构函数（destructor）对于默认构造函数和析构函数来说，trivial就是什么都不做，对于拷贝构造函数和拷贝赋值来...
2020-05-08 11:15:51
1196
原创 类型别名（typedef, typename, using）和decltype
1. 定义别名方法（1）typedeftypedef double wages; //wages是double的同义词typedef wages base, *p; // base是double的同义词，p是double*的同义词typedef和函数指针typedef char (*PTRFUN)(int); //相当于定义了一种新的类型，这里的PTRFUN是一个函数指针类型，其参...
2020-05-08 03:04:15
1280
原创 c++函数指针
1. 函数指针函数：bool lengthCompare(const string&, const string&);函数指针：bool (*pf)(const string&, const string&); //没有初始化这里首先pf是一个指针，右侧是形参列表，表示pf指向的是函数，再看左侧，发现函数的返回类型是布尔值，因此pf是一个指向函数的指针，函数的...
2020-05-08 01:23:15
142
原创 leetcode--动态规划问题总结c++
按照labuladong大佬总结的一些模板，这里总结自己在做题过程中的一些思路和实践。1. 何为动态规划（DP）？按照一些比较官方的定义，就是"记住之前做过的事"，在算法题中更确切的理解应为记住之前得到的答案，然后基于一个递推公式及一个或多个初始状态，将当前子问题的解由上一次子问题的解推出。相关概念：（1）动态规划算法：通过拆分问题，定义问题状态和状态之间的关系（这里我的理解，状态就是问题...
2020-05-07 19:36:34
197
原创 c++string和int互转
一、int转换成string1. to_string函数c++11标准增加了全局函数std::to_string:string to_string (int val);string to_string (long val);string to_string (long long val);string to_string (unsigned val);string to_string...
2020-05-06 18:10:38
175
原创 c++类型转换（四种）
参考链接：https://blog.csdn.net/ydar95/article/details/698225401. C中的类型转换void Test () { int i = 1; // 隐式类型转换 double d = i; printf("%d, %.2f\n" , i, d); int* p = &i; //...
2020-05-06 17:31:36
157
原创 leetcode279--完全平方数（c++）
题目给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。示例 1:输入: n = 12输出: 3 解释: 12 = 4 + 4 + 4.示例 2:输入: n = 13输出: 2解释: 13 = 4 + 9.解法1：动态规划，设置dp[i]，表示生成i需要的完全平方数的个数，其中dp[0] = ...
2020-05-06 15:19:39
595
原创 面试题 04.03. 特定深度节点链表C++
题目给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。示例：输入：[1,2,3,4,5,null,7,8] 1 / \ 2 3 / \ \ 4 5 7 / 8输出：[[1],[2,3],[...
2020-05-05 18:18:21
125
原创 leetcode98--验证二叉搜索树(c++)
题目给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入: 2 / \ 1 3输出: true示例 2:输入: 5 / \ 1 4 / \ 3 6输出:...
2020-05-05 17:27:02
165
原创 leetcode200--c++解答（dfs+bfs+并查集）
题目给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。示例 1:输入:11110110101100000000输出: 1示例 2:输入:11000110000010000011输出: 3解释: 每座岛屿只能...
2020-05-04 21:34:03
317
原创 单调栈C++
单调栈其实就是栈。做单调栈的问题首先应该想到的是，我们需要「后进先出」这种数据结构作为缓存。然后才是栈内的数据性质有单调性。典型问题有：接雨水和柱状图中最大的矩形...
2020-04-30 15:42:34
270
原创 并查集（Union-Find）c++详解
定义并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。 常常在使用中以森林来表示特点1.「并查集」是一种建立在「数组」上的树形结构，并且这棵树是孩子结点指向父亲结点的；2.「并查集」主要用于解决「连通性」问题，重点关注的是我和你是不是朋友，但是我们是几层朋友关系，并不重要；3.「并查集」是树，所以优化的策略依然是和树的高度较劲，优化思路有「...
2020-04-30 15:41:30
1169
原创 二分搜索树c++数据结构
#include <iostream>using namespace std;// 二分搜索树template <typename Key, typename Value>class BST{private: // 二分搜索树中的节点为私有的结构体, 外界不需要了解二分搜索树节点的具体实现 struct Node{ Key k...
2020-04-30 14:21:07
155
原创 二分查找
迭代template<typename T>int binarySearch(T arr[], int n, T target){ // 在arr[l...r]之中查找target int l = 0, r = n-1; while( l <= r ){ //int mid = (l + r)/2; // 防止极端情...
2020-04-30 14:12:32
79
原创 堆排序
1. 堆的基本数据结构template<typename T>class MaxHeap { private: Item* data; int count; public: MaxHeap(int n) { data = new Item[n + 1]; count = 0; } ~MaxHeap(){ delete[] dat...
2020-04-30 14:07:30
48
原创 快速排序c++（含优化）
思想：分而治之#include<iostream>using namespace std;template<typename T>int partition(T a[], int l, int r) { T tmp = a[l]; int k = l; for (int i = l + 1; i <= r; i++ ) { if (a[i] <...
2020-04-30 13:38:49
226
原创 归并排序c++
基本实现（递归）自顶向下的归并排序算法是典型的“分治”算法思想的应用：先分别递归处理规模更小的子数组的排序问题，然后再基于已经排好序的子数组合并成一个规模更大的排序数组，一层一层的递归总是均衡地“一分为二”进行的#include<iostream>using namespace std;// 将a[l...mid]和a[mid+1...r]两部分进行归并template&l...
2020-04-30 12:56:57
252
原创 插入排序和希尔排序c++
//将位置i处的元素放到0和i之间的合适位置#include<iostream>using namespace std;void swap(int a[], int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp;}void selectSort(int a[], int len) { for (int i = ...
2020-04-30 11:30:59
138
原创 选择排序算法c++实现
#include<iostream>using namespace std;void swap(int a[], int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp;}int main() { int a[] = {17, 15, 7, 9, 4}; int len = a.size(); for (int...
2020-04-30 11:04:30
106
原创 leetcode--验证回文字符串（125，680）
题目给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。示例 1:输入: “A man, a plan, a canal: Panama”输出: true示例 2:输入: “race a car”输出: false思路这里比较简单，双指针，分别指向头尾，如果相等，i++,j–，如果不相等则可以判断是否为...
2020-04-24 10:52:50
116
原创 leetcode58-单词反转
题目输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。示例 1：输入: “the sky is blue”输出: “blue is sky the”示例 2：输入: " hello world! "输出: “world! hello”...
2020-04-24 09:50:04
361
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人