思路   题目要求对数时间复杂度，所以立马反应出用二分法；从宏观的角度，本题二分法的思路就是，通过每一次，丢弃k/2个数，直到最后让你比较两个正序数组里的最小数，也就是k==1的情况；   <mark>然后就是细节细节再细节的边界问题；如果，在丢弃数据的过程中，有一个数组遍历完了，那么问题变成在一个数组里面寻找某一个数；</mark> 代码分析 class Solution { public: double getKthNumInTwoSortedArrays(vector<int>& nums1, vector<int&g...

回溯思想个人理解：有条件的穷举，当该路径不满足条件后，就回溯，返回到上一步其他的路径查找答案。 例如：22 括号生成，我们可以利用穷举的方法，列出所有的可能情况，然后去掉不满足的情况；那么我们就要思考如何实现穷举呢？   一般看到穷举，我们似乎可以有点规律的尝试回溯思想，使用递归来实现；然后，考虑去除不满足的情况，可以尝试在递归过程中，避免不满足情况的发生，我们可以利用两个数open，close来记录左右括号出现的次数，close<open ,open<n; 同样的17：电话号码的自由组合，也是一个需要穷举的题目，并且可以尝试使用回溯思想去完成；   当我们选择一个号码后，就会...

总结： 听同学说，只要提交了有AC百分之多少，就会有相应的分数，下次一定要及时提交，然后再优化使其达到AC100%； 对于输入输出的操作还不太熟悉，这也难怪，之前都是使用LeetCode，突然转换到类似牛客的这种方式，不太习惯 总共5道编程题，其实不用太赶，第一次过于谨慎，过于紧张了 一共5道题目 1数组对称输出 2打印字符串中的数字，并排序 3数组里连续k个数，ai、ai+1、...ai+k-1,的众数 4待续 5待续 1数组对称输出 #include<iostream> #incl...

总结，本题需要注意的细节之处有以下几点： 1 字符如何转换为数字？ 2 如何在不使用long数据的情况下，判断数据是否溢出？ 1 字符如何转换为数字？ 可以直接使用字符char-‘0’得到对应的数字，然后乘10累加 int tmp=(s[i]-'0'); Ans=Ans*10+tmp; 2 如何在不使用long数据的情况下，判断数据是否溢出？   由于int可表示的范围是[-231 ,231-1]   也就是[-2147483648 ,2147483647] 我们可以通过比较当前值Ans与231/10的大小关系来判断是否溢出 Ans<231...

听师兄说，去年面试华为，上来就让手撕八皇后，结果师兄二话不说搞定，直接30W+，慕了！ 八皇后问题就是在一个8x8的棋盘上面放置8个棋子，每个棋子的上、下、左、右、左上、左下、右上、右下8个方向不能有其他的皇后。 之前看着一道题的时候，感觉十分麻烦，总感觉细节太多了，然后只知道大的层面用一个dfs（by the way，个人理解，回溯是算法思想，DFS更多是实现工具，最根本的实现方法是递归） 基本思路：   可以认为的控制一行一行的进行皇后放置，首先在第一行进行放置，然后在第二行进行放置…，最后每一行都放置完了，这一种方案就进行到底了； 问题1：如何将方案存储下来呢？ 答：可以采用一个...

文章目录 1 LRU缓存机制 完整代码 2 分割回文串 1 LRU缓存机制 Least Recently Used，最近最少使用法则，如果容器的容量为N，那么容器里面总是保存最近使用的N个数据   设计实现LRU缓存机制，支持put操作，get操作（不存在就返回-1），要求时间复杂度为O(1)； 思考：首先由时间复杂度O(1)，可以想到我们可能需要使用数组以及哈希表；然后我们需要根据数据的使用频率来调整数据，在适当的时候删掉最不经常用的数据，那么我们可能就需要一个支持双向的容器（d...

  下午面试了依图科技，感觉最后一个题目没有发挥好，辜负了面试老师百般引导 目录 1 十进制转26进制 完整代码 2 生成等概率事件 3 universal reference 综合引用 1 十进制转26进制   最开始，没有处理好进位的问题，对于非26的整数倍，都是可以打印出来的，然后如果是26的整数倍，那么就会有问题； void Dto26(const int& aa){ int a=aa; stack<int> r...

目录 sort的自定义compare用法 官方提供的四种comp比较函数 结构体的比较 1 重写比较函数comp 2 结构体内重载运算符 3 结构体外重载运算符 测试 类的比较引发的两个问题 类的默认构造函数 类的构造函数、析构函数设置为private sort的自定义compare...

之前刷题的时候，一直会看见自定义sort的做法，一般的形式是，重新写一个bool的函数，然后作为参数传递给sort函数，但有时候，也会看见，直接传进去一个lambda表达式，比如以下的形式 sort(myStr.begin(),myStr.end(), [](string &a,string &b){ return (a+b)>(b+a); }); 文章目录 lambda表达式的一般形式 捕获列表 参数列表 返回类型 ...

前缀树：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。   正好今天力扣每日一题遇上了，查缺补漏，安排上！   个人对前缀树的理解就是：不多写一个字母！！！比如你要存储word和world，那么最终集合里面在r的后面就开始分叉，一条路指向d，另一条路指向ld； 实现分析 假如我们存储的是小写字母组成的字符串，如力扣208，那么首先我们可以定义一个节点Trie，然后他有26...

本题求数组中的逆序对，很自然的想到了两层for循环，然而困难题，一定超时！ 在评论区看到了一种利用归并排序“治”的过程，顺带将逆序对求出来了，记录一下，顺便将归并排序和快排做一个比较。 目录 归并排序 cpp实现 与快速排序进行比较 快速排序cpp实现 归并排序 正如图所示，归并排序是将原数组不断的划分，然后开始合并，有点二分法的意思；到只剩一个元素...

刷题总结 回溯法 组合问题 力扣77 力扣17 力扣39 力扣40 小结 回溯法 跟着一个很厉害的**博主(代码随想录)**的文章进行总结。 回溯本质上还是遍历搜索，可以用于解决组合、分割、子集、排列、棋盘问题等等，里面有一句总结的非常到位： for表示横向搜索，递归表示纵向搜索； 组合问题 力扣77 典型的组合问题，可以采用典型的解决方法；思路就是，固定一位，然后在余下的里面固定另一位； 记录一下这里的一个错误，就是在最后退出...

对于全局变量，改变它的作用域，使其只能在本源文件里面使用 最开始，在头文件里面定义一个全局变量，然后在main里面，extern 声明，结果报错了 //Header.h #pragma once int num = 0; //Header.cpp #include"Header.h" //main.cpp #include <iostream> using namespace std; extern int num; int main() { cout << num << endl; return 0; } ...

文章目录 Linux入门&Shell语法 Shell传递函数 Shell运算符 算数运算符 chmod 777 file 改变文件的读写权限 chmod +x file 改变文件的执行权限 关系运算符 布尔运算符 逻辑运算符 字符串运算符 文件测试运算符 Shell echo 命令 Shell printf 命令 Shell test ...