每日算法练习题第四篇
前述：数据结构与算法是计算机应用的基础，也是每一个有趣和富有内涵的工程师基本功，本系列文章旨在记录本小白学习算法的过程以及通过算法和数据结构练习来感受Computer Scince的巨大魅力,吸引着我一直在这上面不断探索摸寻。
注：题目均为转载，大部分来自leetcode–>见 leetcode中文站
栏目分级
通过题目的难度依次从易到难分为三个阶段：
- easy
- middle
- hard
实际演练
step1:唯一摩尔斯密码词
国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。为了方便，所有26个英文字母对应摩尔斯密码表如下：
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。
返回我们可以获得所有词不同单词翻译的数量。
输入: words = ["gin", "zen", "gig", "msg"]
输出: 2
解释:
各单词翻译如下:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
共有 2 种不同翻译, "--...-." 和 "--...--.".
解题思路：
- 将字符串数组中的字符串挨个取出，在摩斯表里找到对应的密码值与之匹配，追加到集合里，通过集合HashSet的不重复性，集合的容量即为题目所求的不同单词的数量。
step2:翻转图像
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
示例 1:
输入: [[1,1,0],[1,0,1],[0,0,0]]
输出: [[1,0,0],[0,1,0],[1,1,1]]
解释: 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]
示例 2:
输入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解题思路：
- 仔细观察题目，容易发现一条规则：即奇数个数的密码最中间的数字反转即可，而两边对称的可以分别用1减去对称的值得到结果。比如示例1中的[1,1,0]得到了[1,0,0],那么中间的数字可以记为1-1=0，而左边的数字=1-右边对称的数字，即1-0=1，同理可得右边的答案。故此，不妨设立left=0记为第一个数字的索引,right为最右边数字的索引，依次通过循环遍历直至left>=right，最后返回的数组即为答案。
代码地址见：Github-Algorithm
