TOP100

2021-04-14 本文已影响0人李伟13

142. 环形链表 II

我的思路

①fast = l + ak + x
②slow = l + bk + x
③fast = 2 * slow
2l + 2bk + 2x = l + ak + x ==> l = (a - 2b)k - x
所以：slow从相遇点出发，ptr从head出发，在入口处相遇
如图所示（图挂了）

139. 单词拆分

题解思路

1.使用unordered_set存储dict（因为set有find功能）
2.遍历字符串s.
3.遍历j从 0到i - 1,看是否在dict里面有对应的字符串.有,则dp[j] = true;

需要注意的是,必须是外循环递增i,内循环再递增j < i,我本来打算i = 0, j > i,这样的话需要从右往左遍历(应该).

128. 最长连续序列

题解思路

1.将数组放到unordered_set里去重
2.遍历数组,如果存在比当前数大1的,计数+1,tmpnum++直到没有为止
3.计算max
一个减少时间复杂度的小skill，如果存在比nums[i]小1的就continue了,因为在连续序列的最小数那里已经计算过了,比如说[1,2,3,4].到2的时候,1那里已经计算过整个len了,所以综合起来时间复杂度为O(n)

unordered_set的count的平均时间复杂度为O(1),最坏为O(n),可以去了解下为什么
https://en.cppreference.com/w/cpp/container/unordered_set/count

使用异或

124. 二叉树中的最大路径和

题解思路

1.递归，使用全局变量存储max。
2.节点存储到当前节点的最大值，root.val + max(leftmax, rightmax)
3.max 为root.val + leftmax + rightmax,

121. 买卖股票的最佳时机

我的思路

使用迭代的minnum，maxprofit

我的思路2：动态规划

dp[i] 表示当前最大利润，dp[i] = max(dp[i - 1], prices[i] - minnum);
我觉得反而复杂了

114. 二叉树展开为链表

题解思路

cur右侧移到左侧的最右侧，没有左侧的右侧，移到左侧

while (cur != nullptr) {
     if (cur -> left != nullptr) {
          TreeNode* pre = cur -> left;
          while(pre -> right != nullptr) {
              pre = pre -> right;
          }
          pre -> right = cur -> right;
          cur -> right = cur -> left;
          cur -> left = nullptr;
     }
     cur = cur -> right;
}

105. 从前序与中序遍历序列构造二叉树

我的思路

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int inleft, int preleft, int len) {
        TreeNode* root;
        if (len <= 0) {
            return nullptr;
        }
        if (len > 0) {
            root = new TreeNode(preorder[preleft]);
        }

        int index = inleft;
        for (; index < len + index; ++index) {
            if (preorder[preleft] == inorder[index]) {
                break;
            }
        }
        root -> left = buildTree(preorder, inorder, inleft, preleft + 1, index - inleft);
        root -> right = buildTree(preorder, inorder, index + 1, preleft + index - inleft + 1, len - 1 - index + inleft);
        return root;
    }

注意细节，我在计算rightpreleft的时候使用len - 1 - preleft来计算了，忽略了right的长度

104. 二叉树的最大深度

我的思路

基础递归

if (root == nullptr)      return 0;
return max(maxDepth(root -> left), maxDepth(root -> right)) + 1;

101. 对称二叉树

我的思路

使用两个dfs得到两个vector，因为空这个内容无法用数字代替，所以把数字转化为string类型，空用其他符号表示
比对两个vector
当然最后没有做，因为我觉得有些问题。

题解思路1：递归

在一个dfs内同时搜索左右两边，同时进行，传入左右两个节点。

题解思路2：迭代

迭代用队列来做.

98. 验证二叉搜索树

我的思路

中序遍历，使用vec存。我打算用pre 和cur来做的，结果都是bug,改了一下，改好了
改前

if (root == nullptr) {
            return;
}
if (root -> val <= pre) {
    flag = false;
}
inorder(root -> left);
pre = root -> val;
inorder(root -> right);

改后

if (root == nullptr) {
            return;
}
inorder(root -> left);
if (root -> val <= pre) {
    flag = false;
}
pre = root -> val;
inorder(root -> right);

96. 不同的二叉搜索树

题解思路1

递归

for (int i = 1; i <= n; ++i) {
    ans += numTrees(i - 1) * numTrees(n - i);
}

题解思路2

记忆化递归
把ans存起来

题解思路3

1.n个数组成的不同二叉树,分解为以1为root,左空右n - 1/以2为root 左1右n - 2/..,这样n种方式;
2.以i为root的方式有 [i - 1] * [n - i]种

i from 1 to n
j == 0  ==> 左 ans[0] * 右 ans[n]
j == 1 ==> 左 ans[1] * 右 ans[n - 1]
左[j - 1] 右 [n - j]

for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= i; j++)
        ans[i] += ans[j - 1] * ans[i - j];
    }

84. 柱状图中最大的矩形

思路

单调栈

单调栈模板

for (int i = 0; i< nums.size(); ++i) {
    while (!st.empty() && nums[st.top()] > nums[i]) {
        st.pop();
    }
    st.push(i);
}

需要注意的地方

1.[1,2,3,4,5]
在末尾添0
2.[2,1,2]
在头添0

cur = st.top();
st.pop();
left = st.top() + 1;

79. 单词搜索

思路

回溯

注意的点

1.在主方法中得到true就返回，算是剪枝
2.走过的路用别的符号表示，例如“0”，使用临时变量存储四个方向的返回值，在返回之前把原字符填回去

78. 子集

思路

特点
1.每一个节点均返回
2.满足下一个节点比当前节点大.

""
1      2      3
2 3    3

思路2

无重复子集符合一下排列,假设n = 3
000 001 010 100 101 110 111

int n = 1 << nums.size();
        for (int i = 0; i < n; ++i) {
            tmp.clear();
            int j = 0;
            while (j < nums.size()) {
                if (i & (1 << j)) {
                    tmp.push_back(nums[j]);
                }
                j++;
            }
            ans.push_back(tmp);
        }

再写也写不出来
1.建一个哈希表存t的字母在窗口内的出现次数，通过动态的窗口内包含字符数目（n = t.size()）来维护窗口
2.开滑
2.1 right滑到第一个完全囊括窗口的右边
2.1.1 滑过的哈希字母值均减1，如果遇到t中的字母，则n--;
2.2如果n为0了，窗口到位了，开始记录最短长度
2.2.1 滑左侧的，滑一个加一个哈希值，如果加到一个t中的字母,n++,就又开始滑右边了.

75. 颜色分类

我的思路

sort

思路1

使用left right 和index

while (index <= right) {
    // cout << nums[index] << endl;
    if (nums[index] == 0) {
        if (index != left) {   1  0  2  index ==> [1] left ==>[0]
            swap(nums[index], nums[left]);
        }
        else {
            index++;
        }
        left++;

    }
    else if (nums[index] == 2){
        swap(nums[index], nums[right]);    2  0  1 index ==> [0]  right ==> [2]
        right--;
    }
    else {
        index++;
    }
}

思路2

记录0,1的数.全部为2,替换为1,替换为0

int num = nums[i];
nums[i] = 2;
if (num < 2) {
    nums[n1] = 1;
    n1++;
}
if (num == 0) {
    nums[n0] = 0;
    n0++;
}

72. 编辑距离

思路

dp[i][j]为word1.substr(0, i) 到word2.substr(0,j)的距离
增 dp[i][j - 1] + 1
删 dp[i - 1][j] + 1 这一行删一个相当于上一行增一个,反推
改 dp[i - 1][j - 1] + 1
求min

70. 爬楼梯

我的思路

像斐波那契那样迭代，递归超时

64. 最小路径和

我的思路

grid[i][j] = grid[i][j] + min(grid[i - 1][j], grid[i][j - 1]);

62. 不同路径

我的思路

从右下向左上,垓格子的路径数量等于right + down

56. 合并区间

我的思路

sort
cur[left][right] = [0][1]
while : right > [i + 1][1] ==> right = max(right, [i + 1][1]) 向右延展right

55. 跳跃游戏

我的思路

例如nums[0] == 2那么到i = 1时就只能走1步,max(nums[i], num[i - 1] - 1)如果还没到最后一位就到0.，就到不了了

for (int i = 1; i < nums.size() - 1; ++i) {
    nums[i] = max(nums[i - 1] - 1, nums[i]);
    if (nums[i] == 0) {
        return false;
    }
}
return true;

题解思路

看i + nums[i]能不能覆盖最后一个下标
需要注意的是，遍历的右边界是cover，能到达的最远的地方。

int cover = 0;
for (int i = 0; i <= cover; ++i) {
     cover = max(cover, i + nums[i]);
     if (cover >= nums.size() - 1) return true;
}

53. 最大子序和

我的思路

~~我是傻逼~~

按nums[i] > 0 或< 0分类

for (int i = 1; i < nums.size(); ++i) {
// cout << "cur " << cur << " maxnum " << maxnum << endl;
if (nums[i] > 0) {
    if (maxnum < 0) {
        cur = nums[i];
        maxnum = cur;
    }
    else {
        cur = max(cur + nums[i], nums[i]);
        maxnum = max(maxnum, cur);
    }
}
else {
    if (cur + nums[i] > 0) {
        cur += nums[i];
    }
    else {
        cur = nums[i];
        maxnum = max(maxnum, cur);
    }
}
}

思路1

按sum分.

我大于0就有资本暂时减去num为后面更大的sum做准备
小于0不如等待下一个大于0的num
使用max取的每个阶段的sum的最大值

if (sum > 0) {
    sum += num;
}
else {
    sum = num;
}
ans = max(ans, sum);

思路2 动态规划

dp[i - 1] 表示到i - 1为止的最大连续子数组的和
那么在i时,如果dp[i - 1] < 0 则 dp[i] = nums[i]反之则dp[i] = dp[i - 1] + nums[i]
因为只有前后关系,所以可以优化成如下

dp = dp > 0 ? dp + nums[i] : nums[i];
ans = max(ans, dp);

49. 字母异位词分组

我的思路

sort string 得到string vec键值对

unordered_map<string, vector<string> > m;
for (string& str : strs) {
    string s = str;
    sort(s.begin(), s.end());
    m[s].push_back(str);
}

值得注意的地方↓
第三行代码直接都进行初始化了

unordered_map<string, vector<string> > m;
s = str;
m[s].push_back(str); //直接都进行初始化了。

48. 旋转图像

我的思路

由外向内层序处理

matrix[layer][layer + index] = matrix[layer + slen - index][layer];
matrix[layer + slen - index][layer] = matrix[layer + slen][layer + slen - index];
matrix[layer + slen][layer + slen - index] = matrix[layer + index][layer + slen];
matrix[layer + index][layer + slen] = tmp;

思路2

先右上-左下翻转，再左右对称翻转

46. 全排列

思路1

[1,2,3]的全排列是1+[2,3]的全排列 + (2+ [1,2]) + (3 + [1,2])
使用continue和find来跳过已经使用过的数

        for (int i = 0; i < nums.size(); ++i) {
            auto it = find(tmp.begin(), tmp.end(), nums[i]);
            if (it != tmp.end()) continue;
            tmp.push_back(nums[i]);
            dfs(nums);
            tmp.pop_back();
        }

思路2

https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
交换法

void dfs(vector<int>& nums, int index) {
    if (index == nums.size()) {
        ans.push_back(nums);
        return;
    }
    for (int i = index; i < nums.size(); ++i) {
        swap(nums[index], nums[i]);
        dfs(nums, index + 1);
        swap(nums[index], nums[i]);
}

39. 组合总和

我的思路

使用dfs,但是时间很长，内存很大。

遇到的问题
在引用的情况下使用sort函数导致答案出错。

void dfs(vector<int>& tmp, vector<int>& candidates, int target) {
    if (target == 0) {
        sortans.push_back(tmp);
        return;
    }
    if (target < 0) {
        return;
    }
    for (int i = 0; i < candidates.size(); i++) {
        tmp.push_back(candidates[i]);
        dfs(tmp, candidates, target - candidates[i]);
        tmp.pop_back();
    }
}

改进思路

增加一个下标变量，不往回加譬如[2,3,5] ,3分支就不加2了。也减少了去重操作，速度快了很多

    void dfs(vector<int>& tmp, vector<int>& candidates, int target, int startIndex) {
        if (target == 0) {
            ans.push_back(tmp);
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = startIndex; i < candidates.size(); i++) {
            tmp.push_back(candidates[i]);
            dfs(tmp, candidates, target - candidates[i], i);
            tmp.pop_back();
        }
    }

34. 在排序数组中查找元素的第一个和最后一个位置

我的想法

二分查找，一次找left一次找right

具体边界条件列一列看一看奇数偶数。
找左边界的时候，=放在right那，right大胆移 left = mid+1小心移 1,8,8,8,8,8,8,8,8 最后分析一下1,8 1,8,8的情况，发现没有问题最后left == right
找右边界的时候, = 放在left那,left大胆移1,8,8,8,8,8,8,8,9，分析一下，发现陷入循环，我们让mid靠右

while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
    left = mid + 1;
}
else if (nums[mid] >= target) {
    right = mid;
  }
}

32. 最长有效括号

思路1

正向逆向结合
左向右移动，筛出无效右括号())()()
右向左移动，筛出无效左括号((((())()()

左向右有效括号长度:
1.为左括号，lcnt++，为右括号，rcnt++；
2.lcnt == rcnt； left有效括号 == cnt * 2；
3.rcnt > lcnt rcnt = lcnt = 0;
右向左同理
取max

思路2

正常人没法想出这种思路

stack<int> st;
st.push(-1);
int len = s.size();
int maxlen = 0;
int cntr = 0, cntl = 0;
for (int i = 0; i < len; ++i) {
    if (s[i] == '(') {
        st.push(i);
    }
    else {
        st.pop();
        if (st.empty()) {//只有新的无匹配右括号出现才会有空的情况
            st.push(i);
        }
        else {
            maxlen = max(maxlen, i - st.top());
        }
    }
}

栈底是最后一个没有被匹配的右括号的下标

42. 接雨水

思路1

动态规划，交叉区域

思路2

移动最短边

31. 下一个排列

思路：

三个步骤
1.找到从右往左的第一对降序pair
2.找到右侧第一个比left大的数，swap
3.将left右侧翻转

TOP100

我的思路

我的思路

题解思路

题解思路

我的思路

使用异或

题解思路

我的思路

我的思路2：动态规划

题解思路

我的思路

我的思路

我的思路

我的思路

题解思路1：递归

题解思路2： 迭代

我的思路

题解思路1

题解思路2

题解思路3

我的思路

思路

思路

需要注意的地方

思路

注意的点

思路

思路2

思路

我的思路

思路1

思路2

思路

我的思路

我的思路

我的思路

我的思路

我的思路

题解思路

我的思路

思路1

思路2 动态规划

我的思路

我的思路

思路2

思路1

思路2

我的思路

改进思路

我的想法

思路1

思路2

思路1

思路2

思路：

猜你喜欢

热点阅读

题解思路2：迭代