Few leetcode solutions

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

class Queue {
private:
stack<int> s1,s2 ;

public:
// Push element x to the back of queue.
void push(int x) {
while(!s1.empty())
{

int top=s1.top();
s1.pop();
s2.push(top);
}
s1.push(x);
while(!s2.empty())
{

int top=s2.top();
s2.pop();
s1.push(top);
}
}

// Removes the element from in front of queue.
void pop(void) {
if(!s1.empty())
s1.pop();

}

// Get the front element.
int peek(void) {
if(!s1.empty())
return s1.top();
else
return 0;
}

// Return whether the queue is empty.
bool empty(void) {
if(s1.empty())
return true;
else
return false;
}
};

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

int majorityElement(vector<int>& nums) {
unordered_map<int,int> hsh;
for(int i=0 ; i < nums.size();i++)
{
if(hsh.find(nums[i]) ==hsh.end())
{
hsh[nums[i]]=1;
if(nums.size() ==1) return nums[i];
}
else
{
int count =hsh[nums[i]];
if((count +1) > (nums.size()/2))
return nums[i];
else
hsh[nums[i]]=++count;
}
}
}

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

int singleNumber(vector<int>& nums) {
int result = 0;
int n = nums.size();

int x, sum;
int size=sizeof(int)*16;// for 64 bit
// Iterate through every bit
for (int i = 0; i < size; i++)
{
// Find sum of set bits at ith position in all
// elements
sum = 0;
//way to check bits
x = (1 << i);
for (int j=0; j< n; j++ )
{
if (nums[j] & x)
sum++;
}

// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if (sum % 3)
result |= x;
}

return result;
}

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

int searchInsertUtil(vector<int>& nums, int target, int start , int end) {
int mid =(end+start)/2 ;
if(target < nums[mid])
{
if(mid != start )
return searchInsertUtil(nums,target,0,mid-1);
return mid;
}
else if(target > nums[mid])
{
if(mid !=end)
return searchInsertUtil(nums,target,mid+1,end);
else return mid+1;
}
else
return mid;
}
int searchInsert(vector<int>& nums, int target) {
return searchInsertUtil(nums, target,0 , nums.size()-1);
}

Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> hsh;
for(int i=0 ; i < nums.size();i++)
{
if(hsh.find(nums[i]) == hsh.end())
{
hsh.insert(make_pair(nums[i],nums[i]));
}
else
return true;
}
return false;
}

Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28

int titleToNumber(string s) {
//if(s==NULL) return 0;
int length=s.length();
int nBit=0,sum=0;
for(int i=length-1;i>=0;i--)
{
sum+=(pow(26,nBit)*(s[i]-'A'+1));
nBit++;
}
return sum;
}

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

int hammingWeight(uint32_t n) {
int count =0 ;
while(n!=0)
{
n=n&(n-1);
count ++;
}
return count;
}

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

For this problem, we can consider the time when S enter the loop for the 1st time, which we assume k step from the head. At this time, the F is already in k step ahead in the loop. When will they meet next time?
Still solve the function: t mod n = (k + 2t) mod n
Finally, when t = (n-k), S and F will meet, this is k steps before the start of the loop.

ListNode *detectCycle(ListNode *head) {

if(head == NULL || head->next==NULL ) return NULL;
ListNode* slow =head, *fast=head;

slow=head->next;
fast=head->next->next;
if(head !=NULL && head->next !=NULL)
{
while( fast && fast->next )
{
if(slow == fast)
{
fast=head;
while(slow->val != fast->val)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
slow=slow->next;
fast=fast->next->next;

}
}
return NULL;
}

Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

void setZeroes(vector<vector<int>>& matrix) {
int col=matrix[0].size();
int row=matrix.size();
multimap<int,int> hsh ;
for(int i=0 ; i < row;i++)
{
for(int j=0 ; j < col;j++)
{
if(matrix[i][j]==0)
{
hsh.insert(make_pair(i,j));
//break;
}
}
}
multimap<int,int>::iterator itr=hsh.begin();
while(itr != hsh.end())
{
for(int i=0 ; i < col;i++)
{
matrix[(*itr).first][i]=0;
}
for(int i=0 ; i < row;i++)
{
matrix[i][(*itr).second]=0;
}
itr++;
}

}

<strong>[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
</strong>

bool searchMatrix(vector<vector<int>>& matrix, int target) {
int col = matrix[0].size()-1;
int row=0;
while(col >=0 && row < matrix.size())
{
if(target < matrix[row][col])
col--;
else if(target > matrix[row][col])
row++;
else
return true;
}
return false;
}

Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

• You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8] Output: 167  <strong>Explanation: </strong>nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []   coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

Solution in Java8 :

Get the dp equation for continuous subarray solution of all sizes after appending ballon of weight 1 on both sides of the array.

For size 1 , answer is left * val1 * right

So dp[1][1] =131=3

dp[2][2]=315

dp[3][3]=158

dp[4][4]=581

Now for size 2

dp[1][2] = max(Case1(1st element is last to burst) ,Case2(2nd element is last to burst))

Case1 = leftlastright + last2nd elementright=135 (by the tie first is burst , second is already gone)+315(since when second is burst first , first is already there)

Case2=115+131 So, dp[1][2] as max of 2 cases is 30.

public class BaloonBurst {

public static int maxCoins(int[] arr) {

int n = arr.length;
int[] nums = new int[n+2];
nums[0]=1;
nums[n+1]=1;
for(int i=0; i< arr.length;i++){
nums[i+1]=arr[i];
}

int[][] dp = new int[n+2][n+2];
for(int length =1 ; length <n+1 ; length++)
{
for(int left=1 ; left < n-length+2;left++)
{
int right= left + length-1;
for(int last=left; last < right+1; last++)
{
dp[left][right]=max(dp[left][right],
dp[left][last-1]+ nums[left-1]nums[last]nums[right+1]+
dp[last+1][right]);
System.out.println(dp[left][right]);
}
}
}
return(dp[1][n]);

}

public static void main (String[] args) throws java.lang.Exception {
int[] intArray = new int[]{3,1,5,8 };
//int[] intArray = new int[]{1,2,3,4,5 };
System.out.println(maxCoins(intArray));
}

}