思路：利用unordered_map和unordered_set 前者保存根据字母排序后的单词以及对应的原始单词 如果某一个原始单词已经插入结果，那么将其记录在unordered_set，防止重复插入 代码如下： // // Created by jt on 2020/9/29. // #include <vector> #include <unordered_map> #include <unordered_set> #include <string> using namespace std; class Solution { publi...

回溯法，以行为基准进行回溯，如果当前行列摆放皇后与之前的冲突，则不继续回溯，否则，继续下一行的回溯。 代码如下： // // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: /** * * @param n int整型 * @return int整型 */ int totalNQueens(int n) { // write code here int ...

采用回溯法，以行为基准进行回溯，如果在当前行列放置皇后不会与已有皇后冲突，则放置，否则就不放置。 代码如下： // // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: vector<vector<string> > solveNQueens(int n) { vector<vector<string>> res; vector<int> v...

由于行列不相等，因此定义四个变量用于记录边界： 左边界left 右边界right 上边界top 下边界bottom 然后以top和left基准层层打印，值得注意的是，为了避免重复打印，我们需要在打印下边和左边时额外判断一下top和bottom以及left和right是否相等： // // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: vector<int> spiralOrder(vector<vector&...

先按左边界从小到大排序，然后遍历所有区间，边比较边将区间推入结果，如果当前区间与结果的最后一个区间有重叠，更新结果中最后一个区间的边界，代码如下： // // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { vector<Interval> res; ...

循环遍历原有区间，将待插入区间的右端点、左端点分别与当前区间比较，并更新待插入区间的左右端点，代码如下： // // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval> res; ...

基本思路：遍历字符串，用start指针指向单词开头，end指针指向单词结尾，如果有单词，end-start+1即为最后一个单词的长度。 代码如下： // // Created by jt on 2020/9/29. // class Solution { public: int lengthOfLastWord(const char *s) { if (!s) return 0; // 找到最后一个空格 const char *p = s, *start = nullptr, *end = nullptr; while (...

定义左边界右边界（由矩阵的性质可得，左边界也是上边界、右边界也是下边界），以左边界作为循环条件，循环打印即可： // // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: /** * * @param n int整型 * @return int整型vector<vector<>> */ vector<vector<int> > gener...

由于长宽都比较小，采用棋盘式状态压缩DP解决，此类任务一般是在棋盘内填各种形状的块，然后求方案数。 核心思想是：总方案数等于合法横向摆放小矩形方案数之和。下面的图形中，绿色为横向填充，黄色为纵向填充，图1是合法的，图2则是非法的。 设状态矩阵为dp[i][j]，其中i表示第i列，j表示横跨第i-1列和第i列的横向小矩阵的行号的二进制表示，如： 同时，存在如下约束条件： j&k == 0（设i-1列的状态为k） 摆完第i列后，第i列中放置纵向小矩阵的连续空格数要为偶数个，因此j|k中不能存在连续奇数个空格，这个可以通过预处理获得 对于第二个约束条件，很多题解说的是考虑当第i...

C++求排列有三种方法： 利用库函数next_permutation 基于交换 基于回溯 下面用库函数next_permutation求： // // Created by jt on 2020/9/26. // #include <vector> #include <string> using namespace std; class Solution { public: /** * * @param n int整型 * @param k int整型 * @return string字符串 */ ...

基本思路： 先求链表长度n，然后k = k mod n 将链表首尾相连 找到新的head的前一个节点，断链，返回新head 代码如下： // // Created by jt on 2020/9/26. // class Solution { public: /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* rotateRight(ListNode* head, int k) { // write c...

利用哑节点+三个指针： // // Created by jt on 2020/9/26. // class Solution { public: /** * * @param l1 ListNode类 * @param l2 ListNode类 * @return ListNode类 */ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // write code here ListNode dummy(0); List...

简单的二进制进位，用两个指针分别指向两个字符串，从后向前遍历： 如果有进位，保存进位，然后将剩余部分加入新字符串 遍历完某个字符串后，如果存在进位或另一个字符串没有遍历完，继续处理剩余部分 遍历完毕后将字符串进行反转即可 代码如下： // // Created by jt on 2020/9/26. // #include <string> using namespace std; class Solution { public: /** * * @param a string字符串 * @param b string字符串 *...

这道题目有点类似于atoi（将字符串转化为整数），回想一下atoi：如果第一个非空格字符不存在或者不是数字也不是正负号则返回零，否则开始做类型转换，之后检测到非数字(包括结束符 \0) 字符时停止转换，返回整型数。 这道题目里面我们采取以下步骤： 忽略前置空格和后置空格 正负号只能出现在最前面 句点只能出现一次 不能含有正负号、句点、数字以外的字符 不能为空 不能是单独的正负号或句点 如果是科学计数法，需要符合： 没有空格紧邻e e的前面是数字 e的后面是整数 具体的实现方案： 先判断是否包含e 如果包含e，则先判断e的前后是否紧邻空格 如果是的，返回false 如果不是，判断e的前...