Tag Archives: DFS

剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

示例 1:

输入:board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出:true
示例 2:

输入:board = [[“a”,”b”],[“c”,”d”]], word = “abcd”
输出:false
提示:

1 <= board.length <= 200
1 <= board[i].length <= 200
注意:本题与主站 79 题相同:https://leetcode-cn.com/problems/word-search/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个字符矩阵,问矩阵中是否能走出一条路径,这条路径上的字符串起来和target字符串相等。

典型的DFS题,首先找到第一个字符开始的位置,然后DFS,完整代码如下:

class Solution {
private:
    bool DFS(vector<vector<char>> &board, vector<vector<int>> &visited, int x, int y, const string &word, int idx) {

        if(idx == word.size() - 1) return true;

        visited[x][y] = 1;
        int m = board.size(), n = board[0].size();

        vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
        for(int i = 0; i < dirs.size(); ++i) {
            int u = x + dirs[i][0], v = y + dirs[i][1];
            if(u >= 0 && u < m && v >= 0 && v < n && visited[u][v] == 0 && board[u][v] == word[idx + 1]) {
                bool ans = DFS(board, visited, u, v, word, idx + 1);
                if(ans) return true;
            }
        }

        visited[x][y] = 0;

        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size() == 0) return true;
        int m = board.size(), n = board[0].size();
        vector<vector<int>> visited(m, vector<int>(n, 0));
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(board[i][j] == word[0]) {
                    if(DFS(board, visited, i, j, word, 0)) return true;
                }
            }
        }
        return false;
    }
};

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

剑指 Offer 36. 二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

为了让您更好地理解问题,以下面的二叉搜索树为例:

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意:本题与主站 426 题相同:https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

注意:此题对比原题有改动。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


如何将二叉搜索树转换in-place转换为有序双向链表。

此题同时考察了多个知识点,首先二叉搜索树转换为有序结果,需要使用二叉树的中序遍历,然后要in-place转换为双向链表,则需要在遍历二叉树的过程中,对每个节点,修改其left和right指针,使其分别指向转换后的双向链表的前驱和后继节点。

使用递归的方法,设置两个全局变量pre和head,分别表示当前遍历节点的前驱节点,以及转换后的双向链表的头结点。完整代码如下:

class Solution {
private:
    Node *pre, *head;
    void DFS(Node *root) {
        if(root == NULL) return;

        DFS(root->left);
        if(head == NULL) head = root;
        else pre->right = root;
        
        root->left = pre;
        pre = root;
        DFS(root->right);
    }
public:
    Node* treeToDoublyList(Node* root) {

        if(root == NULL) return NULL;

        pre = head = NULL;

        DFS(root);

        head->left = pre;
        pre->right = head;

        return head;
    }
};

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

LeetCode Number of Nodes in the Sub-Tree With the Same Label

5465. Number of Nodes in the Sub-Tree With the Same Label

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
Output: [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

  • 1 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • labels.length == n
  • labels is consisting of only of lower-case English letters.

给定一棵多叉树(无向图),有n个顶点n-1条边。每个顶点上标了一个字母,问对于每个顶点,在它的子树中,与其字母相同的点有多少个。

每个节点维护一个26长的数组,记录该子树包含所有字母的频数。然后DFS,记录每个节点的这个数组,父节点的数组的值要累加上其直接孩子的这个数组的值。最后查表得到结果。代码如下:

class Solution {
private:
	void DFS(int parid, int curid, vector<vector<int>> &children_string, unordered_map<int, vector<int>> &graph, const string &labels) {
		int mylabel = labels[curid] - 'a';
		++children_string[curid][mylabel];

		for (int i = 0; i < graph[curid].size(); ++i) {
			int childid = graph[curid][i];
			if (childid == parid)continue;
			DFS(curid, childid, children_string, graph, labels);
			for (int j = 0; j < 26; ++j) {
				children_string[curid][j] += children_string[childid][j];
			}
		}
	}
public:
	vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
		unordered_map<int, vector<int>> graph;
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]].push_back(edges[i][1]);
			graph[edges[i][1]].push_back(edges[i][0]);
		}
		vector<vector<int>> children_string(n, vector<int>(26, 0));
		
		DFS(-1, 0, children_string, graph, labels);

		vector<int> ans;
		for (int i = 0; i < n; ++i) {
			int mylabel = labels[i] - 'a';
			ans.push_back(children_string[i][mylabel]);
		}
		return ans;
	}
};

本代码提交AC。

LeetCode Path with Maximum Probability

1514. Path with Maximum Probability

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to endreturn 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Constraints:

  • 2 <= n <= 10^4
  • 0 <= start, end < n
  • start != end
  • 0 <= a, b < n
  • a != b
  • 0 <= succProb.length == edges.length <= 2*10^4
  • 0 <= succProb[i] <= 1
  • There is at most one edge between every two nodes.

给定一个无向图,边表示概率,问从start到end的最大概率是多少。

借此题复习一下若干最短路径算法吧。

首先朴素的DFS,代码如下:

class Solution {
private:
	void DFS(const vector<vector<double>> &graph, vector<int> &visited, int start, int end, double curprob, double &maxprob) {
		
		if (start == end) {
			maxprob = max(maxprob, curprob);
			return;
		}

		int n = graph.size();
		for (int i = 0; i < n; ++i) {
			if (visited[i] == 0 && graph[start][i] >= 0) {
				visited[i] = 1;
				DFS(graph, visited, i, end, curprob*graph[start][i], maxprob);
				visited[i] = 0;
			}
		}

	}
public:
	double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
		vector<vector<double>> graph(n, vector<double>(n, -1.0));
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]][edges[i][1]] = succProb[i];
			graph[edges[i][1]][edges[i][0]] = succProb[i];
		}
		vector<int> visited(n, 0);
		visited[start] = 1;
		double maxprob = 0;
		DFS(graph, visited, start, end, 1, maxprob);
		return maxprob;
	}
};

本代码提交TLE。

其次, 朴素的迪杰斯特拉算法。迪杰斯特拉算法思路很简单,维护两个集合,一个集合S是已经找到最短路径的,另一个集合U是还未找到最短路径的。每次,从U选一个距离最小的节点u,这个节点已经是最短路径了,加入到S中。然后更新与u相连的其他节点的最短路径。如此循环往复。代码如下:

// 朴素迪杰斯特拉
class Solution {

public:
	double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
		vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]][edges[i][1]] = succProb[i];
			graph[edges[i][1]][edges[i][0]] = succProb[i];
		}

		vector<int> visited(n, 0);
		visited[start] = 1;

		vector<double> ans(n, 0);
		for (int i = 0; i < n; ++i) {
			ans[i] = graph[start][i];
		}

		while (true) {
			int maxid = -1;
			double maxprob = 0;
			for (int i = 0; i < n; ++i) {
				if (visited[i] == 0 && ans[i] > maxprob) {
					maxid = i;
					maxprob = ans[i];
				}
			}
			if (maxid == -1 || maxid == end)break; // 遇到end提前结束

			visited[maxid] = 1;


			for (unordered_map<int, double>::iterator it = graph[maxid].begin(); it != graph[maxid].end(); ++it) {
				int next = it->first;
				double prob = it->second;

				if (visited[next] == 0 && (maxprob*prob > ans[next])) {
					ans[next] = maxprob * prob;
				}

			}
		}

		return ans[end];
	}
};

很遗憾,上述代码在最后一个样例上TLE了。

优化版本的迪杰斯特拉算法。朴素迪杰斯特拉算法最耗时的是while循环内的两个for循环,第二个for循环是对找到的u节点的边进行循环,这个无法再优化,主要优化第一个for循环,即在U集合中找距离最短的u节点的过程。这里可以用优先队列来存储U中的所有节点。但是需要注意的是去重,比如题目中的第一个图,对于节点2,节点0弹出pq时,会访问节点2并把节点2加入到pq中;当节点1弹出pq时,又会访问节点2并把节点2加入到pq中,此时pq中出现了两个节点2,只不过prob不一样。所以pq弹出时可能会出现相同的节点,不过由于pq的性质,同样是2,先弹出来的肯定是概率最大的路径(最短路径),所以每次pq弹出时,更新visited数组,后续如果弹出的节点已经visited了,则不需要做第二个for循环了,直接continue。比如题目中的第一个图,0访问2时,压pq的是(id=2,prob=0.2);1访问2时,压pq的是(id=2,prob=0.25)。所以(id=2,prob=0.25)先于(id=2,prob=0.2)弹出,并设置visited[2]=1。当(id=2,prob=0.2)弹出时,visited[2]已经==1了,此时continue。


// 优化的迪杰斯特拉
struct P {
	int id_;
	double prob_;
	P(int id, double prob) :id_(id), prob_(prob) {};

	// priority_queue默认是最大堆,即小于就是小于
	bool operator<(const P& p) const {
		return this->prob_ < p.prob_;
	}
};

class Solution {

public:
	double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
		vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]][edges[i][1]] = succProb[i];
			graph[edges[i][1]][edges[i][0]] = succProb[i];
		}

		vector<int> visited(n, 0);

		vector<double> ans(n, 0);
		ans[start] = 1;

		priority_queue<P> pq;
		pq.push(P(start, 1));

		while (!pq.empty()) {
			P cur = pq.top();
			pq.pop();
			
			if (cur.id_ == end)break; // 提前结束

			if (visited[cur.id_] == 1)continue;
			visited[cur.id_] = 1;

			for (unordered_map<int, double>::iterator it = graph[cur.id_].begin(); it != graph[cur.id_].end(); ++it) {
				int next = it->first;
				double prob = it->second;
				if (cur.prob_*prob > ans[next]) {
					ans[next] = cur.prob_*prob;
					pq.push(P(next, ans[next]));
				}
			}

		}
		return ans[end];
	}
};

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

SPFA算法。SPFA算法的思想可以参考之前的一道题: http://code.bitjoy.net/2014/12/28/hihocoder-1093/

简单来说,SPFA就是带剪枝的BFS。它和迪杰斯特拉算法非常像,迪杰斯特拉算法是每次找U中距离最小的一个节点u,此时u的最短距离已经确定了,后续不会再更新了。因为迪杰斯特拉算法每次加入S的节点都是最优的,所以必须要线性(朴素迪杰斯特拉算法)或者用优先队列的方法从U中找到最小距离节点u。而SPFA算法就更简单一点,该算法不要求每次找到最优的节点u,因为SPFA是渐进逼近最优解的过程,它不需要线性查找,也不需要优先队列,它只需要一个简单的队列即可,每次把可以更新的节点u加入到队列中,然后BFS更新与u相连的其他节点。之前更新过的节点,后续还有可能更新。代码如下:

// SPFA
class Solution {

public:
	double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
		vector<unordered_map<int, double>> graph(n, unordered_map<int, double>());
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]][edges[i][1]] = succProb[i];
			graph[edges[i][1]][edges[i][0]] = succProb[i];
		}

		vector<int> visited(n, 0);
		visited[start] = 1;

		vector<double> ans(n, 0);
		ans[start] = 1;

		queue<int> q;
		q.push(start);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			visited[cur] = 0;

			for (unordered_map<int, double>::iterator it = graph[cur].begin(); it != graph[cur].end(); ++it) {
				int next = it->first;
				double prob = it->second;
				if (ans[cur] * prob > ans[next]) {
					ans[next] = ans[cur] * prob;
					if (visited[next] == 0) {
						visited[next] = 1;
						q.push(next);
					}
				}
			}
		}

		return ans[end];
	}
};

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

hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

#1542 : 无根数变有根树

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一棵包含 N 个节点的无根树,小Hi想知道如果指定其中某个节点 K 为根,那么每个节点的父节点是谁?

输入

第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N。 以下N-1行每行包含两个整数 a 和 b,代表ab之间存在一条边。 1 ≤ ab ≤ N。 输入保证是一棵树。

输出

输出一行包含 N 个整数,分别代表1~N的父节点的编号。对于 K 的父节点输出0。
样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1

给定一个无根树(其实就是DAG),如果以该树的某个顶点K为根,要求输出每个节点的父节点。 简单题,以K为根,进行DFS,遍历过程中记录每个节点的父节点就好了。完整代码如下: [cpp] #include<iostream> #include<vector> #include<algorithm> #include<unordered_set> #include<string> #include<unordered_map> #include<queue> using namespace std; const int kMaxN = 1005; int n, k; vector<int> parent(kMaxN, 0); vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0)); void DFS(int node, int pre) { parent[node] = pre; graph[node][pre] = 0; graph[pre][node] = 0; for (int i = 1; i <= n; ++i) { if (graph[node][i] == 1) { DFS(i, node); } } graph[node][pre] = 1; graph[pre][node] = 1; } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); int a, b; for (int i = 0; i < n – 1; ++i) { scanf("%d %d", &a, &b); graph[a][b] = 1; graph[b][a] = 1; } DFS(k, 0); for (int i = 1; i <= n; ++i) printf("%d ", parent[i]); return 0; } [/cpp] 本代码提交AC,用时42MS。]]>

LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them. Two trees are duplicate if they have the same structure with same node values. Example 1: 

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
The following are two duplicate subtrees:
      2
     /
    4
and
    4
Therefore, you need to return above trees’ root in the form of a list.
给定一棵二叉树,要求找出其中的重复子树,每组重复子树输出其中一个子树即可。 去重最好的办法就是hash,所以思想是把每个子树hash到一个unordered_map中,如果有多个子树hash到同一个桶,则出现了重复。 所以问题的关键是怎样对一个子树hash。我们可以把一棵子树表示成 (left_hash, root, right_hash),其中left_hash和right_hash分别是左子树和右子树的hash字符串,root表示当前根节点的hash字符串。所以这是一个递归定义。规定空节点的hash值为空串””。 根据子树hash的定义,叶子节点的hash值是(“”,val,””)。求解子树hash值的过程可以用中序遍历,左根右。为什么子树hash中需要逗号和括号呢,就是为了保证不同严格区分不同的子树,因为单纯的中序遍历是无法区分某些子树的,比如下面的两个子树,中序遍历结果都是2,1,无法区分;但是用本文的hash方法,得到的hash值分别是(2,1,)和(,2,1),这两个字符串是有区别的。
  1
 /
2
 2
  \
   1
在DFS的过程中,把每个子树的hash值记录到一个unordered_map中,然后遍历unordered_map,如果该桶放了多个子树,则取出其中一个即可。 完整代码如下: [cpp] class Solution { private: string DFS(TreeNode* root, unordered_map<string, vector<TreeNode*>>& inorders) { if (root == NULL)return ""; string left = DFS(root->left, inorders); string right = DFS(root->right, inorders); string cur = "(" + left + "," + to_string(root->val) + "," + right + ")"; inorders[cur].push_back(root); return cur; } public: vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) { unordered_map<string, vector<TreeNode*>> inorders; DFS(root, inorders); vector<TreeNode*> ans; for (auto &it : inorders) { if (it.second.size() > 1) ans.push_back(it.second[0]); } return ans; } }; [/cpp] 本代码提交AC,用时52MS。]]>

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了,则剩余的商品只能按原价购买,算出按原价购买的费用即可。 完整代码如下: [cpp] 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); } }; [/cpp] 本代码提交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的和。 完整代码如下: [cpp] 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); } }; [/cpp] 本代码提交AC,用时172MS。]]>

LeetCode Clone Graph

133. 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.

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:

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).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Example 4:

Input: adjList = [[2],[1]]
Output: [[2],[1]]

Constraints:

  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • Number of Nodes will not exceed 100.
  • There is no repeated edges and no self-loops in the graph.
  • The Graph is connected and all nodes can be visited starting from the given node.

给定一个无向图,要求克隆一个一样的图,也就是深拷贝。 图的问题,想到应该是DFS或者BFS,但是没太想明白,因为DFS过程中可能遇到之前已经new过的节点,不知道怎么判断比较好,查看讨论区,发现每new一个节点,把这个节点存到一个hash表中就好了,下回先查hash表,不中才new新的。 因为每个节点的label是unique的,所以hash的key可以是label,value是node*。 完整代码如下,注意第9行,new出来的节点要先加入hash,再递归DFS,否则递归DFS在hash表中找不到当前的节点,比如{0,0,0}这个样例就会出错。

class Solution {
private:
    unordered_map<int, UndirectedGraphNode*> graph;
public:
    UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node)
    {
        if (node == NULL)
            return NULL;
        if (graph.find(node->label) != graph.end())
            return graph[node->label];
        UndirectedGraphNode* cur = new UndirectedGraphNode(node->label);
        graph[cur->label] = cur;
        for (auto& n : node->neighbors) {
            cur->neighbors.push_back(cloneGraph(n));
        }
        return cur;
    }
};

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

二刷。换了代码模板,方法是一样的,Hash+DFS:

class Solution {
public:
	Node* clone(Node* node, unordered_map<int, Node*> &hash) {
		int val = node->val;
		if (hash.find(val) != hash.end())return hash[val];
		Node *cp = new Node(node->val);
		hash[val] = cp;
		for (int i = 0; i < node->neighbors.size(); ++i) {
			int child = node->neighbors[i]->val;
			if (hash.find(child) != hash.end()) {
				cp->neighbors.push_back(hash[child]);
			}
			else {
				cp->neighbors.push_back(clone(node->neighbors[i], hash));
			}
		}
		return cp;
	}

	Node* cloneGraph(Node* node) {
		if (node == NULL)return NULL;
		unordered_map<int, Node*> hash;
		return clone(node, hash);
	}
};

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

LeetCode Surrounded Regions

130. 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.

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

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.


给定一个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。