Welcome to Andy's Blog!

• LeetCode-Valid Parentheses

  2019-04-01

  LeetCode

  easy

  original problem link #Description Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

  An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

  Note that an empty string is also considered valid.

  Example 1:

  Input: “()” Output: true

  Example 2:

  Input: “()[]{}” Output: true

  Example 3:

  Input: “(]” Output: false

  Example 4:

  Input: “([)]” Output: false

  Example 5:

  Input: “{[]}” Output: true

  original solution #Solution Intuition 首先思考只有一种括号的情况，如(()()()()()),这种情况只要用计数器counter从左到右记录（的数量，遇见（就+1，遇见）就-1，遍历完成之后counter=0，那么输入的String就是valid。 Approach 1: Stacks 当表达式中有多种括号时，可以用stack，从左到右遍历是如果是左括号就入栈，如果遍历到了右括号，就把它和栈顶的左括号进行类型比较，如果类型相同，就pop栈顶的左括号，如果类型不同，那么String就是invalid。

  class Solution {
      public boolean isValid(String s) {
          Stack<Character> parenthese = new Stack<>();
          for(int i=0; i<s.length(); i++){
              if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                  parenthese.push(s.charAt(i));
              } else {
                  if(parenthese.isEmpty()) return false;
                  
                  if((s.charAt(i) == ')' && parenthese.peek().charValue() == '(') || (s.charAt(i) == ']' && parenthese.peek().charValue() == '[') || (s.charAt(i) == '}' && parenthese.peek().charValue() == '{')) {
                  parenthese.pop();
                  } else {
                      return false;
                  }
              }
          }
          return parenthese.isEmpty();
      }
  }
  

  Complexity Runtime: 2 ms, faster than 97.27% of Java online submissions for Valid Parentheses. O(n) Memory Usage: 35.4 MB, less than 37.23% of Java online submissions for Valid Parentheses. O(n)

  另一种代码实现：

  class Solution {
      private HashMap<Character, Character> map;
          
      public Solution() {
          this.map = new HashMap<Character, Character>();
          this.map.put(')', '(');
          this.map.put(']', '[');
          this.map.put('}', '{');
      }
          
      public boolean isValid(String s) {
          Stack<Character> stack = new Stack<>();
              
          for(int i=0; i<s.length(); i++) {
              char c = s.charAt(i);
                  
              if(this.map.containsKey(c)) {
                  char topElement = stack.empty() ? '#' : stack.pop();
                  if(topElement != map.get(c)) return false;
              } else {
                  stack.push(c);
              }
          }
              
          return stack.isEmpty();
      }
  }
  

  Complexity Runtime: 2 ms, faster than 97.27% of Java online submissions for Valid Parentheses. O(n) Memory Usage: 35.6 MB, less than 36.97% of Java online submissions for Valid Parentheses.O(n)

  class Solution {
      public boolean isValid(String s) {
  	Stack<Character> stack = new Stack<Character>();
          for (char c : s.toCharArray()) {
              if (c == '(')
                  stack.push(')');
              else if (c == '{')
                  stack.push('}');
              else if (c == '[')
                  stack.push(']');
              else if (stack.isEmpty() || stack.pop() != c)
                  return false;
          }
          return stack.isEmpty();
     }
  }
  

  Complexity Runtime: 1 ms, faster than 99.89% of Java online submissions for Valid Parentheses. O(n) Memory Usage: 35.6 MB, less than 36.92% of Java online submissions for Valid Parentheses. O(n)

  Read All

  ---

• Introduction_to_Computation-MIT6_0001F16_Lec6

  2019-03-28

  Introduction_to_Computation

  Python  recursion  dcitionary
  • WHAT IS RECURSION?
  • EXAMPLE OF RECURSION
    • Multiplication
      • Iterative Solution
      • Recursion Solution
    • Tower of Hanoi
    • Palindrome
    • Fibonacci

  第六节课，课程马上就要过半，还有点小伤感，但是也有坚持到现在到兴奋。这节课换了一个老师，Eric Grimson,MIT的名誉校长，由于下班回来太累，上课太晚没能看完，今天先做一半的记录，明天早上继续。

  WHAT IS RECURSION?

  Algorithmically: a way to design solutions to problems by divide-and-conquer or decrease-and-conquer

  • reduce a problem to simpler versions of the same problem

  Semantically: a programming technique where a function calls itself

  • in programming, goal is to NOT have infinite recursion
    • must have 1 or more base cases that are easy to solve
    • must solve the same problem on some other input with the goal of simplifying the larger problem input

  EXAMPLE OF RECURSION

  The algorithm of resusion is divided into two ways: 1.recursiv step: think how to reduce problem to a simpler/smaller version of same problem 2.base case: keep reducing problem until reach a simple case that can be solved directly.

  Multiplication

  Iterative Solution

  “multiply a * b” is equivalent to “add a to itself b itmes”

  def mult_iter(a, b):
      result = 0
      while b > 0;
          result += a
          b -= 1
      return result
  

  Recursion Solution

  def mult_recu(a, b):
      if b == 1:
          return a
      else:
          return a + mult_recu(a, b-1)
  

  Tower of Hanoi

  def printMove(fr, to):
      print('move form ' + str(fr) + ' to ' + str(to))
      
  def Towers(n, fr, to ,space):
      if n == 1:
          printMove(fr, to)
      else:
          Towers(n-1, fr, space, to)
          Towers(1, fr, to, space)
          Towers(n-1, space, to, fr)
  

  Palindrome

  def isPalindrome(s):
      def toChars(s):
          s = s.lower()
          ans = ''
          for c in s:
              if c in 'abcdefghijklmnopqrstuvwxyz':
                  ans += c
          return ans
      
      def isPal(s):
          if len(s) <= 1:
              return true
          else:
              return s[0] == s[-1] and isPal(s[1:-1])
      
      return isPal(toChars(s))
  

  Fibonacci

  def fib(x):
      if x == 0 or x == 1:
          return 1
      else:
          # fib(x-1) is the sum of the already existed rabbits in the last month
          # fib(x-2) is the sum of the new born rabbits in this month
          return fib(x-1) + fib(x-2)
  

  this code has two base cases and calls itself twice, the code is inefficient

  we can improve it by dictionary

  def fib_dic(x, d):
      if x in d:
          return d[x]
      else:
          ans = fib_dic(x-1, d) + fib_dic(x-2, d)
          d[x] = ans
          return ans
  
  d = {1:1, 2:2}
  print(fib_dic(6, d))
  

  EFFICIENCY GAINS

  • Calling fib(34) results in 11,405,773 recursive calls to the procedure
  • Calling fib_efficient(34) results in 65 recursive calls to the procedure
  • Using dicSonaries to capture intermediate results can be very efficient

  • But note that this only works for procedures without side effects (i.e., the procedure will always produce the same result for a specific argument independent of any other computaSons between calls)

  Read All

  ---

• Introduction_to_Computation-MIT6_0001F16_Lec5

  2019-03-27

  Introduction_to_Computation

  Python
  • Compound Data Types
    • Tuple
    • List
      • OPERATIONS ON LISTS
        • ADD
        • REMOVE
        • CONVERT
        • SORTED AND REVERSED
  • MUTATION, ALIASING, CLONING

  Ana教授的第五节课，还是那么通俗易懂，先分享一个学习编程很好的网站：http://pythontutor.com/（可能需要科学上网）本篇学习笔记某些截图出自该网站。

  Compound Data Types

  Tuple

  • an ordered sequence of elements, can mix element types
  • cannot change element values,immutable ()
  • represented with parentheses
  • conveniently used to swap variable values:
  • (x, y) = (y, x)

  List

  • ordered sequence of information, accessible by index
  • a list is denoted by square brackets, []
  • a list contains elements
  • usually homogeneous (ie, all integers)
  • can contain mixed types (not common)
  • list elements can be changed so a list is mutable

  OPERATIONS ON LISTS

  ADD

  • add elements to end of list with L.append(element) – mutates the list!
  • combine lists together use L.extend(some_list) – mutate list

  REMOVE

  • delete element at a specific index with del(L[index])
  • remove element at end of list with L.pop(), returns the removed element
  • remove a specific element with L.remove(element)
  • looks for the element and removes it
  • if element occurs multiple times, removes first occurrence
  • if element not in list, gives an error

  CONVERT

  • convert string to list with list(s), returns a list with every character from s an element in L
  • can use s.split(), to split a string on a character parameter, splits on spaces if called without a parameter
  • use ‘‘.join(L) to turn a list of characters into a string, can give a character in quotes to add char between every element

  SORTED AND REVERSED

  https://docs.python.org/3/tutorial/datastructures.html

  MUTATION, ALIASING, CLONING

  • lists are mutable
  • behave differently than immutable types
  • is an object in memory
  • variable name points to object
  • any variable pointing to that object is affected
  • key phrase to keep in mind when working with lists is side effects

  觉得slide很经典，很容易理解概念，就把几页slide截下了 avoid mutating a list as you are iterating over it

  Read All

  ---

• Introduction_to_Computation-MIT6_0001F16_Lec4

  2019-03-26

  Introduction_to_Computation

  Python
  • GOOD PROGRAMMING
    • CREATE STRUCTURE with DECOMPOSITION
    • SUPRESS DETAILS with ABSTRACTION
  • VARIABLE SCOPE

  离上一次上Ana的课已经过离半个月了，自己的执行力和自律性还是不够，继续努力。 很想在FLAG中的一家企业工作，这是现阶段的人生目标。

  GOOD PROGRAMMING

  • more code not necessarily a good thing
  • measure good programmers by the amount of functionality
  • introduce functions
  • mechanism to achieve decomposition and abstraction

  ABSTRACTION IDEA: do not need to know how projector works to use it DECOMPOSITION IDEA: different devices work together to achieve an end goal

  CREATE STRUCTURE with DECOMPOSITION

  in programming, divide code into modules • are self-contained • used to break up code • intended to be reusable • keep code organized • keep code coherent

  SUPRESS DETAILS with ABSTRACTION

  in programming, think of a piece of code as a black box • cannot see details • do not need to see details • do not want to see details • hide tedious coding details

  VARIABLE SCOPE

  • formal parameter gets bound to the value of actual parameter when function is called
  • new scope/frame/environment created when enter a function
  • scope is mapping of names to objects

  

  这节课内容主要就这些，最近也在看《Java核心技术卷一》，一本美国教授写的书，感受最大的不同在于《Java核心技术卷一》很像一本技术大全，几乎囊括了所有Java这门语言的知识点。而Ana上课给人的感觉是一种启发式，开放式的教学。教学内容看似很简单，但是对于MIT刚接触编程的人来说却是一门很好的入门课程，这大概就是教育真正的目的，教会学生找到自己的兴趣所在，激发最原始的求知欲而去自主学习。不得不说MIT真的是一所顶尖的学校，很想去看看，哪怕是旁听一门课程，也感觉此生无憾了。 感谢互联网，感谢MIT，感谢OCW。 我们生活在一个最好的时代。

  Read All

  ---

• Introduction_to_Computation-MIT6_0001F16_Lec3

  2019-03-08

  Introduction_to_Computation

  Python
  • STRINGS
  • GUESS-AND-CHECK
  • APPROXIMATE SOLUTIONS
  • BISECTION SEARCH
  • TODO

  第三节课，Ana讲得很好，继续边学英语边学python

  STRINGS

  • quare brackets used to perform indexing into a string to get the value at a certain index/position

    s = "abc"
    index: 0 1 2  #indexing always starts at 0 
    index: -3 -2 -1  #last element always at index -1
    

  • can slice strings using [start:stop:step]
  • strings are “immutable” – cannot be modified

    s = "hello"
    s[0] = 'y'  #gives an error 
    s = 'y'+s[1:len(s)] #is allowed,s bound to new object
    

  GUESS-AND-CHECK

  the process below also called exhaustive enumeration

  • given a problem…
  • you are able to guess a value for solution
  • you are able to check if the solution is correct
  • keep guessing until find solution or guessed all values

    cube = 8
    for guess in range(abs(cube)+1):
     if guess**3 >= abs(cube):
         break
    if guess**3 != abs(cube):
     print(cube, 'is not a perfect cube')
    else:
     if cube < 0:
         guess = -guess
     print('Cube root of '+str(cube)+' is '+str(guess))
    

  APPROXIMATE SOLUTIONS

  • good enough solution
  • start with a guess and increment by some small value

  • keep guessing if

    guess3-cube

    >= epsilon for some small epsilon

  • decreasing increment (size slower program)
  • increasing epsilon (less accurate answer)

    cube = 27
    epsilon = 0.01
    guess = 0.0
    increment = 0.0001
    num_guesses = 0
    while abs(guess**3 - cube) >= epsilon: and guess <= cube :
      guess += increment
      num_guesses += 1
    print('num_guesses =', num_guesses)
    if abs(guess**3 - cube) >= epsilon:
      print('Failed on cube root of', cube)
    else:
    print(guess, 'is close to the cube root of', cube)
    

  BISECTION SEARCH

  cube = 27
  epsilon = 0.01
  num_guesses = 0
  low = 0
  high = cube
  guess = (high + low)/2.0
  while abs(guess**3 - cube) >= epsilon:
      if guess**3 < cube :
          low = guess
      else:
          high = guess
      guess = (high + low)/2.0
      num_guesses += 1
  print 'num_guesses =', num_guesses
  print guess, 'is close to the cube root of', cube
  

  • guess converges on the order of log2N steps
  • bisection search works when value of function varies
  • monotonically with input
  • code as shown only works for positive cubes > 1 – why?
  • challenges modify to work with negative cubes!
  • modify to work with x < 1!

  TODO

  finish the challenge

  Read All

  ---

• Introduction_to_Computation-MIT6_0001F16_Lec2

  2019-03-07

  Introduction_to_Computation

  Python
  • STRINGS
  • INPUT/OUTPUT: print input
  • COMPARISON OPERATORS ON int,float, string
  • LOGIC OPERATORS ON bools
  • CONTROL FLOW - BRANCHING

  这是MIT的第二节公开课，讲的都是基础的python语法知识，虽然这些语法都知道，但还是坚持把这节课听完，一可以锻炼听力也可以学点专业名次，二，这么简单的课程都不能坚持听完，更别说计划中都算法课了。

  STRINGS

  • enclose in quotation marks or single quotes
  • concatenate strings
  • do some operations on a string as defined in Python docs

  INPUT/OUTPUT: print input

  print("my fav num is", x, ".", "x =", x)
  print("my fav num is " + x_str + ". " + "x = " + x_str)
  
  num = int(input("Type a number... "))
    print(5*num)
  

  input gives you a string so must cast if working with numbers

  COMPARISON OPERATORS ON int,float, string

  LOGIC OPERATORS ON bools

  not a True if a is False False if a is True a and b True if both are True a or b True if either or both are True

  CONTROL FLOW - BRANCHING

  if while for

  Read All

  ---