Как работает пара и вектор в реализации Graph?
Мой ответ может быть слишком поздним, но для версии Swift (любой), это будет, безусловно, полезно и очень легко использовать.
func tableView(_ tableView: UITableView, willDisplay cell: UITableViewCell, forRowAt indexPath: IndexPath) {
if (tableView == self.tableViewMovies) {
//Top Left Right Corners
let maskPathTop = UIBezierPath(roundedRect: cell.bounds, byRoundingCorners: [.topLeft, .topRight], cornerRadii: CGSize(width: 5.0, height: 5.0))
let shapeLayerTop = CAShapeLayer()
shapeLayerTop.frame = cell.bounds
shapeLayerTop.path = maskPathTop.cgPath
//Bottom Left Right Corners
let maskPathBottom = UIBezierPath(roundedRect: cell.bounds, byRoundingCorners: [.bottomLeft, .bottomRight], cornerRadii: CGSize(width: 5.0, height: 5.0))
let shapeLayerBottom = CAShapeLayer()
shapeLayerBottom.frame = cell.bounds
shapeLayerBottom.path = maskPathBottom.cgPath
if (indexPath as NSIndexPath).section == 0 {
if indexPath.row == 0 {
cell.layer.mask = shapeLayerTop
}else if indexPath.row == 2 {
cell.layer.mask = shapeLayerBottom
}
}else if (indexPath as NSIndexPath).section == 1 {
if indexPath.row == 0 {
cell.layer.mask = shapeLayerTop
}else {
cell.layer.mask = shapeLayerBottom
}
}else if (indexPath as NSIndexPath).section == 2 {
if indexPath.row == 0 {
cell.layer.mask = shapeLayerTop
}else if indexPath.row == 2 {
cell.layer.mask = shapeLayerBottom
}
}
}
}
PS: Я использовал следующий код для Swift 3.0.
1 ответ
Давайте посмотрим на это шаг за шагом:
vector<pair<int,int>>adj[1001];
Создание массива размером 1001 вектора. Это эквивалентно наличию list of edges для каждой вершины, базовой концепции списка смежности.
Здесь используется пара, потому что список смежности должен быть отсортирован на основе значения, и если значение одинаково, то следует учитывать индекс.
int values[100001];
int n,m,k,x,y;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
cin>>values[i];
}
Приведенный выше код получает значения из стандартного ввода.
for(int i=0;i<m;i++)
{
cin>>x>>y;
adj[x-1].push_back({values[y-1],y-1}); //problem-1
adj[y-1].push_back({values[x-1],x-1});
}
Здесь вы создаете неориентированный граф с x, имеющим ребро к y, и наоборот.
for(int i=0;i<n;i++)
{
sort(adj[i].begin(),adj[i].end());
}
Сортировка каждого списка смежности в порядке возрастания значений. Если значение одинаковое, сравните индекс
int adj_size=0;
for(int i=0;i<n;i++)
{
adj_size=adj[i].size();
if(k>adj_size)
cout<<-1<<"\n";
else
cout<<(adj[i][adj_size-k].second)+1<<"\n"; //problem-2
}
Возвращает k-й элемент из конца списка смежности, если он существует. В противном случае верните -1.
Наблюдение:
Я думаю, что этот код может не работать, если значения совпадают.
Вместо этого вы должны определить пользовательский компаратор в sort.
Вот так:
sort(adj[i].begin(),adj[i].end(), [](const pair<int, int> &p1, const pair<int, int> &p2) {
if (p1.first != p2.first) {
return p1.first > p2.first;
}
return p1.second < p2.second;
});
И вернуть k-й элемент с самого начала.
Предложение:
Вместо того, чтобы использовать этот подход, я думаю, вы должны пойти на Maxheap.