Leetcode: Word pattern (0ms)

Difficulty: Easy

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Credits:
Special thanks to @minglotus6 for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Hash Table

Show Similar Problems

---------------------------------------

---------------------------------------

1. Using two hash table to record the frequency map. Note that we should check every time when updating the frequency map as:

  a   a   b.....

  aa bb aa.....

has the same frequency map but the mapping is wrong!

2. A good way to extract the string from "aa bb aa ....." is to use "istringstream", some notes about how to use it:

//////////////////////////////////////////

       string str = "qq cc ddd";

       istringstream stream(str);

       int a;

       while (stream >> a){

              cout << a << endl;

       }

///////////////////////////

The output will be 

qq

cc

ddd

And then the loop will terminate automatically. 

///////////////////////////////////////////////////////////////

//codes

       class Solution {

       public:

              bool wordPattern(string pattern, string str) {

                     map<char, int> pat;

                     map<string, int> st;

                     istringstream istr(str);

                     string tmp;

                     int i = 0;

                     while (istr >> tmp){

                           //if # of pattern is shorter

                           if (i == pattern.size())return false;

                           //compose the frequency map

                           pat[pattern[i]]++;

                           st[tmp]++;

                           //check frequency for each step

                           if (pat.find(pattern[i])->second != st.find(tmp)->second)return false;

                           i++;

                     }

                     //if # of pattern is longer

                     if (i<pattern.size())return false;

                     return true;

              }

       };

Leetcode: Bulls and Cows

Difficulty: Easy

You are playing the following Bulls and Cows game with your friend: You write a 4-digit secret number and ask your friend to guess it. Each time your friend guesses a number, you give a hint. The hint tells your friend how many digits are in the correct positions (called "bulls") and how many digits are in the wrong positions (called "cows"). Your friend will use those hints to find out the secret number.

For example:Secret number: "1807" Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)


Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".

Please note that both secret number and friend's guess may contain duplicate digits, for example:Secret number: "1123" Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".



You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.




---------------------------------------------------

-----------------------------------------------------


Make sure you understand the problem:

how many digits are in the correct positions (called "bulls") and how many digits are in the wrong positions (called "cows")!!

Only when they have the same number but not in the same place, in such case there digits can be counted as cows. 

1. Count the number of bulls in the first run. In the same time, build the frequency map for secret array (bull digits not counted in!) and build a tmp string to store all digits without the bulls. 

2. based on the tmp string, deduct the frequency map to count the # of cows. 

////////////////////////////////////////////////

//codes

class Solution {

 public:

        string getHint(string secret, string guess) {

               //find bulls

               unordered_map<char, int> count;

               unsigned bull = 0, cow = 0;

               string tmp;//store all potential cows in guess

               for (int i = 0; i<secret.size(); i++){

                      if (secret[i] == guess[i]) bull++;

                      else{

                            count[secret[i]]++;//store all potential cows in secret

                            tmp += guess[i];

                      }

               }

               //count cow

               for (int i = 0; i<tmp.size(); i++){

                      if (count.find(tmp[i]) != count.end() && count[tmp[i]]>0){

                             cow++;

                            count[tmp[i]]--;

                      }

               }

               //output

               string bu = to_string(bull), co = to_string(cow);

               string final = bu + 'A' + co + 'B';

               return final;

        }

 };

Leetcode: Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Hash Table Math

---------------------------------------------------------------

---------------------------------------------------------------

1. Using normal dividing method: 

    0.16  
6 ) 1.00
    0 
    1 0       <-- Remainder=1, mark 1 as seen at position=0.
    - 6 
      40      <-- Remainder=4, mark 4 as seen at position=1.
    - 36 
       40      <-- Remainder=4 was seen before at position=1, 
so the fractional part which is 16 starts repeating at position=1 => 1(6).

2. take care the extreme input case:

-2147483648 / -1 ---in such case, it should be use long long to deal with it.

related information about above case:

~~~~~~~~~~~~~~~~~~~~`

Practically, this occurs when the programmer is trying to express the minimum integer value, which is -2147483648. This value cannot be written as -2147483648 because the expression is processed in two stages:

1. The number 2147483648 is evaluated. Because it is greater than the maximum integer value of 2147483647, the type of 2147483648 is not int, but unsigned int.
2. Unary minus is applied to the value, with an unsigned result, which also happens to be 2147483648.

The unsigned type of the result can cause unexpected behavior. If the result is used in a comparison, then an unsigned comparison might be used, for example, when the other operand is an int. This explains why the example program below prints just one line.

The expected second line, 1 is greater than the most negative int, is not printed because ((unsigned int)1) > 2147483648 is false.

~~~~~~~~~~~~~~~~~~~~

//////////////////////////////////////////////////

//code

class Solution {

 public:

        string fractionToDecimal(long long numerator, long long denominator) {

               string final;

               //sign

               if (numerator<0 && denominator>0 || numerator>0 && denominator<0) final.push_back('-');

               //integer part

               long long inte = numerator / denominator;

               final += to_string(inte);

               //fraction part       

               inte = (numerator%denominator) * 10;

               if (inte == 0)return final;

               else final += '.';

               unordered_map<long long, char> remain;

               while (inte != 0){

                      if (remain.find(inte) == remain.end()) {

                            long long tmp = inte / denominator;

                            remain[inte] = tmp + '0';

                      }

                      else{

                            //there is repeating

                            for (unordered_map<long long, char>::iterator it = remain.begin(); it != remain.end(); it++){

                                   if (it->first != inte){

                                          final += it->second;

                                   }

                                   else{

                                          final += '(';

                                          final += it->second;

                                   }

                            }

                            final += ')';

                            return final;

                      }

                      inte = inte%denominator * 10;

               }

               //no repeating

               for (unordered_map<long long, char>::iterator it = remain.begin(); it != remain.end(); it++)final += it->second;

               return final;

        }

 };

Leetcode: Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Subscribe to see which companies asked this question

Hide Tags

 Hash Table Math

-------------------------------------
-------------------------------------

Set point(i,j) as the base, calculate the slope between all the other points and the base point(i,j). Then check how many points have the same slope and therefore we can find the temporal max number. Repeat each point as the base and in the final we can find out the global maximal.
Note: the base point should be counted into as well;
          the duplicate points of point(i,j) should be also counted into.


/////////////////////////////////////////////////
//whole project

#include "stdafx.h"

# include <cstdlib>

#include <iostream>     // std::cout

#include <algorithm>    // std::sort

#include <vector>       // std::vector

# include <map>         // std::map

# include <unordered_map>

# include <string>

#include <bitset>

#include <ctype.h>

using namespace std;

 //Definition for a point.

 struct Point {

     int x;

     int y;

     Point() : x(0), y(0) {}

     Point(int a, int b) : x(a), y(b) {}

 };

 class Solution {

 public:

        int maxPoints(vector<Point>& points) {

               //check input

               if (points.size()<3)return points.size();

               //loop

               map<float, int> mSlop;

               int maxNum = 0, len = points.size();

               float slop = 0;

               for (int i = 0; i<len; i++){

                      int count = 0;

                      for (int j = 0; j<len; j++){

                            if (i != j){

                                   if (points[j].y == points[i].y && points[j].x == points[i].x){

                                          count++;

                                          continue;

                                   }

                                   slop = points[j].x - points[i].x == 0 ? INT_MAX : (points[j].y - points[i].y) / (points[j].x - points[i].x);

                                   mSlop[slop]++;

                            }

                      }

                      //find the current max in current loop

                      int curMax = 0;

                      for (map<float, int>::iterator it = mSlop.begin(); it != mSlop.end(); it++){

                            curMax = max(curMax, it->second);

                      }

                      curMax += count;

                      //the max up to now

                      maxNum = maxNum>curMax ? maxNum : curMax;

                      mSlop.clear();

               }

               maxNum++;//itself

               return maxNum;

        }

 };

int main(int argc, char *argv[])

{

       Point *one1 = new Point(-4,-1);

       Point *one2 = new Point(-7,7);

       Point *one3 = new Point(-1,5);

       Point *one4 = new Point(9,-25);

       vector<Point> in;

       in.push_back(*one1);

       in.push_back(*one2);

       in.push_back(*one3);

       in.push_back(*one4);

       Solution s;

       int f = s.maxPoints(in);

}