fengyun's Blog

剑指 Offer 03. 数组中重复的数字 方法一：哈希表，较为简单 方法二：原地置换 所谓原地交换，就是如果发现这个坑里面的萝卜不是这个坑应该有的萝卜，就看看你是哪家的萝卜，然后把你送到哪家，再把你家里现在那个萝卜拿回来。 拿回来之后，再看看拿回来的这个萝卜应该是属于哪家的，再跟哪家交换。 就这样交换萝卜，直到想把这个萝卜送回它家的时候，发现人家家里已经有了这个萝卜了（双胞胎啊），那这个萝卜就多余了，就把这个萝卜上交给国家。 1234567891011int findRepeatNumber(vector<int>& nums) { int len = nums.size(); for(int i = 0;i < len;i++){ while(nums[i] != i){ //只要没有填到相应的坑就一直换 int tmp = nums[i]; //看看你是哪家萝卜 if(nums[tmp] == tmp)return tmp; //看看 ...

子集（阿里巴巴） 我们需要求严格上升的子序列，求严格上升的子序列也是leetcode上的经典题型最长递增子序列，而此题稍作变换，需要求两个数组的严格上升子序列。 我们可以先对x排序，x是上升的，但并不是完全单调上升，因为有相等的x。若假设我们的x是严格单调的的话，这个题就可以转化为，对y求严格单调上升子序列的长度问题即最长递增子序列。（贪心加二分查找） 而对于x相等的情况，我们不妨令y在前的排在前面，这样可以避免重复计算。 12341 2 2 510 21 19 32 这里我们对x相等的y进行从大到小的排序，这时候结果是3，符合题意，因为x相等如果y是从小到大的话，有可能统计重复的x, 我们让y降序排列的话就破坏了y单调上升的可能，不会重复统计x; 这里用贪心能全部过，如果暴力的使用动态规划O(n^2)全不过……（或许也可能是我动态规划写错了….） 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565 ...

模板123456789101112131415161718192021222324252627/* 滑动窗口算法框架 */void slidingWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 增大窗口 right++; // 进行窗口内数据的一系列更新 ... // 判断左侧窗口是否要收缩 while (window needs shrink) { // d 是将移出窗口的字符 ch ...

通常认为，STL是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的，它们各自的含义如表所示。 STL的组成 含义 容器 一些封装数据结构的模板类，例如 vector 向量容器、list 列表容器等。 算法 STL 提供了非常多（大约 100 个）的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都包含在头文件 中，少部分位于头文件 中。 迭代器 在C++STL 中，对容器中数据的读和写，是通过迭代器完成的，扮演着容器和算法之间的胶合剂。 函数对象 如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）。 适配器 可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器。 内存分配器 为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用 ...

迭代器简介迭代器是种遍历容器内元素的 数据类型，这种数据类 型感觉有点像指针，我们理解的时候就理解为迭代器用来指向容器中的某个元素。string, vector, []， 很少用[]来访问元素，更常用的访问方式就是用迭代器(更通用)。 通过迭代器，我们就可以读容器中的元素值，读string中的每个字符，还可以修改某个迭代器所指向的元素值。迭代器像指针一样支持++，–操作 list,map,通常用迭代器来访问元素。 容器的迭代器类型12vector<int> iv = {100,200,300};vector<int>::iterator iter;//定义迭代器，也必须是vector<int> 每个容器都会定义一个iterator固定成员，可以把整个vector<int>::iterator理解为一个类型，这种类型就专门应用于迭代器。当我们用这个类型定义一个变量的时候，这个变量，就是个迭代器，这里iter这个变量就是个迭代器。 迭代器操作迭代器begin()/end()操作begin()/end()返回的是迭代器类型 ...

求取两数平均值123456int a;int b;int c = (a+b)/2;int d = a/2 + b/2;int e = a/2 + b/2 + 1;int f = a/2 + b/2 + (a&b&1); 一般情况下(a+b)/2没问题，但是a和b值都过大时会造成溢出！ 而a/2 + b/2又有可能产生精度丢失，比如a和b的值都为3，结果是2，少了1 。 那么什么时候需要弥补精度呢？答案是a和b都是奇数，也即a和b的最低位是1 因此最终结果int f = a/2 + b/2 + (a&b&1);既避免精度损失又避免溢出。 求取n个数的平均值a1,a2,a3,…,an的平均值 如果a1/n+a2/n+a3/n+...+an/n显然有精度损失，那么如何将损失补回去？ 因此思路变为了对于前面能整除部分直接整除再相加，对于后面余数部分将所有余数加起来再除以n即可。 我们可以 12345678910int average(int a[], int n) { int ret = 0; int m = 0; for (in ...

C语言异常- 程序在运行过程中可能产生异常 - 异常（ Exception ) 与 Bug 的区别 异常是程序运行时可预料的执行分支 Bug 是程序中的错误，不是希望的，是不被预期的运行方式 异常(Exception)和Bug的对比- 异 常 运行时产生除0的情况 需要打开的外部文件不存在 数组访问时越界 - Bug 使用野指针 堆数组使用结束后未释放 选择排序无法处理长度为 0 的数组 C语言经典处理方式if..else12345void func (... ) if ( 判断是否产生异常 ） 正常情况代码逻辑; else 异常情况代码逻辑; 12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>#include <string>using namespace std;double divide(double a, double b, int* valid){ ...

什么是递归？– 递归是一种数学上分而自治的思想（问题分解）• 分解后的问题与原问题的类型完全相同， 但问题复杂度降低• 通过相对简单问题（子问题）的解，能够轻易求得原问题的解 – 递归与递推的思想相同，但是表现形式不同• 递归强调“归”，即：求解子问题后“回到原处”解决当前问题• 递推强调“逐渐接近”，即：在既定策略下一步一步求解问题 递归在程序设计中的应用– 递归函数• 函数体中存在自我调用的函数• 递归函数必须有递归出口（边界条件）• 函数的无限递归将导致程序崩溃（函数调用栈越界） 递归与递推本质差异– 递归在求解原问题时：• 可能将原问题分解为多个子问题，并等待所有子问题求解结束• 得到所有子问题答案后，需要对子问题答案进行汇总，平衡，取舍。。。– 递推在求解原问题时：• 假设在既定策略下，能够逐步接近问题答案• 递推中的策略保证每一个求解步骤总是能接近问题答案 思路： 先想代码出口，最简单的情况即一眼就能看出结果的情况（例如数组大小为1，树的节点只有1个等等） 再思考原问题如何分解小问题，找出递归式，注意小问题和原问题的状态应该是一样的 有时候可能有功能参数，比 ...

左值和右值左值：能用在赋值语句等号左侧的东西， 它能够代表一个地址右值：不能作为左值的值就是右值，右值不能出现在赋值语句中等号的左侧 结论：C++中的一条表达式，要么就是右值，要么就是左值，不可能两者都不是。 左值有的时候能够被当作右值使用 i = i + 1，i是个左值，不是个右值，虽然它出现在了等号右边 i用在等号右边的时候，被当作一个具体的值，我们说i有一种右值属性（不是右值）i出现在等号左边的时候，用的是i这个变量代表的内存中的地址，这就被称为左值属性。 因此一个左值，同时具有左值属性和右值属性 用到左值的运算符有哪些？ 1.赋值运算符 12int a;printf("%d\n", a = 4); //4 整个赋值语句的结果仍然是左值 (a = 5) = 8; 2.取地址& 123int a = 5;&a;//不可以 &5 3.容器的下标[]都需要左值， 123string a = "fengyun"a[0];//不可以 fengyun[0] 4.迭代器的–，++需要左值 12vector<int& ...

[TOC] C++基础[TOC] 类的构造函数、析构函数、赋值函数、拷贝函数赋值函数和拷贝构造函数的区别？构造函数 对象不存在，没用别的对象初始化，在创建一个新的对象时调用构造函数 拷贝构造函数 对象不存在，但是使用别的已经存在的对象来进行初始化 赋值运算符 对象存在，用别的对象给它赋值，这属于重载“=”号运算符的范畴，“=”号两侧的对象都是已存在的 区别： 拷贝构造函数是函数，赋值运算符是运算符重载。 拷贝构造函数会生成新的类对象，赋值运算符不能。 拷贝构造函数是直接构造一个新的类对象，所以在初始化对象前不需要检查源对象和新建对象是否相同；赋值运算符需要上述操作并提供两套不同的复制策略，另外赋值运算符中如果原来的对象有内存分配则需要先把内存释放掉。 形参传递是调用拷贝构造函数（调用的被赋值对象的拷贝构造函数），但并不是所有出现”=”的地方都是使用赋值运算符，如下： 1234Student s;Student s1 = s; // 调用拷贝构造函数Student s2;s2 = s; // 赋值运算符操作 移动构造函数与拷贝构造函数对比 拷贝赋值是通过拷贝构造函数 ...