专栏首页CSDN搜“看,未来”LeetCode精选好题(五)

LeetCode精选好题(五)

1、二叉树的层序锯齿形遍历

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如: 给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下:

[
  [3],
  [20,9],
  [15,7]
]

思路

说白了就是层序遍历加上定层翻转而已。

代码实现

vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int> > a;
        if(root==NULL) return a;
        vector<int> b;
        queue<TreeNode*> q;
        q.push(root);
        int n=0;
        while(!q.empty())
        {
            TreeNode* fz;
            int len=q.size();
            n++;//控制层数
            for(int i=0;i<len;i++)
            {
                fz=q.front();
                b.push_back(fz->val);
                if(fz->left!=NULL) q.push(fz->left);
                if(fz->right!=NULL) q.push(fz->right);
                q.pop();
            } 
            if((n&1)==1)
            {
                a.push_back(b);
            }
            else
            {
                reverse(b.begin(),b.end());
                a.push_back(b);
            }
            b.clear();
        } 
        return a;
    }

2、从二叉树的前序遍历与中序遍历构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

思路

对于任意一颗树而言,前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。

这样以来,我们就知道了左子树的前序遍历和中序遍历结果,以及右子树的前序遍历和中序遍历结果,我们就可以递归地对构造出左子树和右子树,再将这两颗子树接到根节点的左右位置。

代码实现

class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
        
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树,并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树,并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 构造哈希映射,帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

3、不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

问总共有多少条不同的路径?

例如,上图是一个7 x 3 的网格。有多少可能的路径?

示例 1:

输入: m = 3, n = 2 输出: 3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3 输出: 28

提示:

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

友情链接

【奇技淫巧】走地图的不同路径

4、找出二叉树中的第K个最小元素

给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明: 你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1

   3
  / \
 1   4
  \
   2

输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3

      5
      / \
     3   6
    / \
   2   4
  /
 1

输出: 3

进阶: 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?

思路:

中序遍历二叉树,输出第K个值。

代码实现:

void recursion(TreeNode* root,int& res,int& k)
    {
        if(!root)
            return;
        
        recursion(root->left,res,k);
        
        k--;
        if(k == 0)
        {
            res = root->val;
            return;
        }
            
        recursion(root->right,res,k);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        int res;
        recursion(root,res,k);
        
        return res;
    }

5、搜索旋转数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1

思路:

题目要求算法时间复杂度必须是 O(logn) 的级别,这提示我们可以使用二分搜索的方法。

但是数组本身不是有序的,进行旋转后只保证了数组的局部是有序的,这还能进行二分搜索吗?答案是可以的。

可以发现的是,我们将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的。拿示例来看,我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分,其中左边 [4, 5, 6] 这个部分的数组是有序的,其他也是如此。

这启示我们可以在常规二分搜索的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的,并根据有序的那个部分确定我们该如何改变二分搜索的上下界,因为我们能够根据有序的那部分判断出 target 在不在这个部分:

如果 [l, mid - 1] 是有序数组,且 target 的大小满足 [nums[l],nums[mid]),则我们应该将搜索范围缩小至 [l, mid - 1],否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组,且 target 的大小满足 (nums[mid+1],nums[r]],则我们应该将搜索范围缩小至 [mid + 1, r],否则在 [l, mid - 1] 中寻找。

代码实现:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (!n) return -1;
        if (n == 1) return nums[0] == target ? 0 : -1;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

6、删除链表的倒数第N个节点

解法:fast先移动n

代码实现

ListNode* removeNthFromEnd(ListNode* head, int n) {
       if(!head) return NULL;
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode* slow = new_head, *fast = new_head;
        for(int i = 0;i<n;++i){  //fast先移动n
            fast = fast->next;
        }
        if(!fast) return new_head->next;
        while(fast->next){      //一起移动
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return new_head->next;
}

7、环形链表寻找入环点

在快慢指针相遇时,在头结点再放一个慢指针,然后让环中那个慢指针继续走,再相遇,就是入环点。 证明:

在第一次相遇时,有等式: 2(D+S1) = D+nS2+(n+1)S1 ->D+S1 = n(S1+S2) ->D = (n-1)(S1+S2)+S2

也就是说,在快慢指针相遇时,在头结点再放一个慢指针,然后让环中那个慢指针继续走,再相遇,就是入环点。

8、对称二叉树

原来递归的空间复杂度也是O(n),我还以为递归没有空间消耗。

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

思路:

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。 因此,该问题可以转化为:两个树在什么情况下互为镜像?

如果同时满足下面的条件,两个树互为镜像: 它们的两个根结点具有相同的值 每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数,通过「同步移动」两个指针的方法来遍历这棵树,p 指针和 q 指针一开始都指向这棵树的根,随后 p 右移时,q 左移,p 左移时,q 右移。每次检查当前 p 和 q 节点的值是否相等,如果相等再判断左右子树是否对称。

代码实现:

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

假设树上一共 n 个节点。

时间复杂度:这里遍历了这棵树,渐进时间复杂度为 O(n)。
空间复杂度:这里的空间复杂度和递归使用的栈空间有关,这里递归层数不超过 n,故渐进空间复杂度为 O(n)。

9、买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路:C++ 利用哨兵,维护一个单调栈。

首先我们要明确这个是在一个时间序列上的,因此我们不能简单的用 最大减最小解决问题,这里我们通过典型的一个例子来解决这个问题:[7,1,5,3,6,4]

这里我们维护一个单调增的栈 在 pricespricesprices 数组的末尾加上一个 哨兵(也就是一个很小的元素,这里设为 0)),就相当于作为股市收盘的标记(后面就清楚他的作用了) 假如栈空或者入栈元素大于栈顶元素,直接入栈 假如入栈元素小于栈顶元素则循环弹栈,直到入栈元素大于栈顶元素或者栈空 在每次弹出的时候,我们拿他与买入的值(也就是栈底)做差,维护一个最大值。

(灰色标记为扫描过的) ①:第一步,栈空,扫描的是 7,我们直接入栈。

②:第二步,入栈元素为 1,他比栈顶元素小,为了维护这个单调栈,我们把7弹出,又因为他即是栈底又是栈顶所以不需要更新我们的最大值,又因为弹出之后为空,我们将1直接入栈我们直接入栈。

③:第三步,入栈元素为 5,他比栈顶元素大,我们直接入栈

④:第四步,入栈元素为 3,他比栈顶元素 5大,我们直接弹栈,并拿他减去栈底元素1(这就是最重要的,模拟了买卖,因为 5 遇上了比它小的 3,因此即使后面遇到更大的元素 C,但是存在 C−3>C−5,因此它已经没用了,计算之后弹出它

⑤:第五步,入栈元素为 6,比栈顶元素大,入栈。

⑥:第六步,入栈元素为 4,比栈顶元素 6小,根据我们刚刚的理论,在遇上 4 之后,6 的最高利润已经确定了,因为无论后面遇上怎么样的升值,在 4 的时候购买的利润显然更高 所以我们弹出 6,并与栈底(也就是我们买入的价值)做差,并与我们之前维护的最大值进行比较,然后更新。

⑦:第七步,现在 哨兵的作用就非常清楚啦,假如没有哨兵,我们单调栈中还有残留的元素没有进行判断(比如 pricespricesprices 数组单调增的情况下,不加哨兵会出现 max=0 的情况),因此 哨兵的作用就是确保单调栈中的每个元素都被进行判定。因此最后的图像应该是这样:

代码实现:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        vector<int> St;
        prices.emplace_back(-1); \\ 哨兵?‍✈️
        for (int i = 0; i < prices.size(); ++ i){
            while (!St.empty() && St.back() > prices[i]){ \\ 维护单调栈?
                ans = std::max(ans, St.back() - St.front()); \\ 维护最大值
                St.pop_back();
            }
            St.emplace_back(prices[i]);
        }

        return ans;
    }
};

10、计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

思路:

优化:每次剔除的时候,对数组进行去零操作。

代码实现:

int countPrimes(int n) {
    boolean[] isPrim = new boolean[n];
    // 将数组都初始化为 true
    Arrays.fill(isPrim, true);

    for (int i = 2; i < n; i++) 
        if (isPrim[i]) 
            // i 的倍数不可能是素数了
            for (int j = 2 * i; j < n; j += i) 
                    isPrim[j] = false;
    
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;
    
    return count;
}

11、无重复字符的最长子串(滑动窗口)

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3: 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。 请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

思路:

这道题主要用到思路是:滑动窗口 什么是滑动窗口? 其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!

如何移动? 我们只要把队列的左边的元素移出就行了,直到满足题目要求! 一直维持这样的队列,找出队列出现最长的长度时候,求出解! 时间复杂度:O(n)

代码实现:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(); i++){
            while (lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
    		}
        return maxStr;
    }
};

12、颜色分类

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶: 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗?

本问题被称为 荷兰国旗问题 ,最初由 Edsger W. Dijkstra提出。 其主要思想是给每个数字设定一种颜色,并按照荷兰国旗颜色的顺序进行调整。

我们用三个指针(p0, p2 和curr)来分别追踪0的最右边界,2的最左边界和当前考虑的元素。

本解法的思路是沿着数组移动 curr 指针,若nums[curr] = 0,则将其与 nums[p0]互换;若 nums[curr] = 2 ,则与 nums[p2]互换。

class Solution { public: /* 荷兰三色旗问题解 */ void sortColors(vector& nums) { // 对于所有 idx < p0 : nums[idx < p0] = 0 // curr 是当前考虑元素的下标 int p0 = 0, curr = 0; // 对于所有 idx > p2 : nums[idx > p2] = 2 int p2 = nums.size() - 1;

while (curr <= p2) {
  if (nums[curr] == 0) {
    swap(nums[curr++], nums[p0++]);
  }
  else if (nums[curr] == 2) {
    swap(nums[curr], nums[p2--]);
  }
  else curr++;
}

} };

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • FTP文件管理项目(本地云)项目日报(四)

    昨天大家都走出了第一步,客户端陆陆续续都在画界面,服务器方面我也初步建设好数据库和解压包两个模块,其他人也在抓紧学习,呈现出明显的分化,努力的人越努力。

    看、未来
  • 学以致用C++设计模式 之 “门面模式“

    之前一直以为,把模块内聚封装起来叫”模板方法模式“,看来是我狭隘了。模板方法模式是将一组算法封装在一起,组成一个对外接口函数,而”门面模式“(我以前叫它”外观模...

    看、未来
  • 【LeetCode两题选手】算法类题目(7.27)

    回溯法 :一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解的话(或者至少不是最后一个解),回溯算法会通过在上一步进行一些变化抛弃该解...

    看、未来
  • 【剑指Offer】40. 最小的 K 个数

    快速排序的 partition() 方法,会返回一个整数 j 使得 a[l…j-1] 小于等于 a[j],且 a[j+1…h] 大于等于 a[j],此时 a[j...

    瑞新
  • LeetCode Weekly Contest 47解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • C/C++用QT写的五子棋源码

    bear_fish
  • BZOJ2115: [Wc2011] Xor(线性基)

    第一行包含两个整数N和 M, 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边,每行三个整数Si,Ti ,Di,表示 Si 与Ti之间存在 一条权...

    attack
  • 力扣(LeetCode)刷题,简单题(第4期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • 查找算法

    查找,作为应用最为广泛和最基础的算法思想之一,几乎在所有应用程序之中都有它的思想身影。往细一点说:查找可以有 顺序查找、二分查找、散列表查找,下面依次来看一下这...

    指点
  • LeetCode Contest 179

    题解:遍历数组,维护一个最大值,当最大值等于当前的下标+1的时候,就是blue的时候

    ShenduCC

扫码关注云+社区

领取腾讯云代金券