力扣

day1 剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode） class CQueue {private: stack<int> PUSH; stack<int>POP;public: void appendTail(int value) { PUSH.push(value); } int deleteHead() { if(POP.empty()) { int x = 0; while(!PUSH.empty()) { x = PUSH.top(); POP.push(x); PUSH.pop(); } } if(POP.empty())return -1; int x = POP.top(); POP.pop(); return x; }};剑指 Offer 30. 蕴含min函数的栈 - 力扣（LeetCode） class MinStack {private: stack<int>st; stack<int>_min;public: void push(int x) { st.push(x); if(_min.empty() || _min.top()>=x) _min.push(x); } void pop() { int x = st.top(); st.pop(); if(x == _min.top()) { _min.pop(); } } int top() { return st.top(); } int min() { return _min.top(); }};day2 ...

单链表根底题OR36 链表的回文结构 https://www.nowcoder.com/ta/2016test?tag=581 对于一个链表，请设计一个工夫复杂度为O(n),额定空间复杂度为O(1)的算法，判断其是否为回文结构。 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保障链表长度小于等于900。 思路：已知长度小于等于900，那么逆置半个链表也能够看做O(1) 1.先找到两头结点，有两个就返回第二个 2.逆置midnode链表 class PalindromeList {public: struct ListNode* middleNode(struct ListNode* head) { int count = 0; struct ListNode* t = head; while(t!= NULL) { ++count; t = t->next; } int count1 = count/2; t = head; while(count1--) { t = t->next; } return t; }struct ListNode* reverseList(struct ListNode* head){ struct ListNode* t = head; int a[910] = {0}; int count = 0; while(t != NULL) { a[count++] = t->val; t = t->next; } struct ListNode* h = ( struct ListNode*)malloc(sizeof( struct ListNode)); struct ListNode* coph = h; coph->next = NULL; for(int i=count-1;i>=0;--i) { struct ListNode* newnode = ( struct ListNode*)malloc(sizeof( struct ListNode)); newnode->next = NULL; newnode->val = a[i]; h ->next = newnode; h = newnode; } return coph->next;} bool chkPalindrome(ListNode* A) { // write code here struct ListNode* midnode = middleNode(A); struct ListNode* rhead = reverseList(midnode); struct ListNode* t1 = A; struct ListNode* t2 = rhead; while(t2 != NULL) { if(t1->val != t2->val) return false; t1 = t1->next; t2 = t2->next; } return true; }};141. 环形链表 ...

原题链接https://leetcode-cn.com/probl... 解题思路思路外围：nums中只有一部分数字有可能成为最长序列的起始点，咱们只遍历以它们为终点的间断序列 步骤： set(nums)去重：遍历set(sum)，找出“合乎终点资质的下标:i”：i-1不在set(nums)中i+1在set(nums)中遍历这些点，计算以它们为终点的最长间断序列长度工夫复杂度O(n)证实:因为上述第3步中：遍历的序列之间没有重合局部，所以总遍历次数小于等于len(nums)欢送在我的博客轻松摸索更多思路 代码class Solution: def longestConsecutive(self, nums: List[int]) -> int: if not nums: return 0 n=set(nums) starting_points=set() for i in n: if (not i-1 in n) and (i+1 in n): starting_points.add(i) max_l=1 for i in starting_points: cur_l=1 while(i+1 in n): cur_l+=1 i+=1 max_l=max(max_l,cur_l) return max_l

前言毕业多年，却素来没有刷过算法题，始终在鸿鹄之志虚度光阴，在被公司卷完之后，我决定痛定思痛，开启刷题打算。致力不会徒劳，什么时候开始都不晚。第一天废话稍多，心愿本人可能坚持下去。 刷题打算第一天，进度失常，OVER。

1. 交易股票的最佳时机（以下均疏忽暴力求解） 一次遍历策略： 既然只有一次交易，那么能够通过遍从来寻找最大的差值 过程： graph TD应用数组一一存储元素-->寻找前面元素的最低值-->更新并存储其差值工夫复杂度：O(n)空间复杂度：O(1)public class Solution { public int maxProfit(int prices[]) { int minprice = Integer.MAX_VALUE; int maxprofit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] < minprice) { minprice = prices[i]; } else if (prices[i] - minprice > maxprofit) { maxprofit = prices[i] - minprice; } } return maxprofit; }}2. 交易股票的最佳时机 II贪婪算法策略： 隔日上涨：明天买入，今天卖出多日上涨：持有股票到最高点再卖出隔日 / 多日上涨：不交易graph TD遍历数组-->若数值递增则直至上涨的前一天卖出-->若数值递加则不交易-->统计利润总值工夫复杂度：O(n)空间复杂度：O(1)class Solution { public int maxProfit(int[] prices) { int profit = 0; for (int i = 1; i < prices.length; i++) { int tmp = prices[i] - prices[i - 1]; if (tmp > 0) profit += tmp; } return profit; }}3. 交易股票的最佳时机 III工夫复杂度：O(n)空间复杂度：O(1)var maxProfit = function(prices) { const n = prices.length; let buy1 = -prices[0], buy2 = -prices[0]; let sell1 = 0, sell2 = 0; for (let i = 1; i < n; i++) { buy1 = Math.max(buy1, -prices[i]); sell1 = Math.max(sell1, buy1 + prices[i]); buy2 = Math.max(buy2, sell1 - prices[i]); sell2 = Math.max(sell2, buy2 + prices[i]); } return sell2;};4. 交易股票的最佳时机 IV5. 最佳交易股票机会含冷冻期6. 交易股票的最佳时机含手续费

DFS（Deep First Search）深度优先搜寻 与 BFS（Breath First Search）广度优先搜寻DFS：用到了栈构造，先进后出，重点在于递归，适合寻找特定指标 BFS：用到了队列构造，先进先出，重点在于队列，适合大范畴搜查 二叉树的深度优先 二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历（上面解法以中序遍历为例） 1. 递归工夫复杂度：O(n)空间复杂度：O(n)先判断根节点是否存在，再遍历左节点，最初遍历右节点 var inorderTraversal = function(root) { const res = []; const inorder = (root) => { if (!root) { return; } inorder(root.left); res.push(root.val); inorder(root.right); } inorder(root); return res;};2. 迭代工夫复杂度：O(n)空间复杂度：O(n)与办法1相似，区别在于递归时隐式保护一个栈，而在迭代时须要显式地将这个栈模仿进去，其余的实现与细节都雷同var inorderTraversal = function(root) { const res = []; const stk = []; while (root || stk.length) { while (root) { stk.push(root); root = root.left; } root = stk.pop(); res.push(root.val); root = root.right; } return res;};3. Morris 遍历工夫复杂度：O(n)空间复杂度：O(1)如果没有左节点，先将值退出答案数组，再拜访右节点，即 x = x.right如果有左节点，则找到左节点上最右的节点（即左子树中序遍历的最初一个节点，在中序遍历中的前驱节点），记为 predecessor 。依据 predecessor 的右节点是否为空，进行如下操作：如果 \textit{predecessor}predecessor 的右节点为空，则将其右节点指向x，而后拜访左节点，即 x = x.left如果 predecessor 的右节点不为空，则此时其右节点指向 x，阐明曾经遍历完左子树，咱们将 predecessor 的右节点置空，将 x 的值退出答案数组，而后拜访 x 的右节点，即 x = x.right反复上述操作，直至拜访完整棵树var inorderTraversal = function(root) { const res = []; let predecessor = null; while (root) { if (root.left) { // predecessor 节点就是以后 root 节点向左走一步，而后始终向右走至无奈走为止 predecessor = root.left; while (predecessor.right && predecessor.right !== root) { predecessor = predecessor.right; } // 让 predecessor 的右指针指向 root，持续遍历左子树 if (!predecessor.right) { predecessor.right = root; root = root.left; } // 阐明左子树曾经拜访完了，咱们须要断开链接 else { res.push(root.val); predecessor.right = null; root = root.right; } } // 如果没有左孩子，则间接拜访右孩子 else { res.push(root.val); root = root.right; } } return res;};二叉树的广度遍历 ...

最大子序和1. 暴力法工夫复杂度：O(N^2)空间复杂度：O(1)设置两层for循环存储第一个数字的值，顺次加上前面的数字，只存储最大值依此类推 class Solution{public: int maxSubArray(vector<int> &nums) { int max = INT_MIN; int numsSize = int(nums.size()); for (int i = 0; i < numsSize; i++) { int sum = 0; for (int j = i; j < numsSize; j++) { sum += nums[j]; if (sum > max) { max = sum; } } } return max; }};2. 动静布局工夫复杂度：O(N)空间复杂度：O(1)一一加值比拟，存储最大值一旦遇到加值后的后果 < 0，则只保留之前计算的最大值，从新开始下一个加值比拟 class Solution{public: int maxSubArray(vector<int> &nums) { int result = INT_MIN; int numsSize = int(nums.size()); //dp[i]示意nums中以nums[i]结尾的最大子序和 vector<int> dp(numsSize); dp[0] = nums[0]; result = dp[0]; for (int i = 1; i < numsSize; i++) { dp[i] = max(dp[i - 1] + nums[i], nums[i]); result = max(result, dp[i]); } return result; }};3.贪婪算法工夫复杂度：O(N)空间复杂度：O(1)与动静布局基本一致class Solution{public: int maxSubArray(vector<int> &nums) { //相似寻找最大最小值的题目，初始值肯定要定义成实践上的最小最大值 int result = INT_MIN; int numsSize = int(nums.size()); int sum = 0; for (int i = 0; i < numsSize; i++) { sum += nums[i]; result = max(result, sum); //如果sum < 0，从新开始找子序串 if (sum < 0) { sum = 0; } } return result; }};4. 分治法工夫复杂度：O(nlog(n))空间复杂度：O(log(n))class Solution{public: int maxSubArray(vector<int> &nums) { //相似寻找最大最小值的题目，初始值肯定要定义成实践上的最小最大值 int result = INT_MIN; int numsSize = int(nums.size()); result = maxSubArrayHelper(nums, 0, numsSize - 1); return result; } int maxSubArrayHelper(vector<int> &nums, int left, int right) { if (left == right) { return nums[left]; } int mid = (left + right) / 2; int leftSum = maxSubArrayHelper(nums, left, mid); //留神这里应是mid + 1，否则left + 1 = right时，会有限循环 int rightSum = maxSubArrayHelper(nums, mid + 1, right); int midSum = findMaxCrossingSubarray(nums, left, mid, right); int result = max(leftSum, rightSum); result = max(result, midSum); return result; } int findMaxCrossingSubarray(vector<int> &nums, int left, int mid, int right) { int leftSum = INT_MIN; int sum = 0; for (int i = mid; i >= left; i--) { sum += nums[i]; leftSum = max(leftSum, sum); } int rightSum = INT_MIN; sum = 0; //留神这里i = mid + 1，防止反复用到nums[i] for (int i = mid + 1; i <= right; i++) { sum += nums[i]; rightSum = max(rightSum, sum); } return (leftSum + rightSum); }};

无反复字符的最长子串1. 暴力解法工夫复杂度：O(N^3)空间复杂度：O(N)设置两个指针，左、右指针同时指向第一个元素一一挪动右指针，直至右指针所指向的值等于左指针时，终止本轮循环让左指针向右走一位，重置右指针，让右指针等于左指针反复第 2、3 步，直到左指针没有能够指向的值 2. 滑动窗口工夫复杂度：O(N)空间复杂度：O(N)设置左、指针同时指向第一个元素，将它存进map数组里一一挪动右指针，直至右指针所指向的值等于左指针，存下以后字符串长度，左指针也向右挪动到该反复元素的开端以此类推，直至遍历实现，存储最大的字符串长度 var lengthOfLongestSubstring = function (s) { // 哈希汇合，记录每个字符是否呈现过 const occ = new Set(); const n = s.length; // 右指针，初始值为 -1，相当于咱们在字符串的左边界的左侧，还没有开始挪动 let rk = -1, ans = 0; for (let i = 0; i < n; ++i) { if (i != 0) { // 左指针向右挪动一格，移除一个字符 occ.delete(s.charAt(i - 1)); } while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) { // 一直地挪动右指针 occ.add(s.charAt(rk + 1)); ++rk; } // 第 i 到 rk 个字符是一个极长的无反复字符子串 ans = Math.max(ans, rk - i + 1); } return ans;};

两数相加定义两个指针别离指向两个链表的表头另外定义一个指针记录前两个指针相加的后果是否进制，是则加一贮存两个指针存储的加值逐渐相加 const addTwoNumbers = (l1, l2) => { // 定义一个新链表 const l3 = new ListNode(0); // 定义三个链表的指针 let [p1, p2, p3] = [l1, l2, l3]; // c示意进位数，一开始为0 let c = 0; // 遍历两个链表，直到两个都为空为止 while (p1 || p2) { // p1指针以后的值 const v1 = p1 ? p1.val : 0; // p2指针以后的值 const v2 = p2 ? p2.val : 0; // 将两个指针的值和进位相加 const val = v1 + v2 + c; // 更新进位数 c = Math.floor(val / 10); // 更新新链表下一位 p3.next = new ListNode(val % 10); // 如果p1还有值，更新到下一位，p2同理 p1 = p1 ?.next; p2 = p2 ?.next; // p3更新到下一位 p3 = p3.next; } // 如果到最初还有进位，再新加一个节点，存储最初的进位 if (c) p3.next = new ListNode(c); return l3.next;};

合并两个有序链表非递归 var mergeTwoLists = function (l1, l2) { // 虚构头节点 let dummy = new ListNode(-1); let p = dummy; // 两个链表都有值的状况 while (l1 != null && l2 != null) { // 比拟 l1 和 l2 两个指针,将值较小的的节点接到 p 指针 if (l1.val < l2.val) { p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; } // p 指针不断前进 p = p.next; } p.next = l1 == null ? l2 : l1; return dummy.next;};2.递归法 ...

无效的括号工夫复杂度：O(n)，其中 n 是字符串 s 的长度。空间复杂度：O(n+∣∣)，其中 示意字符集，本题中字符串只蕴含 6 种括号，∣∣=6。栈中的字符数量为O(n)，而哈希表应用的空间为 O(∣∣)，相加即可失去总空间复杂度。由题意晓得匹配括号的流程合乎 “ 栈 ” 这种数据结构顺次将左括号放入栈匹配到右括号则出栈遍历完结判断栈是否为空 var isValid = function (s) { const n = s.length; if (n % 2 === 1) { return false; } const pairs = new Map([ [')', '('], [']', '['], ['}', '{'] ]); const stk = []; for (let ch of s) { if (pairs.has(ch)) { if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) { return false; } stk.pop(); } else { stk.push(ch); } }; return !stk.length;};