Welcome to Shanshan Blog!

• Leetcode (190, 191, 338, 371) Bit Series

  2017-02-16

  Leetcode

  Leetcode  Bit
  • Leetcode 190. Reverse Bits
  • Leetcode 191. Number of 1 Bits
  • Leetcode 338. Counting Bits
  • Leetcode 371. Sum of Two Integers

  Bit Series II

  Leetcode 190. Reverse Bits

  • Leetcode 190. Reverse Bits

  Reverse bits of a given 32 bits unsigned integer.

  For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

  class Solution {
  public:
      uint32_t reverseBits(uint32_t n) {
          int res = 0;
          for (int i=0; i<32; i++) {
              res += n&1;
              n>>=1;
              if (i<31)   res <<=1;
          }
          return res;
      }
  };
  

  Leetcode 191. Number of 1 Bits

  • Leetcode 191. 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.

  class Solution {
  public:
      int hammingWeight(uint32_t n) {
          int res = 0;
          while (n) {
              if (n%2==1) res++;
              n /=2;
          }
          return res;
      }
  };
  

  Leetcode 338. Counting Bits

  • Leetcode 338. Counting Bits

  Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

  Example:

  For num = 5 you should return [0,1,1,2,1,2].

  class Solution {
  public:
      vector<int> countBits(int num) {
          vector<int> res(num+1, 0);
          for (int i=1; i<=num; i++)
              res[i] = res[i>>1]+i%2;
          return res;
      }
  };
  

  Leetcode 371. Sum of Two Integers

  • Leetcode 371. Sum of Two Integers

  Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

  Example:

  Given a = 1 and b = 2, return 3.

  class Solution {
  public:
      int getSum(int a, int b) {
          int res = a^b;
          int carray = (a&b)<<1;
          if (carray!=0)  return getSum(res, carray);
          return res;
      }
  };
  

  Read All

  ---

• Leetcode (162, 167, 38, 42) Math Series II

  2017-02-15

  Leetcode

  Leetcode  Math
  • Leetcode 162. Find Peak Element
  • Leetcode 169. Majority Element
  • Leetcode 38. Count and Say
  • Leetcode 42. Trapping Rain Water

  Math Series II

  Leetcode 162. Find Peak Element

  • Leetcode 162. Find Peak Element

  A peak element is an element that is greater than its neighbors.

  Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

  The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

  You may imagine that num[-1] = num[n] = -∞.

  For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

  class Solution {
  public:
      int findPeakElement(vector<int>& nums) {
          if (nums[0]> nums[1] || nums.size() == 1)
              return 0;
          if ( nums[nums.size()-1] > nums[nums.size()-2])
              return nums.size()-1;
          for (int i=0; i<nums.size()-1; i++) 
              if (nums[i]>nums[i-1] && nums[i]>nums[i+1])
                  return i;
          return -1;
      }
  };
  

  Leetcode 169. Majority Element

  • Leetcode 169. 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.

  class Solution {
  public:
      int majorityElement(vector<int>& nums) {
          sort(nums.begin(), nums.end());
          return nums[nums.size()/2];
      }
  };
  

  Leetcode 38. Count and Say

  • Leetcode 38. Count and Say

  The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, …

  1 is read off as “one 1” or 11.

  11 is read off as “two 1s” or 21.

  21 is read off as “one 2, then one 1” or 1211.

  Given an integer n, generate the nth sequence.

  Note: The sequence of integers will be represented as a string.

  class Solution {
  public:
      string countAndSay(int n) {
          string s = "1";
          for (int i=0; i<n-1; i++)
              s = getNext(s);
          return s;
      }
      
      string getNext(string s) {
          const int n = s.size();
          int count = 1;
          char temp = s[0];
          string res = "";
          for (int i=1; i<n; i++) {
              if (s[i]==s[i-1])   count++;
              else {
                  res = res + char(count+int('0')) +temp;
                  temp = s[i];
                  count = 1;
              }
          }
          res = res + char(count+int('0')) +temp;
          return res;
      }
  };
  

  Leetcode 42. Trapping Rain Water

  • Leetcode 42. Trapping Rain Water

  Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

  For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

  

  The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being

  class Solution {
  public:
      int trap(vector<int>& height) {
          int res = 0, l = 0, r = height.size()-1;
          while (l < r) {
              int minh = min(height[l], height[r]);
              if (minh == height[l])
                  while (++l<r && height[l]<minh)
                      res += minh-height[l];
              else
                  while (l<--r && height[r]<minh)
                      res += minh-height[r];
          }
          return res;
      }
  };
  

  Read All

  ---

• Leetcode (131, 132) Palindrome Partitioning

  2017-02-14

  Leetcode

  Leetcode
  • Leetcode 131. Palindrome Partitioning
  • Leetcode 132. Palindrome Partitioning II

  Leetcode Palindrome Partitioning

  Leetcode 131. Palindrome Partitioning

  Leetcode 131. Palindrome Partitioning

  Given a string s, partition s such that every substring of the partition is a palindrome.

  Return all possible palindrome partitioning of s.

  For example, given s = “aab”, Return

  [ ["aa","b"], ["a","a","b"] ]

  class Solution {
  public:
      vector<vector<string>> partition(string s) {
          vector<string> curr;
          vector<vector<string>> res;
          helper(curr, res, s, 0);
          return res;
      }
      
      void helper(vector<string> &curr, vector<vector<string>> &res, string s, int pos) {
          if (pos == s.size())    res.push_back(curr);
          for (int i=pos; i<s.size(); i++) {
              if (isPalindrome(s, pos, i)) {
                  curr.push_back(s.substr(pos, i-pos+1));
                  helper(curr, res, s, i+1);
                  curr.pop_back();
              }
          }
      }
      
      bool isPalindrome(string s, int i, int j){
          while (i<j && s[i]==s[j]){
              i++;
              j--;
          }
          return i>=j;
      }
  };
  

  Leetcode 132. Palindrome Partitioning II

  Leetcode 131. Palindrome Partitioning II

  Given a string s, partition s such that every substring of the partition is a palindrome.

  Return the minimum cuts needed for a palindrome partitioning of s.

  For example, given s = “aab”, Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

  class Solution {
  public:
      int minCut(string s) {
          const int n = s.size();
          vector<vector<int>> isPal(n, vector<int>(n, 0));
          int cut[n] = {0};
          for (int j=0; j<n; j++){
              cut[j] = j;
              for (int i=0; i<=j; i++) {
                  if (s[i] == s[j] &&(j-i<=1 || isPal[i+1][j-1])) {
                      isPal[i][j] = 1;
                      if (i>0)    cut[j] = min(cut[j], cut[i-1]+1);
                      else    cut[j] = 0;
                  }
              }
          }
          return cut[n-1];
      }
  };
  

  Read All

  ---

• Python Cheatsheet: Exception

  2017-02-13

  Python

  Python
  • Try except
  • Try finally
  • Throw out errors Raise
  • Check all the threads inside

  Try except

  try:
      open("abc.txt",'r')
  except IOError:
      print "Cannot open the file!" 
  

  try:
      print  aa
  except  NameError, msg:
      print  msg
  

  Try finally

  Whatever to catch up the errors, still run the finally

  import time
  
  try:
      f = file('poem.txt')
      while True: # our usual file-reading idiom
          line = f.readline()
          if len(line) == 0:
              break
          time.sleep(2)
          print line,
  finally:
      f.close()
      print 'Cleaning up...closed the file'
  

  Throw out errors Raise

  filename = raw_input('please input file name:')
  if filename=='hello':
      raise NameError('input file name error !')
  

  Check all the threads inside

  import exceptions
  dir(exceptions)
  

  Read All

  ---

• 500 Lines or Less Chapter 1: Blockcode A visual programming toolkit 翻译

  2017-02-13

  Translation

  Python  Translation
  • 引言
  • 目标和结构
  • 脚本的性质
  • Web应用程序
  • 代码
  • 我们学到的

  500 Lines or Less

  引言

  Dethe是一个极客的爸爸，具审美的程序员，导师，也是Waterbear可视化编程工具的创造者。他共同主办了温哥华创造者教育沙龙，希望用机器人折纸兔子填补世界。

  在基于块(block-based)的编程语言中，通过拖动和连接代表程序一部分的块来编写程序。基于块的语言与传统的输入单词和符号的编程语言不同。

  学习编程语言可能是困难的，因为他们对很细微的打字错误也非常敏感。大多数编程语言都是区分大小写的，具有艰涩难懂的的语法，如果你放了分号在错误的地方，或者更糟糕的是遗漏一个分号，则会被拒绝运行。而且，目前使用的大多数编程语言基于英语，语法不能被本土化。

  相比之下，完善的块语言可以完全消除语法错误。你可以创建一个存在逻辑错误的程序，但不能创建一个有语法错误的程序。块语言更容易被发现：您可以在块列表中查看语言的结构和库。此外，块可以被翻译为任何语种，并且不改变编程语言的含义。

  

  基于块的语言有着悠久的历史，其中一些突出的是 Lego Mindstorms, Alice3D, StarLogo, 特别是Scratch。 还有几个用于在网络上基于块的编程的工具：Blockly, AppInventor, Tynker, 和其他.基于块的语言有着悠久的历史，其中一些突出的是 Lego Mindstorms, Alice3D, StarLogo, 特别是Scratch。还有几个用于在网络上基于块的编程的工具：Blockly, AppInventor, Tynker, 和其他.

  本章中的代码是基于开源项目Waterbear，它不是一种语言，而是一种使用基于块的语法包装现有语言的工具。这样的包装器的优点包括上面提到的：消除语法错误，可用组件的可视显示，易于定位。此外，可视代码有时更容易阅读和调试，并且块可以通过预键入子类使用。

  这种语言的龟图的选择可以追溯到Logo语言，它是专门教儿童程序。上面的几个基于块的语言包括龟图形，它是一个足够小的域，以便能够捕获在一个紧凑约束的项目。

  如果你想了解一个基于块的语言是什么样子，你可以试验本章中从程序的GitHub中获得。

  目标和结构

  我想用这个代码完成几件事情。首先，我想要实现一个用于龟图的块语言，通过使用简单的HTML，CSS和JavaScript结构，你可以通过简单的拖放块来编写代码来创建图像。其次，我想展示块如何为迷你龟语言之外的其他语言的框架。

  为此，我们将特定于龟语言的所有内容封装到一个文件turtle.js中，可以轻松地与另一个文件交换。没有其他应该具体到乌龟语言;其余的应该只是处理块(blocks.js和menu.js)或通常有用的web工具(util.js，drag.js，file.js)。这是目标，虽然为了保持项目小规模，一些实用程序不太通用，主要用于它们的块。

  在编写一个块语言时，令我惊讶的是，语言是它自己的IDE。你不能只是在你喜欢的文本编辑器中编写块; IDE必须与块语言并行设计和开发。这有一些优点和缺点。优点是每个人都将使用一致的环境。缺点是它可能是一个巨大的分心，从构建块语言本身。

  脚本的性质

  Blockcode脚本，像其他语言的脚本，都是遵循操作序列。在Blockcode的情况下，脚本由HTML元素组成，它们被迭代，并且每个都与一个特定的JavaScript函数相关联，该函数将在轮到该块时运行。一些块可以包含其他块，并且一些块可以包含传递给函数的数字参数。

  在大多数（基于文本的）语言中，脚本经历几个阶段：词法分析器将文本转换为识别的令牌，解析器将令牌组织成抽象语法树，然后根据语言将程序编译成机器代码，送入解释器。这是一个简化;可以有更多的步骤。对于Blockcode，脚本区域中的块的布局已经表示我们的抽象语法树，因此我们不需要词法和解析阶段。我们使用Visitor模式迭代这些块，并调用与每个块相关联的预定义JavaScript函数来运行程序。

  不是简单地调用相关的JavaScript函数，我们可以用一个块语言替换turtle.js，该语言为不同的虚拟机发出字节码，甚至编译器的CPP代码。块语言（作为Waterbear项目的一部分）用于生成Java机器人代码，用于编程Arduino，以及用于编写在Raspberry Pi上运行的Minecraft。

  Web应用程序

  为了使工具尽可能广泛使用，它是网络本地的。它是用HTML，CSS和JavaScript编写的，所以它应该在大多数浏览器和平台中工作。

  现代网络浏览器是强大的平台，拥有丰富的工具，用于构建优秀的应用程序。如果实现变得太复杂，我认为这是一种迹象，我不是在做“网络方式”，并在可能的情况下，试图重新考虑如何更好地使用浏览器工具。

  Web应用程序和传统桌面或服务器应用程序之间的一个重要区别是缺少main()或其他入口点。没有明确的运行循环，因为它已经内置在浏览器中并且隐含在每个网页上。我们所有的代码将被解析并在加载时执行，这时我们可以注册我们感兴趣的事件与用户交互。第一次运行后，所有与代码的进一步交互将通过我们设置和注册的回调，是否注册事件（如鼠标移动），超时（使用指定的周期性触发）或帧处理程序（为每个屏幕重画，一般每秒60帧）。浏览器不会公开全功能线程（只有无共享的Web工作线程）。

  代码

  我试着在整个项目中遵循一些约定和最佳实践。每个JavaScript文件都包含在一个函数中，以避免将变量泄漏到全局环境中。如果它需要将变量暴露给其他文件，它将根据文件名定义一个全局文件，其中包含已有的函数。这将在文件的末尾，接着由该文件设置的任何事件处理程序，所以你总是可以看到一个文件的结尾，看看它处理什么事件和它已有的函数。

  代码风格是程序性的，不是面向对象的或功能性的。我们在这些范例中做同样的事情，但这将需要更多的设置代码和包装器来强加已经存在的DOM。最近关于自定义元素的工作使得以OO方式使用DOM变得更加容易，并且在Functional JavaScript上已经有很多好的成果，但是它需要一些脚本，所以它让程序更简单。

  此项目中有8个源文件，但index.html和blocks.css是应用程序的基本结构和样式，将不再讨论。两个JavaScript文件将不会在任何详细讨论：util.js有一些函数，并作为不同浏览器实现之间的桥梁，类似于像jQuery库，但不到50行代码。 file.js是一个类似的实用程序，用于加载和保存文件和序列化脚本。

  这些是剩余的文件：

  • block.js是基于块的语言的抽象表示。

  • drag.js实现了语言的关键交互：允许用户从可用块的列表（“菜单”）拖动块以将它们组装到程序（“脚本”）中。

  • menu.js有一些帮助代码，负责实际运行用户的程序。

  • turtle.js定义了我们的块语言（龟图）的细节并初始化它的特定块。这是将被替换的文件，以便创建不同的块语言。

  • blocks.js

  每个块由几个HTML元素组成，样式为CSS，带有一些JavaScript事件处理程序，用于拖放和修改输入参数。blocks.js文件有助于创建和管理作为单个对象的这些元素分组。当块类型被添加到块菜单中时，它与JavaScript函数相关联以实现语言，因此脚本中的每个块必须能够找到其相关联的函数并在脚本运行时调用它。

  

  块具有两个可选的结构位。它们可以具有单个数字参数（具有默认值），并且可以是用于其他块的容器。这些是硬性限制，但在一个更大的系统中会放宽要求。 在Waterbear中，还有可以作为参数传递的表达式块; 支持多种类型的多个参数。

  <!-- The HTML structure of a block -->
  <div class="block" draggable="true" data-name="Right">
      Right
      <input type="number" value="5">
      degrees
  </div>
  

  注意菜单中的块和脚本中的块之间没有区别很重要。根据它们被拖动的位置拖动也会稍有不同，当我们运行一个脚本时，它只看到脚本区域中的块，但它们基本上是相同的结构，这意味着从菜单进入脚本。

  createBlock(name，value，contents)函数返回一个块作为填充了所有内部元素的DOM元素，准备插入文档中。这可以用于创建菜单的块，或用于恢复保存在文件或localStorage中的脚本块。虽然它是灵活的方式，它是专门为Blockcode“语言”构建，并对它做出假设，所以如果有一个值，假设值表示一个数字参数，并创建一个类型“数字”的输入。由于这是Blockcode的限制，这是被允许的，但是如果我们要扩展块以支持其他类型的参数或多个参数，代码将需要被更改。

      function createBlock(name, value, contents){
          var item = elem('div',
              {'class': 'block', draggable: true, 'data-name': name},
              [name]
          );
          if (value !== undefined && value !== null){
              item.appendChild(elem('input', {type: 'number', value: value}));
          }
          if (Array.isArray(contents)){
              item.appendChild(
                  elem('div', {'class': 'container'}, contents.map(function(block){
                  return createBlock.apply(null, block);
              })));
          }else if (typeof contents === 'string'){
              // Add units (degrees, etc.) specifier
              item.appendChild(document.createTextNode(' ' + contents));
          }
          return item;
      }
  

  我们有一些实用程序用于处理块作为DOM元素：

  • blockContents(block)检索容器块的子块。如果在容器块上调用，它总是返回一个列表，在简单块上总是返回null

  • blockValue(block)返回块上输入的数值，如果块没有输入元素，则返回null

  • blockScript(block)将返回一个适合于使用JSON序列化的结构，以便以可轻松恢复的形式保存块

  • runBlocks(block)是程序，运行块中的每个块

      function blockContents(block){
          var container = block.querySelector('.container');
          return container ? [].slice.call(container.children) : null;
      }
  
      function blockValue(block){
          var input = block.querySelector('input');
          return input ? Number(input.value) : null;
      }
  
      function blockUnits(block){
          if (block.children.length > 1 &&
              block.lastChild.nodeType === Node.TEXT_NODE &&
              block.lastChild.textContent){
              return block.lastChild.textContent.slice(1);
          }
      }
  
      function blockScript(block){
          var script = [block.dataset.name];
          var value = blockValue(block);
          if (value !== null){
              script.push(blockValue(block));
          }
          var contents = blockContents(block);
          var units = blockUnits(block);
          if (contents){script.push(contents.map(blockScript));}
          if (units){script.push(units);}
          return script.filter(function(notNull){ return notNull !== null; });
      }
  
      function runBlocks(blocks){
          blocks.forEach(function(block){ trigger('run', block); });
      }
  

  drag.js

  drag.js是通过实现视图的菜单部分和脚本部分之间的交互，将HTML的静态块转换为动态编程语言。用户通过将块从菜单拖动到脚本中来构建其程序，并且系统在脚本区域中运行块。

  我们使用HTML5拖放; 它需要的特定JavaScript事件处理程序在这里定义。尽管内置对拖放支持很好，但它确实有相当大的限制。

  我们在文件的顶部定义一些变量。

      var dragTarget = null; // Block we're dragging
      var dragType = null; // Are we dragging from the menu or from the script?
      var scriptBlocks = []; // Blocks in the script, sorted by position
  

  根据拖动的开始和结束位置，拖放会有不同的效果：

  • 如果从脚本拖动到菜单，请删除dragTarget（从脚本中删除块）。

  • 如果从脚本拖动到脚本，请移动dragTarget（移动现有脚本块）。

  • 如果从菜单拖动到脚本，请复制dragTarget（在脚本中插入新块）。

  • 如果从菜单拖动到菜单，则不执行任何操作。

  在dragStart(evt)处理程序期间，我们跟踪是从菜单复制块还是从脚本中移动（或内部）。 我们还获取脚本中未被拖动的所有块的列表，以供稍后使用。evt.dataTransfer.setData调用用于浏览器和其他应用程序（或桌面）之间进行拖动，我们没有使用它，但仍然需要调用以解决错误。

      function dragStart(evt){
          if (!matches(evt.target, '.block')) return;
          if (matches(evt.target, '.menu .block')){
              dragType = 'menu';
          }else{
              dragType = 'script';
          }
          evt.target.classList.add('dragging');
          dragTarget = evt.target;
          scriptBlocks = [].slice.call(
              document.querySelectorAll('.script .block:not(.dragging)'));
          // For dragging to take place in Firefox, we have to set this, even if
          // we don't use it
          evt.dataTransfer.setData('text/html', evt.target.outerHTML);
          if (matches(evt.target, '.menu .block')){
              evt.dataTransfer.effectAllowed = 'copy';
          }else{
              evt.dataTransfer.effectAllowed = 'move';
          }
      }
  

  当我们拖动时，dragenter，dragover和dragout事件通过突出显示有效的放置目标等来添加视觉提示的机会。其中，我们只使用dragover。

      function dragOver(evt){
          if (!matches(evt.target, '.menu, .menu *, .script, .script *, .content')) {
              return;
          }
          // Necessary. Allows us to drop.
          if (evt.preventDefault) { evt.preventDefault(); }
          if (dragType === 'menu'){
              // See the section on the DataTransfer object.
              evt.dataTransfer.dropEffect = 'copy';  
          }else{
              evt.dataTransfer.dropEffect = 'move';
          }
          return false;
      }
  

  当我们释放鼠标时，我们得到一个drop事件。这是神奇之处。 我们必须检查我们从哪里拖动（回到dragStart）和我们拖到哪里。 然后我们复制块，移动块或根据需要删除块。 我们使用trigger()（在util.js中定义）来触发一些自定义事件，以供我们自己在块逻辑中使用，因此我们可以在脚本更改时刷新脚本。

      function drop(evt){
          if (!matches(evt.target, '.menu, .menu *, .script, .script *')) return;
          var dropTarget = closest(
              evt.target, '.script .container, .script .block, .menu, .script');
          var dropType = 'script';
          if (matches(dropTarget, '.menu')){ dropType = 'menu'; }
          // stops the browser from redirecting.
          if (evt.stopPropagation) { evt.stopPropagation(); }
          if (dragType === 'script' && dropType === 'menu'){
              trigger('blockRemoved', dragTarget.parentElement, dragTarget);
              dragTarget.parentElement.removeChild(dragTarget);
          }else if (dragType ==='script' && dropType === 'script'){
              if (matches(dropTarget, '.block')){
                  dropTarget.parentElement.insertBefore(
                      dragTarget, dropTarget.nextSibling);
              }else{
                  dropTarget.insertBefore(dragTarget, dropTarget.firstChildElement);
              }
              trigger('blockMoved', dropTarget, dragTarget);
          }else if (dragType === 'menu' && dropType === 'script'){
              var newNode = dragTarget.cloneNode(true);
              newNode.classList.remove('dragging');
              if (matches(dropTarget, '.block')){
                  dropTarget.parentElement.insertBefore(
                      newNode, dropTarget.nextSibling);
              }else{
                  dropTarget.insertBefore(newNode, dropTarget.firstChildElement);
              }
              trigger('blockAdded', dropTarget, newNode);
          }
      }
  

  dragEnd(evt)在我们鼠标向上时调用，但是是在我们处理drop事件之后。 这是我们可以清理，从元素中删除类，并为下一次拖动重置的地方。

      function _findAndRemoveClass(klass){
          var elem = document.querySelector('.' + klass);
          if (elem){ elem.classList.remove(klass); }
      }
  
      function dragEnd(evt){
          _findAndRemoveClass('dragging');
          _findAndRemoveClass('over');
          _findAndRemoveClass('next');
      }
  

  menu.js

  文件menu.js是块与在运行时调用的函数相关联的，并且包含用于在用户构建它时实际运行脚本的代码。每次修改脚本时，都会自动重新运行。

  在此上下文中的“菜单”不是下拉（或弹出）菜单，就像在大多数应用程序中，但是您可以为您的脚本选择的块列表。这个的文件设置，并用一个循环块关闭菜单。

  单个文件来收集随机函数是有用的，特别是当架构正在开发时。保持干净的房子的理论是有指定的地方杂乱，这也适用于建立一个程序架构。一个文件或模块变成了没有一个明确的地方。随着这个文件的增长，重要的是注意新兴的模式：几个相关的功能可以分离成一个单独的模块（或连接在一起成一个更一般的功能）。你不想让catch-all无限地增长，而只是一个临时的持有地方，直到找出正确的方式来组织代码。

  我们保留引用到menu和script中，因为我们需要经常使用。我们还将使用scriptRegistry，其中我们在菜单中存储块的脚本。我们使用非常简单的名称到脚本映射，它不支持具有相同名称的多个菜单块或重命名块。更复杂的脚本环境需要更强大的东西。

  我们使用scriptDirty来跟踪脚本自上次运行以来是否已被修改，所以我们不会一直不断地运行它。

      var menu = document.querySelector('.menu');
      var script = document.querySelector('.script');
      var scriptRegistry = {};
      var scriptDirty = false;
  

  当我们想要通知系统在下一次处理程序中运行脚本时，我们调用runSoon()将scriptDirty设置为true。系统每次调用run()，但是除非scriptDirty设置好，否则立即返回。当scriptDirty设置好时，它运行所有脚本块，并且触发事件以让特定语言处理脚本运行前后所需的任何任务。这使得块工具包与龟语言分离，使块可重用（或者语言可插入，取决于你如何看待它）。

  作为运行脚本的一部分，我们遍历每个块，调用runEach(evt)，它在块上设置一个类，然后找到并执行它的相关函数。如果我们放慢，你应该能够看到代码执行的每个块突出显示。

  下面的requestAnimationFrame方法，浏览器提供用于动画的方法。它需要一个函数，它将被调用在由浏览器呈现的下一个帧（每秒60帧）。我们实际获得多少帧取决于我们能够在该调用中完成工作有多快。

      function runSoon(){ scriptDirty = true; }
  
      function run(){
          if (scriptDirty){
              scriptDirty = false;
              Block.trigger('beforeRun', script);
              var blocks = [].slice.call(
                  document.querySelectorAll('.script > .block'));
              Block.run(blocks);
              Block.trigger('afterRun', script);
          }else{
              Block.trigger('everyFrame', script);
          }
          requestAnimationFrame(run);
      }
      requestAnimationFrame(run);
  
      function runEach(evt){
          var elem = evt.target;
          if (!matches(elem, '.script .block')) return;
          if (elem.dataset.name === 'Define block') return;
          elem.classList.add('running');
          scriptRegistry[elem.dataset.name](elem);
          elem.classList.remove('running');
      }
  

  我们使用menuItem(name, fn, value, contents)将块添加到菜单中，它需要一个正常块，将它与一个函数相关联，并放入菜单栏。

      function menuItem(name, fn, value, units){
          var item = Block.create(name, value, units);
          scriptRegistry[name] = fn;
          menu.appendChild(item);
          return item;
      }
  

  我们在这里定义repeat(block)在乌龟语言之外，因为它在其他的语言中通常有用 如果我们有条件句和读写变量的块，他们也可以使用，或者到一个单独的跨语言模块，但现在我们只有通用块中的一个被定义。

      function repeat(block){
          var count = Block.value(block);
          var children = Block.contents(block);
          for (var i = 0; i < count; i++){
              Block.run(children);
          }
      }
      menuItem('Repeat', repeat, 10, []);
  

  turtle.js

  turtle.js 是海龟块语言的实现。它没有暴露任何函数在其他代码中，所以不被依赖。 这样我们可以换出一个文件来创建一个新的块语言。

  

  龟语言是一种图形编程风格，首先被Logo广为流行，你想象乌龟携带一支笔在屏幕上走。 你让乌龟拿起笔（停止绘图，但仍然移动），把笔放下（在任何地方留下一条线），向前移动一些步，或者转几度。 只是那些命令，结合循环，可以创建令人惊讶的错综复杂的图像。

  在这个版本的龟图中，我们有一些额外的块。技术上，我们不需要向右转和左转，因为你可以有一个得到另一负数个。同样，可以使用向前移动和负数执行向后移动。在这种情况下，它更加平衡。

  上面的图是通过将两个循环放在另一个循环中并向前移动并向右移动到每个循环，然后以交互方式播放参数直到得想要到的图。

      var PIXEL_RATIO = window.devicePixelRatio || 1;
      var canvasPlaceholder = document.querySelector('.canvas-placeholder');
      var canvas = document.querySelector('.canvas');
      var script = document.querySelector('.script');
      var ctx = canvas.getContext('2d');
      var cos = Math.cos, sin = Math.sin, sqrt = Math.sqrt, PI = Math.PI;
      var DEGREE = PI / 180;
      var WIDTH, HEIGHT, position, direction, visible, pen, color;
  

  reset()函数将所有状态变量清除为默认值。如果我们要支持多龟，这些变量将被封装在一个对象中。我们还有一个效用，deg2rad(deg)，因为我们做UI的度数，但是我们绘制弧度。 最后，drawTurtle()绘制龟本身。默认乌龟是一个三角形，但你可以覆盖掉，以绘制一个更美观的乌龟。

  注意，drawTurtle使用我们定义的相同的原始操作来实现海龟绘图。 有时你不想在不同的抽象层重复使用代码，但是当意义清楚时，它可能是代码大小和性能的一大进步。

      function reset(){
          recenter();
          direction = deg2rad(90); // facing "up"
          visible = true;
          pen = true; // when pen is true we draw, otherwise we move without drawing
          color = 'black';
      }
  
      function deg2rad(degrees){ return DEGREE * degrees; }
  
      function drawTurtle(){
          var userPen = pen; // save pen state
          if (visible){
              penUp(); _moveForward(5); penDown();
              _turn(-150); _moveForward(12);
              _turn(-120); _moveForward(12);
              _turn(-120); _moveForward(12);
              _turn(30);
              penUp(); _moveForward(-5);
              if (userPen){
                  penDown(); // restore pen state
              }
          }
      }
  

  我们有一个特殊的块在当前鼠标位置绘制一个给定半径的圆。 特殊在于drawCircle因为，虽然你可以通过重复MOVE 1 RIGHT 1360次绘制一个圆，控制圆的大小是非常困难的。

      function drawCircle(radius){
          // Math for this is from http://www.mathopenref.com/polygonradius.html
          var userPen = pen; // save pen state
          if (visible){
              penUp(); _moveForward(-radius); penDown();
              _turn(-90);
              var steps = Math.min(Math.max(6, Math.floor(radius / 2)), 360);
              var theta = 360 / steps;
              var side = radius * 2 * Math.sin(Math.PI / steps);
              _moveForward(side / 2);
              for (var i = 1; i < steps; i++){
                  _turn(theta); _moveForward(side);
              }
              _turn(theta); _moveForward(side / 2);
              _turn(90);
              penUp(); _moveForward(radius); penDown();
              if (userPen){
                  penDown(); // restore pen state
              }
          }
      }
  

  我们主要在于moveForward，处理一些基本的三角法，并检查笔是向上还是向下。

      function _moveForward(distance){
          var start = position;
          position = {
              x: cos(direction) * distance * PIXEL_RATIO + start.x,
              y: -sin(direction) * distance * PIXEL_RATIO + start.y
          };
          if (pen){
              ctx.lineStyle = color;
              ctx.beginPath();
              ctx.moveTo(start.x, start.y);
              ctx.lineTo(position.x, position.y);
              ctx.stroke();
          }
      }
  

  大多数龟命令可以根据我们上面构建的内容轻松地定义。

      function penUp(){ pen = false; }
      function penDown(){ pen = true; }
      function hideTurtle(){ visible = false; }
      function showTurtle(){ visible = true; }
      function forward(block){ _moveForward(Block.value(block)); }
      function back(block){ _moveForward(-Block.value(block)); }
      function circle(block){ drawCircle(Block.value(block)); }
      function _turn(degrees){ direction += deg2rad(degrees); }
      function left(block){ _turn(Block.value(block)); }
      function right(block){ _turn(-Block.value(block)); }
      function recenter(){ position = {x: WIDTH/2, y: HEIGHT/2}; }
  

  当我们想要更新时，清除功能恢复一切回到我们开始的地方。

      function clear(){
          ctx.save();
          ctx.fillStyle = 'white';
          ctx.fillRect(0,0,WIDTH,HEIGHT);
          ctx.restore();
          reset();
          ctx.moveTo(position.x, position.y);
      }
  

  当这个脚本首次加载和运行时，我们使用reset和clear来初始化绘制乌龟。

      onResize();
      clear();
      drawTurtle();
  

  现在我们可以使用上面的函数，使用menu.js中的Menu.item函数来创建用于从中构建脚本的块。这些被拖动到位完成用户的程序。

      Menu.item('Left', left, 5, 'degrees');
      Menu.item('Right', right, 5, 'degrees');
      Menu.item('Forward', forward, 10, 'steps');
      Menu.item('Back', back, 10, 'steps');
      Menu.item('Circle', circle, 20, 'radius');
      Menu.item('Pen up', penUp);
      Menu.item('Pen down', penDown);
      Menu.item('Back to center', recenter);
      Menu.item('Hide turtle', hideTurtle);
      Menu.item('Show turtle', showTurtle);
  

  我们学到的

  为什么不使用MVC？

  Model-View-Controller(MVC)是80年代Smalltalk程序的很好的设计选择，它可以在一些变体或其他的web应用程序中工作，但它不是每个问题的正确工具。所有的状态（MVC中的“模型”）被块语言中的块元素捕获，所以将它复制到Javascript中没有什么好处，除非模型有其他需要。

  Waterbear的早期版本很大程度上保持模型在JavaScript中并与DOM同步，我才注意到，超过一半的代码和90％的错误是由于保持模型与DOM同步。消除重复允许代码更简单和更健壮，并且对于DOM元素的所有状态，可以通过查看开发工具中的DOM来找到许多错误。所以在这种情况下，构建进一步分离MVC比我们已经在HTML/CSS/JavaScript几乎没有什么好处。

  Toy Changes导致实际更改

  构建一个小的，严格范围的更大的系统是一个有趣的练习。有时在一个大的系统中，有些事情你不愿改变，因为他们影响太多的其他事情。在一个小型版本中，你可以自由地实验和学习的东西，然后回到较大的系统。对我来说，更大的系统是Waterbear，这个项目对Waterbear的结构有很大的影响。

  小实验失败确定

  我能用这种精简块语言做的一些实验是：

  • 使用HTML5拖放，

  • 直接通过迭代DOM运行块调用相关函数，

  • 分离从HTML DOM清理运行的代码，

  • 简化的hit测试，

  • 构建我们自己的小向量和sprite库（对于游戏块），和

  • “实时编码”，其中每当更改块脚本时显示结果。

  我们倾向于忽视我们工作中的失败和死胡同，失败被惩罚而不是被视为学习的重要工具，但如果你要向前推进，失败是必不可少的。虽然我确实得到了HTML5拖放工作，但事实上它在任何移动浏览器上都不被支持，这意味着它是Waterbear的非初学者。将代码分离出来，通过迭代代码块来运行代码，我已经开始将这些想法带到Waterbear，并在测试和调试方面有了极大的改进。简单的命中测试，有一些修改，也回到了Waterbear，微小的矢量和sprite库。

  我们试图建立什么？

  构建一个更小的版本的一个更大的系统，将重点放在重要的部分真正是什么。有没有遗留的历史原因，没有目的（或更糟，分散注意力的目的）？有没有功能没有一个用途，但你必须支付维护？用户界面能否简化？所有这些都是很大的问题要求，同时制作一个小版本。可以进行重大改变，如重新组织布局，而不必担心通过更复杂的系统级联的后果，甚至可以指导重构复杂系统。

  程序是一个过程，而不是一个事情

  有些事情我不能在这个项目的范围内进行实验，我可以使用blockcode的代码库来测试。创建“功能”块将是有趣的，其从现有块中创建新块。在受限环境中实现撤消/重做将更简单。使块接受多个参数，而没有根本扩展的复杂性将是有用的。并且找到各种方式在线共享块脚本将带来整个工具的webbiness。

  Read All

  ---

• Leetcode (72) Edit Distance

  2017-02-12

  Leetcode

  Leetcode
  • Leetcode 72. Edit Distance

  Leetcode 72. Edit Distance

  Leetcode 72. Edit Distance

  Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

  You have the following 3 operations permitted on a word:

  a) Insert a character b) Delete a character c) Replace a character

  The idea is from blog

  本题是典型的适合使用动态规划的题目。在斯坦福的公开课(中文，英文)上，有对这个问题的详细说明，所以接下来就继续使用斯坦福公开课的例子了。 如果要计算单词”INTENTION”和单词”EXECUTION”之间的编辑距离，那么该怎么计算呢？ 首先，把这个问题简单化。把上面两个单词简化为长度为1的两个单词I和E。 如果要“I”变化为”E”，可以把”I”替换为”E” 如果要“I”变化为空串” “，可以把”I”删除，从而形成”” 如果要空串“ ”变化为”E”，可以把”E”插入，从而形成E 上面三种变化分别表示替换，删除，插入这三种基本操作。 接下来，定义一个表达式D(i,j)。它表示从第1个字单词的第0位至第i位形成的子串和第2个单词的第0位至第j位形成的子串的编辑距离。 显然，可以计算出动态规划的初始表达式，如下: D(i,0) = i D(0,j) = j 然后，考虑动态规划的状态转移方程式，如下: D(i-1, j) + 1 D(i,j)=min ( D(i, j-1) + 1 ) D(i-1, j-1) +2( if X(i) != Y(j) ) ; D(i-1,j-1) ( if X(i) == Y(j) ) 上面的状态转移方程的含义是，D(i,j)的值，要么是D(i-1, j)的操作完成之后删除一个字符(第1个单词的第i个字符)，要么是D(i, j-1)的操作完成之后增加一个字符(第2个单词的第j个字符)，要么是D(i-1, j-1)的操作完成自后替换一个字符(如果第1个单词的第i个字符和第2个单词的第j个字符不等)，或者是D(i-1, j-1)的操作完成自后什么也不做(如果第1个单词的第i个字符和第2个单词的第j个字符相等)。其中，课件定义删除，插入，替换的操作步数分别为一步，一步，两步。

  class Solution {
  public:
      int minDistance(string word1, string word2) {
          const int l1 = word1.size();
          const int l2 = word2.size();
          vector<vector<int>> dp(l1+1, vector<int>(l2+1, 0));
          for (int i=1; i<=l1; i++)
              dp[i][0] = i;
          for (int j=1; j<=l2; j++)
              dp[0][j] = j;
          for (int i=1; i<=l1; i++)
              for (int j=1; j<=l2; j++){
                  dp[i][j]= min(dp[i-1][j]+1, dp[i][j-1]+1);
                  if (word1[i-1] != word2[j-1])
                      dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
                  else
                      dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
              }
          return dp[l1][l2];
      }
  };
  

  Read All

  ---