Leetcode103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
1 2 3 4 5 6 7 8 9 10 11 12
Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ]
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Leetcode108. Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
1 2 3 4 5 6 7 8 9
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
Leetcode109. Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
1 2 3 4 5 6 7 8 9
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Leetcode116. Populating Next Right Pointers in Each Node
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with ‘#’ signifying the end of each level.
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle. In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle
1 2 3 4 5 6
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). 简单dp,注意从后向前就行。
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
1 2
Input: [7,1,5,3,6,4] Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price. Example 2:
1 2
Input: [7,6,4,3,1] Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Say you have an array prices for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
1 2 3 4
Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2: Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
1 2 3 4
Example 3: Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
classSolution { public: intmaxProfit(vector<int>& prices){ int res = 0; for(int i = 1; i < prices.size();i ++) { if(prices[i] > prices[i - 1]) { res += (prices[i] - prices[i - 1]); } } return res; } };
Leetcode123. Best Time to Buy and Sell Stock III
Say you have an array for which the i th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
1 2 3 4
Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
1 2 3 4 5
Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
1 2 3
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
这道是要求最多交易两次,找到最大利润,还是需要用动态规划Dynamic Programming来解,而这里我们需要两个递推公式来分别更新两个变量local和global,我们其实可以求至少k次交易的最大利润,找到通解后可以设定 k = 2,即为本题的解答。我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润,此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润,此为全局最优。它们的递推式为:
classSolution { public: intmaxProfit(vector<int> &prices){ if (prices.empty()) return0; int n = prices.size(), g[n][3] = {0}, l[n][3] = {0}; for (int i = 1; i < prices.size(); ++i) { int diff = prices[i] - prices[i - 1]; for (int j = 1; j <= 2; ++j) { l[i][j] = max(g[i - 1][j - 1] + max(diff, 0), l[i - 1][j] + diff); g[i][j] = max(l[i][j], g[i - 1][j]); } } return g[n - 1][2]; } };
Leetcode124. Binary Tree Maximum Path Sum
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
在递归函数中,如果当前结点不存在,直接返回0。否则就分别对其左右子节点调用递归函数,由于路径和有可能为负数,这里当然不希望加上负的路径和,所以和0相比,取较大的那个,就是要么不加,加就要加正数。然后来更新全局最大值结果 res,就是以左子结点为终点的最大 path 之和加上以右子结点为终点的最大 path 之和,还要加上当前结点值,这样就组成了一个条完整的路径。而返回值是取 left 和 right 中的较大值加上当前结点值,因为返回值的定义是以当前结点为终点的 path 之和,所以只能取 left 和 right 中较大的那个值,而不是两个都要,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intmaxPathSum(TreeNode* root){ int res = INT_MIN; helper(root, res); return res; } inthelper(TreeNode* node, int& res){ if (!node) return0; int left = max(helper(node->left, res), 0); int right = max(helper(node->right, res), 0); res = max(res, left + right + node->val); returnmax(left, right) + node->val; } };
Leetcode125. Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
1 2
Input: "A man, a plan, a canal: Panama" Output: true
classSolution { public: boolislegal(char s){ if ('A'<=s && s<='Z' || 'a'<=s && s<='z' || '0'<=s && s<='9') returntrue; returnfalse; } boolisPalindrome(string s){ if(s == "" || s.length()==1 || s.length()==0) returntrue; int left = 0, cur = 0, right = s.size(); while(left < right) { while(left < right && !islegal(s[left])) left ++; while(left < right && !islegal(s[right])) right --; if('A'<=s[left] && s[left]<='Z') s[left] += 32; if('A'<=s[right] && s[right]<='Z') s[right] += 32; if(s[left] != s[right]) returnfalse; left ++; right --; } returntrue; } };
Leetcode126. Word Ladder II
Given two words ( beginWord and endWord ), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord , such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
classSolution { public: unordered_map<string, int> data; vector<vector<int>> g; vector<int> f; vector<vector<string>> res; vector<string> wl; voiddfs(int u, int ed, vector<string>& ans){ ans.push_back(wl[u]); if (u == ed) { res.push_back(ans); return; } for (int v : g[u]) { if (f[v] + 1 == f[u]) { dfs(v, ed, ans); ans.pop_back(); } } } vector<vector<string>> findLadders(string bw, string ew, vector<string>& wl) { wl.push_back(bw); for (int i = 0; i < wl.size(); i ++) data[wl[i]] = i;
if (!data.count(ew)) return {}; int ed = data[ew]; int st = wl.size()-1; g.assign(wl.size(), {}); for (int i = 0; i < wl.size(); i ++) { int m = wl[i].length(); for (int j = 0; j < m; j ++) { char c = wl[i][j]; for (int k = 0; k < 26; k ++) { if (c - 'a' != k) { wl[i][j] = k + 'a'; if (!data.count(wl[i])) continue; int v = data[wl[i]]; g[i].push_back(v); } } wl[i][j] = c; } }
f.assign(wl.size(), 1e9); queue<int> q; f[ed] = 0; q.push(ed); while(!q.empty()) { int t = q.front(); q.pop(); for (int v : g[t]) { if (f[t] + 1 < f[v]) { f[v] = f[t] + 1; q.push(v); } } }
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
classSolution { public: intlongestConsecutive(vector<int>& nums){ unordered_set<int> s(nums.begin(), nums.end()); int res = 0; int local_res; for(int i : nums) { if (!s.count(i)) continue; int res1 = 1; int prev = i-1, next = i+1; s.erase(i); while(s.count(prev)) s.erase(prev--); while(s.count(next)) s.erase(next++); res = max(res, next-prev-1); } return res; } };
Leetcode129. Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
1 2 3 4 5 6 7 8 9
Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25.
Example 2:
1 2 3 4 5 6 7 8 9 10 11 12
Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026.
Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
Example:
1 2 3 4 5 6 7 8 9 10
X X X X X O O X X X O X X O X X After running your function, the board should be:
X X X X X X X X X X X X X O X X
Explanation: Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ on the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.
classSolution { public: intminCut(string s){ if (s.empty()) return0; int n = s.size(); vector<int> dp(n + 1, INT_MAX); dp[0] = -1; for (int i = 0; i < n; ++i) { for (int len = 0; i - len >= 0 && i + len < n && s[i - len] == s[i + len]; ++len) { dp[i + len + 1] = min(dp[i + len + 1], 1 + dp[i - len]); } for (int len = 0; i - len >= 0 && i + len + 1 < n && s[i - len] == s[i + len + 1]; ++len) { dp[i + len + 2] = min(dp[i + len + 2], 1 + dp[i - len]); } } return dp[n]; } };
Leetcode133. Clone Graph
Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
1 2 3 4
class Node { public int val; public List<Node> neighbors; }
Test case format:
For simplicity sake, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.
Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
1 2 3 4 5 6 7
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
Note:
If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Input: gas = [1,2,3,4,5] cost = [3,4,5,1,2]
Output: 3
Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
1 2
Input: [2,2,3,2] Output: 3
这道题就是除了一个单独的数字之外,数组中其他的数字都出现了三次,还是要利用位操作 Bit Manipulation 来解。可以建立一个 32 位的数字,来统计每一位上1出现的个数,如果某一位上为1的话,那么如果该整数出现了三次,对3取余为0,这样把每个数的对应位都加起来对3取余,最终剩下来的那个数就是单独的数字。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: intsingleNumber(vector<int>& nums){ int sum = 0; int res = 0; for(int i = 0; i < 32; i ++) { sum = 0; for(int j = 0; j < nums.size(); j ++) { sum += (nums[j] >> i) & 1; } res |= ((sum % 3) << i); } return res; } };
Leetcode138. Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.
The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
Example 1:
1 2
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
classSolution { public: Node* copyRandomList(Node* head){ if(!head) returnNULL; Node* cur = head, *res = newNode(-1), *res_head = res; unordered_map<Node*, Node*> ma; while(cur != NULL) { Node *new_cur = newNode(cur->val); res->next = new_cur; res = res->next; ma[cur] = new_cur; cur = cur->next; } cur = head; res = res_head->next; while(cur != NULL) { if(cur->random != NULL) res->random = ma[cur->random]; res = res->next; cur = cur->next; } return res_head->next; } };
Leetcode139. Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
1 2 3
Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
1 2 3 4
Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
1 2 3 4 5 6 7 8
Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ]
Example 2:
1 2 3 4 5 6 7 8 9 10
Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word.
classSolution { public: vector<string> wordBreak(string s, vector<string>& wordDict){ unordered_map<string, vector<string>> m; returnhelper(s, wordDict, m); } vector<string> helper(string s, vector<string>& wordDict, unordered_map<string, vector<string>>& m){ if (m.count(s)) return m[s]; if (s.empty()) return {""}; vector<string> res; for (string word : wordDict) { if (s.substr(0, word.size()) != word) continue; vector<string> rem = helper(s.substr(word.size()), wordDict, m); for (string str : rem) { res.push_back(word + (str.empty() ? "" : " ") + str); } } return m[s] = res; } };
Leetcode141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
1 2 3
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
1 2 3
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
1 2 3
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
1 2 3
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
1 2 3
Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.
这个求单链表中的环的起始点是之前那个判断单链表中是否有环的延伸,可参之前那道 Linked List Cycle。这里还是要设快慢指针,不过这次要记录两个指针相遇的位置,当两个指针相遇了后,让其中一个指针从链表头开始,此时再相遇的位置就是链表中环的起始位置,为啥是这样呢,因为快指针每次走2,慢指针每次走1,快指针走的距离是慢指针的两倍。而快指针又比慢指针多走了一圈。所以 head 到环的起点+环的起点到他们相遇的点的距离 与 环一圈的距离相等。现在重新开始,head 运行到环起点 和 相遇点到环起点 的距离也是相等的,相当于他们同时减掉了 环的起点到他们相遇的点的距离。
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…. You may not modify the values in the list’s nodes, only nodes itself may be changed.
classSolution { public: voidadd(vector<int>& res, TreeNode* root){ if (root == NULL) return ; if (root->left) add(res, root->left); if (root->right) add(res, root->right); res.push_back(root->val); } vector<int> postorderTraversal(TreeNode* root){ if (root == NULL) return {}; vector<int> res; add(res, root); return res; } };
Leetcode146. LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.
Follow up: Could you do both operations in O(1) time complexity?
classLRUCache{ public: LRUCache(int capacity) { cap = capacity; } intget(int key){ auto it = m.find(key); if (it == m.end()) return-1; l.splice(l.begin(), l, it->second); return it->second->second; } voidput(int key, int value){ auto it = m.find(key); if (it != m.end()) l.erase(it->second); l.push_front(make_pair(key, value)); m[key] = l.begin(); if (m.size() > cap) { int k = l.rbegin()->first; l.pop_back(); m.erase(k); } } private: int cap; list<pair<int, int>> l; unordered_map<int, list<pair<int, int>>::iterator> m; };
Leetcode147. Insertion Sort List
Sort a linked list using insertion sort.
A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list
Algorithm of Insertion Sort:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
classSolution { public: intevalRPN(vector<string>& tokens){ if(tokens.size() == 1) returnstoi(tokens[0]); stack<int> s; for(int i = 0; i < tokens.size(); i ++) { if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") { s.push(stoi(tokens[i])); } else { int a1 = s.top(); s.pop(); int a2 = s.top(); s.pop(); if (tokens[i] == "+") s.push(a2 + a1); if (tokens[i] == "-") s.push(a2 - a1); if (tokens[i] == "*") s.push(a2 * a1); if (tokens[i] == "/") s.push(a2 / a1); } } return s.top(); } };
Leetcode151. Reverse Words in a String
Given an input string, reverse the string word by word.
Example 1:
1 2
Input: "the sky is blue" Output: "blue is sky the"
Example 2:
1 2 3
Input: " hello world! " Output: "world! hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
1 2 3
Input: "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
intmaxSubArray(int A[], int n) { assert(n > 0); if (n <= 0) return0; int global = A[0]; int local = A[0]; for(int i = 1; i != n; ++ i) { local = MAX(A[i], local + A[i]); global = MAX(local, global); } return global; }
/********************************************************************************** * * The API: int read4(char *buf) reads 4 characters at a time from a file. * * The return value is the actual number of characters read. * For example, it returns 3 if there is only 3 characters left in the file. * * By using the read4 API, implement the function int read(char *buf, int n) * that reads n characters from the file. * * Note: * The read function will only be called once for each test case. * **********************************************************************************/
// Forward declaration of the read4 API. intread4(char *buf);
classSolution { public: /** * @param buf Destination buffer * @param n Maximum number of characters to read * @return The number of characters read */ intread(char *buf, int n){ srand(time(0)); if (rand()%2){ returnread1(buf, n); } returnread2(buf, n); }
//read the data in-place. potential out-of-boundary issue intread1(char *buf, int n){ int len = 0; int size = 0;
// `buf` could be accessed out-of-boundary while(len <=n && (size = read4(buf))>0){ size = len + size > n ? n - len : size; len += size; buf += size; } return len; }
//using a temp-buffer to avoid peotential out-of-boundary issue intread2(char *buf, int n){ char _buf[4]; // the buffer for read4() int _n = 0; // the return for read4() int len = 0; // total buffer read from read4() int size = 0; // how many bytes need be copied from `_buf` to `buf` while((_n = read4(_buf)) > 0){ //check the space of `buf` whether full or not size = len + _n > n ? n-len : _n; strncpy(buf+len, _buf, size); len += size; //buffer is full if (len>=n){ break; } } return len; } };
Leetcode159. Longest Substring with At Most Two Distinct Characters
Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.
Example 1:
1 2 3
Input: "eceba" Output: 3 Explanation: _t_ is "ece" which its length is 3.
Example 2:
1 2 3
Input: "ccaabbb" Output: 5 Explanation: _t_ is "aabbb" which its length is 5.
这道题给我们一个字符串,让求最多有两个不同字符的最长子串。那么首先想到的是用 HashMap 来做,HashMap 记录每个字符的出现次数,然后如果 HashMap 中的映射数量超过两个的时候,这里需要删掉一个映射,比如此时 HashMap 中e有2个,c有1个,此时把b也存入了 HashMap,那么就有三对映射了,这时 left 是0,先从e开始,映射值减1,此时e还有1个,不删除,left 自增1。这时 HashMap 里还有三对映射,此时 left 是1,那么到c了,映射值减1,此时e映射为0,将e从 HashMap 中删除,left 自增1,然后更新结果为 i - left + 1,以此类推直至遍历完整个字符串,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intlengthOfLongestSubstringTwoDistinct(string s){ int res = 0, left = 0; unordered_map<char, int> m; for (int i = 0; i < s.size(); ++i) { ++m[s[i]]; while (m.size() > 2) { if (--m[s[left]] == 0) m.erase(s[left]); ++left; } res = max(res, i - left + 1); } return res; } };
我们除了用 HashMap 来映射字符出现的个数,还可以映射每个字符最新的坐标,比如题目中的例子 “eceba”,遇到第一个e,映射其坐标0,遇到c,映射其坐标1,遇到第二个e时,映射其坐标2,当遇到b时,映射其坐标3,每次都判断当前 HashMap 中的映射数,如果大于2的时候,那么需要删掉一个映射,还是从 left=0 时开始向右找,看每个字符在 HashMap 中的映射值是否等于当前坐标 left,比如第一个e,HashMap 此时映射值为2,不等于 left 的0,那么 left 自增1,遇到c的时候,HashMap 中c的映射值是1,和此时的 left 相同,那么我们把c删掉,left 自增1,再更新结果,以此类推直至遍历完整个字符串,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intlengthOfLongestSubstringTwoDistinct(string s){ int res = 0, left = 0; unordered_map<char, int> m; for (int i = 0; i < s.size(); ++i) { m[s[i]] = i; while (m.size() > 2) { if (m[s[left]] == left) m.erase(s[left]); ++left; } res = max(res, i - left + 1); } return res; } };
后来又在网上看到了一种解法,这种解法是维护一个 sliding window,指针 left 指向起始位置,right 指向 window 的最后一个位置,用于定位 left 的下一个跳转位置,思路如下:
若当前字符和前一个字符相同,继续循环。
若不同,看当前字符和 right 指的字符是否相同
若相同,left 不变,右边跳到 i - 1
若不同,更新结果,left 变为 right+1,right 变为 i - 1
最后需要注意在循环结束后,还要比较结果 res 和 s.size() - left 的大小,返回大的,这是由于如果字符串是 “ecebaaa”,那么当 left=3 时,i=5,6 的时候,都是继续循环,当i加到7时,跳出了循环,而此时正确答案应为 “baaa” 这4个字符,而我们的结果 res 只更新到了 “ece” 这3个字符,所以最后要判断 s.size() - left 和结果 res 的大小。
另外需要说明的是这种解法仅适用于于不同字符数为2个的情况,如果为k个的话,还是需要用上面两种解法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: intlengthOfLongestSubstringTwoDistinct(string s){ int left = 0, right = -1, res = 0; for (int i = 1; i < s.size(); ++i) { if (s[i] == s[i - 1]) continue; if (right >= 0 && s[right] != s[i]) { res = max(res, i - left); left = right + 1; } right = i - 1; } returnmax(s.size() - left, res); } };
Leetcode160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
Example 1:
1 2 3
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
1 2 3
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Output: Reference of the node with value = 2 Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
1 2 3 4
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: null Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so return null.
A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
Example 1:
1 2 3
Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
1 2 3 4
Input: nums = [1,2,1,3,5,6,4] Output: 1 or 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
classSolution { public: intfindPeakElement(vector<int>& nums){ int left = 0, right = nums.size()-1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] >= nums[mid+1]) right = mid; else left = mid + 1; } return right; } };
leetcode165. Compare Version Numbers
Given two version numbers, version1 and version2, compare them.
Version numbers consist of one or more revisions joined by a dot ‘.’. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character. Revisions are 0-indexed from left to right, with the leftmost revision being revision 0, the next revision being revision 1, and so on. For example 2.5.33 and 0.1 are valid version numbers.
To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer value ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.
Return the following:
If version1 < version2, return -1.
If version1 > version2, return 1.
Otherwise, return 0.
Example 1:
1 2 3
Input: version1 = "1.01", version2 = "1.001" Output: 0 Explanation: Ignoring leading zeroes, both "01" and "001" represent the same integer "1".
Example 2:
1 2 3
Input: version1 = "1.0", version2 = "1.0.0" Output: 0 Explanation: version1 does not specify revision 2, which means it is treated as "0".
Example 3:
1 2 3
Input: version1 = "0.1", version2 = "1.1" Output: -1 Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.
classSolution { public: string fractionToDecimal(int numerator, int denominator){ string res = ""; int l1 = numerator >= 0 ? 1 : -1; int l2 = denominator >= 0 ? 1 : -1; longlong num = abs((longlong)numerator); longlong den = abs((longlong)denominator); longlong out = num / den; longlong remain = num % den; if(numerator == 0) return"0"; if(l1 * l2 == -1) res = "-"; res = res + to_string(out); if(remain == 0) return res; res = res + "."; string s = ""; unordered_map<int, int> m; int pos = 0; while(remain != 0) { if(m.find(remain) != m.end()) { s.insert(m[remain], "("); s = s + ")"; return res + s; } m[remain] = pos; out = (remain * 10) / den; remain = (remain * 10) % den; s = s + to_string(out); pos ++; } return res + s; } };
Leetcode167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
1 2 3
Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
乍一看来,Two Sum II 这道题和 Two Sum 问题一样平平无奇。然而,这道题实际上内藏玄机,加上了数组有序的变化之后,它就换了一套解法。
classSolution { public: intmajorityElement(vector<int>& nums){ int m = nums[0], i, count = 1; int numsSize = nums.size(); for (i = 1; i < numsSize; i ++) { if (count == 0){ m = nums[i]; count ++; } elseif (m == nums[i]) count++; else count--; } return m; } };
Leetcode170. Two Sum III - Data structure design
Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value.
让我们设计一个 Two Sum 的数据结构。先来看用 HashMap 的解法,把每个数字和其出现的次数建立映射,然后遍历 HashMap,对于每个值,先求出此值和目标值之间的差值t,然后需要分两种情况来看,如果当前值不等于差值t,那么只要 HashMap 中有差值t就返回 True,或者是当差值t等于当前值时,如果此时 HashMap 的映射次数大于1,则表示 HashMap 中还有另一个和当前值相等的数字,二者相加就是目标值,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classTwoSum { public: voidadd(int number){ ++m[number]; } boolfind(int value){ for (auto a : m) { int t = value - a.first; if ((t != a.first && m.count(t)) || (t == a.first && a.second > 1)) { returntrue; } } returnfalse; } private: unordered_map<int, int> m; };
Leetcode171. Excel Sheet Column Number
Given a column title as appear in an Excel sheet, return its corresponding column number.
Example 1:
1 2
Input: "A" Output: 1
Example 2:
1 2
Input: "AB" Output: 28
Example 3:
1 2
Input: "ZY" Output: 701
给一个excel表中的列标,把它转换成十进制的数,简单,但是要用long才能过。
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { public: inttitleToNumber(string s){ int length = s.length(); long result = 0; long temp = 1; for(int i = length - 1; i >= 0; i--) { result += (s[i] - 'A' + 1) * temp; temp *= 26; } return result; } };
简单做法:
1 2 3 4 5 6 7 8 9
public int titleToNumber(String s) { if (s.length() == 0 || s == null) return 0; int sum = 0; for (int i = 0; i < s.length(); i++) { sum = sum * 26 + (s.charAt(i) - 'A' + 1); } return sum; }
Leetcode172. Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
关键在于理解inorder的stack代表了什么含义,为什么要用到这个stack:stack的存在是为了我们找回来时的路。但是不一定立刻就去找到successor,如果call到了,再沿着栈顶元素去找。而做法就是首先将最左边的路径一路推进栈,每次从栈中pop来提取next。提取之后还要保证,如果栈顶有right,那么一路将top -> right 的left推入栈;如果没有right,栈顶本身就是successor。这样做完这一系列检查后,栈顶元素就可以保证是successor。
/** * 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) {} * }; */ classBSTIterator { public: stack<TreeNode*> s; BSTIterator(TreeNode* root) { //s = new stack<TreeNode*>(); while(root != NULL) { s.push(root); root = root->left; } } /** @return the next smallest number */ intnext(){ TreeNode* cur = s.top(); s.pop(); TreeNode *temp = cur->right; while(temp) { s.push(temp); temp = temp->left; } return cur->val; } /** @return whether we have a next smallest number */ boolhasNext(){ return !s.empty(); } };
Leetcode175. Combine Two Tables
Table: Person +————-+———+ | Column Name | Type | +————-+———+ | PersonId | int | | FirstName | varchar | | LastName | varchar | +————-+———+ PersonId is the primary key column for this table.
Table: Address +————-+———+ | Column Name | Type | +————-+———+ | AddressId | int | | PersonId | int | | City | varchar | | State | varchar | +————-+———+ AddressId is the primary key column for this table.
Write a SQL query for a report that provides the following information for each person in the Person table, regardless if there is an address for each of those people:
1
FirstName, LastName, City, State
Person表左连接 Address表查询,不能用条件查询,因为不管该人是否有地址
1 2 3
# Write your MySQL query statement below select FirstName, LastName, City, State from Person leftjoin Address on Person.PersonId=Address.PersonId
Leetcode176. Second Highest Salary
Write a SQL query to get the second highest salary from the Employee table.
For example, given the above Employee table, the query should return 200 as the second highest salary. If there is no second highest salary, then the query should return null.
刚开始的想法是使用ORDER BY指令排序,然后通过LIMIT输出第二行数据就可以了,但是这样做会有两个bug,一个是如果存在两个Id有相同的Salary并且都为最高,则我们的输出还是最高Salary;另一个就是这样无法满足题目要求的If there is no second highest salary, then the query should return null。这是因为SELECT指令会在没有满足条件的输出时,会输出空。
所以我们应该使用MAX()函数,其满足没有记录时输出null的条件。
题解:
1 2 3
# Write your MySQL query statement below SELECTMAX(Salary) AS SecondHighestSalary FROM Employee WHERE Salary < (SELECTMAX(Salary) FROM Employee);
Leetcode177. Nth Highest Salary
Write a SQL query to get the nth highest salary from the Employee table.
For example, given the above Employee table, the nth highest salary where n = 2 is 200. If there is no nth highest salary, then the query should return null.
CREATEFUNCTION getNthHighestSalary(N INT) RETURNSINT BEGIN declare m int; set m = n -1; RETURN ( # Write your MySQL query statement below. selectdistinct salary from Employee orderby salary desc limit m, 1 ); END
Leetcode178. Rank Scores
Write a SQL query to rank scores. If there is a tie between two scores, both should have the same ranking. Note that after a tie, the next ranking number should be the next consecutive integer value. In other words, there should be no “holes” between ranks.
1 is the only number that appears consecutively for at least three times.
1 2 3 4 5 6 7 8
# Write your MySQL query statement below
selectdistinct l1.num as ConsecutiveNums from logs l1, logs l2, logs l3 where l1.id = l2.id-1 and l2.id = l3.id-1 and l1.num = l2.num and l2.num = l3.num;
Leetcode181. Employees Earning More Than Their Managers
The Employee table holds all employees including their managers. Every employee has an Id, and there is also a column for the manager Id.
1 2 3 4 5 6 7 8
+----+-------+--------+-----------+ | Id | Name | Salary | ManagerId | +----+-------+--------+-----------+ | 1 | Joe | 70000 | 3 | | 2 | Henry | 80000 | 4 | | 3 | Sam | 60000 | NULL | | 4 | Max | 90000 | NULL | +----+-------+--------+-----------+
Given the Employee table, write a SQL query that finds out employees who earn more than their managers. For the above table, Joe is the only employee who earns more than his manager.
1 2 3 4 5
+----------+ | Employee | +----------+ | Joe | +----------+
自连接,找出比其上司挣得更多的员工。
1 2 3
# Write your MySQL query statement below select r1.Name as Employee from Employee as r1, Employee as r2 where r1.ManagerId = r2.Id and r1.Salary > r2.Salary
Leetcode182. Duplicate Emails
Write a SQL query to find all duplicate emails in a table named Person.
# Write your MySQL query statement below selectdistinct r1.Email as Email from Person as r1, Person as r2 where r1.Email = r2.Email and r1.Id != r2.Id
Leetcode183. Customers Who Never Order
Suppose that a website contains two tables, the Customers table and the Orders table. Write a SQL query to find all customers who never order anything.
Table: Customers.
1 2 3 4 5 6 7 8
+----+-------+ | Id | Name | +----+-------+ | 1 | Joe | | 2 | Henry | | 3 | Sam | | 4 | Max | +----+-------+
Using the above tables as example, return the following:
1 2 3 4 5 6
+-----------+ | Customers | +-----------+ | Henry | | Max | +-----------+
使用NOT IN
1 2 3
select Name as Customers from Customers where Id notin (select CustomerId from Orders)
使用左外连接 然后使用条件语句
1 2 3 4 5
SELECT C.Name Customers FROM Customers C LEFTJOIN Orders O ON C.Id=O.CustomerId WHERE O.CustomerId ISNULL;
Leetcode184. Department Highest Salary
The Employee table holds all employees. Every employee has an Id, a salary, and there is also a column for the department Id.
1 2 3 4 5 6 7 8 9
+----+-------+--------+--------------+ | Id | Name | Salary | DepartmentId | +----+-------+--------+--------------+ | 1 | Joe | 70000 | 1 | | 2 | Jim | 90000 | 1 | | 3 | Henry | 80000 | 2 | | 4 | Sam | 60000 | 2 | | 5 | Max | 90000 | 1 | +----+-------+--------+--------------+
The Department table holds all departments of the company.
1 2 3 4 5 6
+----+----------+ | Id | Name | +----+----------+ | 1 | IT | | 2 | Sales | +----+----------+
Write a SQL query to find employees who have the highest salary in each of the departments. For the above tables, your SQL query should return the following rows (order of rows does not matter).
1 2 3 4 5 6 7
+------------+----------+--------+ | Department | Employee | Salary | +------------+----------+--------+ | IT | Max | 90000 | | IT | Jim | 90000 | | Sales | Henry | 80000 | +------------+----------+--------+
SELECT Department.name `Department`, Employee.name `Employee`, Salary FROM Employee JOIN Department ON Employee.DepartmentId = Department.Id WHERE (Employee.DepartmentId, Salary) IN (SELECT DepartmentId, MAX(Salary) FROM Employee GROUPBY DepartmentId)
Leetcode185. Department Top Three Salaries
Table: Employee
1 2 3 4 5 6 7 8
+--------------+---------+ | Column Name | Type | +--------------+---------+ | Id | int | | Name | varchar | | Salary | int | | DepartmentId | int | +--------------+---------+
Id is the primary key for this table.Each row contains the ID, name, salary, and department of one employee.
Table: Department
1 2 3 4 5 6
+-------------+---------+ | Column Name | Type | +-------------+---------+ | Id | int | | Name | varchar | +-------------+---------+
Id is the primary key for this table. Each row contains the ID and the name of one department.
A company’s executives are interested in seeing who earns the most money in each of the company’s departments. A high earner in a department is an employee who has a salary in the top three unique salaries for that department.
Write an SQL query to find the employees who are high earners in each of the departments.
Return the result table in any order.
The query result format is in the following example:
Employee table:
1 2 3 4 5 6 7 8 9 10 11
+----+-------+--------+--------------+ | Id | Name | Salary | DepartmentId | +----+-------+--------+--------------+ | 1 | Joe | 85000 | 1 | | 2 | Henry | 80000 | 2 | | 3 | Sam | 60000 | 2 | | 4 | Max | 90000 | 1 | | 5 | Janet | 69000 | 1 | | 6 | Randy | 85000 | 1 | | 7 | Will | 70000 | 1 | +----+-------+--------+--------------+
Department table:
1 2 3 4 5 6
+----+-------+ | Id | Name | +----+-------+ | 1 | IT | | 2 | Sales | +----+-------+
Result table:
1 2 3 4 5 6 7 8 9 10
+------------+----------+--------+ | Department | Employee | Salary | +------------+----------+--------+ | IT | Max | 90000 | | IT | Joe | 85000 | | IT | Randy | 85000 | | IT | Will | 70000 | | Sales | Henry | 80000 | | Sales | Sam | 60000 | +------------+----------+--------+
In the IT department:
Max earns the highest unique salary
Both Randy and Joe earn the second-highest unique salary
Will earns the third-highest unique salary
In the Sales department:
Henry earns the highest salary
Sam earns the second-highest salary
There is no third-highest salary as there are only two employees
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# Write your MySQL query statement below select t2.name as Department, t1.Employee , t1.salary from ( select e1.id, e1.name as employee, e1.salary, e1.departmentid from Employee e1 innerjoin Employee e2 on e1.departmentid = e2.departmentid and e1.salary<=e2.salary groupby e1.id havingcount(distinct(e2.salary))<=3 ) t1 innerjoin (select*from Department )t2 on t1.DepartmentId = t2.id
Leetcode187. Repeated DNA Sequences
The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.
For example, “ACGAATTCCG” is a DNA sequence. When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Example 1:
1 2
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"]
classSolution { public: vector<string> findRepeatedDnaSequences(string s){ if (s.length() <= 10) return {}; vector<string> v; int mask = 0x7ffffff, cur = 0; unordered_map<int, int> m; for (int i = 0; i < 9; i ++) cur = (cur << 3) | (s[i] & 7); for (int i = 9; i < s.length(); i ++) { cur = ((cur & mask)<<3) | (s[i] & 7); if (m.count(cur)) { if (m[cur] == 1) v.push_back(s.substr(i-9, 10)); m[cur] ++; } else m[cur] = 1; } return v; } };
Leetcode189. Rotate Array
Given an array, rotate the array to the right by k steps, where k is non-negative.
Follow up: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem. Could you do it in-place with O(1) extra space?
Example 1:
1 2 3 4 5 6
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
1 2 3 4 5
Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
因为长度为n的数组只需要更新n次,所以我们用一个 for 循环来处理n次。首先 pre 更新为 cur,然后计算新的 idx 的位置,然后将 nums[idx] 上的值先存到 cur 上,然后把 pre 赋值给 nums[idx],这相当于把上一轮的 nums[idx] 赋给了新的一轮,完成了数字的交换,然后 if 语句判断是否会变到处理过的数字。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: voidrotate(vector<int>& nums, int k){ if (nums.empty() || (k %= nums.size()) == 0) return; int temp; int length = nums.size(); int idx = 0, start = 0, cur = nums[0], pre = -1; for(int i = 0; i < length; i ++) { pre = cur; idx = (idx + k) % length; cur = nums[idx]; nums[idx] = pre; if (idx == start) { idx = ++start; cur = nums[idx]; } } } };
classSolution { public: voidrotate(vector<int>& nums, int k){ if (nums.empty() || (k %= nums.size()) == 0) return; int n = nums.size(); reverse(nums.begin(), nums.begin() + n - k); reverse(nums.begin() + n - k, nums.end()); reverse(nums.begin(), nums.end()); } };
Leetcode190. Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
Example 1:
1 2 3
Input: 00000010100101000001111010011100 Output: 00111001011110000010100101000000 Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:
1 2 3
Input: 11111111111111111111111111111101 Output: 10111111111111111111111111111111 Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
把要翻转的数从右向左一位位的取出来,如果取出来的是1,将结果 res 左移一位并且加上1;如果取出来的是0,将结果 res 左移一位,然后将n右移一位即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution { public: uint32_treverseBits(uint32_t n){ int res = 0; for(int i = 0; i < 32; i ++) { if(n & 1) res = (res << 1) + 1; else res = res << 1; n = n >> 1; } return res; } };
Leetcode191. Number of 1 Bits
Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight).
Example 1:
1 2 3
Input: 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:
1 2 3
Input: 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:
1 2 3
Input: 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
同样的位操作
1 2 3 4 5 6 7 8 9 10 11 12
classSolution { public: inthammingWeight(uint32_t n){ int res = 0; for(int i = 0; i < 32; i ++) { if(n & 1) res ++; n = n >> 1; } return res; } };
Leetcode192. Word Frequency
Write a bash script to calculate the frequency of each word in a text file words.txt.
For simplicity sake, you may assume:
words.txt contains only lowercase characters and space ‘ ‘ characters.
Each word must consist of lowercase characters only.
Words are separated by one or more whitespace characters.
Example:
Assume that words.txt has the following content:
1 2
the day is sunny the the the sunny is is
Your script should output the following, sorted by descending frequency:
Given a text file file.txt that contains list of phone numbers (one per line), write a one liner bash script to print all valid phone numbers.
You may assume that a valid phone number must appear in one of the following two formats: (xxx) xxx-xxxx or xxx-xxx-xxxx. (x means a digit)
You may also assume each line in the text file must not contain leading or trailing white spaces.
Example: Assume that file.txt has the following content:
1 2 3
987-123-4567 123 456 7890 (123) 456-7890
Your script should output the following valid phone numbers:
1 2
987-123-4567 (123) 456-7890
写一个bash命令,用grep加上正则表达式:
1 2
# Read from the file file.txt and output all valid phone numbers to stdout. grep -e '^[0-9]\{3\}-[0-9]\{3\}-[0-9]\{4\}$' -e '^([0-9]\{3\}) [0-9]\{3\}-[0-9]\{4\}$' file.txt
Leetcode194. Transpose File
Given a text file file.txt, transpose its content.
You may assume that each row has the same number of columns, and each field is separated by the ‘ ‘ character.
For example, return the following Ids for the above Weather table:
1 2 3 4 5 6
+----+ | Id | +----+ | 2 | | 4 | +----+
1 2 3 4
select a.Id from Weather a innerjoin Weather b on b.Date+interval1day=a.Date where a.Temperature>b.Temperature;
1 2 3 4
select a.Id from Weather a innerjoin Weather b on datediff(a.RecordDate, b.RecordDate) =1 where a.Temperature>b.Temperature;
Leetcode198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2:
Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
classSolution { public: introb(vector<int>& nums){ int sumEven=0; int sumOdd=0; for (int i = 0; i < nums.size(); i++) { if (i % 2 == 0) { sumEven += nums[i]; sumEven = max(sumEven,sumOdd); } else { sumOdd += nums[i]; sumOdd = max(sumEven,sumOdd); } } returnmax(sumOdd, sumEven); } };
Leetcode199. Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
这道题要求我们打印出二叉树每一行最右边的一个数字,实际上是求二叉树层序遍历的一种变形,我们只需要保存每一层最右边的数字即可,可以参考我之前的博客 Binary Tree Level Order Traversal 二叉树层序遍历,这道题只要在之前那道题上稍加修改即可得到结果,还是需要用到数据结构队列queue,遍历每层的节点时,把下一层的节点都存入到queue中,每当开始新一层节点的遍历之前,先把新一层最后一个节点值存到结果中,代码如下:
classSolution { public: vector<int> rightSideView(TreeNode *root){ vector<int> res; if (!root) return res; queue<TreeNode*> q; q.push(root); while (!q.empty()) { res.push_back(q.back()->val); int size = q.size(); for (int i = 0; i < size; ++i) { TreeNode *node = q.front(); q.pop(); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return res; } };
Leetcode200. Number of Islands
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.
You may return the answer in any order.
Example 1:
Input: [“bella”,”label”,”roller”] Output: [“e”,”l”,”l”] Example 2:
Leetcode1003. Check If Word Is Valid After Substitutions
We are given that the string “abc” is valid.
From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X + “abc” + Y is also valid.
If for example S = “abc”, then examples of valid strings are: “abc”, “aabcbc”, “abcabc”, “abcabcababcc”. Examples of invalid strings are: “abccba”, “ab”, “cababc”, “bac”.
Return true if and only if the given string S is valid.
Example 1:
1 2 3 4 5
Input: "aabcbc" Output: true Explanation: We start with the valid string "abc". Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".
Example 2:
1 2 3 4 5
Input: "abcabcababcc" Output: true Explanation: "abcabcabc" is valid after consecutive insertings of "abc". Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".
Example 3:
1 2
Input: "abccba" Output: false
Example 4:
1 2
Input: "cababc" Output: false
Note:
1 <= S.length <= 20000
S[i] is ‘a’, ‘b’, or ‘c’
使用 vector 来模拟栈, 当遍历访问到 c 时, 需要判断 stack 中是否已经有 a 和 b 的存在.
Given an array A of 0s and 1s, we may change up to K values from 0 to 1.
Return the length of the longest (contiguous) subarray that contains only 1s.
Example 1:
1 2 3 4 5
Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
1 2 3 4 5
Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 Output: 10 Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
用个变量 cnt 记录当前将0变为1的个数,在遍历数组的时候,若遇到了0,则 cnt 自增1。若此时 cnt 大于K了,说明该缩小窗口了,用个 while 循环,若左边界为0,移除之后,此时 cnt 应该自减1,left 自增1,每次用窗口大小更新结果 res 即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { public: intlongestOnes(vector<int>& nums, int k){ int left = 0; int cnt = 0, res = 0, len = nums.size(); for(int i = 0; i < len; i ++) { if (nums[i] == 0) cnt ++; while(cnt > k) { if (nums[left] == 0) cnt --; left ++; } res = max(res, i - left + 1); } return res; } };
我们也可以写的更简洁一些,不用 while 循环,但是还是用的滑动窗口的思路,其中i表示左边界,j为右边界。在遍历的时候,若遇到0,则K自减1,若K小于0了,且 A[i] 为0,则K自增1,且i自增1,最后返回窗口的大小即可,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11
classSolution { public: intlongestOnes(vector<int>& A, int K){ int n = A.size(), i = 0, j = 0; for (; j < n; ++j) { if (A[j] == 0) --K; if (K < 0 && A[i++] == 0) ++K; } return j - i; } };
Leetcode1005. Maximize Sum Of Array After K Negations
Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total. (We may choose the same index i multiple times.) Return the largest possible sum of the array after modifying it in this way.
Example 1:
1 2 3
Input: A = [4,2,3], K = 1 Output: 5 Explanation: Choose indices (1,) and A becomes [4,-2,3].
Example 2:
1 2 3
Input: A = [3,-1,0,2], K = 3 Output: 6 Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].
Example 3:
1 2 3
Input: A = [2,-3,-1,5,-4], K = 2 Output: 13 Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].
classSolution { public: intlargestSumAfterKNegations(vector<int>& A, int K){ int b = 0, s = 0, length = A.size(); int i = 0, sum = 0; sort(A.begin(), A.end()); if(A[0] >= 0) { if(K % 2) A[0] = -A[0]; } else { i = 0; while(i < length && A[i] < 0 && K --) { A[i] = -A[i]; i++; } if (K > 0 && K%2 != 0) { abs(A[i]) < abs(A[i-1]) ? A[i] = -A[i] : A[i-1] = -A[i-1]; } } for(i = 0; i < length; i ++) sum += A[i]; return sum; } };
Leetcode1006. Clumsy Factorial
Normally, the factorial of a positive integer n is the product of all positive integers less than or equal to n. For example, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.
We instead make a clumsy factorial: using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: multiply (*), divide (/), add (+) and subtract (-) in this order.
For example, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. However, these operations are still applied using the usual order of operations of arithmetic: we do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.
Additionally, the division that we use is floor division such that 10 * 9 / 8 equals 11. This guarantees the result is an integer.
Implement the clumsy function as defined above: given an integer N, it returns the clumsy factorial of N.
classSolution { public: intclumsy(int n){ int sum = 0, i = n, j = 0; while(i > 0) { int tmp = 1; if (i != n) tmp = -1; for (j = 0; j < 4 && i > 0; j ++) { if (j == 0) tmp *= (i --); if (j == 1) tmp *= (i --); if (j == 2) tmp /= (i --); if (j == 3) tmp += (i --); } sum += tmp; if (i == 0) break; } return sum; } };
其他的做法:用个变量j来循环遍历这个数组,从而知道当前该做什么操作。还需要一个变量 cur 来计算乘和除优先级的计算,初始化为N,此时从 N-1 遍历到1,若遇到乘号,则 cur 直接乘以当前数字,若遇到除号,cur 直接除以当前数字,若遇到加号,可以直接把当前数字加到结果 res 中,若遇到减号,此时需要判断一下,因为只有第一个乘和除后的结果是要加到 res 中的,后面的都是要减去的,所以要判断一下若当前数字等于 N-4 的时候,加上 cur,否者都是减去 cur,然后 cur 更新为当前数字,因为减号的优先级小于乘除,不能立马运算。之后j自增1并对4取余,最终返回的时候也需要做个判断,因为有可能数字比较小,减号还没有出来,且此时的最后面的乘除结果还保存在 cur 中,那么是加是减还需要看N的大小,若小于等于4,则加上 cur,反之则减去 cur,参见代码如下:
classSolution { public: intclumsy(int N){ int res = 0, cur = N, j = 0; vector<char> ops{'*', '/', '+', '-'}; for (int i = N - 1; i >= 1; --i) { if (ops[j] == '*') { cur *= i; } elseif (ops[j] == '/') { cur /= i; } elseif (ops[j] == '+') { res += i; } else { res += (i == N - 4) ? cur : -cur; cur = i; } j = (j + 1) % 4; } return res + ((N <= 4) ? cur : -cur); } };
再来看一种比较简洁的写法,由于每次遇到减号时,优先级会被改变,而前面的乘除加是可以提前计算的,所以可以每次处理四个数字,即首先处理 N, N-1, N-2, N-3 这四个数字,这里希望每次可以得到乘法计算时的第一个数字,可以通过N - i*4得到,这里需要满足i*4 < N,知道了这个数字,然后可以立马算出乘除的结果,只要其大于等于3。然后需要将乘除之后的结果更新到 res 中,还是需要判断一下,若是第一个乘除的结果,需要加上,后面的都是减去。乘除后面跟的是加号,所以要加上 num-3 这个数字,前提是 num 大于3,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { public: intclumsy(int N){ int res = 0; for (int i = 0; i * 4 < N; ++i) { int num = N - i * 4, t = num; if (num >= 3) t = num * (num - 1) / (num - 2); res += (i == 0) ? t : -t; if (num > 3) res += (num - 3); } return res; } };
Leetcode1007. Minimum Domino Rotations For Equal Row
In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)
We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.
Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.
If it cannot be done, return -1.
Example 1:
1 2 3 4 5
Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2] Output: 2 Explanation: The first figure represents the dominoes as given by tops and bottoms: before we do any rotations. If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
Example 2:
1 2 3 4
Input: tops = [3,5,1,2,3], bottoms = [3,6,3,3,4] Output: -1 Explanation: In this case, it is not possible to rotate the dominoes to make one row of values equal.
Constraints:
2 <= tops.length <= 2 * 104
bottoms.length == tops.length
1 <= tops[i], bottoms[i] <= 6
这道题说是有长度相等的两个数组A和B,分别表示一排多米诺的上边数字和下边数字,多米诺的个数和数组的长度相同,数字为1到6之间,问最少旋转多少次多米诺,可以使得上边或下边的数字全部相同。例子1中给了图解,很好的帮我们理解题意,实际上出现次数越多的数字越可能就是最终全部相同的数字,所以统计A和B中每个数字出现的次数就变的很重要了,由于A和B中有可能相同位置上的是相同的数字,则不用翻转,要使得同一行变为相同的数字,翻转的地方必须是不同的数字,如何才能知道翻转后可以使同一行完全相同呢?需要某个数字在A中出现的次数加上在B中出现的次数减去A和B中相同位置出现的次数后正好等于数组的长度,这里就需要用三个数组 cntA,cntB,和 same 来分别记录某个数字在A中,B中,A和B相同位置上出现的个数,然后遍历1到6,只要符合上面提到的条件,就可以直接返回数组长度减去该数字在A和B中出现的次数中的较大值。
classSolution { public: intminDominoRotations(vector<int>& tops, vector<int>& bottoms){ int n = tops.size(), res = 0; vector<int> cnt1(7, 0), cnt2(7, 0), same(7, 0); for (int i = 0; i < n; i ++) { cnt1[tops[i]] ++; cnt2[bottoms[i]] ++; if (tops[i] == bottoms[i]) same[tops[i]] ++; }
for (int i = 1; i < 7; i ++) { if (cnt1[i] + cnt2[i] - same[i] == n) return n - max(cnt1[i], cnt2[i]); } return-1; } };
Leetcode1008. Construct Binary Search Tree from Preorder Traversal
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
Every non-negative integer N has a binary representation. For example, 5 can be represented as “101” in binary, 11 as “1011” in binary, and so on. Note that except for N = 0, there are no leading zeroes in any binary representation.
The complement of a binary representation is the number in binary you get when changing every 1 to a 0 and 0 to a 1. For example, the complement of “101” in binary is “010” in binary.
For a given number N in base-10, return the complement of it’s binary representation as a base-10 integer.
Example 1:
1 2 3
Input: 5 Output: 2 Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.
Example 2:
1 2 3
Input: 7 Output: 0 Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.
Example 3:
1 2 3
Input: 10 Output: 5 Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.
classSolution { public: intbitwiseComplement(int N){ if(N == 0) return1; if(N == 1) return0; vector<int> re; while(N) { re.push_back(N & 1); N = N >> 1; } reverse(re.begin(), re.end()); int res = 0; for(int i = 0; i < re.size(); i ++) { res = res * 2 + (~re[i] & 1); } return res; } };
方法二,利用位运算直接取反。
1 2 3 4 5 6 7 8 9 10 11
classSolution { public: intbitwiseComplement(int N){ int i = 0; if(!N) return1; while(N > pow(2, i)) i ++; return (~N) & ((int)pow(2, i) - 1); } };
Leetcode1010. Pairs of Songs With Total Durations Divisible by 60
In a list of songs, the i-th song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
Example 1:
1 2 3 4 5 6
Input: [30,20,150,100,40] Output: 3 Explanation: Three pairs have a total duration divisible by 60: (time[0] = 30, time[2] = 150): total duration 180 (time[1] = 20, time[3] = 100): total duration 120 (time[1] = 20, time[4] = 40): total duration 60
Example 2:
1 2 3
Input: [60,60,60] Output: 3 Explanation: All three pairs have a total duration of 120, which is divisible by 60.
如果两首歌时间之和要能被60整除,说明余数为0,那么假设第一首歌对60的余数是 a ,那么另一首歌的对60的余数为 60-a 才行。所以我们可以用一个长度为60的数组,下标刚好对应求余后的数,每次找到一个新的歌余数为 a,就看它前面对应余数为 60-a 的有多少首歌,即可以匹配为多少对。最后这首歌的余数对应的下标数组值 ++。
这样解决之后,我们只用遍历一次数组即可,所以时间复杂度是 O(n) ,但是需要了额外的空间开销。
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { public: intnumPairsDivisibleBy60(vector<int>& time){ int length = time.size(); int res = 0; vector<int> yushu(60, 0); for(int i = 0; i < length; i ++) { res += yushu[(60 - time[i]%60)%60]; yushu[ time[i]%60 ] ++; } return res; } };
Leetcode1011. Capacity To Ship Packages Within D Days
A conveyor belt has packages that must be shipped from one port to another within D days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.
Example 1:
1 2 3 4 5 6 7 8
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Example 2:
1 2 3 4 5 6
Input: weights = [3,2,2,4,1,4], D = 3 Output: 6 Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this: 1st day: 3, 2 2nd day: 2, 4 3rd day: 1, 4
classSolution { public: intshipWithinDays(vector<int>& weights, int days){ int sum = 0, size = weights.size(), max_val = -1, need; for (int i = 0; i < size; i ++) { max_val = max(max_val, weights[i]); sum += weights[i]; } int left = max_val, right = sum, mid; while(left < right) { mid = left + (right - left) / 2; int cur = 0; need = 1; for (int i = 0; i < size; i ++) { if (cur + weights[i] > mid) { need ++; cur = 0; } cur += weights[i]; } if (need > days) left = mid+1; else right = mid; } return right; } };
Leetcode1013. Partition Array Into Three Parts With Equal Sum
Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.
Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[A.length - 1])
classSolution { public: boolcanThreePartsEqualSum(vector<int>& A){ int sum = 0, part_sum = 0, i; for(int i = 0; i < A.size(); i ++) sum += A[i]; if(sum % 3 != 0) returnfalse; sum /= 3; for(i = 0; i < A.size(); i ++) { part_sum += A[i]; if(part_sum == sum) break; } for(part_sum = 0, i = i + 1; i < A.size(); i++) { part_sum += A[i]; if(part_sum == sum) break; } if(i < A.size() - 1) returntrue; returnfalse; } };
Leetcode1014. Best Sightseeing Pair
Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.
The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.
Return the maximum score of a pair of sightseeing spots.
这道题给了一个正整数的数组A,定义了一种两个数字对儿的记分方式,为A[i] + A[j] + i - j,现在让找出最大的那组的分数。利用加法的分配律,可以得到A[i] + i + A[j] - j,为了使这个表达式最大化,A[i] + i自然是越大越好,这里可以使用一个变量 mx 来记录之前出现过的A[i] + i的最大值,则当前的数字就可以当作数对儿中的另一个数字,其减去当前坐标值再加上 mx 就可以更新结果 res 了,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11
classSolution { public: intmaxScoreSightseeingPair(vector<int>& values){ int maxx = INT_MIN, res = INT_MIN; for (int i = 0; i < values.size(); i ++) { res = max(res, maxx + values[i] - i); maxx = max(maxx, values[i] + i); } return res; } };
Leetcode1015. Smallest Integer Divisible by K
Given a positive integer K, you need to find the length of the smallest positive integer N such that N is divisible by K, and N only contains the digit 1.
Return *the length of *N. If there is no such N, return -1.
Note: N may not fit in a 64-bit signed integer.
Example 1:
1 2 3
Input: K = 1 Output: 1 Explanation: The smallest answer is N = 1, which has length 1.
Example 2:
1 2 3
Input: K = 2 Output: -1 Explanation: There is no such positive integer N divisible by 2.
Example 3:
1 2 3
Input: K = 3 Output: 3 Explanation: The smallest answer is N = 111, which has length 3.
从1开始检查,每次乘以 10 再加1,就可以得到下一个数字,但是由于K可能很大,则N就会超出整型数的范围,就算是长整型也不一定 hold 的住,所以不能一直变大,而是每次累加后都要对 K 取余,若余数为0,则直接返回当前长度,若不为0,则用余数乘以 10 再加1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: intsmallestRepunitDivByK(int k){ if (k % 2 == 0 || k % 5 == 0) return-1; int r = 0; for (int i = 1; i <= k; i ++) { r = r * 10 + 1; if (r % k == 0) return i; r = r % k; } return-1; } };
Leetcode1016. Binary String With Substrings Representing 1 To N
Given a binary string S (a string consisting only of ‘0’ and ‘1’s) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.
验证从N到1之间所有的数字,先求出其二进制数的字符串,在 C++ 中可以利用 bitset 来做,将其转为字符串即可。由于定义了 32 位的 bitset,转为字符串后可能会有许多 leading zeros,所以首先要移除这些0,通过在字符串中查找第一个1,然后通过取子串的函数就可以去除所有的起始0了。然后在S中查找是否存在这个二进制字符串,若不存在,直接返回 false,遍历完成后返回 true 即可,参见代码如下:
学到了,bitset还可以这么用,转成二进制字符串确实很方便。
1 2 3 4 5 6 7 8 9 10
classSolution { public: boolqueryString(string S, int N){ for (int i = N; i > 0; --i) { string b = bitset<32>(i).to_string(); if (S.find(b.substr(b.find("1"))) == string::npos) returnfalse; } returntrue; } };
Leetcode1017. Convert to Base -2
Given an integer n, return a binary string representing its representation in base -2.
Note that the returned string should not have leading zeros unless the string is “0”.
classSolution { public: string baseNeg2(int N){ string res; while (N != 0) { int rem = N % (-2); N /= -2; if (rem < 0) { rem += 2; N += 1; } res = to_string(rem) + res; } return res == "" ? "0" : res; } };
Leetcode1018. Binary Prefix Divisible By 5
Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)
Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.
Example 1:
1 2 3
Input: [0,1,1] Output: [true,false,false] Explanation: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. Only the first number is divisible by 5, so answer[0] is true.
由第 4 点, 可以将 number % 5 作为一个整体, 更新公式为 a = (a * 2 + A[i]) % 5.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: vector<bool> prefixesDivBy5(vector<int>& A){ vector<bool> res; int ans = 0, temp = 1; for(int i = 0; i < A.size(); i ++) { ans = ((ans * 2)%5 + A[i])%5; if(ans % 5 == 0) res.push_back(true); else res.push_back(false); } return res; } };
Leetcode1019. Next Greater Node In Linked List
You are given the head of a linked list with n nodes.
For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.
Return an integer array answer where answer[i] is the value of the next greater node of the ith node (1-indexed). If the ith node does not have a next greater node, set answer[i] = 0.
Example 1:
1 2
Input: head = [2,1,5] Output: [5,5,0]
Example 2:
1 2
Input: head = [2,7,4,3,5] Output: [7,0,5,5,0]
这道题给了一个链表,让找出每个结点值的下一个较大的结点值,跟之前的 Next Greater Element I,Next Greater Element II,和 Next Greater Element III 很类似,不同的是这里不是数组,而是链表,就稍稍的增加了一些难度,因为链表无法直接根据下标访问元素,在遍历链表之前甚至不知道总共有多少个结点。基本上来说,为了达到线性的时间复杂度,这里需要维护一个单调递减的栈,若当前的数字小于等于栈顶元素,则加入栈,若当前数字大于栈顶元素,非常棒,说明栈顶元素的下一个较大数字找到了,标记上,且把栈顶元素移除,继续判断下一个栈顶元素和当前元素的关系,直到当前数字小于等于栈顶元素为止。通过这种方法,就可以在线性的时间内找出所有数字的下一个较大的数字了。
这里新建两个数组,res 和 nums 分别保存要求的结果和链表的所有结点值,还需要一个栈 st 和一个变量 cnt(记录当前的数组坐标),然后开始遍历链表,首先把当前结点值加入数组 nums,然后开始循环,若栈不空,且当前结点值大于栈顶元素(注意这里单调栈存的并不是结点值,而是该值在 nums 数组中的坐标值,这是为了更好的在结果 res 中定位),此时用该结点值来更新结果 res 中的对应的位置,然后将栈顶元素移除,继续循环直到条件不满足位置。然后把当前的坐标加入栈中,此时还要更新结果 res 的大小,因为由于链表的大小未知,无法直接初始化 res 的大小,当然我们可以在开头的时候先遍历一遍链表,得到结点的个数也是可以的,参见代码如下:
Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)
A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.
Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.
Example 1:
1 2 3 4
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3 Explanation: There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.
Example 2:
1 2 3 4
Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] Output: 0 Explanation: All 1s are either on the boundary or can reach the boundary.
Note:
1 <= A.length <= 500
1 <= A[i].length <= 500
0 <= A[i][j] <= 1
All rows have the same size.
这道题给了一个只有0和1的二维数组A,其中0表示海洋,1表示陆地,每次只能从一块陆地走到和其相连的另一块陆地上,问有多少块陆地可以不用走到边界上。其实这道题就是让找出被0完全包围的1的个数,反过来想,如果有1在边界上,那么和其相连的所有1都是不符合题意的,所以只要以边界上的1为起点,遍历所有和其相连的1,并且标记,则剩下的1一定就是被0完全包围的。遍历的方法可以用 BFS 或者 DFS,先来看 BFS 的解法,使用一个队列 queue,遍历数组A,现将所有1的个数累加到结果 res,然后将边界上的1的坐标加入队列中。然后开始 while 循环,去除队首元素,若越界了,或者对应的值不为1,直接跳过。否则标记当前位置值为0,并且 res 自减1,然后将周围四个位置都排入队列中,最后返回结果 res 即可,参见代码如下:
classSolution { public: voiddfs(vector<vector<int>>& grid, int i, int j){ if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1) return; grid[i][j] = 0; dfs(grid, i, j+1); dfs(grid, i, j-1); dfs(grid, i+1, j); dfs(grid, i-1, j); } intnumEnclaves(vector<vector<int>>& grid){ int m = grid.size(), n = grid[0].size(), num1 = 0; for (int i = 0; i < m; i ++) { if (grid[i][0] == 1) dfs(grid, i, 0); if (grid[i][n-1] == 1) dfs(grid, i, n-1); } for (int i = 0; i < n; i ++) { if (grid[0][i] == 1) dfs(grid, 0, i); if (grid[m-1][i] == 1) dfs(grid, m-1, i); } for (int i = 0; i < m; i ++) for (int j = 0; j < n; j ++) if (grid[i][j] == 1) num1 ++; return num1; } };
Leetcode1021. Remove Outermost Parentheses
A valid parentheses string is either empty (“”), “(“ + A + “)”, or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, “”, “()”, “(())()”, and “(()(()))” are all valid parentheses strings.
A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.
Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + … + P_k, where P_i are primitive valid parentheses strings.
Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.
Example 1:
1 2 3 4 5
Input: "(()())(())" Output: "()()()" Explanation: The input string is "(()())(())", with primitive decomposition "(()())" + "(())". After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
Example 2:
1 2 3 4 5
Input: "(()())(())(()(()))" Output: "()()()()(())" Explanation: The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))". After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
Example 3:
1 2 3 4 5
Input: "()()" Output: "" Explanation: The input string is "()()", with primitive decomposition "()" + "()". After removing outer parentheses of each part, this is "" + "" = "".
Given a binary tree, each node has value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.
classSolution { public: int result; voiddfs(TreeNode* root ,int now){ if(!root->left && !root->right){ result += (now<<1) + root->val; } int val = (now<<1) + root->val; if(root->left) dfs(root->left, val); if(root->right) dfs(root->right, val); } intsumRootToLeaf(TreeNode* root){ result=0; dfs(root,0); return result; } };
Leetcode1023. Camelcase Matching
A query word matches a given pattern if we can insert lowercase letters to the pattern word so that it equals the query. (We may insert each character at any position, and may insert 0 characters.)
Given a list of queries, and a pattern, return an answer list of booleans, where answer[i] is true if and only if queries[i] matches the pattern.
Example 1:
1 2 3 4 5 6
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB" Output: [true,false,true,true,false] Explanation: "FooBar" can be generated like this "F" + "oo" + "B" + "ar". "FootBall" can be generated like this "F" + "oot" + "B" + "all". "FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".
Example 2:
1 2 3 4 5
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa" Output: [true,false,true,false,false] Explanation: "FooBar" can be generated like this "Fo" + "o" + "Ba" + "r". "FootBall" can be generated like this "Fo" + "ot" + "Ba" + "ll".
Example 3:
1 2 3 4
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT" Output: [false,true,false,false,false] Explanation: "FooBarTest" can be generated like this "Fo" + "o" + "Ba" + "r" + "T" + "est".
Note:
1 <= queries.length <= 100
1 <= queries[i].length <= 100
1 <= pattern.length <= 100
All strings consists only of lower and upper case English letters.
Solution 1, Find For each query, find all letters in pattern left-to-right. If we found all pattern letters, check that the rest of the letters is in the lower case.
For simplicity, we can replace the found pattern letter in query with a lowercase ‘a’.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
vector<bool> camelMatch(vector<string>& qs, string pattern, vector<bool> res = {}){ for (auto i = 0; i < qs.size(); ++i) { for (auto p = -1, j = 0; j < pattern.size(); ++j) { p = qs[i].find(pattern[j], p + 1); if (p == string::npos) { res.push_back(false); break; } qs[i][p] = 'a'; } if (res.size() <= i) res.push_back(all_of(begin(qs[i]), end(qs[i]), [](char ch) { returnislower(ch); })); } return res; }
Solution 2, Simple Scan Instead of using the find function, we can just check all characters in the query. If a character matches the pattern pointer (pattern[p]), we advance that pointer (++p). Otherwise, we check that the query character is in the lower case.
检查查询的字符串,如果一个字符与pattern[p]匹配了,就继续,如果不匹配,看是不是小些
With this solution, it’s also easer to realize that the complexity is O(n), where n is the total number of query characters.
1 2 3 4 5 6 7 8 9 10
vector<bool> camelMatch(vector<string>& qs, string pattern, vector<bool> res = {}){ for (auto i = 0, j = 0, p = 0; i < qs.size(); ++i) { for (j = 0, p = 0; j < qs[i].size(); ++j) { if (p < pattern.size() && qs[i][j] == pattern[p]) ++p; elseif (!islower(qs[i][j])) break; } res.push_back(j == qs[i].size() && p == pattern.size()); } return res; }
Complexity Analysis
Runtime: O(n), where n is all letters in all queries. We process each letter only once.
Memory: O(m), where m is the number of queries (to store the result).
时间复杂度O(n),空间复杂度O(m)
Leetcode1024. Video Stitching
You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.
Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].
Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]). If the task is impossible, return -1.
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 Output: 3 Explanation: We take the clips [0,2], [8,10], [1,9]; a total of 3 clips. Then, we can reconstruct the sporting event as follows: We cut [1,9] into segments [1,2] + [2,8] + [8,9]. Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].
Example 2:
1 2 3 4
Input: clips = [[0,1],[1,2]], T = 5 Output: -1 Explanation: We can't cover [0,5] with only [0,1] and [0,2].
Example 3:
1 2 3 4
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9 Output: 3 Explanation: We can take clips [0,4], [4,7], and [6,9].
Example 4:
1 2 3 4
Input: clips = [[0,4],[2,8]], T = 5 Output: 2 Explanation: Notice you can have extra video after the event ends.
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number N on the chalkboard. On each player’s turn, that player makes a move consisting of:
Choosing any x with 0 < x < N and N % x == 0. Replacing the number N on the chalkboard with N - x. Also, if a player cannot make a move, they lose the game.
Return True if and only if Alice wins the game, assuming both players play optimally.
Example 1:
1 2 3
Input: 2 Output: true Explanation: Alice chooses 1, and Bob has no more moves.
Example 2:
1 2 3
Input: 3 Output: false Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Note:
1 <= N <= 1000
两个人玩游戏,给一个数字N,先轮到A走,A选一个数字x使得0 < x < N且N % x == 0,之后N变为N-x,如果谁选不出来x,那就输了,A遇见偶数赢,奇数输。
Leetcode1026. Maximum Difference Between Node and Ancestor
Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.
(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)
Example 1:
1 2 3 4 5 6 7 8 9
Input: [8,3,10,1,6,null,14,null,null,4,7,13] Output: 7 Explanation: We have various ancestor-node differences, some of which are given below : |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
Note:
The number of nodes in the tree is between 2 and 5000.
Given an array A of integers, return the length of the longest arithmetic subsequence in A.
Recall that a subsequence of A is a list A[i_1], A[i_2], …, A[i_k] with 0 <= i_1 < i_2 < … < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).
Example 1:
1 2 3 4
Input: A = [3,6,9,12] Output: 4 Explanation: The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
1 2 3 4
Input: A = [9,4,7,2,10] Output: 3 Explanation: The longest arithmetic subsequence is [4,7,10].
Example 3:
1 2 3 4
Input: A = [20,1,15,3,10,5,8] Output: 4 Explanation: The longest arithmetic subsequence is [20,15,10,5].
classSolution { public: intlongestArithSeqLength(vector<int>& A){ int res = 0, n = A.size(); vector<vector<int>> dp(n, vector<int>(2000)); for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { int diff = A[i] - A[j] + 1000; dp[i][diff] = dp[j][diff] + 1; res = max(res, dp[i][diff]); } } return res + 1; } };
Leetcode1028. Recover a Tree From Preorder Traversal
We run a preorder depth-first search (DFS) on the root of a binary tree.
At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.
If a node has only one child, that child is guaranteed to be the left child.
Given the output traversal of this traversal, recover the tree and return its root.
遍历输入字符串,先提取短杠的个数,因为除了根结点之外,所有的深度值都是在结点值前面的,所有用一个 for 循环先提取出短杠的个数 level,然后提取结点值,也是用一个 for 循环,因为结点值可能是个多位数,有了结点值之后我们就可以新建一个结点了。下一步就比较 tricky 了,因为先序遍历跟 DFS 搜索一样有一个回到先前位置的过程,比如例子1中,当我们遍历到结点5的时候,此时是从叶结点4回到了根结点的右子结点5,现在栈中有4个结点,而当前深度为1的结点5是要连到根结点的,所以栈中的无关结点就要移除,需要把结点 2,3,4 都移除,就用一个 while 循环,假如栈中元素个数大于当前的深度 level,就移除栈顶元素。那么此时栈中就只剩根结点了,就可以连接了。此时我们的连接策略是,假如栈顶元素的左子结点为空,则连在左子结点上,否则连在右子结点上,因为题目中说了,假如只有一个子结点,一定是左子结点。然后再把当前结点压入栈即可,字符串遍历结束后,栈中只会留有一个结点(题目中限定了树不为空),就是根结点,直接返回即可,参见代码如下:
classSolution { public: TreeNode* dfs(string s, int& cur, int depth){ if (cur == s.length()) returnNULL; int i = cur, len = s.length(); while(i < len && i < cur+depth) { if (s[i] != '-') break; i ++; } if (i != cur+depth) returnNULL; int val = 0; while(i < len) if ('0' <= s[i] && s[i] <= '9') val = val * 10 + s[i++] - '0'; else break; TreeNode* res = newTreeNode(val); cur = i; res->left = dfs(s, cur, depth+1); res->right = dfs(s, cur, depth+1); return res; } TreeNode* recoverFromPreorder(string s){ int pos = 0; returndfs(s, pos, 0); } };
Leetcode1029. Two City Scheduling
There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].
Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.
Example 1:
1 2 3 4 5 6 7
Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20.
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
Note:
1 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costs[i][1]。 返回将每个人都飞到某座城市的最低费用,要求每个城市都有 N 人抵达。
classSolution { public: staticboolcomp(vector<int>&a, vector<int>&b){ return a[0]-a[1] < b[0]-b[1]; } inttwoCitySchedCost(vector<vector<int>>& costs){ int result=0; if(costs.size()==0) return result; sort(costs.begin(), costs.end(), comp); int ii=costs.size(); int i; for(i=0;i<ii/2;i++) result += costs[i][0]; for(;i<ii;i++) result+=costs[i][1]; return result; } };
Leetcode1030. Matrix Cells in Distance Order
We are given a matrix with R rows and C columns has cells with integer coordinates (r, c), where 0 <= r < R and 0 <= c < C.
Additionally, we are given a cell in that matrix with coordinates (r0, c0).
Return the coordinates of all cells in the matrix, sorted by their distance from (r0, c0) from smallest distance to largest distance. Here, the distance between two cells (r1, c1) and (r2, c2) is the Manhattan distance, |r1 - r2| + |c1 - c2|. (You may return the answer in any order that satisfies this condition.)
Example 1:
1 2 3
Input: R = 1, C = 2, r0 = 0, c0 = 0 Output: [[0,0],[0,1]] Explanation: The distances from (r0, c0) to other cells are: [0,1]
Example 2:
1 2 3 4
Input: R = 2, C = 2, r0 = 0, c0 = 1 Output: [[0,1],[0,0],[1,1],[1,0]] Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2] The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.
Example 3:
1 2 3 4
Input: R = 2, C = 3, r0 = 1, c0 = 2 Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]] Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2,2,3] There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].
classSolution { public: staticboolcomp(vector<int>& a, vector<int>& b){ return a[2] < b[2]; } vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) { int k = 0; vector<vector<int>> v(R*C, vector<int>(3)); for (int i = 0; i < R; i ++) { for(int j = 0; j < C; j ++) { v[k][0] = i; v[k][1] = j; v[k][2] = abs(i - r0) + abs(j - c0); k ++; } } sort(v.begin(), v.end(), comp); for(int kk = 0; kk < R*C; kk ++) { v[kk].pop_back(); } return v; } };
Leetcode1031. Maximum Sum of Two Non-Overlapping Subarrays
Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen.
The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping.
A subarray is a contiguous part of an array.
Example 1:
1 2 3
Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2 Output: 20 Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.
Example 2:
1 2 3
Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2 Output: 29 Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.
Example 3:
1 2 3
Input: nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3 Output: 31 Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.
classSolution { public: intmaxSumTwoNoOverlap(vector<int>& nums, int l, int m){ int n = nums.size(), res = 0; vector<int> sum(n, 0); vector<vector<int>> dp(n, vector<int>(2, 0)); for (int i = 0; i < n; i ++) { for (int j = 0; j < l && i+j < n; j ++) dp[i][0] += nums[i+j]; for (int j = 0; j < m && i+j < n; j ++) dp[i][1] += nums[i+j]; } for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { if (i + l <= j) res = max(res, dp[i][0]+dp[j][1]); if (j + m <= i) res = max(res, dp[i][0]+dp[j][1]); } } return res; } };
classSolution { public: intmaxSumTwoNoOverlap(vector<int>& A, int L, int M){ for (int i = 1; i < A.size(); ++i) { A[i] += A[i - 1]; } int res = A[L + M - 1], Lmax = A[L - 1], Mmax = A[M - 1]; for (int i = L + M; i < A.size(); ++i) { Lmax = max(Lmax, A[i - M] - A[i - M - L]); Mmax = max(Mmax, A[i - L] - A[i - M - L]); res = max(res, max(Lmax + A[i] - A[i - M], Mmax + A[i] - A[i - L])); } return res; } };
Leetcode1033. Moving Stones Until Consecutive
Three stones are on a number line at positions a, b, and c. Each turn, you pick up a stone at an endpoint (ie., either the lowest or highest position stone), and move it to an unoccupied position between those endpoints. Formally, let’s say the stones are currently at positions x, y, z with x < y < z. You pick up the stone at either position x or position z, and move that stone to an integer position k, with x < k < z and k != y. The game ends when you cannot make any more moves, ie. the stones are in consecutive positions.
When the game ends, what is the minimum and maximum number of moves that you could have made? Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]
Example 1:
1 2 3
Input: a = 1, b = 2, c = 5 Output: [1,2] Explanation: Move the stone from 5 to 3, or move the stone from 5 to 4 to 3.
Example 2:
1 2 3
Input: a = 4, b = 3, c = 2 Output: [0,0] Explanation: We cannot make any moves.
Example 3:
1 2 3
Input: a = 3, b = 5, c = 1 Output: [1,2] Explanation: Move the stone from 1 to 4; or move the stone from 1 to 2 to 4.
classSolution { public: vector<int> numMovesStones(int a, int b, int c){ int sum_ = a + b + c; int min_ = min(a, min(b, c)); int max_ = max(a, max(b, c)); int mid_ = sum_ - min_ - max_; if (max_ - min_ == 2) return {0, 0}; int min_move = min(mid_ - min_, max_ - mid_) <= 2 ? 1 : 2; int max_move = max_ - min_ - 2; return {min_move, max_move}; } };
Leetcode1034. Coloring A Border
Given a 2-dimensional grid of integers, each value in the grid represents the color of the grid square at that location.
Two squares belong to the same connected component if and only if they have the same color and are next to each other in any of the 4 directions.
The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).
Given a square at location (r0, c0) in the grid and a color, color the border of the connected component of that square with the given color, and return the final grid.
classSolution { public: vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) { int m = grid.size(), n = grid[0].size(), ori_color = grid[row][col]; vector<vector<int>> visited(m, vector<int>(n, 0)); vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} ; queue<int> q; q.push(row*n + col); visited[row][col] = 1; while(!q.empty()) { int x = q.front() / n; int y = q.front() % n; q.pop(); if (x == 0 || x == m-1 || y == 0 || y == n-1) grid[x][y] = color; for (int i = 0; i < 4; i ++) { int xx = x + dirs[i][0]; int yy = y + dirs[i][1]; if (xx < 0 || xx >= m || yy < 0 || yy >= n || visited[xx][yy] == 1) continue; if (grid[xx][yy] == ori_color) { q.push(xx * n + yy); visited[xx][yy] = 1; } else grid[x][y] = color; } } return grid; } };
Leetcode1035. Uncrossed Lines
We write the integers of A and B (in the order they are given) on two separate horizontal lines.
Now, we may draw connecting lines : a straight line connecting two numbers A[i] and B[j] such that:A[i] == B[j];
The line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.
Return the maximum number of connecting lines we can draw in this way.
Example 1:
1 2 3 4
Input: A = [1,4,2], B = [1,2,4] Output: 2 Explanation: We can draw 2 uncrossed lines as in the diagram. We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.
Example 2:
1 2
Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2] Output: 3
Example 3:
1 2
Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1] Output: 2
classSolution { public: intmaxUncrossedLines(vector<int>& A, vector<int>& B) { int m = A.size(), n = B.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (A[i - 1] == B[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } };
Leetcode1037. Valid Boomerang
A boomerang is a set of 3 points that are all distinct and not in a straight line. Given a list of three points in the plane, return whether these points are a boomerang.
Leetcode1038. Binary Search Tree to Greater Sum Tree
Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.
As a reminder, a binary search tree is a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.
Leetcode1039. Minimum Score Triangulation of Polygon
You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the ith vertex (i.e., clockwise order).
You will triangulate the polygon into n - 2 triangles. For each triangle, the value of that triangle is the product of the values of its vertices, and the total score of the triangulation is the sum of these values over all n - 2 triangles in the triangulation.
Return the smallest possible total score that you can achieve with some triangulation of the polygon.
Example 1:
1 2 3
Input: values = [1,2,3] Output: 6 Explanation: The polygon is already triangulated, and the score of the only triangle is 6.
Example 2:
1 2 3 4
Input: values = [3,7,4,5] Output: 144 Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144. The minimum score is 144.
classSolution { public: intminScoreTriangulation(vector<int>& A){ int n = A.size(); vector<vector<int>> dp(n, vector<int>(n)); for (int len = 2; len < n; ++len) { for (int i = 0; i + len < n; ++i) { int j = i + len; dp[i][j] = INT_MAX; for (int k = i + 1; k < j; ++k) { dp[i][j] = min(dp[i][j], dp[i][k] + A[i] * A[k] * A[j] + dp[k][j]); } } } return dp[0][n - 1]; } };
Leetcode1041. Robot Bounded In Circle
On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:
“G”: go straight 1 unit;
“L”: turn 90 degrees to the left;
“R”: turn 90 degrees to the right.
The robot performs the instructions given in order, and repeats them forever.
Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.
Example 1:
1 2 3 4
Input: instructions = "GGLLGG" Output: true Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0). When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
Example 2:
1 2 3
Input: instructions = "GG" Output: false Explanation: The robot moves north indefinitely.
classSolution { public: boolisRobotBounded(string instructions){ vector<vector<int>> dirs{{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; int xx = 0, yy = 0; int direction = 0; for (int i = 0; i < instructions.size(); i ++) { if (instructions[i] == 'G') { xx += dirs[direction][0]; yy += dirs[direction][1]; } elseif (instructions[i] == 'L') direction = (direction + 1 ) % 4; elseif (instructions[i] == 'R') direction = (direction + 4 - 1) % 4; } return (xx == 0 && yy == 0) || direction != 0; } };
Leetcode1042. Flower Planting With No Adjacent
You have N gardens, labelled 1 to N. In each garden, you want to plant one of 4 types of flowers. paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y. Also, there is no garden that has more than 3 paths coming into or leaving it.
Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.
Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.
Example 1:
1 2
Input: N = 3, paths = [[1,2],[2,3],[3,1]] Output: [1,2,3]
Example 2:
1 2
Input: N = 4, paths = [[1,2],[3,4]] Output: [1,2,1,2]
Example 3:
1 2
Input: N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]] Output: [1,2,3,4]
Note:
1 <= N <= 10000
0 <= paths.size <= 20000
No garden has 4 or more paths coming into or leaving it.
It is guaranteed an answer exists.
有 N 个花园,按从 1 到 N 标记。在每个花园中,你打算种下四种花之一。 paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。另外,没有花园有 3 条以上的路径可以进入或者离开。你需要为每个花园选择一种花,使得通过路径相连的任何两个花园中的花的种类互不相同。以数组形式返回选择的方案作为答案 answer,其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: vector<int> gardenNoAdj(int N, vector<vector<int>>& paths){ vector<int> res(N, 0); vector<vector<int>> graph(N); for(int i = 0 ; i < paths.size(); i ++) { graph[paths[i][0]-1].push_back(paths[i][1]-1); graph[paths[i][1]-1].push_back(paths[i][0]-1); } for (int i = 0; i < N; ++i) { int mask = 0; for (constauto& j : graph[i]) mask |= (1 << res[j]); for (int c = 1; c <= 4 && res[i] == 0; ++c) if (!(mask & (1 << c))) res[i] = c; } return res; } };
Leetcode1043. Partition Array for Maximum Sum
Given an integer array arr, you should partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning.
classSolution { public: intmaxSumAfterPartitioning(vector<int>& arr, int k){ int n = arr.size(); vector<int> dp(n + 1); for (int i = 1; i <= n; ++i) { int curMax = 0; for (int j = 1; j <= k && i - j >= 0; ++j) { curMax = max(curMax, arr[i - j]); dp[i] = max(dp[i], dp[i - j] + curMax * j); } } return dp[n]; } };
Leetcode1046. Last Stone Weight
We have a collection of stones, each stone has a positive integer weight.
Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)
Example 1:
1 2 3 4 5 6 7
Input: [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.
classSolution { public: intlastStoneWeight(vector<int>& stones){ int p, q; if(stones.size() == 1) return stones[0]; while(stones.size() >= 2) { heapsort(stones); p = stones.back(); stones.pop_back(); q = stones.back(); stones.pop_back(); int diff = p - q; if(diff) stones.push_back(diff); } if(stones.empty()) return0; return stones[0]; } voidheapsort(vector<int>& stones){ if(stones.size() <= 1) return; build_heap(stones); int heap_size = stones.size(); while(heap_size >= 2) { swap(stones[0], stones[heap_size - 1]); heap_size --; max_heapify(stones, 0, heap_size); } } voidbuild_heap(vector<int>& stones){ for(int i=stones.size()/2; i>=0; i--){ max_heapify(stones, i, stones.size()); } } voidmax_heapify(vector<int>& stones, int i, int heap_size){ int large = i; if(2*i+1<heap_size && stones[i]<stones[2*i+1]) large = 2*i+1; if(2*i+2<heap_size && stones[large]<stones[2*i+2]) large = 2*i+2; if(large != i){ swap(stones[i], stones[large]); max_heapify(stones, large, heap_size); } } voidswap(int &a, int &b){ int temp; temp = a; a = b; b = temp; } };
Leetcode1047. Remove All Adjacent Duplicates In String
Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.
We repeatedly make duplicate removals on S until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.
Example 1:
1 2 3 4
Input: "abbaca" Output: "ca" Explanation: For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
string removeDuplicates(string S){ string res = ""; for (char& c : S) if (res.size() && c == res.back()) res.pop_back(); else res.push_back(c); return res; }
1 2 3 4 5 6 7 8 9 10
classSolution { public: string removeDuplicates(string S){ string a; for (auto& c : S) if (a.size() && a.back() == c) a.pop_back(); else a.push_back(c); return a; } };
classSolution { public: string removeDuplicates(string S){ string res=""; int len = 0; int S_len = S.size(); for(int i=0;i<S_len;i++){ if( len>0 && res[len-1]==S[i]){ res.pop_back(); len--; } else{ res += S[i]; len++; } } return res; } };
Leetcode1048. Longest String Chain
Given a list of words, each word consists of English lowercase letters.
Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, “abc” is a predecessor of “abac”.
A *word chain *is a sequence of words [word_1, word_2, …, word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.
Example 1:
1 2 3
Input: words = ["a","b","ba","bca","bda","bdca"] Output: 4 Explanation: One of the longest word chain is "a","ba","bda","bdca".
Example 2:
1 2
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"] Output: 5
Constraints:
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.
classSolution { public: intlongestStrChain(vector<string>& words){ int n = words.size(), res = 1; sort(words.begin(), words.end(), [](string& a, string& b){ return a.size() < b.size(); }); unordered_map<string, int> dp; for (string word : words) { dp[word] = 1; for (int i = 0; i < word.size(); ++i) { string pre = word.substr(0, i) + word.substr(i + 1); if (dp.count(pre)) { dp[word] = max(dp[word], dp[pre] + 1); res = max(res, dp[word]); } } } return res; } };
Leetcode1049. Last Stone Weight II
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
Example 1:
1 2 3 4 5 6 7
Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then, we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then, we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then, we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.
classSolution { public: intlastStoneWeightII(vector<int>& stones){ vector<bool> dp(1501); dp[0] = true; int sum = 0; for (int stone : stones) { sum += stone; for (int i = min(1500, sum); i >= stone; --i) { dp[i] = dp[i] || dp[i - stone]; } } for (int i = sum / 2; i >= 0; --i) { if (dp[i]) return sum - 2 * i; } return0; } };
Leetcode1051. Height Checker
Students are asked to stand in non-decreasing order of heights for an annual photo.
Return the minimum number of students not standing in the right positions. (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)
Example 1:
1 2
Input: [1,1,4,2,1,3] Output: 3
Explanation: Students with heights 4, 3 and the last 1 are not standing in the right positions.
classSolution { public: /*int heightChecker(vector<int>& heights) { int res=0; for(int i=1;i<heights.size()-1;i++){ if(!(heights[i]>=heights[i-1] && heights[i]<=heights[i+1])) res++; } return res; } */ intheightChecker(vector<int>& h){ int res = 0 vector<int> s = h; sort(begin(s), end(s)); for (auto i = 0; i < h.size(); ++i) res += h[i] != s[i]; return res; } };
Leetcode1052. Grumpy Bookstore Owner
Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.
On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.
The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.
Return the maximum number of customers that can be satisfied throughout the day.
Example 1:
1 2 3 4
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 Output: 16 Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
Note:
1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1
滑动窗口. 统计在大小为 X 的窗口中, 有多少顾客刚好处在店主脾气不好的时刻, 即grumpy[i] == 1。其中grumpy[i] == 0对应的顾客始终是满意的, 使用 base 来统计. 而对于那些grumpy[i] == 1的顾客, 只有在他们刚好在滑动窗口中, 才能满意, 用 new_satisfied 统计在滑动窗口中新满意的顾客, 在窗口滑动过程中使用 max_satisfied 来记录最大值. 最后返回 base + max_satisfied.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: intmaxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes){ int res = 0, len = grumpy.size(); int sat = 0, new_sat = 0, max_sat = 0; for (int i = 0; i < len; i ++) { if (grumpy[i] == 0) sat += customers[i]; else new_sat += customers[i]; if (i >= minutes) new_sat -= (customers[i-minutes] * grumpy[i-minutes]); max_sat = max(max_sat, new_sat); } return sat + max_sat; } };
Leetcode1053. Previous Permutation With One Swap
Given an array of positive integers arr (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr, that can be made with exactly one swap (A swap exchanges the positions of two numbers arr[i] and arr[j]). If it cannot be done, then return the same array.
这道题说在一个仓库,有一排条形码,这里用数字表示,现在让给数字重新排序,使得相邻的数字不相同,并且说了一定会有合理的答案。意思就是说最多的重复个数不会超过数组长度的一半,否则一定会有相邻的重复数字。那么来分析一下题目,既然是为了避免重复数字被排在相邻的位置,肯定是要优先关注出现次数多的数字,因为它们更有可能出现在相邻的位置。这道题是可以用贪婪算法来做的,每次取出出现次数最多的两个数字,将其先排列起来,然后再取下一对出现次数最多的两个数字,以此类推直至排完整个数组。这里为了快速知道出现次数最多的数字,可以使用优先队列来做,里面放一个 pair 对儿,由频率和数字组成,这样优先队列就可以根据频率由高到低来自动排序了。统计频率的话就使用一个 HashMap,然后将频率和数字组成的 pair 对儿加入优先队列。进行 while 循环,条件是队列中的 pair 对儿至少两个,这样才能每次取出两个,将其加入结果 res 中,然后其频率分别减1,只要没减到0,就都加回优先队列中。最后可能队列还有一个剩余,有的话将数字加入结果 res 中即可,参见代码如下:
classSolution { public: vector<int> rearrangeBarcodes(vector<int>& barcodes){ int n = barcodes.size(), pos = 0; vector<int> res(n); vector<pair<int, int>> vec; unordered_map<int, int> numCnt; for (int num : barcodes) ++numCnt[num]; for (auto &a : numCnt) { vec.push_back({a.second, a.first}); } sort(vec.rbegin(), vec.rend()); for (auto &a : vec) { for (int i = 0; i < a.first; ++i, pos += 2) { if (pos >= n) pos = 1; res[pos] = a.second; } } return res; } };
Leetcode1055. Shortest Way to Form String
From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions).
Given two strings source and target, return the minimum number of subsequences of source such that their concatenation equals target. If the task is impossible, return -1.
Example 1:
1 2 3
Input: source = "abc", target = "abcbc" Output: 2 Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".
Example 2:
1 2 3
Input: source = "abc", target = "acdbc" Output: -1 Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target string.
Example 3:
1 2 3
Input: source = "xyz", target = "xzyxz" Output: 3 Explanation: The target string can be constructed as follows "xz" + "y" + "xz".
Constraints:
Both the source and target strings consist of only lowercase English letters from “a”-“z”.
The lengths of source and target string are between 1 and 1000.
classSolution { public: intshortestWay(string source, string target){ int res = 0, j = 0, m = source.size(), n = target.size(); while (j < n) { int pre = j; for (int i = 0; i < m; ++i) { if (j < n && source[i] == target[j]) ++j; } if (j == pre) return-1; ++res; } return res; } };
classSolution { public: intshortestWay(string source, string target){ int res = 1, pos = -1, n = target.size(); for (int i = 0; i < n; ++i) { if (source.find(target[i]) == -1) return-1; pos = source.find(target[i], pos + 1); if (pos == -1) { ++res; pos = source.find(target[i]); } } return res; } };
Leetcode1056. Confusing Number
Given a number N, return true if and only if it is a confusing number , which satisfies the following condition:
We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid. A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.
Example 1:
1 2 3 4
Input: 6 Output: true Explanation: We get `9` after rotating `6`, `9` is a valid number and `9!=6`.
Example 2:
1 2 3 4
Input: 89 Output: true Explanation: We get `68` after rotating `89`, `86` is a valid number and `86!=89`.
Example 3:
1 2 3 4
Input: 11 Output: false Explanation: We get `11` after rotating `11`, `11` is a valid number but the value remains the same, thus `11` is not a confusing number.
Example 4:
1 2 3 4
Input: 25 Output: false Explanation: We get an invalid number after rotating `25`.
Note:
0 <= N <= 10^9
After the rotation we can ignore leading zeros, for example if after rotation we have 0008 then this number is considered as just 8.
这道题定义了一种迷惑数,将数字翻转 180 度,其中 0, 1, 8 旋转后保持不变,6变成9,9变成6,数字 2, 3, 4, 5, 和 7 旋转后变为非法数字。若能将某个数翻转后成为一个合法的新的数,就说这个数是迷惑数。这道题的难度并不大,就是考察的是遍历整数各个位上的数字,使用一个 while 循环,然后用 mod10 取出当前最低位上的数字,将不合法的数字放入一个 HashSet 中,这样直接在 HashSet 中查找一下当前数字是否存在,存在直接返回 false。不存在的话,则要进行翻转,因为只有6和9两个数字翻转后会得到不同的数字,所以单独判断一下,然后将当前数字拼到 num 的最低位即可,最终拼成的 num 就是原数字 N 的翻转,最后别忘了比较一下是否相同,参见代码如下:
解法一:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: boolconfusingNumber(int N){ int num = 0, oldN = N; unordered_set<int> invalid{{2, 3, 4, 5, 7}}; while (N > 0) { int digit = N % 10; if (invalid.count(digit)) returnfalse; if (digit == 6) digit = 9; elseif (digit == 9) digit = 6; num = num * 10 + digit; N /= 10; } return num != oldN; } };
classSolution { public: boolconfusingNumber(int N){ unordered_map<int, int> m{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}}; long oldN = N, res = 0; while (N > 0) { if (!m.count(N % 10)) returnfalse; res = res * 10 + m[N % 10]; N /= 10; } return res != oldN; } };
下面来看一种双指针的解法,这里先用一个数组 rotate 来按位记录每个数字翻转后得到的数字,用 -1 来表示非法情况,然后将数字 N 转为字符串,用两个指针 left 和 right 分别指向开头和末尾。用 while 循环进行遍历,假如此时 left 和 right 中有任何一个指向的数字翻转后是非法,直接返回 false。然后看 left 指向的数字翻转后跟 right 指向的数字是否相同,若不同,则将 res 标记为 true,然后移动 left 和 right 指针,最终返回 res 即可,参见代码如下:
解法三:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: boolconfusingNumber(int N){ bool res = false; vector<int> rotate{0, 1, -1, -1, -1, -1, 9, -1, 8, 6}; string str = to_string(N); int n = str.size(), left = 0, right = n - 1; while (left <= right) { if (rotate[str[left] - '0'] == -1 || rotate[str[right] - '0'] == -1) returnfalse; if (rotate[str[left] - '0'] != (str[right] - '0')) res = true; ++left; --right; } return res; } };
Leetcode1057. Campus Bikes
On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.
Our goal is to assign a bike to each worker. Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, and assign the bike to that worker. (If there are multiple (worker, bike) pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index; if there are multiple ways to do that, we choose the pair with the smallest bike index). We repeat this process until there are no available workers.
The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Return a vector ans of length N, where ans[i] is the index (0-indexed) of the bike that the i-th worker is assigned to.
Example 1:
1 2 3 4
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] Output: [1,0] Explanation: Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].
Example 2:
1 2 3 4
Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]] Output: [0,2,1] Explanation: Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].
classSolution { public: vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes){ int m = workers.size(), n = bikes.size(); vector<int> assignedWorker(m, -1), assignedBike(n, -1); vector<vector<pair<int, int>>> buckets(2001); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]); buckets[dist].push_back({i, j}); } } for (int dist = 0; dist <= 2000; ++dist) { for (int k = 0; k < buckets[dist].size(); ++k) { if (assignedWorker[buckets[dist][k].first] == -1 && assignedBike[buckets[dist][k].second] == -1) { assignedWorker[buckets[dist][k].first] = buckets[dist][k].second; assignedBike[buckets[dist][k].second] = buckets[dist][k].first; } } } return assignedWorker; } };
Leetcode1058. Minimize Rounding Error to Meet Target
Given an array of prices [p1,p2…,pn] and a target, round each price pi to Roundi(pi) so that the rounded array [Round1(p1),Round2(p2)…,Roundn(pn)] sums to the given target. Each operation Roundi(pi) could be either Floor(pi) or Ceil(pi).
Return the string “-1” if the rounded array is impossible to sum to target. Otherwise, return the smallest rounding error, which is defined as Σ |Roundi(pi) - (pi)| for i from 1 to n, as a string with three places after the decimal.
Example 1:
1 2 3 4
Input: prices = [“0.700”,”2.800”,”4.900”], target = 8 Output: “1.000” Explanation: Use Floor, Ceil and Ceil operations to get (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 .
Example 2:
1 2 3 4
Input: prices = [“1.500”,”2.500”,”3.500”], target = 10 Output: “-1” Explanation: It is impossible to meet the target.
Note:
1 <= prices.length <= 500.
Each string of prices prices[i] represents a real number which is between 0 and 1000 and has exactly 3 decimal places. target is between 0 and 1000000.
先对nums排序。然后开始遍历,计算nums相邻两个元素之间的数字数即nums[i] - pre - 1个,是否可以满足需要的k。如果能满足,那么直接找出要返回的数字pre+k。如果不能满足,把k去掉已能满足的数字nums[i] - pre - 1。最后如果所有的nums数字都已经用完,但是还不能满足k,则需要返回nums[nums.size() - 1] + k。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intmissingElement(vector<int>& nums, int k){ sort(nums.begin(), nums.end()); int pre = nums[0]; for (int i = 1; i < nums.size(); ++i) { if (k < nums[i] - pre) { return pre + k; } else { k -= nums[i] - pre - 1; } pre = nums[i]; } return pre + k; } };
classSolution { public: intfixedPoint(vector<int>& A){ int left = 0; int right = A.size() - 1; while (left + 1 < right) { int mid = left + (right - left) / 2; if (A[mid] >= mid) { right = mid; } else { left = mid; } } if (left == A[left]) { return left; } if (right == A[right]) { return right; } return-1; } };
Leetcode1065. Index Pairs of a String
Given a text string and words (a list of strings), return all index pairs [i, j] so that the substring text[i]…text[j] is in the list of words.
Example 1:
1 2
Input: text = “thestoryofleetcodeandme”, words = [“story”,”fleet”,”leetcode”] Output: [[3,7],[9,13],[10,17]]
Example 2:
1 2 3 4
Input: text = “ababa”, words = [“aba”,”ab”] Output: [[0,1],[0,2],[2,3],[2,4]] Explanation: Notice that matches can overlap, see “aba” is found in [0,2] and [2,4].
Note:
All strings contains only lowercase English letters.
It’s guaranteed that all strings in words are different.
1 <= text.length <= 100
1 <= words.length <= 20
1 <= words[i].length <= 50
Return the pairs [i,j] in sorted order (i.e. sort them by their first coordinate in case of ties sort them by their second coordinate).
classSolution { public: string gen(string str, int i){ string res; while (i--) { res += str; } return res; } string gcdOfStrings(string str1, string str2){ int l1 = str1.length(), l2 = str2.length(); int length = min(l1, l2); string res; for(int i = length; i > 0; i --) { if(l1 % i == 0 && l2 % i == 0) { int t1 = l1 / i; int t2 = l2 / i; string gcd = str1.substr(0, i); string s1 = gen(gcd, t1); string s2 = gen(gcd, t2); if ((s1 == str1) && (s2 == str2)) { res = gcd; break; } } } return res; } };
题目要求 X 能除尽 str1 且 X 能除尽 str2,且 X 为最长。那么可以理解为 str1 由 m 个 X 连接而成, str2 由 n 个 X 连接而成。由此可知 str1 + str2 由 m + n 个 X 拼接而成,而且 str1 + str2 与 str2 + str1 在值上是相等的。然后此题就转化为了求最大公约数。str1 和 str2 长度的最大公约数,就是所求 X 的长度。
classSolution { public: intmaxEqualRowsAfterFlips(vector<vector<int>>& matrix){ unordered_map<string, int> m; for (auto& mat : matrix) { int length = mat.size(); string str(length, ' '); if (mat[0] == 0){ for(int i = 0; i < length; i ++) { mat[i] ^= 1; str[i] = mat[i] == 1 ? '1': '0'; } } else { for(int i = 0; i < length; i ++) { str[i] = mat[i] == 1 ? '1' : '0'; } } m[str] ++; } int res = 0; for (auto it = m.begin(); it != m.end(); it ++) res = max(res, it->second); return res; } };
Leetcode1073. Adding Two Negabinary Numbers
Given two numbers arr1 and arr2 in base -2, return the result of adding them together.
Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array, format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.
Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.
这道题说是有两个负二进制数是用数组来表示的,现在让返回它们相加后的结果,还是放在数组中来表示。这道题其实利用的方法跟那道很像,都是一位一位的处理的,直接加到结果 res 数组中的。这里使用两个指针i和j,分别指向数组 arr1 和 arr2 的末尾,然后用个变量 carry 表示进位,当i大于等于0时,carry 加上i指向的数字,并且i自减1,同理,当j大于等于0时,carry 加上j指向的数字,并且j自减1。由于数组中当每位上只能放一个数字,所以让 carry ‘与’上1,并加入到结果 res 数组后。然后需要再填充更高一位上的数字,对于二进制来说,直接右移1位即可,这里由于是负二进制,所以右移1位之后再取负。之后要移除所有的 leading zeros,因为这里高位是加到了 res 的后面,所以要去除末尾的零,使用个 while 去除。最后别忘了将 res 翻转一下返回即可,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2){ vector<int> res; int carry = 0, i = (int)arr1.size() - 1, j = (int)arr2.size() - 1; while (i >= 0 || j >= 0 || carry) { if (i >= 0) carry += arr1[i--]; if (j >= 0) carry += arr2[j--]; res.push_back(carry & 1); carry = -(carry >> 1); } while (res.size() > 1 && res.back() == 0) res.pop_back(); reverse(res.begin(), res.end()); return res; } };
Leetcode1078. Occurrences After Bigram
Given words first and second, consider occurrences in some text of the form “first second third”, where second comes immediately after first, and third comes immediately after second.
For each such occurrence, add “third” to the answer, and return the answer.
Example 1:
1 2
Input: text = "alice is a good girl she is a good student", first = "a", second = "good" Output: ["girl","student"]
Example 2:
1 2
Input: text = "we will we will rock you", first = "we", second = "will" Output: ["we","rock"]
Note:
1 <= text.length <= 1000
text consists of space separated words, where each word consists of lowercase English letters.
1 <= first.length, second.length <= 10
first and second consist of lowercase English letters.
You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.
Example 1:
1 2 3
Input: "AAB" Output: 8 Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
这道题实际上需要用单调栈的思路来做,首先需要统计每个字母出现的次数,这里可以使用一个大小为 128 的数组 cnt 来表示,还需要一个数组 visited 来记录某个字母是否出现过。先遍历一遍字符串,统计每个字母出现的次数到 cnt 中。再遍历一遍给定的字符串,对于遍历到的字母,在 cnt 数组中减去一个,然后看该字母是否已经在 visited 数组中出现过,是的话直接跳过。否则需要进行一个 while 循环,这里的操作实际上是为了确保得到的结果是字母顺序最小的,若当前字母小于结果 res 中的最后一个字母,且该最后的字母在 cnt 中还存在,说明之后还会遇到这个字母,则可以在 res 中先去掉这个字母,以保证字母顺序最小,并且 visited 数组中标记为0,表示未访问。这里是尽可能的将 res 打造成单调递增的,但如果后面没有这个字母了,就不能移除,所以说并不能保证一定是单调递增的,但可以保证得到的结果是字母顺序最小的。while 循环退出后,将该字母加到结果 res 后,并且 visited 标记为1。这里还有个小 trick,结果 res 在初始化给个0,这样就不用判空了,而且0是小于所有字母的,不会影响这个逻辑,最后返回的时候去掉首位0就行了,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: string smallestSubsequence(string s){ string res = "0"; vector<int> cnt(128), visited(128); for (char c : s) ++cnt[c]; for (char c : s) { --cnt[c]; if (visited[c]) continue; while (c < res.back() && cnt[res.back()]) { visited[res.back()] = 0; res.pop_back(); } res += c; visited[c] = 1; } return res.substr(1); } };
Leetcode1089. Duplicate Zeros
Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right. Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place, do not return anything from your function.
Example 1:
1 2 3
Input: [1,0,2,3,0,4,5,0] Output: null Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]
Example 2:
1 2 3
Input: [1,2,3] Output: null Explanation: After calling your function, the input array is modified to: [1,2,3]
classSolution { public: voidduplicateZeros(vector<int>& arr){ int n = arr.size(); int slow = 0, fast = 0; while(fast < n) { if(arr[slow] == 0) fast ++; fast ++; slow ++; } fast --; slow --; while(slow >= 0) { if(fast < n) arr[fast] = arr[slow]; if(arr[slow] == 0) arr[--fast] = arr[slow]; fast --; slow --; } } };
Leetcode1090. Largest Values From Labels
We have a set of items: the i-th item has value values[i] and label labels[i].
Then, we choose a subset S of these items, such that:
|S| <= num_wanted
For every label L, the number of items in S with label L is <= use_limit.
Return the largest possible sum of the subset S.
Example 1:
1 2 3
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], `num_wanted` = 3, use_limit = 1 Output: 9 Explanation: The subset chosen is the first, third, and fifth item.
Example 2:
1 2 3
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], `num_wanted` = 3, use_limit = 2 Output: 12 Explanation: The subset chosen is the first, second, and third item.
Example 3:
1 2 3
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], `num_wanted` = 3, use_limit = 1 Output: 16 Explanation: The subset chosen is the first and fourth item.
Example 4:
1 2 3
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], `num_wanted` = 3, use_limit = 2 Output: 24 Explanation: The subset chosen is the first, second, and fourth item.
classSolution { public: intshortestPathBinaryMatrix(vector<vector<int>>& grid){ if (grid[0][0] == 1) return-1; int res = 0, n = grid.size(); set<vector<int>> visited; visited.insert({0, 0}); queue<vector<int>> q; q.push({0, 0}); vector<vector<int>> dirs{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; while (!q.empty()) { ++res; for (int i = q.size(); i > 0; --i) { auto t = q.front(); q.pop(); if (t[0] == n - 1 && t[1] == n - 1) return res; for (auto dir : dirs) { int x = t[0] + dir[0], y = t[1] + dir[1]; if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] == 1 || visited.count({x, y})) continue; visited.insert({x, y}); q.push({x, y}); } } } return-1; } };
Leetcode1093. Statistics from a Large Sample
You are given a large sample of integers in the range [0, 255]. Since the sample is so large, it is represented by an array count where count[k] is the number of times that k appears in the sample.
Calculate the following statistics:
minimum: The minimum element in the sample.
maximum: The maximum element in the sample.
mean: The average of the sample, calculated as the total sum of all elements divided by the total number of elements.
median:
If the sample has an odd number of elements, then the median is the middle element once the sample is sorted.
If the sample has an even number of elements, then the median is the average of the two middle elements once the sample is sorted.
mode: The number that appears the most in the sample. It is guaranteed to be unique.
Return the statistics of the sample as an array of floating-point numbers [minimum, maximum, mean, median, mode]. Answers within 10-5 of the actual answer will be accepted.
Example 1:
1 2 3 4 5 6 7
Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] Output: [1.00000,3.00000,2.37500,2.50000,3.00000] Explanation: The sample represented by count is [1,2,2,2,3,3,3,3]. The minimum and maximum are 1 and 3 respectively. The mean is (1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375. Since the size of the sample is even, the median is the average of the two middle elements 2 and 3, which is 2.5. The mode is 3 as it appears the most in the sample.
Example 2:
1 2 3 4 5 6 7
Input: count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] Output: [1.00000,4.00000,2.18182,2.00000,1.00000] Explanation: The sample represented by count is [1,1,1,1,2,2,2,3,3,4,4]. The minimum and maximum are 1 and 4 respectively. The mean is (1+1+1+1+2+2+2+3+3+4+4) / 11 = 24 / 11 = 2.18181818... (for display purposes, the output shows the rounded number 2.18182). Since the size of the sample is odd, the median is the middle element 2. The mode is 1 as it appears the most in the sample.
Constraints:
count.length == 256
0 <= count[i] <= 109
1 <= sum(count) <= 109
The mode of the sample that count represents is unique.
classSolution { public: vector<double> sampleStats(vector<int>& count){ double mn = 256, mx = 0, mean = 0, median = 0, sum = 0; int cnt = 0, mode = 0; for (int i = 0; i < count.size(); ++i) { if (count[i] == 0) continue; if (mn == 256) mn = i; mx = i; sum += (double)i * count[i]; cnt += count[i]; if (count[i] > count[mode]) mode = i; } mean = sum / cnt; int first = (cnt + 1) / 2, second = (cnt + 2) / 2, cur = 0; for (int i = 0; i < count.size(); ++i) { if (cur < first && cur + count[i] >= first) median += i / 2.0; if (cur < second && cur + count[i] >= second) median += i / 2.0; cur += count[i]; } return {mn, mx, sum / cnt, median, (double)mode}; } };
Leetcode1094. Car Pooling
You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)
Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.
Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.
HTTP 中包括许多方法,Get 和 Post 是 HTTP 中最常用的两个方法,基本上使用 HTTP 方法中有 99% 都是在使用 Get 方法和 Post 方法,所以有必要我们对这两个方法有更加深刻的认识。
get 方法一般用于请求,比如你在浏览器地址栏输入 www.cxuanblog.com 其实就是发送了一个 get 请求,它的主要特征是请求服务器返回资源,而 post 方法一般用于 表单的提交,相当于是把信息提交给服务器,等待服务器作出响应,get 相当于一个是 pull/拉的操作,而 post 相当于是一个 push/推的操作。get 方法是不安全的,因为你在发送请求的过程中,你的请求参数会拼在 URL 后面,从而导致容易被攻击者窃取,对你的信息造成破坏和伪造;/test/demo_form.asp?name1=value1&name2=value2而 post 方法是把参数放在请求体 body 中的,这对用户来说不可见。
1 2 3
POST /test/demo_form.asp HTTP/1.1 Host: w3schools.com name1=value1&name2=value2
get 请求的 URL 有长度限制,而 post 请求会把参数和值放在消息体中,对数据长度没有要求。
get 请求会被浏览器主动 cache,而 post 不会,除非手动设置。
get 请求在浏览器反复的 回退/前进 操作是无害的,而 post 操作会再次提交表单请求。
get 请求在发送过程中会产生一个 TCP 数据包;post 在发送过程中会产生两个 TCP 数据包。对于 get 方式的请求,浏览器会把 http header 和 data 一并发送出去,服务器响应 200(返回数据);而对于 post,浏览器先发送 header,服务器响应 100 continue,浏览器再发送 data,服务器响应 200 ok(返回数据)。
X-Frame-Options:HTTP 首部字段是可以自行扩展的。所以在 Web 服务器和浏览器的应用上,会出现各种非标准的首部字段。首部字段 X-Frame-Options 属于 HTTP 响应首部,用于控制网站内容在其他 Web 网站的 Frame 标签内的显示问题。其主要目的是为了防止点击劫持(clickjacking)攻击。
下面是一个响应头的汇总,基于 HTTP 1.1
地址栏输入 URL 发生了什么
首先,你需要在浏览器中的 URL 地址上,输入你想访问的地址。然后,浏览器会根据你输入的 URL 地址,去查找域名是否被本地 DNS 缓存,不同浏览器对 DNS 的设置不同,如果浏览器缓存了你想访问的 URL 地址,那就直接返回 ip。如果没有缓存你的 URL 地址,浏览器就会发起系统调用来查询本机 hosts 文件是否有配置 ip 地址,如果找到,直接返回。如果找不到,就向网络中发起一个 DNS 查询。
首先来看一下 DNS 是啥,互联网中识别主机的方式有两种,通过主机名和 IP 地址。我们人喜欢用名字的方式进行记忆,但是通信链路中的路由却喜欢定长、有层次结构的 IP 地址。所以就需要一种能够把主机名到 IP 地址的转换服务,这种服务就是由 DNS 提供的。DNS 的全称是 Domain Name System 域名系统。DNS 是一种由分层的 DNS 服务器实现的分布式数据库。DNS 运行在 UDP 上,使用 53 端口。
DNS 是一种分层数据库,它的主要层次结构如下
一般域名服务器的层次结构主要是以上三种,除此之外,还有另一类重要的 DNS 服务器,它是 本地 DNS 服务器(local DNS server)。严格来说,本地 DNS 服务器并不属于上述层次结构,但是本地 DNS 服务器又是至关重要的。每个 ISP(Internet Service Provider) 比如居民区的 ISP 或者一个机构的 ISP 都有一台本地 DNS 服务器。当主机和 ISP 进行连接时,该 ISP 会提供一台主机的 IP 地址,该主机会具有一台或多台其本地 DNS 服务器的 IP地址。通过访问网络连接,用户能够容易的确定 DNS 服务器的 IP地址。当主机发出 DNS 请求后,该请求被发往本地 DNS 服务器,它起着代理的作用,并将该请求转发到 DNS 服务器层次系统中。
首先,查询请求会先找到本地 DNS 服务器来查询是否包含 IP 地址,如果本地 DNS 无法查询到目标 IP 地址,就会向根域名服务器发起一个 DNS 查询。
classSolution { public: string freqAlphabets(string s){ string res = ""; for(int i = 0; i < s.length(); ) { char c = s[i]; if(i+2 < s.length() && s[i+2] == '#') { char cc = s[i+1]; int temp = (c - '0') * 10 + (cc - '0') - 1; res += ('a' + temp); i += 3; } else { char cc = 'a' + (c - '0' - 1); res += cc; i += 1; } } return res; } };
Leetcode1313. Decompress Run-Length Encoded List
We are given a list nums of integers representing a list compressed with run-length encoding.
Consider each adjacent pair of elements [freq, val] = [nums[2i], nums[2i+1]] (with i >= 0). For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.
Return the decompressed list.
Example 1:
1 2 3 4 5
Input: nums = [1,2,3,4] Output: [2,4,4,4] Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2]. The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4]. At the end the concatenation [2] + [4,4,4] is [2,4,4,4].
classSolution { public: boolhave0(int nn){ while(nn) { int temp = nn % 10; if(temp == 0) returntrue; nn = nn / 10; } returnfalse; } vector<int> getNoZeroIntegers(int n){ for(int i = 1; i <= n/2; i ++) { if(!have0(i) && !have0(n-i)) return {i, n-i}; } return {}; } };
Leetcode1323. Maximum 69 Number
Given a positive integer num consisting only of digits 6 and 9. Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).
Example 1:
1 2 3 4 5 6 7 8
Input: num = 9669 Output: 9969 Explanation: Changing the first digit results in 6669. Changing the second digit results in 9969. Changing the third digit results in 9699. Changing the fourth digit results in 9666. The maximum number is 9969.
Example 2:
1 2 3
Input: num = 9996 Output: 9999 Explanation: Changing the last digit 6 to 9 results in the maximum number.
Example 3:
1 2 3
Input: num = 9999 Output: 9999 Explanation: It is better not to apply any change.
翻转一位数(6变9)找到最大的,只要找到从头到尾第一个6就行。
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { public: intmaximum69Number(int num){ string numm = to_string(num); for(int i =0; i < numm.size(); i ++) { if(numm[i] == '6'){ numm[i] = '9'; returnstoi(numm); } } return num; } };
Leetcode1331. Rank Transform of an Array
Given an array of integers arr, replace each element with its rank. The rank represents how large the element is. The rank has the following rules:
Rank is an integer starting from 1. The larger the element, the larger the rank. If two elements are equal, their rank must be the same. Rank should be as small as possible.
Example 1:
1 2 3
Input: arr = [40,10,20,30] Output: [4,1,2,3] Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.
把一个数组中的数字用排序后这个数字的rank来替换,注意没有跨越rank的那种情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: vector<int> arrayRankTransform(vector<int>& arr){ map<int, int> mp; vector<int> rr(arr); sort(rr.begin(), rr.end()); int rank = 1; for(int i = 0; i < rr.size(); i ++) { if(mp[rr[i]] == 0) mp[rr[i]] = rank ++; } for(int i = 0; i < arr.size(); i ++) { arr[i] = mp[arr[i]]; } return arr; } };
Leetcode1332. Remove Palindromic Subsequences
Given a string s consisting only of letters ‘a’ and ‘b’. In a single step you can remove one palindromic subsequence from s.
Return the minimum number of steps to make the given string empty.
A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.
A string is called palindrome if is one that reads the same backward as well as forward.
Example 1:
1 2 3
Input: s = "ababa" Output: 1 Explanation: String is already palindrome
Example 2:
1 2 3 4
Input: s = "abb" Output: 2 Explanation: "abb" -> "bb" -> "". Remove palindromic subsequence "a" then "bb".
Example 3:
1 2 3 4
Input: s = "baabb" Output: 2 Explanation: "baabb" -> "b" -> "". Remove palindromic subsequence "baab" then "b".
Example 4:
1 2
Input: s = "" Output: 0
由于只有 a 和 b 两个字符。其实最多的消除次数就是 2。因为我们无论如何都可以先消除全部的 1 再消除全部的 2(先消除 2 也一样),这样只需要两次即可完成。 我们再看一下题目给的一次消除的情况,题目给的例子是“ababa”,我们发现其实它本身就是一个回文串,所以才可以一次全部消除。那么思路就有了:
如果 s 是回文,则我们需要一次消除;否则需要两次,一定要注意特殊情况, 对于空字符串,我们需要 0 次
Given a m * n matrix mat of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k weakest rows in the matrix ordered from the weakest to the strongest.
A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Input: mat = [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]], k = 3 Output: [2,0,3] Explanation: The number of soldiers for each row is: row 0 -> 2 row 1 -> 4 row 2 -> 1 row 3 -> 2 row 4 -> 5 Rows ordered from the weakest to the strongest are [2,0,3,1,4]
Example 2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Input: mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2 Output: [0,2] Explanation: The number of soldiers for each row is: row 0 -> 1 row 1 -> 4 row 2 -> 1 row 3 -> 1 Rows ordered from the weakest to the strongest are [0,2,3,1]
classSolution { public: vector<int> kWeakestRows(vector<vector<int>>& mat, int k){ vector<int> weak; for(int i = 0; i < mat.size(); i ++) { weak.push_back(0); int count = 0; for(int j = 0; j < mat[i].size(); j ++) { count += mat[i][j]; } weak[i] = count; } map<int, vector<int>> mp; for(int i = 0; i < mat.size(); i ++) { mp[weak[i]].push_back(i); } sort(weak.begin(), weak.end()); vector<int> res; int kk = 0; for(auto i = mp.begin(); i != mp.end() ; i ++) { for(int ii = 0; ii < (i->second).size(); ii ++) { res.push_back((i->second)[ii]); kk ++; if(kk == k) break; } if(kk == k) break; } return res; } };
Leetcode1340. Jump Game V
Given an array of integers arr and an integer d. In one step you can jump from index i to index:
i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.
In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).
You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.
Notice that you can not jump outside of the array at any time.
Example 1:
1 2 3 4 5
Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2 Output: 4 Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown. Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9. Similarly You cannot jump from index 3 to index 2 or index 1.
Example 2:
1 2 3
Input: arr = [3,3,3,3,3], d = 3 Output: 1 Explanation: You can start at any index. You always cannot jump to any index.
Example 3:
1 2 3
Input: arr = [7,6,5,4,3,2,1], d = 1 Output: 7 Explanation: Start at index 0. You can visit all the indicies.
Constraints:
1 <= arr.length <= 1000
1 <= arr[i] <= 105
1 <= d <= arr.length
给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到:
i + x ,其中 i + x < arr.length 且 0 < x <= d 。
i - x ,其中 i - x >= 0 且 0 < x <= d 。
除此以外,你从下标 i 跳到下标 j 需要满足:arr[i] > arr[j] 且 arr[i] > arr[k] ,其中下标 k 是所有 i 到 j 之间的数字(更正式的,min(i, j) < k < max(i, j))。
classSolution { public: vector<vector<int>> g; vector<int> dp; intdfs(int u){ if (dp[u] != -1) return dp[u]; dp[u] = 0; for (int v : g[u]) { int dist = dfs(v); // f[v] dp[u] = max(dp[u], dist); // 取最大的f[v] } dp[u] ++; // 这个++表示u到v的这条边 return dp[u]; } intmaxJumps(vector<int>& arr, int d){ int n = arr.size(); g.assign(n, vector<int>()); for (int i = 0; i < n; i ++) { // 在两个方向上,构图 for (int j = 1; j <= d && i - j >= 0 && arr[i-j] < arr[i]; j ++) // 最远不能超过d,高度小过a[i],不能跑出去边界 g[i].push_back(i - j); for (int j = 1; j <= d && i + j < n && arr[i+j] < arr[i]; j ++) // 最远不能超过d,高度小过a[i],不能跑出去边界 g[i].push_back(i + j); } dp.assign(n, -1); // 从一个点出发能走的最长路径 for (int i = 0; i < n; i ++) dfs(i);
int res = -1; for (int i = 0; i < n; i ++) res = max(res, dp[i]); return res; } };
Leetcode1346. Check If N and Its Double Exist
Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).
More formally check if there exists two indices i and j such that :
i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]
Example 1:
1 2 3
Input: arr = [10,2,5,3] Output: true Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.
Example 2:
1 2 3
Input: arr = [7,1,14,11] Output: true Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.
Example 3:
1 2 3
Input: arr = [3,1,7,11] Output: false Explanation: In this case does not exist N and M, such that N = 2 * M.
注意0的问题,只有有两个0的时候返回true
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { public: boolcheckIfExist(vector<int>& arr){ map<int, int> mp; for(int i = 0; i < arr.size(); i ++) mp[arr[i]] ++; for(int i = 0; i < arr.size(); i ++) { if(mp[arr[i]*2] && arr[i] != 0 || arr[i] == 0 && mp[arr[i]] > 1 ) returntrue; } returnfalse; } };
Leetcode1349. Maximum Students Taking Exam
Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by ‘#’ character otherwise it is denoted by a ‘.’ character.
Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible..
Students must be placed in seats in good condition.
Example 1:
1 2 3 4 5
Input: seats = [["#",".","#","#",".","#"], [".","#","#","#","#","."], ["#",".","#","#",".","#"]] Output: 4 Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.
Example 2:
1 2 3 4 5 6 7
Input: seats = [[".","#"], ["#","#"], ["#","."], ["#","#"], [".","#"]] Output: 3 Explanation: Place all students in available seats.
Example 3:
1 2 3 4 5 6 7
Input: seats = [["#",".",".",".","#"], [".","#",".","#","."], [".",".","#",".","."], [".","#",".","#","."], ["#",".",".",".","#"]] Output: 10 Explanation: Place students in available seats in column 1, 3 and 5.
classSolution { public: boolcheck2(int s, int ss, int m){ for (int k = 0; k < m; k ++) { int b = (s >> k) & 1; if (!b) continue; int bss0 = 0, bss2 = 0; if (k) bss0 = (ss >> (k-1)) & 1; if (k != m-1) bss2 = (ss >> (k+1)) & 1; if (bss0 || bss2) returnfalse; } returntrue; } boolcheck(int s, const vector<char>& line, int m){ int preb = 0; for (int k = 0; k < m; k ++) { int b = (s >> k) & 1; if (b && line[k] == '#') returnfalse; if (preb && b) returnfalse; preb = b; } returntrue; } intmaxStudents(vector<vector<char>>& seats){ int n = seats.size(), m = seats[0].size(); int maxseats = 1 << m; vector<int> y(maxseats, 0); vector<int> x(maxseats, 0); vector<bool> oky(maxseats, true); vector<bool> okx(maxseats, true); for (int i = 0; i < n; i ++) { x.assign(maxseats, 0); okx.assign(maxseats, false); for (int s = 0; s < maxseats; s ++) { okx[s] = check(s, seats[i], m); if (!okx[s]) continue; int cnt = 0; for (int k = 0; k < m; k ++) cnt += ( s >> k) & 1; for (int ss = 0; ss < maxseats; ss ++) if (oky[ss]) { if (!check2(s, ss, m)) continue; x[s] = max(x[s], y[ss] + cnt); } } swap(x, y); swap(okx, oky); } int maxv = 0; for (int v : y) maxv = max(maxv, v); return maxv; } };
Leetcode1351. Count Negative Numbers in a Sorted Matrix
Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise. Return the number of negative numbers in grid.
Example 1:
1 2 3
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix.
统计一个矩阵中有多少个负数?有毛病,这么简单。
1 2 3 4 5 6 7 8 9 10 11
classSolution { public: intcountNegatives(vector<vector<int>>& grid){ int res = 0; for(int i = 0; i < grid.size(); i ++) for(int j = 0; j < grid[0].size(); j ++) if(grid[i][j] < 0) res ++; return res; } };
Leetcode1356. Sort Integers by The Number of 1 Bits
Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.
Return the sorted array.
Example 1:
1 2 3 4 5 6 7
Input: arr = [0,1,2,3,4,5,6,7,8] Output: [0,1,2,4,8,3,5,6,7] Explantion: [0] is the only integer with 0 bits. [1,2,4,8] all have 1 bit. [3,5,6] have 2 bits. [7] has 3 bits. The sorted array by bits is [0,1,2,4,8,3,5,6,7]
Example 2:
1 2 3
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1] Output: [1,2,4,8,16,32,64,128,256,512,1024] Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.
classSolution { public: staticintbitnum(int a){ int res = 0; while(a) { res += a & 1; a = a >> 1; } return res; } staticboolcmp(int a, int b){ if(bitnum(a) < bitnum(b)) returntrue; elseif(bitnum(a) == bitnum(b)) return a < b; else returnfalse; } vector<int> sortByBits(vector<int>& arr){ sort(arr.begin(), arr.end(), cmp); return arr; } };
Leetcode1360. Number of Days Between Two Dates
Write a program to count the number of days between two dates. The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.
Leetcode1365. How Many Numbers Are Smaller Than the Current Number
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j’s such that j != i and nums[j] < nums[i].
Return the answer in an array.
Example 1:
1 2 3 4 5 6 7 8
Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 there exist one smaller number than it (1). For nums[3]=2 there exist one smaller number than it (1). For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
classSolution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums){ vector<int> res; map<int, int> mp; for(int i = 0; i < nums.size(); i ++) { mp[nums[i]] ++; } int presum = 0; for(auto a = mp.begin(); a != mp.end(); a ++) { int sec = a->second; mp[a->first] = presum; presum = presum + sec; } for(int i = 0; i < nums.size(); i ++){ res.push_back(mp[nums[i]]); } return res; } };
Leetcode1370. Increasing Decreasing String
Given a string s. You should re-order the string using the following algorithm:
Pick the smallest character from s and append it to the result.
Pick the smallest character from s which is greater than the last appended character to the result and append it.
Repeat step 2 until you cannot pick more characters.
Pick the largest character from s and append it to the result.
Pick the largest character from s which is smaller than the last appended character to the result and append it.
Repeat step 5 until you cannot pick more characters.
Repeat the steps from 1 to 6 until you pick all characters from s.
In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.
Return the result string after sorting s with this algorithm.
Example 1:
1 2 3 4 5 6 7
Input: s = "aaaabbbbcccc" Output: "abccbaabccba" Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc" After steps 4, 5 and 6 of the first iteration, result = "abccba" First iteration is done. Now s = "aabbcc" and we go back to step 1 After steps 1, 2 and 3 of the second iteration, result = "abccbaabc" After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"
classSolution { public: string sortString(string s){ string res; vector<int> ma(26, 0); int i = 0, len = s.length(); for(int i = 0; i < len; i ++) ma[s[i] - 'a'] ++; int count = 0; while(count < len) { for(int i = 0; i < 26; i ++) if(ma[i]) { res += ('a' + i); ma[i] --; count ++; } for(int i = 25; i >= 0; i --) if(ma[i]) { res += ('a' + i); ma[i] --; count ++; } } return res; } };
Leetcode1374. Generate a String With Characters That Have Odd Counts
Given an integer n, return a string with n characters such that each character in such string occurs an odd number of times. The returned string must contain only lowercase English letters. If there are multiples valid strings, return any of them.
Example 1:
1 2 3
Input: n = 4 Output: "pppz" Explanation: "pppz" is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as "ohhh" and "love".
Example 2:
1 2 3
Input: n = 2 Output: "xy" Explanation: "xy" is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as "ag" and "ur".
返回一个字符串,每个字母都只出现过奇数次。神经病题,要处理奇数和偶数的不同情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: string generateTheString(int n){ string res; if(n % 2 == 0) { for(int i = 0; i < n-1; i ++) res += 'a'; res += 'b'; } if(n % 2 == 1) { for(int i = 0; i < n; i ++) res += 'a'; } return res; } };
Leetcode1380. Lucky Numbers in a Matrix
Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order. A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.
Example 1:
1 2 3
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column
Example 2:
1 2 3
Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]] Output: [12] Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.
classSolution { public: vector<int> luckyNumbers(vector<vector<int>>& matrix){ vector<int> res; int row = matrix.size(), col = matrix[0].size(); for(int i = 0; i < row; i ++) { int j = 0, minn = 999999, minn_j = -1; for(; j < col; j ++) { if(minn > matrix[i][j]) { minn = matrix[i][j]; minn_j = j; } } int ii; for(ii = 0; ii < row; ii ++) if(matrix[ii][minn_j] > minn) break; if(ii == row) res.push_back(minn); } return res; } };
Leetcode1385. Find the Distance Value Between Two Arrays
Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays. The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2 Output: 2 Explanation: For arr1[0]=4 we have: |4-10|=6 > d=2 |4-9|=5 > d=2 |4-1|=3 > d=2 |4-8|=4 > d=2 For arr1[1]=5 we have: |5-10|=5 > d=2 |5-9|=4 > d=2 |5-1|=4 > d=2 |5-8|=3 > d=2 For arr1[2]=8 we have: |8-10|=2 <= d=2 |8-9|=1 <= d=2 |8-1|=7 > d=2 |8-8|=0 <= d=2
计算一行中没有差的绝对值大于d的行数。「距离值」 定义为符合此描述的元素数目:对于元素 arr1[i] ,不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intfindTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d){ int res = 0; for(int i = 0; i < arr1.size(); i ++) { int j; for(j = 0; j < arr2.size(); j ++) { if(abs(arr1[i] - arr2[j]) <= d) break; } if(j == arr2.size()) res ++; } return res; } };
Leetcode1389. Create Target Array in the Given Order
Given two arrays of integers nums and index. Your task is to create target array under the following rules:
Initially target array is empty.
From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
Repeat the previous step until there are no elements to read in nums and index.
Return the target array.
It is guaranteed that the insertion operations will be valid.
voidmove(vector<int>& nums, int i){ int ii; for(ii = i + 1; ii < nums.size() && nums[ii] != -1; ii ++); for(int k = ii; k > i; k --) { nums[k] = nums[k-1]; } } vector<int> createTargetArray(vector<int>& nums, vector<int>& index){ vector<int> res(nums.size(), -1); for(int i = 0; i < nums.size(); i ++) { if(res[index[i]] == -1) res[index[i]] = nums[i]; else { move(res, index[i]); res[index[i]] = nums[i]; } } return res; } };
Leetcode1394. Find Lucky Integer in an Array
Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value. Return a lucky integer in the array. If there are multiple lucky integers return the largest of them. If there is no lucky integer return -1.
Example 1:
1 2 3
Input: arr = [2,2,3,4] Output: 2 Explanation: The only lucky number in the array is 2 because frequency[2] == 2.
Example 2:
1 2 3
Input: arr = [1,2,2,3,3,3] Output: 3 Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.
classSolution { public: intfindLucky(vector<int>& arr){ sort(arr.begin(), arr.end()); int prev = arr[0], count = 1, res = -1; for(int i = 1; i < arr.size(); i ++) { if(prev != arr[i]) { if(count == prev) res = prev; prev = arr[i]; count = 1; } else { count ++; } } if(count == prev) res = prev; return res; } };
Leetcode1399. Count Largest Group
Given an integer n. Each number from 1 to n is grouped according to the sum of its digits. Return how many groups have the largest size.
Example 1:
1 2 3 4
Input: n = 13 Output: 4 Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13: [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.
CPU访问内存是用段地址+偏移地址来实现的,由于在实模式之下,段地址需要乘以16后才能与偏移地址相加,求出的和便是物理地址,CPU便拿此地址直接用了。在接电的一瞬间,CPU的cs:ip寄存器被强制初始化为0xF000:0xFFF0。由于开机的时候处于实模式,在实模式下的段基址要乘以16,也就是左移4位,于是0xF000:0xFFF0的等效地址将是0xFFFF0,此地址便是BIOS的入口地址。物理地址0xFFFF0处应该是指令,否则会出错,里面有条指令jmp far f000:e05b,这是条跳转指令,也就是证明了在内存物理地址0xFFFF0处的内容是一条跳转指令。
8086CPU要求物理地址0x0~0x3FF存放中断向量表,所以此处不能动了;按 DOS 1.0 要求的最小内存32KB来说,MBR希望给人家尽可能多的预留空间,所以MBR只能放在32KB的末尾;MBR本身也是程序,是程序就要用到栈,估计1KB内存够用了。结合以上三点,选择32KB中的最后1KB最为合适,32KB换算为十六进制为0x8000,减去1KB(0x400)的话,等于0x7c00。这就是倍受质疑的0x7c00 的由来。
第58行的$$是指本section的起始地址,上面说过了$是本行所在的地址,故$-$$是本行到本section的偏移量。由于MBR的最后两个字节是固定的内容,分别是0x55和0xaa,要预留出这2个字节,故本扇区内前512-2=510字节要填满,第50行的times 510-($-$$) db 0是在用0将本扇区剩余空间填充。
对于受访者为数据段(段描述符中 type 字段中未有X 可执行属性)来说:只有访问者的权限大于等于该DPL 表示的最低权限才能够继续访问,否则连这个门槛都迈不过去。对于受访者为代码段(段描述符中 type 字段中含有X 可执行属性)来说:只有访问者的权限等于该DPL 表示的最低权限才能够继续访问,CPU 没有理由先自降等级后再去做某事。
操作系统为每个进程提供了一个PCB,Process Control Block,即程序控制块,用它来记录与此进程相关的信息,比如进程状态、PID、优先级等。每个进程都有自己的PCB,所有PCB 放到一张表格中维护,这就是进程表,PCB 又可称为进程表项。“寄存器映像”用来保存进程的“现场”,进程在处理器上运行时,所有寄存器的值都将保存到此处。
汇编代码在输出部分,"g" (thread->self_kstack)使thread->self_kstack的值作为输入,采用通用约束g,即内存或寄存器都可以。在汇编语句部分, movl %0, %%esp,也就是使thread->self_kstack的值作为栈顶,此时thread->self_kstack指向线程栈的最低处,这是我们在函数thread_create中设定的。接下来的这连续4 个弹栈操作:pop %%ebp; pop %%ebx; pop %%edi; pop %%esi使之前初始化的0 弹入到相应寄存器中。
Linux 提供了称为文件结构的数据结构,专门用于记录与文件操作相关的信息,每次打开一个文件就会产生一个文件结构,多次打开该文件就为该文件生成多个文件结构,各自文件操作的偏移量分别记录在不同的文件结构中,从而实现了即使同一个文件被同时多次打开,各自操作的偏移量也互不影响的灵活性。Linux 把所有的“文件结构”组织到一起形成数组统一管理,该数组称为文件表。
/* init 进程 */ voidinit(void){ uint32_t ret_pid = fork(); if(ret_pid) { printf("i am father, my pid is %d, child pid is %d\n", getpid(), ret_pid); } else { printf("i am child, my pid is %d, ret pid is %d\n", getpid(), ret_pid); } while(1); }
为了解决这一问题,Raft提出了两阶段的成员变更方法。集群先从旧成员配置Cold切换到一个过渡成员配置,称为共同一致(joint consensus),共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew,一旦共同一致Cold U Cnew被提交,系统再切换到新成员配置Cnew。
完美的静态分析满足sound和complete的。Sound > Truth > Complete,Truth是说所有可能的行为,Sound说的是包含Truth且有其他的,Complete只有Truth中所有可能行为的一部分,Complete中爆出来的一定是Truth中的,而Sound中爆出来的不一定是Truth中的。
transfer function:正常的分析是按照程序执行的顺序分析。语句s对应的transfer function用fs来表示,则OUT[s] = fs(IN[s]),这句话是说,输入是执行s之前的value=IN[s],转化为s执行完之后状态OUT[s]。另一种是反向分析,逆向程序执行的顺序,则IN[s] = fs(OUT[s])。
控制流的约束(control flow’s constraints):一共是n条语句,在一个代码块中的控制流,IN[s(s+1)] = OUT[s(i)], for all i = 1, 2, ..., n-1,每一个语句的IN都是上一个语句的OUT。代码块的关系:IN[B]=IN[s1] OUT[B]=OUT[sn]。
一个基本块的transfer function,是其中所有语句的transfer function,即OUT[B]=fb(IN[B]), fb=fsn*...*fs2*fs1,IN[B]=∩ (P: a predecessor of B) OUT[P]
D: v = x op y这个语句生成v的一个definition,然后‘kills’其他所有对v的定义,但是保留了对其他变量的定义。transfer function为OUT[B]=(gen B)∪(IN[B]-kill(B)),去掉其他所有定义这个变量的语句。
control flow:IN[B]=∪ (P: a predecessor of B) OUT[P],就是B所有的前驱P的OUT的并,一条结果都不放过,都考虑成B的IN。
定义可达性分析算法:
1 2 3 4 5 6 7 8 9 10 11
INPUT: CFG(kill(B) and gen(B) computed for each basic block B) OUTPUT: IN[B] and OUT[B] for each basic block B METHOD: OUT[entry] = Φ for (each basic block B\entry) OUT[B] = Φ while(changes to any OUT occur) for(each basic block B\entry) { IN[B] = ∪ (P: a predecessor of B) OUT[P] OUT[B] = gen(B) ∪ (IN[B] - kill(B)) }
INPUT: CFG(def(B) and use(B) computed for each basic block B) OUTPUT: IN[B] and OUT[B] for each basic block B METHOD: IN[exit] = Φ for (each basic block B\entry) IN[B] = Φ while(changes to any IN occur) for(each basic block B\exit) { OUT[B] = ∪ (P: a successor of B) IN[P] IN[B] = use(B) ∪ (OUT[B] - def(B)) }
对一个程序进行分析,跟上边的分析类似,只是是从下向上的分析。
Available Expressions Analysis可用表达式分析
一个表达式x op y,如果所有路径从入口到p都一定要计算表达式x op y,且在计算x op y之后没有x和y的重定义,则称表达式x op y在点p是活的。
这个定义也说明了在程序p中,可以用x op y的结果替换掉这个表达式。
这个可以用于检测全局的通用表达式
抽象:表达式可以用bit vector来表示。
对于a = x op y,使用forward分析方法,它的IN={a+b},它的OUT中应该加上x op y,因为x op y是刚执行的,被看成是gen;然后从IN中删掉所有涉及a的语句,这被看成是kill。所以,OUT[B]=gen(B)∪(IN[B]-kill(B)),IN[B]=∩(P a predecessor of B)OUT[P]。这里使用了交集,因为所有从入口到p点的路径都需要通过x op y这个函数。
INPUT: CFG(kill(B) and gen(B) computed for each basic block B) OUTPUT: IN[B] and OUT[B] for each basic block B METHOD: OUT[entry] = Φ for (each basic block B\entry) OUT[B] = Φ while(changes to any OUT occur) for(each basic block B\entry) { IN[B] = ∩ (P: a predecessor of B) OUT[P] OUT[B] = gen(B) ∪ (IN[B] - kill(B)) }
May Analyses是一个bottom,代表一个不安全的结果,算是一个下界;另外有一个上界,是安全但是不完全/没用的结果。这里中间有一个Truth,将safe和unsafe隔开。如何知道分析一定是safe的?这是由单调性决定的。May Analyses从底部一直向上走,我们向上走先接触到的是最小不动点。从最底部走到最顶部,是从精度最高走到精度最低的。所以May Analyses一般都首先初始化为空。
MOP就是枚举从Entry到Si所有的Path,然后把三条路径的FP结果join/meet起来,公式是:MOP[Si] = ⊔/⊓ FP(OUT[Entry]), A path P from Entry to Si,所有path应用transfer function之后进行meet/join,找到确界。有一些path是不可能走到的,所以这是不精确的。
INPUT: CFG(kill(B) and gen(B) computed for each basic block B) OUTPUT: IN[B] and OUT[B] for each basic block B METHOD: OUT[entry] = Φ for (each basic block B\entry) OUT[B] = Φ Worklist <- all basic blocks while(worklist is not empty) Pick a basic block B from Worklist old_OUT = OUT[B] IN[B] = ∪ (P: a predecessor of B) OUT[P] OUT[B] = gen(B) ∪ (IN[B] - kill(B)) if (old_OUT ≠ OUT[B]) Add all successors of B to Worklist
void foo() { Number n = new One(); int x = n.get(); }
interface Number { int get(); } class Zero implements Number { public int get() {return 0;} } class One implements Number { public int get() {return 1;} } class Two implements Number { public int get() {return 2;} }
class A { static void main() { A a = new A(); A b = new B(); A c = b.foo(a); } A foo(A x) { ... } } class B extends A { A foo(A y) { A r = new A(); return r; } }
一开始的时候WL为空,RM为空,CG为空。首先调用AddReachable函数把入口函数加入到可达图中,此时RM为{A.main()},在AddReachable仍需把main函数中的x = new T()形式的语句加入到WL中,WL中变为[<a, {o3}>, <b, {o4}>],再根据上边的指针分析算法进行分析。
struct redisServer { //上一次进行抽样的时间 long long ops_sec_last_sample_time; //上一次抽样时,服务器已执行命令的数量 long long ops_sec_last_sample_ops; // REDIS_OPS_SEC_SAMPLES 大小(默认值为16 )的环形数组, //数组中的每个项都记录了一次抽样结果。 long long ops_sec_samples[REDIS_OPS_SEC_SAMPLES]; // ops_sec_samples 数组的索引值, //每次抽样后将值自增一, //在值等于16 时重置为0 , //让ops_sec_samples 数组构成一个环形数组。 int ops_sec_idx; // ... };
在发送SLAVEOF no one命令之后,领头Sentinel会以每秒一次的频率(平时是每十秒一次),向被升级的从服务器发送INFO命令,并观察命令回复中的角色(role)信息,当被升级服务器的role从原来的slave变为master时,领头Sentinel就知道被选中的从服务器已经顺利升级为主服务器了。 例如,在上图所展示的例子中,领头Sentinel会一直向server2发送INFO命令,当server2返回的命令回复从:
1 2 3 4 5
# Replication role:slave ... # Other sections ...
变为:
1 2 3 4 5
# Replication role:master ... # Other sections ...
def CLUSTER_ADDSLOTS(*all_input_slots): # 遍历所有输入槽,检查它们是否都是未指派槽 for i in all_input_slots: # 如果有哪怕一个槽已经被指派给了某个节点 # 那么向客户端返回错误,并终止命令执行 if clusterState.slots[i] != NULL: reply_error() return
# 如果所有输入槽都是未指派槽 # 那么再次遍历所有输入槽,将这些槽指派给当前节点 for i in all_input_slots: # 设置clusterState 结构的slots 数组 # 将slots[i]的指针指向代表当前节点的clusterNode 结构 clusterState.slots[i] = clusterState.myself
classSolution: # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0] # 函数返回True/False defduplicate(self, numbers, duplication): ifnot numbers: returnFalse for _, v inenumerate(numbers): if v >= len(numbers) or v < 0: returnFalse for i inrange(len(numbers)): while numbers[i] != i: if numbers[i] == numbers[numbers[i]]: duplication[0] = numbers[i] returnTrue else: idx = numbers[i] numbers[i], numbers[idx] = numbers[idx], numbers[i] returnFalse
使用 O(1) 空间的解法: 但条件一定要明确,存在重复数字。思维类似于寻找链表环的入口。
1 2 3 4 5 6 7 8 9 10 11
classSolution: defduplicateInArray(self, nums): f = s = 0 while f == 0or f != s: f = nums[nums[f]] s = nums[s] f = 0 while f != s: f = nums[f] s = nums[s] return s
classSolution(object): defhasPath(self, matrix, string): ifnot matrix ornot matrix[0] ornot string: returnFalse m, n = len(matrix), len(matrix[0]) state = [[True] * n for _ inrange(m)]
defdfs(i, j, pos): if0 <= i < m and0 <= j < n and state[i][j]: state[i][j] = ret = False if matrix[i][j] == string[pos]: if pos == len(string) - 1: returnTrue ret = dfs(i, j-1, pos+1) or dfs(i, j+1, pos+1) or dfs(i-1, j, pos+1) or dfs(i+1, j, pos+1) ifnot ret: state[i][j] = True return ret
for i inrange(m): for j inrange(n): if matrix[i][j] == string[0]: if dfs(i, j, 0): returnTrue returnFalse
实现函数double Power(double base, int exponent),求base的 exponent次方。不得使用库函数,同时不需要考虑大数问题。
解法:
1 2 3 4 5 6 7 8 9 10
classSolution: # 简单快速幂解法 defPower(self, base, exponent): exp = abs(exponent) r = 1 while exp: if exp & 1: r *= base base *= base exp >>= 1 return r if exponent >= 0else1/r
classSolution(object): defisMatch(self, s, p): dp = [[False] * (len(p)+1) for _ inrange(len(s)+1)] dp[0][0] = True for j inrange(1, len(p)+1): if p[j-1] == '*': dp[0][j] = dp[0][j-2] for i inrange(1, len(s)+1): for j inrange(1, len(p)+1): if p[j-1] != '*': dp[i][j] = dp[i-1][j-1] and p[j-1] in (s[i-1], '.') else: dp[i][j] = dp[i][j-2] or dp[i-1][j] and p[j-2] in (s[i-1], '.') return dp[-1][-1]
for c in s: if c.isdigit(): isFirst = False continue if c notin validList: returnFalse if c == 'e'or c == 'E': if isFirst: returnFalse isFirst = True validList = set(['+', '-']) if c == '.': validList = set(['e', 'E']) if c == '+'or c == '-': ifnot isFirst: returnFalse validList.remove('+') validList.remove('-')
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None
classSolution: deffindKthToTail(self, head, k): ifnot head or k <= 0: returnNone fast = slow = head for _ inrange(k): # 快慢指针来走,之所以先判断是为了防止 k 等于链表长度的情况。 ifnot fast: returnNone fast = fast.next while fast: fast, slow = fast.next, slow.next return slow
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None classSolution: defEntryNodeOfLoop(self, pHead): pre = post = pHead while pre and pre.next: # 确保快指针有意义没有到头 post = post.next# 慢指针走一步 pre = pre.next.next# 快指针走两步 if pre == post: # 相遇的时候即是有环 post = pHead # 慢指针再从头走 while pre != post: # 两个指针都是每次一步直到相遇 pre = pre.next post = post.next return post # 相遇的地方即是环的入口 returnNone
classSolution: defisPopOrder(self, pushV, popV): iflen(pushV) != len(popV): returnFalse stack, i = [], 0# 用 stack 来模拟进出栈。 for v in pushV: stack.append(v) while stack and stack[-1] == popV[i]: stack.pop() i += 1 returnnot stack
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None classSolution: # 返回从上到下每个节点值列表,例:[1,2,3] defPrintFromTopToBottom(self, root): res = [] if root: level = [root] while level: res.extend([x.val for x in level]) level = [leaf for node in level for leaf in (node.left, node.right) if leaf] return res
classSolution: defpermutation(self, nums): perms = [[]] for n in nums: perms = [ p[:i] + [n] + p[i:] for p in perms for i inrange((p+[n]).index(n)+1)] return perms
classSolution: defFindGreatestSumOfSubArray(self, array): best = cur = array[0] for i inrange(1, len(array)): cur = max(array[i], array[i] + cur) best = max(best, cur) return best
classSolution: defnumberOf1Between1AndN_Solution(self, n): count, i = 0, 1 while i <= n: a, b = n // i, n % i count += (a+8) // 10 * i + (a%10 == 1) * (b+1) i *= 10 return count
classSolution(object): # 快速跳过不用检查的位数,确定区间。 defdigitAtIndex(self, n): n -= 1 for digit inrange(1, 11): first = 10 ** (digit - 1) if n < 9 * first * digit: returnint(str(first + n // digit)[n % digit]) n -= 9 * first * digit
classSolution: defgetTranslationCount(self, s): ifnot s: return0 l = r = 1 for i inrange(len(s)-2, -1, -1): if s[i] == '1'or s[i] == '2'and s[i+1] < '6': l, r = l + r, l else: r = l return l
classSolution: deflengthOfLongestSubstring(self, s): start = maxLength = 0 used = {} for i, c inenumerate(s): if c in used and start <= used[c]: start = used[c] + 1 else: maxLength = max(maxLength, i - start + 1) used[c] = i return maxLength
classSolution: # 面试用装x解法 deffindNumberAppearingOnce(self, nums): a = b = 0 for n in nums: a = (a ^ n) & ~b b = (b ^ n) & ~a return a
1 2 3 4 5 6 7 8 9 10 11
classSolution: # 常规解法 deffindNumberAppearingOnce(self, nums): ans = 0 for i inrange(32): cnt = 0 for n in nums: if (n >> i) & 1: cnt += 1 if cnt % 3: ans |= 1 << i return ans if ans < 2**31else ans - 2**32
classSolution: defmaxSlidingWindow(self, nums: List[int], k: int) -> List[int]: dq = collections.deque() # 使用双向队列解决本题 res = [] for i, v inenumerate(nums): while dq and nums[dq[-1]] < v: # dq中如果存在多个元素 dq.pop() # 一定是降序排列的 dq += i, if dq[0] == i - k: # 判断dq中第一位是否有效 dq.popleft() if i >= k - 1: # 满足滑动窗口长度才有输出 res += nums[dq[0]], return res