Welcome to Shanshan Blog!

• Leetcode (65) Valid Number

  2017-02-26

  Leetcode

  Leetcode
  • Leetcode 65. Valid Number

  Leetcode 65. Valid Number

  • Leetcode 65. Valid Number

  Validate if a given string is numeric.

  Some examples:

  "0" => true
  
  " 0.1 " => true
  
  "abc" => false
  
  "1 a" => false
  
  "2e10" => true
  

  Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

  class Solution {
  public:
      bool isNumber(string s) {
          int i = 0, k = 0;
          while (s[i]==' ')   i++;
          if (s[i]=='+' || s[i]=='-') i++;
          while (isdigit(s[i])) {
              i++;
              k++;
          }
          if (s[i]=='.')  i++;
          while (isdigit(s[i])) {
              i++;
              k++;
          }
          if (k==0)   return false;
          if (s[i]=='e') {
              i++, k = 0;  
              if(s[i]=='+' || s[i] == '-') i++;  
              while(isdigit(s[i])) i++, k++;  
              if(k == 0) return false;  
          }
          while(s[i] == ' ') i++;  
          return i == s.size();  
      }
  };
  

  Read All

  ---

• Leetcode (51, 52) N-Queen I, II

  2017-02-25

  Leetcode

  Leetcode
  • Leetcode 51. N-Queens
  • Leetcode 52. N-Queens II

  Leetcode N-Queen I, II

  Leetcode 51. N-Queens

  • Leetcode 51. N-Queens

  The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

  

  Given an integer n, return all distinct solutions to the n-queens puzzle.

  Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

  For example, There exist two distinct solutions to the 4-queens puzzle:

  ` [ [“.Q..”, // Solution 1 “…Q”, “Q…”, “..Q.”],

  [”..Q.”, // Solution 2 “Q…”, “…Q”, “.Q..”] ] `

  class Solution {
  public:
      void helper(int row, int col, int dia, int back_dia, vector<vector<string>> &res, vector<string> &board, int n) {
          if (row==n) {
              res.push_back(board);
              return;
          }
          for (int i=0; i<n; i++) {
              int curr = 1<<i;
              if (curr&col || curr&back_dia || curr&dia)   continue;
              board[row][i] = 'Q';
              helper(row+1, col|curr, (dia|curr)>>1, (back_dia|curr)<<1,  res, board, n);
              board[row][i] = '.';
          }
      }
      
      vector<vector<string>> solveNQueens(int n) {
          string dots(n, '.');
          vector<string> board(n, dots);
          vector<vector<string>> res;
          helper(0, 0, 0, 0, res, board, n);
          return res;
      }
  };
  

  Leetcode 52. N-Queens II

  • Leetcode 52. N-Queens II

  Follow up for N-Queens problem.

  Now, instead outputting board configurations, return the total number of distinct solutions.

  class Solution {
  public:
      void helper(int row, int col, int dia, int back_dia, int n, int &count) {
          if (row==n) {
              count++;
              return;
          }
          for (int i=0; i<n; i++) {
              int curr = 1<<i;
              if (curr&col || curr&back_dia || curr&dia)   continue;
              helper(row+1, col|curr, (dia|curr)>>1, (back_dia|curr)<<1, n, count);
          }
      }
      
      int totalNQueens(int n) {
          int count = 0;
          helper(0, 0, 0, 0, n, count);
          return count;
      }
  };
  

  Read All

  ---

• Python Cheatsheet: Decorator

  2017-02-24

  Python

  Python
  • Why Decorator
  • Decorator with parameter
    • Inner Decorator

  Why Decorator

  Assume we has a function called myfunc, we wanna to call the function in another function. So

  

  In this way, every time you have to use “deco(myfunc)”.

  That’s why we use the decorator.

  

  “@deco” means “myfunc = deco(myfunc)”

  Decorator with parameter

  

  “addFunc(3, 8) = deco(True)( addFunc(3, 8))”, “myFunc() = deco(False)( myFunc ())”

  Inner Decorator

  In python, there are three inner decorator: staticmethod, classmethod, property.

  • staticmethod: the difference with method in class is without self. And it can be used without the object.

  • classmethod: the difference with method in class is the first parameter is clf, instead of self.

  • property: to get the values in class.

  

  Read All

  ---

• Python Cheatsheet: Regular Expression

  2017-02-23

  Python

  Python
  • re module
  • HTML tags
  • re.findall()
  • Substitute String
  • Full

  re module

  Python re module provides regular expression functions.

  # -*- coding: UTF-8 -*-
  import re
  
  # re.match
  print(re.match('www', 'www.runoob.com').span())
  print(re.match('com', 'www.runoob.com'))
  
  # re.search
  ## partner
  key = r"<html><body><h1>hello world<h1></body></html>"
  p1 = r"(?<=<h1>).+?(?=<h1>)"## regular expression
  pattern1 = re.compile(p1)
  match1 = re.search(pattern1, key)
  print match1.group(0)
  
  # re.match means if the string is not match the pattern at the begining, then fail, return None
  # re.search will search the whole string to find all
  
  
  #re.sub to replace the match part
  phone = "2004-959-559 # 这是一个国外电话号码"
  
  # delete python comment
  num = re.sub(r'#.*$', "", phone)
  print "电话号码是: ", num
  
  # delete -
  num = re.sub(r'\D', "", phone)
  print "电话号码是 : ", num
  

  HTML tags

  

  re.findall()

  # split all string
  source = "Hello World Ker HAHA"
  print re.findall('[\w]+', source)
  
  import urllib
  s = urllib.urlopen('https://www.python.org')
  html = s.read()
  s.close()
  print re.findall('<[^/>][^>]*>', html)[0:2]
  

  Substitute String

  # Substitute String
  res = "1a2b3c"
  print re.sub(r'[a-z]',' ', res)
  # substitute with group reference
  date = r'2016-01-01'
  print re.sub(r'(\d{4})-(\d{2})-(\d{2})',r'\2/\3/\1/',date)
  

  Full

  

  Read All

  ---

• Leetcode (54) Spiral Matrix I, II

  2017-02-22

  Leetcode

  Leetcode
  • Leetcode 54. Spiral Matrix
  • Leetcode 59. Spiral Matrix II

  Leetcode Spiral Matrix

  Leetcode 54. Spiral Matrix

  • Leetcode 54. Spiral Matrix

  Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

  For example, Given the following matrix:

  [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

  You should return [1,2,3,6,9,8,7,4,5].

  class Solution {
  public:
      vector<int> spiralOrder(vector<vector<int>>& matrix) {
          vector<int> res;
          if (matrix.empty()) return res;
          const int m = matrix.size();
          const int n = matrix[0].size();
          int left = 0, right = n-1, up = 0, down = m-1, dir = 0;
          for (int k=0, i=0, j=0; k<m*n; k++) {
              res.push_back(matrix[i][j]);
              if (dir == 0) {
                  if (j==right) {
                      i++;
                      dir = 1;
                      up++;
                  }
                  else    j++;
              }  else if (dir == 1) {
                  if (i==down) {
                      j--;
                      dir = 2;
                      right--;
                  } 
                  else  i++;
              } else if (dir == 2) {
                  if (j==left) {
                      dir = 3;
                      i--;
                      down--;
                  }
                  else    j--;
              } else {
                  if (i==up) {
                      dir = 0;
                      j++;
                      left++;
                  }
                  else    i--;
              }
          }
          return res;
      }
  };
  

  Leetcode 59. Spiral Matrix II

  • Leetcode 59. Spiral Matrix II

  Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

  For example, Given n = 3,

  You should return the following matrix:

  [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

  class Solution {
  public:
      vector<vector<int>> generateMatrix(int n) {
          vector<vector<int>> table(n, vector<int>(n, 0));
          int i = 0, j =0, k=1;
          while (k<=n*n) {
              while (j<n && table[i][j]==0)   table[i][j++] = k++;
              i++;j--;
              while (i<n && table[i][j]==0)   table[i++][j] = k++;
              i--;j--;
              while (j>=0 && table[i][j]==0)   table[i][j--] = k++;
              i--;j++;
              while (i>=0 && table[i][j]==0)   table[i--][j] = k++;
              i++;j++;
          }
          return table;
      }
  };
  

  Read All

  ---

• Leetcode (33) Wildcard Matching

  2017-02-21

  Leetcode

  Leetcode
  • Leetcode 44. Wildcard Matching

  Leetcode Matrix Series

  Leetcode 44. Wildcard Matching

  • Leetcode 44. Wildcard Matching

  Implement wildcard pattern matching with support for ‘?’ and ‘’. ` ‘?’ Matches any single character. ‘’ Matches any sequence of characters (including the empty sequence).

  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”, “”) → true isMatch(“aa”, “a”) → true isMatch(“ab”, “?”) → true isMatch(“aab”, “ca*b”) → false `

  class Solution {
  public:
      bool isMatch(string s, string p) {
          int i = 0, j = 0, asterick = -1;
          int match;
          while (i < s.size()) {
              if (j<p.size() && p[j]=='*') {
                  match = i;
                  asterick = j++;
              }
              else if (j<p.size() && (s[i]==p[j] || p[j]=='?')) {
                  i++;
                  j++;
              }
              else if (asterick >= 0) {
                  i = ++match;
                  j = asterick+1;
              }
              else    return false;
          }
          while (j<p.size() && p[j]=='*') j++;
          return j==p.size();
      }
  };
  

  Read All

  ---