Drucken Clam's Coding Blog

Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. Solution C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { bool isValid( int board[], int row) { for ( int i = 0 ; i < row; ++ i) { if (board[i] == board[row]) return false ; if (abs(board[i] - board[row]) == row - i) return false ; } return true ; } void nQueen( int n, int row, int board[], int & ret) { if (row == n) { ret ++ ; } else { for ( int i = 0 ; i < n; ++ i) { board[row] = i; if (isValid(board, row)) { nQueen(n, row + 1 , board, ret); } } } } public: int totalNQueens( int n) { int board[n]; for ( int i = 0 ; i < n; +...

There are two sorted arrays  nums1  and  nums2  of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Solution C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { private: double intFindMedianSortedArrays(vector < int >& nums1, int low1, int high1, vector < int >& nums2, int low2, int high2, int k) { if (high1 - low1 > high2 - low2) { return intFindMedianSortedArrays(nums2, low2, high2, nums1, low1, high1, k); } if (low1 > high1) { return nums2[low2 + k - 1 ]; } if (k == 1 ) { return min(nums1[low1], nums2[low2]); } int na = min(k / 2 , high1 - low1 + 1 ); int nb = k - na; if (nums1[low1 + na - 1 ] > nums2[low2 + nb - 1 ]) { ...

Say you have an array for which the  i th  element is the price of a given stock on day  i . Design an algorithm to find the maximum profit. You may complete at most  k  transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: int maxProfit( int k, vector < int >& prices) { const int N = prices.size(); if (N == 0 ) return 0 ; if (k >= N - 1 ) { int ret = 0 ; for ( int i = 1 ; i < N; ++ i) { if ((prices[i] - prices[i - 1 ]) > 0 ) { ret += prices[i] - prices[i - 1 ]; } } return ret; } // maxProfits[i][j] max profits at most i transactions from day 0 to day j ...

The demons had captured the princess ( P ) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight ( K ) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health ( negative  integers) upon entering these rooms; other rooms are either empty ( 0's ) or contain magic orbs that increase the knight's health ( positive  integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. For example, given the dungeon below, the initial health of th...

Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range. Solution C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { void radixSort(vector < int >& num, int exp) { vector < int > output(num.size(), 0 ); int count[ 10 ] = { 0 }; for ( int n : num) { count[n / exp % 10 ] ++ ; } for ( int i = 1 ; i < 10 ; ++ i) { count[i] += count[i - 1 ]; } for ( auto it = num.rbegin(); it != num.rend(); ++ it) { output[count[ * it / exp % 10 ] - 1 ] = * it; count[ * it / exp % 10 ] -- ; } num = output; }...

Implement regular expression matching with support for  '.'  and  '*' . '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true Solution C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public: bool isMatch(string s, string p) { if (s == p) return true ; if (p.empty()) return false ; const int M = s.length(); ...

Follow up  for "Find Minimum in Rotated Sorted Array": What if  duplicates  are allowed? Would this affect the run-time complexity? How and why? Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.,  0 1 2 4 5 6 7  might become  4 5 6 7 0 1 2 ). Find the minimum element. The array may contain duplicates. Solution C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { int intFindMin(vector < int >& num, int low, int high) { while (low < high) { int mid = (low + high) / 2 ; if (num[mid] > num[mid + 1 ]) return num[mid + 1 ]; if (num[mid] == num[low] || num[mid] == num[high]) { return min(intFindMin(num, mid + 1 , high), intFindMin(num, low, mid)); } if (num[mid] > num[high]) { low = mid + 1 ; } else if (num[mid] ...

Given  n  points on a 2D plane, find the maximum number of points that lie on the same straight line. Solution C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 /** * Definition for a point. * struct Point { * int x; * int y; * Point() : x(0), y(0) {} * Point(int a, int b) : x(a), y(b) {} * }; */ struct VecHash { size_t operator () ( const pair < int , int >& p) const { hash < int > ()(p.first) ^ hash < int > ()(p.second); } }; class Solution { private: int gcd( int x, int y) { if (x < y) return gcd(y, x); while (y) { int tmp = y; y = x % y; x = tmp; } return x; } pair < int , int > reduceVec( int x, int y) { i...