Another Casual Coder

Another problem involving Priority Queues. Key point here is to create the weight that includes the value and the index. Standard way of doing that would be value*[MaxIndex + constant] + index. Use a hash table to mark the used cells and neighbors. Code is down below, cheers, ACC.

Find Score of an Array After Marking All Elements - LeetCode

Input: nums = [2,1,3,4,5,2]
Output: 7
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,1,3,4,5,2].
- 2 is the smallest unmarked element, so we mark it and its left adjacent element: [2,1,3,4,5,2].
- 4 is the only remaining unmarked element, so we mark it: [2,1,3,4,5,2].
Our score is 1 + 2 + 4 = 7.

Input: nums = [2,3,5,1,3,2]
Output: 5
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,5,1,3,2].
- 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [2,3,5,1,3,2].
- 2 is the only remaining unmarked element, so we mark it: [2,3,5,1,3,2].
Our score is 1 + 2 + 2 = 5.

public class Solution {
 public long FindScore(int[] nums)
 {
 PriorityQueue pQueue = new PriorityQueue(true);
 for (int i = 0; i < nums.Length; i++)
 {
 double weight = nums[i] * (1000000.0 + 7) + i;
 pQueue.Enqueue(i, weight);
 }
 long score = 0;
 Hashtable marked = new Hashtable();
 while (pQueue.Count > 0)
 {
 double tempPriority = 0;
 int index = (int)pQueue.Dequeue(out tempPriority);
 if (!marked.ContainsKey(index))
 {
 score += (long)nums[index];
 for (int i = index - 1; i <= index + 1; i++)
 if (!marked.ContainsKey(i)) marked.Add(i, true);
 }
 }
 return score;
 }
}
public class PriorityQueue
{
 public struct HeapEntry
 {
 private object item;
 private double priority;
 public HeapEntry(object item, double priority)
 {
 this.item = item;
 this.priority = priority;
 }
 public object Item
 {
 get
 {
 return item;
 }
 }
 public double Priority
 {
 get
 {
 return priority;
 }
 }
 }
 private bool ascend;
 private int count;
 private int capacity;
 private HeapEntry[] heap;
 public int Count
 {
 get
 {
 return this.count;
 }
 }
 public PriorityQueue(bool ascend, int cap = -1)
 {
 capacity = 10000000;
 if (cap > 0) capacity = cap;
 heap = new HeapEntry[capacity];
 this.ascend = ascend;
 }
 public object Dequeue(out double priority)
 {
 priority = heap[0].Priority;
 object result = heap[0].Item;
 count--;
 trickleDown(0, heap[count]);
 return result;
 }
 public object Peak(out double priority)
 {
 priority = heap[0].Priority;
 object result = heap[0].Item;
 return result;
 }
 public object Peak(/*out double priority*/)
 {
 //priority = heap[0].Priority;
 object result = heap[0].Item;
 return result;
 }
 public void Enqueue(object item, double priority)
 {
 count++;
 bubbleUp(count - 1, new HeapEntry(item, priority));
 }
 private void bubbleUp(int index, HeapEntry he)
 {
 int parent = (index - 1) / 2;
 // note: (index > 0) means there is a parent
 if (this.ascend)
 {
 while ((index > 0) && (heap[parent].Priority > he.Priority))
 {
 heap[index] = heap[parent];
 index = parent;
 parent = (index - 1) / 2;
 }
 heap[index] = he;
 }
 else
 {
 while ((index > 0) && (heap[parent].Priority < he.Priority))
 {
 heap[index] = heap[parent];
 index = parent;
 parent = (index - 1) / 2;
 }
 heap[index] = he;
 }
 }
 private void trickleDown(int index, HeapEntry he)
 {
 int child = (index * 2) + 1;
 while (child < count)
 {
 if (this.ascend)
 {
 if (((child + 1) < count) &&
 (heap[child].Priority > heap[child + 1].Priority))
 {
 child++;
 }
 }
 else
 {
 if (((child + 1) < count) &&
 (heap[child].Priority < heap[child + 1].Priority))
 {
 child++;
 }
 }
 heap[index] = heap[child];
 index = child;
 child = (index * 2) + 1;
 }
 bubbleUp(index, he);
 }
}