Tag Archives: 递归

LeetCode Shopping Offers

LeetCode Shopping Offers
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

  1. There are at most 6 kinds of items, 100 special offers.
  2. For each item, you need to buy at most 6 of them.
  3. You are not allowed to buy more items than you want, even if that would lower the overall price.

给定每个商品的单价和需要购买的数量,并且有一些special offer,相当于捆绑销售的优惠套餐。问刚好买到给定数量的商品,所花的最低费用是多少。
注意给定的限制条件中商品最多只有6种,且每件最多只购买6件,所以可以考虑用暴力方法。
把special offer看成一个背包问题里的“商品”,对于每个special offer,我们有两种选择,可以用或者不用。如果需要的needs数组每一项都大于等于某个special offer的每一项,即可以用该special offer,我们比较用和不用该special offer的最终花费,取花费低的。如果用该special offer,则needs数组需要减掉sp捆绑的每件商品的件数,然后继续递归该sp是否可用,相当于完全背包,不计件数的。如果该sp不能用,则递归考虑下一个sp。最后如果递归考虑完所有sp了,则剩余的商品只能按原价购买,算出按原价购买的费用即可。
完整代码如下:

class Solution {
private:
	int dot(vector<int>& price, vector<int>& needs) {
		int ans = 0;
		for (int i = 0; i < needs.size(); ++i) {
			ans += price[i] * needs[i];
		}
		return ans;
	}
	int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) {
		if (idx == special.size())return dot(price, needs); // 原价购买
		int i = 0, n = special[idx].size();
		vector<int> small_needs = needs;
		for (i = 0; i < n - 1; ++i) {
			if (special[idx][i] > needs[i])break;
			small_needs[i] -= special[idx][i];
		}
		if (i == n - 1)return min(shopping(price, special, small_needs, idx) + special[idx][n - 1], shopping(price, special, needs, idx + 1));
		else return shopping(price, special, needs, idx + 1);
	}
public:
	int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
		return shopping(price, special, needs, 0);
	}
};

本代码提交AC,用时6MS。
参考:https://leetcode.com/articles/shopping-offers/,下次记得看到这种数据量非常小的题,首先尝试暴力方法!

LeetCode Range Sum Query - Mutable

LeetCode Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

给定一个一维数组,要求实现范围求和,即求[i,j]之间的元素的和。sumRange(i,j)求i~j的元素和,update(i,val)更新下标为i的元素值为val。
第一敏感使用线段树,很久之前在hihoCoder上遇到过
建树的方法是类似于树的后序遍历,即左右根。不断把[start,end]二分,构建左右子树,然后构建当前节点,当前节点的sum等于左右子树的sum的和。在递归的时候,递归到start==end时,说明只有一个元素了,此时sum就等于该元素。
查询的方法和建树方法类似,判断区间[i,j]和区间[start,end]的关系,假设start和end的中点是mid,如果j<=mid,递归在左子树查询;如果i>mid,递归在右子树查询;否则在[i,mid]和[mid+1,j]查询然后求和。
更新的方法和查询的方法类似,也是不断判断i和mid的关系,在左子树或者右子树递归更新,当找到该叶子节点时,更新它的sum,返回父节点也更新sum等于新的左右子树的sum的和。
完整代码如下:

class NumArray {
private:
	struct Node {
		int start, end, sum;
		Node *left, *right;
		Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {};
	};
	Node *root;
	Node* constructTree(vector<int> &nums, int start, int end) {
		Node* node = new Node(start, end);
		if (start == end) {
			node->sum = nums[start];
			return node;
		}
		int mid = start + (end - start) / 2;
		node->left = constructTree(nums, start, mid);
		node->right = constructTree(nums, mid + 1, end);
		node->sum = node->left->sum + node->right->sum;
		return node;
	}
	int sumRange(int i, int j, Node *root) {
		if (root == NULL)return 0;
		if (i == root->start&&j == root->end)return root->sum;
		int mid = root->start + (root->end - root->start) / 2;
		if (j <= mid)return sumRange(i, j, root->left);
		else if (i > mid)return sumRange(i, j, root->right);
		else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right);
	}
	void update(int i, int val, Node *root) {
		if (root->start == root->end && root->start == i) {
			root->sum = val;
			return;
		}
		int mid = root->start + (root->end - root->start) / 2;
		if (i <= mid)update(i, val, root->left);
		else update(i, val, root->right);
		root->sum = root->left->sum + root->right->sum;
	}
public:
	NumArray(vector<int> nums) {
		root = NULL;
		if (!nums.empty())root = constructTree(nums, 0, nums.size() - 1);
	}
	void update(int i, int val) {
		if (root == NULL)return;
		update(i, val, root);
	}
	int sumRange(int i, int j) {
		if (root == NULL)return 0;
		return sumRange(i, j, root);
	}
};

本代码提交AC,用时172MS。

LeetCode Surrounded Regions

LeetCode Surrounded Regions
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.
For example,

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

给定一个board,要求把其中被X包围的O也改为X,这里的包围必须四周全都有X
开始的想法是,这个问题类似于找岛屿的问题,可以用BFS/DFS或者并查集,但是感觉不太好弄,比如虽然并查集能找到所有岛屿,但是要区分全包围和半包围还是有点麻烦。
查看讨论区,解法很巧妙。半包围的O肯定出现在边缘,所以我们先从边缘的O开始DFS,把所有半包围的O改为一个其他的字符,比如'1'。这样之后,剩余的所有O肯定是被X全包围的,而那些被标记为'1'的,则是原来被半包围的'O'。所以最后,我们遍历整个board,遇到'O'直接改为'X'就好,遇到'1',则改回原来的'O'。直接O(1)空间复杂度就搞定了,不错。
代码如下:

vector<vector<int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };
class Solution {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	void dfs(vector<vector<char>>& board, int x, int y) {
		board[x][y] = '1';
		for (int i = 0; i < dirs.size(); ++i) {
			int u = x + dirs[i][0], v = y + dirs[i][1];
			if (isOk(u, v) && board[u][v] == 'O') dfs(board, u, v);
		}
	}
public:
	void solve(vector<vector<char>>& board) {
		if (board.empty() || board[0].empty())return;
		m = board.size(), n = board[0].size();
		for (int i = 0; i < m; ++i) {
			if (board[i][0] == 'O') dfs(board, i, 0);
			if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
		}
		for (int j = 0; j < n; ++j) {
			if (board[0][j] == 'O') dfs(board, 0, j);
			if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
		}
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (board[i][j] == 'O')board[i][j] = 'X';
				else if (board[i][j] == '1')board[i][j] = 'O';
			}
		}
	}
};

本代码提交AC,用时13MS。

LeetCode Design Excel Sum Formula

LeetCode Design Excel Sum Formula
Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:
Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from 'A' to 'Z'. It represents that the width is the number of characters from 'A' to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from 'A'.
 
void Set(int row, char column, int val): Change the value at C(row, column) to be val.
 
int Get(int row, char column): Return the value at C(row, column).
 
int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula.
numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, "F7" represents the cell at (7, F).
If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.
 
Example 1:

Excel(3,"C");
// construct a 3*3 2D array with all zero.
//   A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6

Note:

  1. You could assume that there won't be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
  2. The test cases are using double-quotes to represent a character.
  3. Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

本题要求设计一个简单的Excel表格求和功能。主要实现三个接口:

  • Get(int row, char column),获取坐标为(row,column)的cell的值
  • Set(int row, char column, int val),把坐标为(row,column)的值设置为val
  • Sum(int row, char column, List of Strings : numbers),numbers表示一系列求和公式,把公式计算结果填入坐标(row,column)中,并且当公式中的格子更新时,该公式计算出来的值也要更新。

本题的难点是,如果C3=A1+B2,如果更新了B2,下次get(C3)时,得到的结果也必须是用更新过的B2的值。而且还有可能A1的值也是用某个公式计算出来的。
当时比赛的时候,有一些思路,但是逻辑不是很清晰,后来参考这个题解,逻辑很清楚
Excel包含两个成员,二维矩阵matrix表示一个excel表格,hashmap formula的key为某个格子,value为该格子对应的求和公式。如果某个格子的值是实实在在的值,不是用公式计算出来的,则不在这个hashmap中。

  • 对于get,如果坐标不在formula中,说明该格子是实实在在的值,直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
  • 对于set,直接把matrix对应坐标设置为value就好,注意的是,因为set之后就变成了实实在在的值,所以要清空formula中该格子的公式(如果有的话)。
  • 对于sum,计算字符串公式的值,把结果填入对应的格子,然后在formula中设置该格子的公式。

问题的难点是怎样对一个公式求值。说穿了其实就是不停的递归调用get函数,因为get函数如果该cell没有在formula中,则返回实实在在的值,否则递归计算formula的值。想象一下,就是不停的对一个坐标递归求值,直到不能递归时,返回matrix中的值,然后递归累加起来。想明白了其实很简单,代码注意把公共的计算部分抽象出来。
完整代码如下:

class Excel {
private:
	vector<vector<int>> matrix;
	unordered_map<int, vector<string>> formula;
	// 把坐标hash成一个int
	int id(int r, char c) {
		return r * 27 + c - 'A' + 1;
	}
	void parse(string& s, int& r, char& c) {
		c = s[0];
		r = stoi(s.substr(1));
	}
	int get_cell(string& s) {
		int r;
		char c;
		parse(s, r, c);
		return get(r, c);
	}
	int get_range(string& s) {
		size_t pos = s.find(':');
		string s1 = s.substr(0, pos), s2 = s.substr(pos + 1);
		int r1, r2;
		char c1, c2;
		parse(s1, r1, c1);
		parse(s2, r2, c2);
		int ans = 0;
		for (int i = r1; i <= r2; ++i) {
			for (char c = c1; c <= c2; ++c) {
				ans += get(i, c);
			}
		}
		return ans;
	}
	int get_cells(vector<string>& strs) {
		int ans = 0;
		for (auto& s : strs) {
			if (s.find(':') == string::npos)
				ans += get_cell(s);
			else
				ans += get_range(s);
		}
		return ans;
	}
public:
	Excel(int H, char W) {
		matrix.clear();
		formula.clear();
		for (int i = 0; i <= H; ++i) {
			matrix.push_back(vector<int>(W - 'A' + 1, 0));
		}
	}
	void set(int r, char c, int v) {
		matrix[r] = v;
		formula.erase(id(r, c)); // caution
	}
	int get(int r, char c) {
		if (formula.find(id(r, c)) == formula.end())return matrix[r];
		return get_cells(formula[id(r, c)]);
	}
	int sum(int r, char c, vector<string> strs) {
		int ans = get_cells(strs);
		matrix[r] = ans;
		formula[id(r, c)] = strs;
		return ans;
	}
};

本代码提交AC,用时6MS。

LeetCode Mini Parser

LeetCode Mini Parser
Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].

Example 1:

Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

给定一个嵌套的字符串,要求把它解析成一个NestedInteger。
解法1,使用栈。遇到左括号时,增加一个空的NestedInteger实例,压栈。遇到逗号时,把前面的数add到栈顶的NestedInteger中。遇到右括号时,把栈顶的NestedInteger弹栈,并add到新的栈顶(相当于前一个)NestedInteger中。最后栈顶只有一个元素,返回该元素即可。
代码如下:

class Solution {
public:
	NestedInteger deserialize(string s) {
		auto isnumber = [](char c) {return c == '-' || isdigit(c); };
		stack<NestedInteger> stk;
		stk.push(NestedInteger());
		for (auto it = s.begin(); it != s.end();) {
			if (isnumber(*it)) {
				auto it2 = find_if_not(it, s.end(), isnumber);
				int v = stoi(string(it, it2));
				stk.top().add(NestedInteger(v));
				it = it2;
			}
			else {
				if (*it == '[') {
					stk.push(NestedInteger());
				}
				else if (*it == ']') {
					NestedInteger tmp = stk.top();
					stk.pop();
					stk.top().add(tmp);
				}
				++it;
			}
		}
		return stk.top().getList().front();
	}
};

本代码提交AC,用时19MS。
解法2,递归法。如果当前的字符串是一个裸的整数的话,类似于样例1,则直接返回以该数为参数的NestedInteger;否则剥掉左括号[,递归反序列化,把递归的结果add到当前的NestedInteger中。
代码如下:

class Solution {
private:
	NestedInteger deserialize(istringstream &in) {
		int number;
		if (in >> number)
			return NestedInteger(number);
		in.clear();
		in.get();
		NestedInteger list;
		while (in.peek() != ']') {
			list.add(deserialize(in));
			if (in.peek() == ',')in.get();
		}
		in.get();
		return list;
	}
public:
	NestedInteger deserialize(string s) {
		istringstream in(s);
		return deserialize(in);
	}
};

本代码提交AC,用时19MS。
参考1,栈:https://discuss.leetcode.com/topic/54904/c-non-recursive-one-pass-solution-using-stack-a-possible-implementation-of-nestedinteger
参考2,递归:https://discuss.leetcode.com/topic/54258/python-c-solutions/10

LeetCode Lowest Common Ancestor of a Binary Tree

LeetCode Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.


给定一棵二叉树和两个节点p,q,问p和q的最近公共祖先节点是哪个。LCA问题
思路:要找p和q的最近公共祖先,很直观的方法是找到从根节点分别到p和q的路径,然后把其中一条路径(比如根到p)上的点hash成path1,从另一条路径(比如根到q)的底端(q)往根节点走,把走过的每个点去path1中找,如果找到,则就是他们的LCA,因为这是距离q最近、且在path1中的点。
但是怎样找到根到p和q的路径呢。这里换一种思路,定义如下新的数据结构,par表示该节点的父节点,根节点的父节点为-1。

struct MyNode {
	TreeNode* node;
	int par;
	MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};

先整体把树层次遍历一遍,成为一个保存MyNode的数组,记录每个点的父节点在数组中的下标。在遍历的同时,记录下p和q节点的下标。这样通过下标往前递归就可以找到p和q到根节点的路径了。
找到路径之后,对其中一条路径hash,另一条路径在该hash中找。代码如下:

class Solution {
private:
	struct MyNode {
		TreeNode* node;
		int par;
		MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
	};
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		vector<MyNode> nodes;
		int i = 0, j = 0;
		queue<MyNode> tree;
		tree.push({ root,-1 });
		while (!tree.empty()) {
			MyNode cur = tree.front();
			tree.pop();
			if (cur.node == NULL) continue;
			if (cur.node == p)i = nodes.size();
			if (cur.node == q)j = nodes.size();
			tree.push({ cur.node->left,nodes.size() });
			tree.push({ cur.node->right,nodes.size() });
			nodes.push_back(cur);
		}
		if (i == j)return nodes[i].node;
		unordered_set<int> path1;
		while (i != -1) {
			path1.insert(i);
			i = nodes[i].par;
		}
		while (j != -1) {
			if (path1.find(j) != path1.end()) {
				return nodes[j].node;
			}
			j = nodes[j].par;
		}
		return NULL;
	}
};

本代码提交AC,用时19MS。
讨论区还有一种递归的解法,很有意思。我们在以root为根的树中找p和q的LCA,如果root等于p或q其中之一,说明p或q就是他们的LCA。否则分别在左子树和右子树中递归的找LCA,如果发现在左右子树中找到的LCA都不为null,说明他们p和q分别位于root的两个子树,类似样例中的5和1,则root就是他们的LCA。如果某个子树返回的LCA为空,说明p和q都不在这个子树中,则先遇到谁,谁就是LCA,比如样例中的5和4,都不在3的右子树,在递归3的左子树的时候,先遇到了5,所以5是LCA。
完整代码如下:

class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root == NULL || root == p || root == q)return root;
		TreeNode* left = lowestCommonAncestor(root->left, p, q);
		TreeNode* right = lowestCommonAncestor(root->right, p, q);
		if (left != NULL&&right != NULL)return root;
		return left != NULL ? left : right;
	}
};

本代码提交AC,用时23MS。

LeetCode Merge Two Binary Trees

LeetCode Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:

Input:
	Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7
Output:
Merged tree:
	     3
	    / \
	   4   5
	  / \   \
	 5   4   7

Note: The merging process must start from the root nodes of both trees.


上午又参加了一场LeetCode的比赛,第三题花了不少时间,第四题在11:06分AC了,但是比赛好像在11:00就结束了。。。无语,排名只有376。
这题要求把两棵二叉树合并,如果对应位置都有节点,则新节点的值等于两个老节点的值之和,否则等于有值的那个节点。
简单题,直接递归merge就好。代码如下:

class Solution {
public:
	TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
		if (t1 == NULL&&t2 == NULL)return NULL;
		if (t1 == NULL&&t2 != NULL)return t2;
		if (t1 != NULL&&t2 == NULL)return t1;
		TreeNode* left = mergeTrees(t1->left, t2->left);
		TreeNode* right = mergeTrees(t1->right, t2->right);
		TreeNode* root = new TreeNode(t1->val + t2->val);
		root->left = left;
		root->right = right;
		return root;
	}
};

本代码提交AC,用时49MS。

LeetCode Longest Palindromic Subsequence

LeetCode Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is "bb".


求一个字符串的最长回文子序列
使用DP求解,假设dp[i][j]表示原字符串范围[i,j]中的最长回文子序列的长度。则如果s[i]==s[j],则dp[i][j]=dp[i+1][j-1]+2,即是临近内层的最长回文子序列长度加2。如果s[i]!=s[j],则dp[i][j]=max(dp[i][j-1],dp[i+1][j]),即是左端或者右端最长回文子序列长度的最大值。
初始时dp[i][i]=1,即单个字符自成回文,长度为1。
代码如下:

class Solution2 {
public:
	int longestPalindromeSubseq(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		for (int i = n - 1; i >= 0; --i) {
			dp[i][i] = 1;
			for (int j = i + 1; j < n; ++j) {
				if (s[i] == s[j])dp[i][j] = dp[i + 1][j - 1] + 2;
				else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
			}
		}
		return dp[0][n - 1];
	}
};

本代码提交AC,用时68MS。
上述计算有些区间会重复计算dp[i][j],可以用递归方法求解,并且把计算过的值记录下来,下次遇到查询时直接返回。代码如下:

class Solution {
private:
	int helper(int l, int r, const string &s, vector<vector<int>> &dp) {
		if (l > r)return 0;
		if (l == r)return 1;
		if (dp[l][r] != 0)return dp[l][r];
		if (s[l] == s[r])dp[l][r] = helper(l + 1, r - 1, s, dp) + 2;
		else dp[l][r] = max(helper(l, r - 1, s, dp), helper(l + 1, r, s, dp));
		return dp[l][r];
	}
public:
	int longestPalindromeSubseq(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		return helper(0, n - 1, s, dp);
	}
};

本代码提交AC,用时49MS。
参考:https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution/2

LeetCode Array Nesting

LeetCode Array Nesting
A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].
Sets S[K] for 0 <= K < N are defined as follows:
S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.
Sets S[K] are finite for each K and should NOT contain duplicates.
Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.
Example 1:

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Note:

  1. N is an integer within the range [1, 20,000].
  2. The elements of A are all distinct.
  3. Each element of array A is an integer within the range [0, N-1].

求嵌套集合的最大长度。首先给定原数组A,嵌套集合为S[K] = { A[K], A[A[K]], A[A[A[K]]], ... },就是不断的把值当下标递归的取值,因为数组A中的值的范围也是0~n-1的,所以下标不会超出范围。
暴力方法就是求出每一个S[K]的大小,然后求最大值。但是仔细分析一个样例就会发现,很多S[K]集合是完全一样的,比如第一个样例中,S[0]和S[2]都等于{5,6,2,0},因为他们构成了一个循环。所以我们可以创建一个visited数组,访问过就置1,只对哪些visited为0的下标开始递归。这样对于第一个样例,其实只需要3次递归就可以了,也就是下标到值的构成的图中环的个数:{5,6,2,0},{3},{1,4}。所以总的复杂度其实只有O(n)。
代码如下:

class Solution {
private:
	int nest(vector<int> &nums, vector<int> &visited, int k) {
		int ans = 0;
		while (visited[k] == 0) {
			visited[k] = 1;
			++ans;
			k = nums[k];
		}
		return ans;
	}
public:
	int arrayNesting(vector<int>& nums) {
		int n = nums.size();
		vector<int> visited(n, 0);
		int ans = 0;
		for (int i = 0; i < nums.size(); ++i) {
			if (visited[i] == 0) {
				int cur = nest(nums, visited, i);
				ans = max(ans, cur);
			}
		}
		return ans;
	}
};

本代码提交AC,用时39MS。

LeetCode Construct String from Binary Tree

LeetCode Construct String from Binary Tree
You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.
The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /
  4
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \
      4
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

本题要求把一棵二叉树转换为一个字符串,使用先序遍历的方法,并且左右子树需要用括号括起来,但是要保证从该字符串能唯一恢复回原来的二叉树,而且要去掉不必要的空括号。
首先明确先序遍历:根左右,不难。然后要删掉不必要的空括号,观察第二个样例,发现如果左孩子为空,则左孩子的空括号不能省,但是如果右孩子或者左右孩子都为空,则他们的空括号可以省略。所以分几种情况递归求解即可。
代码如下:

class Solution {
public:
	string tree2str(TreeNode* t) {
		if (!t)return "";
		if (!t->left && !t->right)return to_string(t->val);
		if (!t->left)return to_string(t->val) + "()(" + tree2str(t->right) + ")";
		if (!t->right)return to_string(t->val) + "(" + tree2str(t->left) + ")";
		return to_string(t->val) + "(" + tree2str(t->left) + ")(" + tree2str(t->right) + ")";
	}
};

本代码提交AC,用时19MS。