Leetcode题解 剑指 Offer 60. n个骰子的点数
PROBLEM剑指 Offer 60. n个骰子的点数
难度 中等
MY ANSWER动态规划，res[i][j]代表用 i 个骰子掷出 j 值。时间复杂度为O(n^2)，空间复杂度O(n^2)。
递推方程为：res[i][j] = (res[i-1][j-1] + ... + res[i-1][j-6]) / 6
class Solution {public: vector<double> dicesProbability(int n) { vector<vector<double>> res(n + 1, vector<double> (n * 6 + 1, 0)); for(int i = 1; i <= 6; i++) { res[1][i] = 1.0 / 6.0; } for(int i = 2; i <= n; i++) { for(int j = i; j ...
Leetcode题解 剑指 Offer 59 - I. 滑动窗口的最大值
PROBLEM剑指 Offer 59 - I. 滑动窗口的最大值
难度 困难
MY ANSWER使用优先队列维护滑动窗口，存储值和索引，时间复杂度O(nlogn)，空间复杂度O(n)。
BETTER SOLUTION使用deque构造单调栈维护滑动窗口，保存了从最大值开始的递减序列。时间复杂度O(n)，空间复杂度O(k)。
每次滑动，出窗元素若是最大值，则单调栈栈底出栈。然后检查栈顶是否大于入窗元素，若小于则出栈，以此来维护单调栈的单调性。最后将入窗元素入栈，栈底作为当前窗口的最大值加入到结果中。
class Solution {public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> tmp; vector<int> res; if(nums.empty()) { return res; } tmp. ...
Leetcode题解 剑指 Offer 58 - I. 翻转单词顺序
PROBLEM剑指 Offer 58 - I. 翻转单词顺序
难度 简单
MY ANSWER使用栈读入单词，时间空间复杂度O(n)。还可使用双指针，从尾向前遍历，思路相似。
class Solution {public: string reverseWords(string s) { stack<string> voc; int start = 0, len = 1, flag = 0; cout<<isgraph(' ')<<endl; for(int i = 0; i < s.size(); i++) { if(!flag && isgraph(s[i])) { start = i; len = 1; flag = 1; } else if( ...
Leetcode题解 剑指 Offer 56 - II. 数组中数字出现的次数 II
PROBLEM剑指 Offer 56 - II. 数组中数字出现的次数 II
难度 中等
MY ANSWER哈希表存储出现次数，时间空间复杂度为O(n)。
BETTER SOLUTION基本思想：
可以使用基础做法来实现，数组统计二进制位的1的个数。时间复杂度O(n)，空间复杂度O(1)。自动机做法复杂度相同，但计算次数更少。
有限状态自动机
根据状态转移图得出布尔运算式：
以上是对数字的二进制中 “一位” 的分析，而 int 类型的其他 31 位具有相同的运算规则，因此可将以上公式直接套用在 32 位数上。
遍历完所有数字后，各二进制位都处于状态 00 和状态 01 （取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ），而此两状态是由 one 来记录的（此两状态下 two 恒为 0 ），因此返回 one 即可。
class Solution {public: int singleNumber(vector<int>& nums) { int ones = 0, twos = 0; for(in ...
Leetcode题解 剑指 Offer 56 - I. 数组中数字出现的次数
PROBLEM剑指 Offer 56 - I. 数组中数字出现的次数
难度 中等
MY ANSWER无。
BETTER SOLUTION先遍历使用异或计算出独立数字a^b，然后找出a^b中一个为1的位，即a和b不相同的一位。用此位将数组分成含a的一组与含b的一组，可知这两组的其他数字都是若干对重复数字。对这两组进行异或，即可得出a与b。时间复杂度O(n)，空间复杂度O(1)。
class Solution {public: vector<int> singleNumbers(vector<int>& nums) { int x = 0, y = 0, n = 0, m = 1; for(int num : nums) // 1. 遍历异或 n ^= num; while((n & m) == 0) // 2. 循环左移，计算 m m <<= 1; for(int num : n ...
Leetcode题解 剑指 Offer 55 - II. 平衡二叉树
PROBLEM剑指 Offer 55 - II. 平衡二叉树
难度 简单
MY ANSWER遍历每个节点获得深度，判断是否平衡。时间复杂度O(nlogn)，空间复杂度O(n)。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int depth(TreeNode* root) { if(!root) { return 0; } else { return max(depth(root->left), depth(root->ri ...
Leetcode题解 剑指 Offer 53 - I. 在排序数组中查找数字 I
PROBLEM剑指 Offer 53 - I. 在排序数组中查找数字 I
剑指 Offer 53 - II. 0～n-1中缺失的数字
难度 简单
MY ANSWER二分，时间复杂度O(logn)，空间复杂度O(1)。
BETTER SOLUTION贴一下简洁代码。
调用两次二分查找第一个比target大的索引，最后一个比target小的索引。
class Solution {public: int search(vector<int>& nums, int target) { // 搜索右边界 right int i = 0, j = nums.size() - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] <= target) i = m + 1; else j = m - 1; } int right = i; ...
Leetcode题解 剑指 Offer 52. 两个链表的第一个公共节点
PROBLEM剑指 Offer 52. 两个链表的第一个公共节点
难度 简单
MY ANSWER先遍历一遍得到链表的长度，然后长的先走差值，再一起走比较节点地址是否相等。时间复杂度O(m+n)，空间复杂度O(1)。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int alen = 0, blen = 0; ListNode* tmp = headA; while(tmp) { tmp = tmp->next; ...
Leetcode题解 剑指 Offer 51. 数组中的逆序对
PROBLEM剑指 Offer 51. 数组中的逆序对
难度 困难
MY ANSWER无，以为有O(n)解法。
BETTER SOLUTION归并排序的同时进行逆序对的计算，时间复杂度O(nlogn)，空间复杂度O(n)。
class Solution {public: int reversePairs(vector<int>& nums) { vector<int> tmp(nums.size()); return mergeSort(0, nums.size() - 1, nums, tmp); }private: int mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp) { // 终止条件 if (l >= r) return 0; // 递归划分 int m = (l + r) / 2; ...
Leetcode题解 剑指 Offer 49. 丑数
PROBLEM剑指 Offer 49. 丑数
难度 中等
MY ANSWER逐个数检验，TLE。
BETTER SOLUTION动态规划，根据前面的数生成下一个丑数。时间复杂度O(n)，空间复杂度O(n)。
class Solution {public: int nthUglyNumber(int n) { int a = 0, b = 0, c = 0; int dp[n]; dp[0] = 1; for(int i = 1; i < n; i++) { int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5; dp[i] = min(min(n2, n3), n5); if(dp[i] == n2) a++; if(dp[i] == n3) b++; if(dp[i] == n5) c++; } ...