LeetCode 11-20

LeetCode11 Container With Most Water

Given $N$ integers $a_1, a_2, \ldots, a_n$, where each defines a vertical line from $(i, 0)$ to $(i, a_i)$, find the maximum area enclosed by two such lines and the x-axis.

There is a similar problem later on. Use two-sided greediness: discard the shorter line each time for $O(n)$ time complexity.

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int sz=height.size();
        if(sz==0||sz==1)return 0;

        int le=0,ri=sz-1;
        int res=0;
        int weight=sz-1;
        while(le<ri)
        {
        	res=max(res,min(height[le],height[ri])*weight);
        	int h1=height[le];
        	int h2=height[ri];
        	if(h1<h2)
        	{
        		le++;
        	}
        	else
        	{
        		ri--;
        	}
        	weight--;
        }
        return res;
    }
}t;

LeetCode12 Integer to Roman

Convert an integer to its Roman-numeral string.

Process each digit: 0–3 follow one pattern, 4 another, 5–8 another, and 9 a final pattern.

class Solution
{
public:
	string intToRoman(int num)
	{
		int n[4] = { 1000,100,10,1 };
		char r5[4] = { ' ','D','L','V' };
		char r1[4] = { 'M','C','X','I' };

		string res = "";
		for (int i = 0; i < 4; i++)
		{
			int k = num / n[i];

			if (k == 9)
			{
				res = res + r1[i] + r1[i - 1];
			}
			else if (k == 4)
			{
				res = res + r1[i] + r5[i];
			}
			else if (k >= 5 && k <= 8)
			{
				res = res + r5[i];
				for (int j = 0; j < k - 5; j++)
				{
					res = res + r1[i];
				}
			}
			else
			{
				for (int j = 0; j < k; j++)
				{
					res = res + r1[i];
				}
			}
			num = num%n[i];
		}
		return res;
	}
};

LeetCode19 Remove Nth Node From End of List

Remove the nth node from the end of a linked list.

Keep two pointers n - 1 nodes apart. When the trailing pointer reaches the end, the leading pointer is at the node to remove.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
    	if(head==NULL)
    	{
    		return NULL;
    	}
    	ListNode *pre = NULL;
    	ListNode *p = head;
    	ListNode *q = head;
    	ListNode *res = head;
    	for(int i=0;i<n-1;i++)
    	{
    		q=q->next;
    	}

    	while(q->next)
    	{
    		pre=p;
    		p=p->next;
    		q=q->next;
    	}
    	if(pre)
    	{
    	     pre->next=p->next;   
    	}
    	else
    	{
    	     res=head->next;
    	}
    	return res;
	}
};