1. Toy模板网首页
  2. > Toy博客

【leetcode刷题之路】初级算法（2）——链表+树+排序和搜索+动态规划

9月前 作者：小天才才 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了【leetcode刷题之路】初级算法（2）——链表+树+排序和搜索+动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

3 链表

3.1 【链表】删除链表中的节点

https://leetcode.cn/problems/delete-node-in-a-linked-list/

给出的就是要删除的那个节点，直接前后移动就行了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

3.2 【双指针】删除链表的倒数第 N 个结点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

利用双指针left和right，首先让right遍历n个节点，再让两个指针同时遍历，当right遍历到链表结尾时，left所指的就是倒数第n个节点，正常删除即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* left = head;
        ListNode* right = head;
        for(int i=0;i<n;i++)
        {
            right = right->next;
        }
        if(right == nullptr) return head->next;
        while(right->next!=nullptr)
        {
            left = left->next;
            right = right->next;
        }
        left->next = left->next->next;
        return head;
    }
};

3.3 【链表】反转链表

https://leetcode.cn/problems/reverse-linked-list/

使用头插法解决，后续考虑一下递归和栈。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* ans = nullptr;
        ListNode* x = head;
        while(x)
        {
            ListNode* p = x;
            x = x->next;
            p->next = ans;
            ans = p;
        }
        return ans;
    }
};

3.4 【链表】合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/

常规做法，挨个比较大小，后续考虑如何用递归完成。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;

        ListNode* ans = new ListNode();
        ListNode* tmp = ans;
        while(list1 && list2)
        {
            if(list1->val <= list2->val)
            {
                tmp->next = list1;
                list1 = list1->next;
            }
            else
            {
                tmp->next = list2;
                list2 = list2->next;
            }
            tmp = tmp->next;
        }
        if(!list1) tmp->next = list2;
        if(!list2) tmp->next = list1;
        return ans->next;
    }
};

3.5 【链表】回文链表

https://leetcode.cn/problems/palindrome-linked-list/

首先将链表进行反转，然后按照链表长度的一半逐一进行比较即可，这里要注意赋值的问题，一开始我是想直接把head赋值给一个空链表，后面发现指针这个东西都是指向同一个地址的，所以其中一个的结构变了另一个也会跟着变，后来就改用数组来存head里面原来正序的数字了，后期可以考虑一下如何用双指针（快慢指针）和栈怎么解决。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* res = nullptr;
        vector<int> num;
        int length = 0;
        while(head)
        {
            num.push_back(head->val);
            ListNode *temp = head;
            head = head->next;
            temp->next = res;
            res = temp;
            length++;
        }
        int i = 0;
        while(res && i*2<=length-1)
        {
            if(num[i] != res->val) return false;
            res = res->next;
            i++;
        }
        return true;
    }
};

3.6 【双指针】环形链表

https://leetcode.cn/problems/linked-list-cycle/

定义快慢指针，快指针一次走两步，慢指针一次走一步，如果存在环，则两个指针总会相遇，否则不存在环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

4 树

4.1 【递归】二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

递归解决，分别遍历左右子树，找出其中的最大值作为树的最大深度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        else
        {
            int left_depth = maxDepth(root->left);
            int right_depth = maxDepth(root->right);
            return max(left_depth,right_depth)+1;
        }
    }
};

4.2 【递归】验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

递归实现，首先要明白二叉搜索树的判定条件，一是左子树<root<右子树，二是下面的左子树的值要比当前结点小，而右子树的值要比当前结点大，也就是不能只在一个小的子树上满足这个条件，往上回溯几代之后这个条件要依然满足才行。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root , NULL , NULL);
    }

    bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {
        if(root == NULL) return true;
        else
        {
            if(min != NULL && root->val <= min->val) return false;
            if(max != NULL && root->val >= max->val) return false;
        }
        return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
    }
};

4.3 【递归】对称二叉树

https://leetcode.cn/problems/symmetric-tree/

以下是递归解法，详见代码，之后需要考虑一下非递归如何实现。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        //如果root为空，则返回true
        if(root == NULL) return true;
        else return isSymmetric(root->left, root->right);
    }

    bool isSymmetric(TreeNode* left, TreeNode* right) {
        //如果左右子树均为空，则返回true
        if(left == NULL && right == NULL) return true;
        //如果只有一个子树为空，或者两个子树均不为空但值不相等，则返回false
        else if(left == NULL || right == NULL || left->val != right->val) return false;
        //比较左子树的右子树和右子树的左子树是否对称、左子树的左子树和右子树的右子树是否对称
        else return isSymmetric(left->right, right->left) && isSymmetric(left->left, right->right);
    }
};

4.4 【BFS】二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/

BFS解题，按照树的每一层进行遍历，首先定义队列，如果当前节点不为空，则加入队列，之后分别遍历该节点的左右子树，依次重复上述操作，直到最后队列元素为空。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == NULL) return ans;
        queue<TreeNode*> tree_node;
        tree_node.push(root);
        while(!tree_node.empty())
        {
            int n = tree_node.size();
            vector<int> subtree;
            for(int i=0;i<n;i++)
            {
                TreeNode* temp = tree_node.front();
                tree_node.pop();
                subtree.push_back(temp->val);
                if(temp->left != NULL) tree_node.push(temp->left);
                if(temp->right != NULL) tree_node.push(temp->right);
            }
            ans.push_back(subtree);
        }
        return ans;
    }
};

4.5 【分治】将有序数组转换为二叉搜索树

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

分治解题，将构造树的过程分为两部分，首先从数组的中间元素开始，左边的数为左子树，右边的数为右子树，依次往后递推。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0) return NULL;
        else return sortedArrayToBST(nums, 0, nums.size()-1);
    }

    TreeNode* sortedArrayToBST(vector<int>& nums, int start, int end) {
        if(start > end) return NULL;
        else
        {
            int mid = (start + end) / 2;
            TreeNode* root = new TreeNode(nums[mid]);
            root->left = sortedArrayToBST(nums, start, mid-1);
            root->right = sortedArrayToBST(nums, mid+1, end);
            return root;
        }
    }
};

5 排序和搜索

5.1 【排序】合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/

直接把nums2的值赋值到nums1后面，然后对nums1进行排序即可。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i=0;i<n;i++)
        {
            nums1[m+i] = nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};

5.2 【二分】第一个错误的版本

https://leetcode.cn/problems/first-bad-version/

二分法解题，注意遍历大小是从1到n，不要越界了。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1 , right = n;
        while(left<right)
        {
            int mid = left + (right - left) / 2;
            if(!isBadVersion(mid)) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

6 动态规划

6.1 【动态规划】爬楼梯

https://leetcode.cn/problems/climbing-stairs/

爬一楼需要1次，爬二楼需要2次，爬三楼需要3次，这个3次可以看做是从一楼+2或者二楼+1
也就是f（n）=f（n-1）+f（n-2）

class Solution {
public:
    int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;

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

6.2 【动态规划】买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

动态规划解题，首先定义数组dp[i][2]

  • dp[i][0]：表示第i+1天结束的时候，如果手里没有持有股票，最大的利润是多少
  • dp[i][1]：表示第i+1天结束的时候，如果手里持有股票，最大的利润是多少

在这里我们分别对上述两个进行计算：

  • dp[i][0]
    这个考虑到两种情况，一是第i天没有持有股票，所以与第i天未持有股票的利润一样，二是第i天持有股票，但是决定在第i+1天卖掉，所以利润为第i天持有股票的利润+第i+1天该股票的价格，两个取最大值即可
  • dp[i][1]
    这个也考虑到两种情况，一是第i天持有股票，所以与第i天持有股票的利润一样，二是第i天未持有股票，但是决定在第i天买入，所以利润为负值，两个取最大值即可
//原始代码
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();
        if(length==1) return 0;
        int dp[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i=1;i<length;i++)
        {
            dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1],-prices[i]);
        }
        return dp[length-1][0];
    }
};

//优化后的代码---用两个变量代替数组
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();
        if(length==1) return 0;
        int stock_unhold = 0;
        int stock_hold = -prices[0];
        for(int i=1;i<length;i++)
        {
            stock_unhold = max(stock_unhold,stock_hold + prices[i]);
            stock_hold = max(stock_hold,-prices[i]);
        }
        return stock_unhold;
    }
};

6.3 【动态规划】最大子数组和

https://leetcode.cn/problems/maximum-subarray/

利用动态规划，首先定义数组dp[i]，表示终点下标为i的序列的最大子数组和，主要考虑以下两种情况：

  • 如果dp[i-1]大于0，则继续向前增加下标为i的数值，作为dp[i]的子数组和
  • 如果dp[i-1]小于0，则从这里开始停止，重新计算子数组和，赋值为0后再加入下标为i的数值，作为dp[i]的子数组和

最后的结果就是数组中最大的那个值

//原始
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int length = nums.size();
        if(length==1) return nums[0];
        int dp[length];
        int ans = nums[0];
        dp[0] = nums[0];
        for(int i=1;i<length;i++)
        {
            dp[i] = max(dp[i-1],0) + nums[i];
            if(dp[i] > ans) ans = dp[i];
        }
        return ans;
    }
};

//优化代码---用变量代替数组
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int length = nums.size();
        if(length==1) return nums[0];
        int dps = nums[0];
        int ans = nums[0];
        for(int i=1;i<length;i++)
        {
            dps = max(dps,0) + nums[i];
            if(dps > ans) ans = dps;
        }
        return ans;
    }
};

6.4 【动态规划】打家劫舍

https://leetcode.cn/problems/house-robber/

利用动态规划，首先定义数组dp[i][2]，状态转移如下所示：

  • dp[i][0]表示第i家不被偷，则前一家可能被偷，也可能没有被偷，取最大值即可；
  • dp[i][1]表示第i家被偷，则前一家一定没有被偷，所以为dp[i-1][0]+nums[i]

最后在第i家的时候取被偷和未被偷之间的最大值即可文章来源地址https://www.toymoban.com/news/detail-494757.html

class Solution {
public:
    int rob(vector<int>& nums) {
        int length = nums.size();
        if(length==1) return nums[0];
        int dp[length][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for(int i=1;i<length;i++)
        {
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        if(dp[length-1][0] > dp[length-1][1]) return dp[length-1][0];
        else return dp[length-1][1];
    }
};

到了这里，关于【leetcode刷题之路】初级算法（2）——链表+树+排序和搜索+动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包