菜鸡的博客 | WTCL

第一个只出现一次的字符

你快乐吗？

第一个只出现一次的字符 C++，Hash。简单的Hash： class Solution { public: int FirstNotRepeatingChar(string str) { vector<int> hash(128, 0); for (char &it : str) hash[it]+...

Posted by bbkgl on September 26, 2019

矩形覆盖

你快乐吗？

矩形覆盖 C++，还是动态规划，也是斐波那契数列，当然边界条件有点不一样的。思路如下：显然f(1) = 1 显然f(2) = 2 当面积为3x2的时候，填充可以两种填充方式由1x2再填充两块砖填满3x2；有2x2再填充一块砖填满3x2；上述1本来有两种填充得到3x2，但是有一种和2x2重叠了，所以实际...

Posted by bbkgl on September 26, 2019

用两个栈实现队列

你快乐吗？

用两个栈实现队列思路很简单：入栈只入栈1 出栈只从栈2出，出栈时如果栈2右元素则顶部元素出栈，否则让栈1元素全部压入到栈2，然后栈2最上面元素出栈代码如下： class Solution { public: void push(int node) { stack1.push(node); } int pop() { ...

Posted by bbkgl on September 26, 2019

求1到n累加和

你快乐吗？

求1+2+3+…+n C++，递归 + &&的短路原则。 &&逻辑运算的短路原则就是，如果左边已经为false，则不再计算右边。所以如果碰到左边为0，则不计算右边，终止递归。 class Solution { public: int Sum_Solution(int n) { int ans = n; n &...

Posted by bbkgl on September 26, 2019

正则表达式匹配

你快乐吗？

正则表达式匹配 C++，dp，递归，字符串匹配。像这种题，最容易忘记，索性思路写的详细一点。大体思路：使用从前往后“消除”的思路，使用双指针，对于指针之前的可以不管，只判断当前位置和以后的字符串的匹配情况，然后使用相同的策略进行递归匹配。详细匹配步骤：如果str和pattern指针都指向\0，则说明已经全部匹配成功了；如果str和pattern指针指向的字符相等...

Posted by bbkgl on September 26, 2019

树的子结构

你快乐吗？

树的子结构 C++, dfs。判断B树是不是A树的子结构。是子结构！！！不是子树！！！思路：遍历整棵树A，将A树的每个结点和树B的根结点比较如果值相等，从当前结点开始，两棵树同时dfs（前序），对每个结点进行比较：如果两个结点都为空，则说明刚刚经过的路径是完全一样的；如果A的结点为空，而B的结点不为空，说明B在当前路径上比A多...

Posted by bbkgl on September 26, 2019

栈的压入、弹出序列

你快乐吗？

栈的压入、弹出序列 C++，栈模拟。模拟所有数据出栈和入栈的过程：遍历要出栈的每个元素；如果栈顶不是当前要出栈的元素，说明得继续入栈；入栈直到栈顶是当前要出栈的元素；最后正常的话，所有元素都出栈；不正常的话，会出现要出栈的某个元素A，就算把所有元素都入栈，都无法让栈顶元素B = A；代码： class Solution { public: ...

Posted by bbkgl on September 26, 2019

构建乘积数组

你快乐吗？

构建乘积数组 C++，类似于动态规划应该。利用两个数组，记录每一个位置之前所有元素的乘积和之后所有元素的乘积。而本题要求的正是每个元素除了自己以外所有元素的乘积，将之前和之后相乘就行了。但实际上，这两个数组是多余的，只要用返回答案的数组来记录就行了。第一遍遍历可以得到每个元素之前所有元素的乘积，第二遍从后往前遍历，记录每个元素之后的所有元素的乘积，如果直接乘会覆盖，所有定义一个...

Posted by bbkgl on September 26, 2019

最小的K个数

你快乐吗？

最小的K个数 C++，topK问题。一般来说这种题有两种种“可行”的方法：最小/大堆，O(nlogk)；快排的partition思想，O(n)；在C++中，可以用STL中的优先队列来建立最小堆，但面试手撕代码的时候可不会让用库函数和容器。所以这里用最大堆来实解决topK的问题，注意三个测例的坑点： k <= 0，报超时或者段错误； k > ...

Posted by bbkgl on September 26, 2019

替换空格

你快乐吗？

替换空格 C++，思路：从前往后遍历一次，统计空格的个数cnt；得到替换后字符串的总长度应该为length + cnt + 2；从后往前遍历，指针left在原字符串尾，指针right在新字符串尾，注意left指针开始位是最后的\0；如果碰到的是空格，将空格替换，同时right应该移动三次，而left移动一次；如果不是空格，直接复制就行了；循环跳出条...

Posted by bbkgl on September 26, 2019

我太菜了

第一个只出现一次的字符

你快乐吗？

矩形覆盖

你快乐吗？

用两个栈实现队列

你快乐吗？

求1到n累加和

你快乐吗？

正则表达式匹配

你快乐吗？

树的子结构

你快乐吗？

栈的压入、弹出序列

你快乐吗？

构建乘积数组

你快乐吗？

最小的K个数

你快乐吗？

替换空格

你快乐吗？

FEATURED TAGS

ABOUT ME

FRIENDS