1.滑动窗口的最大值（剑指offer原59题）
- 解题思路：其实是一个队列的问题，用一个队列去维护当前窗口中的所有元素；首先将超出窗口中的队头元素先删掉，然后将新的元素插入当前窗口中，插入时要判断新插入的元素与队尾元素的大小，如果队尾元素较小，则先删除队尾元素再插入。
#include <iostream> #include <vector> #include <deque> using namespace std; class Solution{ public: vector<int> maxInWindows(vector<int>& nums, int k) // k是窗口的大小 { vector<int> res; deque<int> q; for(int i = 0; i < nums.size(); i++) { while(q.size() && q.front() <= i - k) q.pop_front(); // 将已经划出窗口中的元素从队列中删除 while(q.size() && nums[q.back()] <= nums[i]) nums.pop_back(); // 如果在队尾插入的元素大于等于当前队尾的元素值，就可以删除队尾的元素！ q.push_back(i); if(i >= k - 1) res.push_back(nums[q.front()]); } return res; } };
2.n个骰子的点数，这里求的是扔n次骰子，n次中骰子点数之和是s的，所有方案可能的数！(与剑指offer60题有点差别！)
- 解题思路：每次扔骰子，最小值是1，最大值是6；所以扔n个骰子在地上后的，最小值就是n，最大值就是6*n。dfs()算法的思路：
#include <iostream> #include <vector> using namespace std; // dfs方法来解决：注意两点，第一是状态的表示是什么(从输出中来)？第二是按照什么顺序来计算第一步中的状态？ class Solution{ public: vector<int> numberOfDice(int n){ vector<int> res; for(int i = n; i <= 6 * n; i++) res.push_back(dfs(n, i)); // dfs(n, s)表示的就是所要输出的结果；也就是每次求总和是s的情况下，一共投了n次骰子，一共有多少种方案 return res; } int dfs(int n, int sum){ if(sum < 0) return 0; if(n == 0) return !sum; for(int i = 1; i <= 6; i++) { res += dfs(n - 1, sum - i); // 热狗法：最后一次骰子点数已经确定时，则只需要计算前面投了n-1次骰子，总和是s-i的情况下，一共有多少种方案。 } return res; } };
- 动态规划算法dp的思路：
#include <iostream> #include <vector> using namespace std; // dp方法来解决：注意三点，第一是状态的表示是什么(从输出中来)？第二是如何计算第一步中的状态？第三是边界问题 class Solution{ public: vector<int> numberOfDice(int n){ vector<vector<int>> f(n + 1, vector<int>(n * 6 + 1)); // dp的状态表示 f[0][0] = 1; // 当所有的骰子都没有扔出时，总和s=0时，只有一种方案；总和s=1, 2, 3, 4, ....都是不合法的！ for(int i = 1; i <= n; i++){ // 先循环扔出去的次数 for(int j = 1; j <= i * 6; j++){ // 再循环总和s是多少 for(int k = 1; k <= min(j, 6); k++){ // 枚举最后一次的点数是多少 f[i][j] += f[i- 1][j - k]; // 状态f[i][j]表示前i次总和是j的方案数！ } } } vector<int> res; for(int i = n; i <= n * 6; i++) res.push_back(f[n][i]); return res; } };
3.扑克牌的顺子(剑指offer原61题)
- 解题思路：模拟人的想法，先将除去了大小王之外的牌拿过来，如果有相同元素，则一定不是顺子！如果没有任何两个元素相同，看一下牌中最小值与最大值的差距是否在4以内。如果满足条件，则可以将缺失的部分用大小王来进行填补。
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 从扑克牌中随机抽5张牌，判断是不是一个顺子。 class Solution{ public: bool isContinous(vector<int>& nums) { if(nums.empty()) return false; sort(nums.begin(), nums.end()); int k = 0; while(!nums[k]) k++; // 去掉行首的0 for(int i = k + 1; i < nums.size(); i++){ // 去掉重复元素 if(nums[i] == nums[i - 1]) return false; } return nums.back() - nums[k] <= 4; } };
4.圆圈中最后剩下的数字(剑指offer原62题)----约瑟夫环问题
- 解题思路：f(n,m)表示总共n个数字，每次报到数字m时，就将此数字从环中删除,最后剩下的数字。f(n-1,m)表示从剩下的n-1个数字中，每次报到数字m时，就将此数字从环中删除，最后剩下的数字。观察f(n,m)与f(n-1,m)之间的关系，可知f(n,m) = (f(n-1,m) + m) % n,其中边界条件是f(n==1, m) = 0;
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution{ public: int lastRemaining(int n, int m){ if(n == 1) return 0; return (lastRemaining(n - 1, m) + m) % n; } };
5.股票的最大利润（剑指offer原63题）
- 解题思路：找出前i天的最小值，利用一个变量minValue来存储。第i天卖出的价格是nums[i]，最大利润res是等于第i天卖出价格与前i天中价格最低时买入的价格之差，此时获得的利润是最大的。
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution{ public: int maxDiff(vector<int>& nums) { if(nums.empty()) return 0; int res = 0; // 最大利润 for(int i = 1, minValue = nums[0]; i < nums.size(); i++){ res = max(res, nums[i] - minValue); // minValue表示前i天的最小值，nums[i]表示第i天卖出的价格！ minValue = min(minValue, nums[i]); } return res; } };
6.求1+2+3+...+n，不能使用乘除法和各种循环、判断语句(剑指offer原64题)
- 解题思路：使用递归的思路来写，但是将当中的if语句，改成&&运算符。
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution{ public: int getSum(int n){ int res = n; n > 0 && (res += getSum(n - 1)); // 实际是对if(n > 0) res += getSum(n - 1);语句的改写 return res; } };
7.不用加减乘除做加法(剑指offer原65题)
- 解题思路：模拟计算机中的加法A + B，结果是CD。其中C是十位，D是个位。A和B对应位上的取值有四种(0 0、0 1、1 0、1 1)，C上的结果是(0 0 0 1),D上的结果是(0 1 1 0)。可以将C上的结果看出(A对应位上的取值 & B对应位上的取值)；将D上的结果看出(A对应位上的取值 ^ B对应位上的取值)。因此，可以将多位数相加A + B可以看出是A + B= A^B(无进位) + (A & B << 1)(A & B表示的就是进位)。
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution{ public: int add(int num1, int num2){ while(num2){ int sum = num1 ^ num2; int carry = (num1 & num2) << 1; num1 = sum; num2 = carry; } return num1; } };
8.构建乘积数组(剑指offer原66题)[不能用除法、只能开一个数组]
- 解题思路：B[i] = A[0] * A[1] * ... * A[i-1] * A[i+1] * ... * A[n-1]。可以先算i的左半边 A[0] * A[1] * ... * A[i-1]，然后算i的右半边A[i+1] * ... * A[n-1]，最后两部分相乘。
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution{ public: vector<int> multiply(const vector<int>& A){ if(A.empty()) return vector<int>(); int n = A.size(); vector<int> B(n); // 先算A[0]到A[i-1]的乘积 for(int i = 0, p = 1; i < n; i++){ B[i] = p; p *= A[i]; } // 再算A[i+1]到A[n-1]的乘积 for(int i = n - 1, p = 1; ~i; i--){ B[i] *= p; p *= A[i]; } return B; } };
9.把字符串转换成整数(剑指offer原67题)
- 解题思路：处理好各种边界问题！
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; class Solution{ public: int strToInt(string str) { int k = 0; while(k < str.size() && str[k] == ' ') k++; // 忽略所有的行首空格！ long long number = 0; bool is_minus = false; // 忽略完行首的空格后，可能有-/+的符号 if(str[k] == '+') k++; else if(str[k] == '-') k++, is_minus = true; while(k < str.size() && str[k] >= '0' && str[k] <= '9'){ number = number * 10 + str[k] - '0'; // 字符串表示的数字转换成真正的数字 k++; } if(is_minus) number *= -1; // 处理负数的情况 if(number > INT_MAX) number = INT_MAX; if(number < INT_MIN) number = INT_MIN; return (int)number; } };
10.树中两个结点的最低公共祖先(剑指offer原68题)
- 解题思路：给出的两个结点的位置可能有两种情况，一种是两个结点出现在一个结点的左右两个子树上；另一种是一个给定的结点出现最低公共祖先节点上，另一个给定的结点出现在左子树或右子树上！具体的方法是：先遍历左子树，检查是否有给定的两个结点p、q；再遍历右子树，检查是否有给定的两个结点p、q。如果左右子树中同时出现了p、q，则当前结点就是需要返回的就是最低公共祖先结点；如果只在左子树或右子树中出现p、q，则返回值就是p、q的最低公共祖先。
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr){} }; class Solution{ public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){ if(!root) return nullptr; // 空树 if(root == p || root == q) return root; auto left = lowestCommonAncestor(root->left, p, q); // 检查一下左边是否有p和q auto right = lowestCommonAncestor(root->right, p, q); // 检查一下右边是否有p和q if(left && right) return root; if(left) return left; return right; } };
11.数字在排序数组中出现的次数(剑指offer原53题--题目一）
- 解题思路：**二分法解决！**就是此数字第一次出现的位置与此数字最后一次出现的位置，两者之间的数的个数就是该数字出现的次数！
#include <iostream> #include <vector> #include <string> using namespace std; class Solution{ public: int getNumberOfK(vector<int>& nums, int k){ if(nums.empty()) return 0; int l = 0, r = nums.size() - 1; while(l < r){ int mid = l + r >> 1; if(nums[mid] < k) l = mid + 1; else r = mid; } if(nums[l] != k) return 0; int left = l; l = 0, r = nums.size() - 1; while(l < r){ int mid = l + r + 1 >> 1; if(nums[mid] <= k) l = mid; else r = mid - 1; } return r - left + 1; } };
12.0到n-1中缺失的数字(剑指offer原53题---题目二)
- 题目要求的是：长度为n的数组,将其中的一个数删掉，只剩下n-1个数了。将剩下的n-1个数作为程序的输入，找出被删除的那个数！
- 解题思路：先计算0到n-1中的n个数的和，再减去当前序列中的每个数，也就可以得到答案了。
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; class Solution{ public: int getMissingNumber(vector<int>& nums){ // nums是输入的n-1个数 int n = nums.size() + 1; int res = (n - 1) * n / 2; for(auto x: nums) res -= x; return res; // res就是0到n-1中缺失的那个数字 } };
13.数组中数值和下标相等的元素(剑指offer原53题---题目三)
- 解题思路：因为给定的数组nums具有单调递增的性质，可以使用二分查找，时间复杂度是O(logn)。考察数组nums[i]-i是否具有单调性。即（nums[i]-i >= nums[i-1] - (i-1)是否成立？）
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; class Solution{ public: int getNumberSameAsIndex(vector<int>& nums){ int l = 0, r = nums.size() - 1; while(l < r){ int mid = l + r >> 1; if(nums[mid] - mid >= 0) r = mid; else l = mid + 1; } if(nums[r] - r == 0) return r; // 相等元素的下标 return -1; } };
14.二叉搜索树的第K个大的结点(剑指offer原54题)
- 解题思路：先对二叉搜索树进行中序遍历，每遍历到一个结点后，就对K进行减一操作。直到k减小到0后，就已经找到了第K个大的结点。
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; // 二叉树的定义 struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr){} }; class Solution{ public: TreeNode* ans; TreeNode* KthNode(TreeNode* root, int k){ dfs(root, k); return ans; } void dfs(TreeNode* root, int& k){ if(!root) return; dfs(root->left, k); // 中序遍历 k--; if(!k) ans = root; if(k > 0) dfs(root->right, k); } };
15.二叉树的深度(剑指offer原55题)
- 解题思路：深度就是找出从根结点到叶子节点的路径最长长度！具体就是找出根节点的左右子树两者中更长者的深度+1，即二叉树的深度。左右子树的深度用递归的方法来求解，当递归到叶子节点时，递归停止！
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; // 二叉树的定义 struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr){} }; class Solution{ public: int treeDepth(TreeNode* root){ if(!root) return 0; // 递归终止条件！ return max(treeDepth(root->left), treeDepth(root->right)) + 1; } };
16.平衡二叉树(剑指offer原55题--题目二)
- 解题思路：利用上一题的思路，求出左右子树的深度之差是否是大于1的，如果所有点的深度差都不大于1的话，则是平衡二叉树；如果任意一个结点的左右子树深度之差大于1，则一定是非平衡二叉树!
#include <iostream> #include <cmath> using namespace std; // 二叉树的定义 struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(nullptr), right(nullptr){} }; class Solution{ public: bool ans = true; bool isBalanced(TreeNode* root){ dfs(root); return ans; } int dfs(TreeNode* root){ if(!root) return 0; int left = dfs(root->left), right = dfs(root->right); if(abs(left - right) > 1) ans = false; return max(left, right) + 1; // 当前结点的深度 == 当前结点左右子树的深度的更大者 + 1 } };
17.数组中只出现一次的两个数字(剑指offer原56题)
- 原题是：一个数组中除了两个数字之外，其他数字都出现了2次。利用程序找出这两个只出现一次的数字！
- 解题思路：
#include <iostream> #include <vector> #include <string> using namespace std; class Solution{ public: vector<int> findNumsAppearance(vector<int>& nums){ int sum = 0; for(auto x : nums) sum ^= x; // 先求所有数字的异或和,也就是sum = x ^ y x,y分别表示数组中只出现一次的数字 int k = 0; while(!(sum >> k & 1)) k++; // 然后从sum中找出其二进制表示中任意一位不为0的位，k存储的就是x ^ y结果中第k位是1的那一位 int first = 0; for(auto x : nums){ if(x >> k & 1) // 将x的二进制表示中第k位是1的划分到第一个集合first中！ first ^= x; // 第一个集合异或的结果first 第二个结果异或的结果first ^ sum } return vector<int>{first, sum ^ first}; } };
- 先考虑一种简单的情况，数组中除了一个数字只出现一次外，其余数字都出现了2次，找出这个只出现一次的数字。利用异或运算的特点，所有出现两次的数字异或时都被消成0，再将异或结果与只出现一次的数字进行异或，结果就是我们要找的数字。
- 本题中只出现一次的数字有两个，如何找出这两个只出现一次的数呢?利用上面一样的操作，对所有的数字执行异或操作，得到的结果是两个只出现一次的数字的异或，由于两个数字都只出现一次。因此，最终的异或结果肯定不等于0。因为两个只出现一次的数字的异或的结果不等于0，所以异或结果的二进制表示中肯定有一位是1。假设异或结果中的第3位是1，则两个只出现一次的数字二进制表示的第3位一定是不相同的。此时，将原始数组中所有数字划分成两个集合，划分的依据就是看数组中每个数字的第3位是0还是1。因此，两个只出现一次的数字一定不在同一个集合中！所有出现两次的数字一定在同一个集合中！此时，两个集合中的数字就转化成最开始讨论的一种简单情况的例子。
18.数组中唯一只出现一次的数字(剑指offer原56题--题目2)
- 原题目：一个数组中除了一个数字只出现一次外，其他数字都出现了三次，找出那个只出现一次的数字。
- 解题思路：有限状态机原理，初始的状态是(ones=0,twos=0);输入的数字的二进制表示中某一位是1时，状态转移成(1,0),接着数字的二进制表示中某一位仍然是1时，状态转移成(0,1),接着数字的二进制表示中某一位继续是1时，状态转移成(0,0)。也就是每三个状态构成一个循环；当输入的数字的二进制表示中某一位是0时，从初始的状态是(ones=0,twos=0)转移至自身(0,0)；当所有的输入数字中某一位出现次数是%3余1时，状态就转移到(1,0)；当所有的输入数字中某一位出现次数是%3余0时，状态就转移到(0,0)状态。ones就代表了上面两种情况的结果。数组中唯一只出现一次的数字。
#include <iostream> #include <vector> #include <string> using namespace std; class Solution{ public: int findNumberAppearingOnce(vector<int>& nums){ int ones = 0, twos = 0; for(auto x : nums){ ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones; } return ones; } };
19.和为s的数字(剑指offer原57题---题目一)
- 解题思路1：暴力解法，先依次遍历每个数字，遍历到某个数字时，固定这个数字。再依次判断数组中其余的n-1个数字与它的和是否等于target。
#include <iostream> #include <vector> #include <string> using namespace std; // 暴力解法O(n**2) class Solution{ public: vector<int> findNumberWithSum(vector<int>& nums, int target){ for(int i = 0; i < nums.size(); i++){ for(int j = 0; j < i; j++){ if(nums[i] + nums[j] == target) return vector<int>{nums[i], nums[j]}; } } } };
- 解题思路2：对第二重循环进行优化，第二重循环的目的是判断对于j < i这个范围内，是否存在一个数字nums[j]使得target - nums[i] == nums[j]成立。因此，可以使用哈希表来统计数字nums[j]是否出现从而来优化，使得时间复杂度变成O(n)。
#include <iostream> #include <vector> #include <string> #include <unordered_set> using namespace std; class Solution{ public: vector<int> findNumberWithSum(vector<int>& nums, int target){ unordered_set<int> hash; for(int i = 0; i < nums.size(); i++){ if(hash.count(target - nums[i])) return vector<int>{target - nums[i], nums[i]}; // hash.count(target - nums[i])就是判断nums[j]是否在j < i的范围内出现！ hash.insert(nums[i]); } return vector<int>(); } };
20.和为s的连续正数序列(剑指offer原57题---题目二)
- 原题：输入一个正数s,输出所有和为s的连续正数序列，序列中至少含有两个数。
- 解题思路：暴力方法是给出区间的起点i,再给出区间的终点j。利用求和公式计算出区间[i,j]中数字的和是否为s，时间复杂度是O(n**2)。改进的方法是：假设区间[i,j]中数字的和是s，当区间左端点i向右移动到i1时，区间的右端点j也会向右移动到j1，如果右端点j向左移动到j2，则区间[i1,j2]中的数字之和一定是小于s的。总结起来就是使用双指针算法，时间复杂度变成O(n)。
#include <iostream> #include <vector> #include <string> using namespace std; // 暴力方法：O(n**2) class Solution{ public: vector<vector<int>> findContinuousSequence(int sum){ vector<vector<int>> res; for(int i = 1, j = 1, s = 1; i <= sum; i++) // s是当前序列的和 { while(s < sum) s += ++j; if(s == sum && j - i + 1 > 1){ // [i,j]中包含的元素个数是: j - i + 1 vector<int> line; for(int k = i; k <= j; k++) line.push_back(k); // line是一个一维数组，数组中存放的是区间[i,j]中和为s的数字 res.push_back(line); } s -= i; } return res; } };
21.翻转单词顺序(剑指offer原58题---题目一)
- 原题：输入一个句子，翻转句子中单词的顺序，但每个单词内的字母顺序不变。
- 解题思路：先用双指针i和j，将整个句子的每个单词以字母为单位进行翻转；然后对句子的每个单词进行翻转。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; class Solution{ public: string reverseWords(string s){ reverse(s.begin(), s.end()); // 等价于for(int i = 0, j = s.size() - 1; i < j; i++, j--) swap(s[i], s[j]); 第一步首先对整个句子进行翻转 for(int i = 0; i < s.size(); i++){ // 对第一步中翻转后的每个单词进行翻转，下面是从一段字符串中提取出一个单词的操作！ int j = i; while(j < s.size() && s[j] != ' ') j++; reverse(s.begin() + i, s.begin() + j); i = j; } return s; } };
22.左旋转字符串(剑指offer原58题---题目二)
- 原题是：将字符串中的前面的前n位移动到字符串的尾部。
- 解题思路：和上一题一样的思路，先对整个字符串进行翻转。然后将翻转后的结果分成两个部分：前str.size() - n个字符和倒数n个字符，然后分别对上面的两部分进行翻转即可。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; class Solution{ public: string leftRotateString(string str, int n){ reverse(str.begin(), str.end()); reverse(str.begin(), str.begin() + str.size() - n); reverse(str.begin() + str.size() - n, str.end()); return str; } };
23.数字序列中某一位的数字(剑指offer原44题)
- 解题思路：
- 1.确定是几位数（n - 10*1 - 90*2 - 900*3 - ...）
- 2.确定是几位数的第几个数
- 3.确定那个数的第几位
- 详细过程：首先要确定第n位对应的数字在什么范围内，也就是确定第n位对应的数字是几位数。因为一位数有10个，占10位，两位数有90个，占180位，三位数有900个，占2700位。假设输入的是第1000位，则第1000位对应的应该是一个三位数（因为1000-10-180 = 720 < 2700）；然后确定第1000位对应的是哪个三位数上的某一位。因为经过上一步的分析可知，输入的第1000位出现在两位数之后的第720位，因为三位数每个数占3位，所以输入的第1000位对应的应该是第240个三位数中的某一位！由于三位数从100开始，所以第240个三位数是100 + 240 - 1 = 339；最后确定对应是339中的哪一位（因为720 / 3 = 240，所以应该对应339的最后一位9）
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; class Solution{ public: int digitAtIndex(int n){ long long i = 1, s = 9, base = 1; // i是几位数 s是几位数的个数 base是几位数的开始第一个数字 // 确定n对应是几位数 while(n > i * s){ n -= i * s; i++; s *= 10; base *= 10; } // 确定是几位数中的哪个数 int number = base + (n + i - 1) / i - 1; // 确定那个数的第几位 int r = n % i ? n % i : i; for(int j = 0; j < i - r; j++) number /= 10; return number % 10; } };
24.把数组排成最小的数(剑指offer原45题)
- 解题思路：首先在数组中定义两个数字之间的小于<关系：即a < b等价于ab < ba。然后将原始的输入数组按照定义的小于关系重新排序，一次拼接派好序后的数组中的数字即可。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; class Solution{ public: static bool cmp(int a, int b){ auto as = to_string(a), bs = to_string(b); return as + bs < bs + as; } string printMinNumber(vector<int>& nums){ sort(nums.begin(), nums.end(), cmp); string res; for(auto x : nums) res += to_string(x); return res; } };
25.把数字翻译成字符串(剑指offer原46题)
- 解题思路：大部分计数的问题，可以看成是动态规划的问题。问题的关键是a.状态表示 b.状态如何计算 c.边界怎么定义。f(i)表示前i位数字一共有多少种翻译方式，f(i) 如何计算？如果将第i位数字单独翻译成一个字母，则f(i)可表示为前i-1位数字一共有多少种翻译方式；如果将第i位和第i-1位数字翻译成两个个字母，则f(i)可表示为前i-2为数字一共有多少种翻译方式。综合上述两种情况,f(i) = f(i-1) + f(i-2)。注意第二种情况：f(i-2)是将第i和第i-1位数字联合起来翻译成字母，因此必须有约束,范围是[10,25]之间。最后，考虑边界f(0) = 1。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; class Solution{ public: int getTranslationCount(string s){ int n = s.size(); vector<int> f(n+1); f[0] = 1; for(int i = 1; i <= n; i++){ f[i] = f[i - 1]; // 第一种情况 int t = (s[i-2] - '0') * 10 + s[i-1] - '0'; // 第二种情况 if(t >= 10 && t <= 25) f[i] += f[i-2]; } return f[n]; } };
