shxifs的博客

原创 对数的不常用性质

原创 常用的放缩法

原创 排序不等式应用

逆序和<乱序和<正序和经典例题：1、a,b,c均为正数：

原创 糖水不等式

如果,,一定有一种比较直观的证明方法是比较（a,b）（0,0）与（a,b）（-m, -m）的斜率。如果把a,b,m扩展为实数，这种方法比较好迅速判断大小。

原创 排序不等式证明n次均值不等式

要证：令，设，有取由排序不等式有：所以原式子成立

原创 射影定理证明均值不等式

原创 数学常用技巧

集合：集合运算的分配律与反演律（摩根律）、容斥原理、有限等集的性质函数：映射方法、偏导、拉格朗日乘数法、拉格朗日中值定理、不动点与稳定点、自对称与他对称、线性复合函数、双层复合最值、切比雪夫最佳逼近直线理论、平口单峰函数、泰勒展开数列：高阶等差数列及其性质、无穷递缩等比数列、构造递推关系、特征根法、不动点法、常见周期数列、第二数学归纳法三角函数：合分比定理、射影定理、正切定理、半角定理、三倍角公式、和差化积与积化和差公式、半角公式（不是半角定理）、各种三角代换方法、各种三角恒等式、反三角函数、三

原创 补码一位除法的原理

在分析补码除法时，需要额外考虑符号位参与计算。在这里为了表示方便，用[x]表示x的补码，x*表示x绝对值。在比较被除数x和除数y的大小关系时，由于参与运算的均为补码，不能直接用[x]-[y]来比较大小。例如[5-9] mod 10 = 6，但实际上5比9要小。所以直接考虑绝对值的计算。x,y同号时，计算x*-y*可以用[x]-[y]表示，结果符号与y符号相同则表示够减，与y符号不同则不...

原创 定点数除法溢出的原因

书上说的是定点数除法第一步可以判断是否溢出，上商时商“0”不溢出，商“1”为溢出。这是因为符号位已用异或额外判断，定点数除法是|x|与|y|相除，符号位必须为0（正），并不像常规的算数除法一样可以任意商1。...

原创 补码一位乘法的公式及证明

原创 补码和移码为什么是符号位取反的关系？

补码的公式为：

原创 动态规划之填表法

动态规划基本上都需要开辟一个数组来记录状态, 数组是基于所给条件利用动归方程把表填满. 现在总结一下填表的注意事项.1.表的行数是所给条件的索引数+12.dp表第一行(或第一列)需要根据实际条件初始化例子: 给定字符串s和t，判断s是否为t的子序列。(可以不连续)动态规划方程为:(dp[i][j]表示长度为i的s串是否是长度为j的t串的子序列)if(s[i]...

原创 KMP算法next数组的理解

next数组实际是储存某个位置前面的子串中前缀和后缀最大的相同字符个数。前缀：包括第一个字符的连续字符串。（真前缀，不包括自己）后缀：包括最后一个字符的连续字符串。（真后缀，不包括自己）例如：abababaci = 0时, 子字符串为"a" 没有真前缀与真后缀, 所以next[0] = 0.i = 1时, 子字符串为"ab", 没有共同的前后缀, 所以next[1] = 0....

原创 单调栈和单调队列的理解

1、单调栈单调栈是指一个栈内部的元素具有严格单调性的一种数据结构，分为单调递增栈和单调递减栈。其具有以下两个性质：1，满足栈底到栈顶的元素具有严格单调性。2，满足栈的先进后出特性，越靠近栈顶的元素越后出栈。元素进栈过程：对于一个单调递增栈来说，若当前进栈的元素为a，如果a<栈顶元素，则直接将a进栈。如果a≥栈顶元素，则不断将栈顶元素出栈，直到满足a...

原创 378. 有序矩阵中第K小的元素

给定一个n x n矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个元素。示例:matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15]],k = 8,返回 13。思路:二分查找, 并计算每一次小于等于中间值的元素个数 如果<k, 前半段舍掉...

原创 自己写的二分查找模板(3)

二分查找真的是博大精深啊。自己又总结了一遍, 把每一类问题都归类如下:(差不多9类) 数组全部有序, 无重复 标准二分查找 大于等于目标值的数 大于目标值的数 小于等于目标值的数 小于目标值的数 数组全部有序, 有重复 查找目标值的左边界 查找目标值的右边界 数组部分有序, 无重复 (例如求旋转数组的最小值, 这个时候可以把最小值看做是求右边有序序列的左边界,这...

原创 自己写的二分查找模板(2)

关于二分查找的类型以及变式不同写法的关键:while循环条件是l < r还是 l <= r 中值m靠左还是靠右 区间是左开右闭还是左右都闭先贴上C++标准库的写法.public int lower_bound(int nums, int target, int l, int r){ while(l < r) { int m = (...

原创 自己写的二分查找模板

存在三种基本模式:1. 标准二分查找2. 二分查找左边界3. 二分查找右边界只有第1种情况能够在循环内部返回. 这种标准二分查找是左闭右开的写法. 查找范围是 l <= n < r 中间位置计算时, m = (l+r)/2, 这样得到的中间位置靠左. m = (l+r)/2 +1, 这样得到的中间位置靠右. 其中, 2.3两种情况下, 左边界和右边界分别需...

原创 922. 按奇偶排序数组 II

一开始怪自己蠢, 只想到i++,j++的方法. 后来看了题解, 才知道用+=2最方便.这样这个题目思路比较简单了. 只需要分别找到偶数位和奇数位不合条件的数, 交换即可.class Solution { public int[] sortArrayByParityII(int[] A) { int n = A.length; int x = 0;...

原创 非递减数列

给定一个长度为n的整数数组，你的任务是判断在最多改变1 个元素的情况下，该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的：对于数组中所有的i (1 <= i < n)，满足array[i] <= array[i + 1]。输入: [4,2,3]输出: True解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。这个题目需要自己总...

原创 最短无序连续子数组

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。输入: [2, 6, 4, 8, 10, 9, 15]输出: 5解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。这个题其实不算太难，不想用排序做，所以刚拿到题目的时候没啥太好的思路。经过自...

原创 矩阵操作之：方向向量法

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度(向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。输入:[[1,1,1], [1,0,1], [1,1,1]]输出:[[0, 0, 0], [0, 0, 0], [0, 0, 0]]看到这个题目一开始没啥思路，只有...

原创 元素归位法

给定一个范围在1 ≤ a[i] ≤ n (n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。示例:输入:[4,3,2,7,8,2,3,1]输出:[5,6]这种题目直...

原创 第三大的数

设置测试用例的也太恶心了，居然以-2147483648作为输入，而且还放在第二个位置，导致程序很难识别究竟是输入的MIN还是本来就有的MIN。为了简单起见，想了一个办法，把所有的MIN输入值改为MIN+2，这样就能把输入MIN的和初始化的MIN区分开。class Solution { public int thirdMax(int[] nums) { int ma...

原创 in-place算法之双指针法

283. 移动零给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。示例:输入: [0,1,0,3,12]输出: [1,3,12,0,0]拿到这个题目，我首先的想法是比较暴力的算法。pre指针指向第一个不0的，再固定pre，扫描右边cur指向第一个为0的，然后交换位置。这样复杂度为O(n2)。有一种比较简单的方法 -> i...

原创 数组的循环移位深入探讨

三次反转法比较简单，我想的是怎么才能用一般的循环移位法，同时又不开新数组，用O（1）的空间来循环移位。思路想的很快，把i位移动到(i+k)%n位，然后不移动i+1位，而是直接移动((i+k)%n+k)%n位，依次类推。[1, 2, 1, 4, 5, 6][1, 2, 1, 4, 3, 6][5, 2, 1, 4, 3, 6][5, 2, 1, 2, 3, 6][5, 2, ...

原创 摩尔投票法的理解

摩尔投票法基于这样一个事实，当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。算法步骤：1.count = 0；num = nums[0]; 表示从此时开始计算投票。2.遍历数组，如果接下来出现的数字与num相同，count加1。如果不同，count减1。3.如果count == 0，表示之前出现的所有数字中num都是可以凑成不同的数对...

原创 go中接口的理解

1.接口声明后，需要在后面对应的结构体（或变量中）实现。2.接口的实现形式：（函数与方法的区别）func(接收器) 函数名（参数表）{}3.接口变量需要声明：var namer = new(...)本质上是一个指针，能储存两个地址，第一个是结构体（或变量）的地址，第二个是该结构体（或变量）对应的实现的接口地址。即使结构体为空，也能调用该接口方法。4.接口的调用与结构...

原创 关于map容器用迭代器访问元素的方法

map是模板，一个map变量key和value两个值，你在这里是想用类似map&lt;int,int&gt; m_map的变量来表示背包里的东西，m_map-&gt;first可以取得key值，m_map-&gt;second可以取得value值；map自动按照key值按升序排列，key的值不能修改，可以修改value的值。...

原创 缓冲区发送消息PV操作题目详细分析

进程A1、A2、…Anl通过m个缓冲区向进程B1、B2、…Bn2不断地发送消息。发送和接收工作遵循如下规则：(1)每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样。(2)对于每一个消息，B1、B2、…Bn2都需各接收一次，读入自己的数据区内。(3)m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。 试用wait、signal操作描述它们的同步关系。...

原创 进程同步之理发师问题的理解

描述：理发店有一位理发师和一把理发椅。如果没有顾客,则理发师在理发椅上睡觉;当有顾客到达时,如理发师在睡觉则唤醒他理发,如果理发师正忙着理发,则坐在椅上等待。　　　编写程序实现理发师和顾客行为的正确描述。  行为分析：　　Ø理发师行为:睡觉、理发。没有顾客睡觉，有顾客理发。　　Ø顾客行为:理发或等待。　　Ø相互作用：　　　　理发师与顾客之间:同步　　　　顾客与顾客之...

原创 信号量与进程同步的简单理解

信号量可以用来解决互斥与同步问题，它只能被两个标准的原语，wait(S) 和 signal(S) 来访问，也可以记为“P操作”和“V操作”。 P/V操作： wait(S){ while(S&lt;=0); S = S - 1; } signal(S){ S = S + 1; }s&gt;=0可以表示可用资源数...

原创 88. Merge Sorted Array

class Solution {public: void merge(vector&lt;int&gt;&amp; nums1, int m, vector&lt;int&gt;&amp; nums2, int n) { if (m&lt;0&amp;n&lt;0) return; vector&lt;int&gt; c(m+n);...

原创 26. Remove Duplicates from Sorted Array

class Solution {public: int removeDuplicates(vector&lt;int&gt;&amp; nums) { if (nums.empty()) return 0; int pre = 0, cur = 0, n = nums.size(); while (cur &lt; n) { ...

原创 121. Best Time to Buy and Sell Stock

class Solution {public: int maxProfit(vector&lt;int&gt;&amp; prices) { int res = 0, buy = INT_MAX; for (int price : prices) { buy = min(buy, price); res =...

原创 27. Remove Element

class Solution {public: int removeElement(vector&lt;int&gt;&amp; nums, int val) { int res = 0; for (int i = 0; i &lt; nums.size(); ++i) { if (nums[i] != val) nums[res...

原创 283. Move Zeroes

class Solution {public: void moveZeroes(vector&lt;int&gt;&amp; nums) { for(int i=0,j=0;i&lt;nums.size();++i) { if(nums[i]) swap(nums[i],nums[j++]); } ...

原创 189. Rotate Array

class Solution {public: void rotate(vector&lt;int&gt;&amp; nums, int k) { vector&lt;int&gt; array=nums; for(int i=0;i&lt;nums.size();++i) { nums[(i+k)%(nums.s...

原创 167. Two Sum II - Input array is sorted

class Solution {public: vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; numbers, int target) { int l=0,r=numbers.size()-1; while(l&lt;r) { int sum=numbers[r]+n...

原创 119. Pascal's Triangle II

class Solution {public: vector&lt;int&gt; getRow(int rowIndex) { vector&lt;int&gt; out; if(rowIndex&lt;0) return out; out.assign(rowIndex+1,0); for(in...