Practice

第1题删除不超过一个元素，其余严格升序

1.给定一个整形数组，删除不超过一个元素，判断其是否按严格升序。 英文原题是这样来描述的： Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Note: sequence a0, a1, …, an is considered to be a strictly increasing if a0 < a1 < ... < an. Sequence containing only one element is also considered to be strictly increasing.

举例：

• For sequence = [1, 3, 2, 1], the output should be
  solution(sequence) = false.

  There is no one element in this array that can be removed in order to get a strictly increasing sequence.

• For sequence = [1, 3, 2], the output should be
  solution(sequence) = true.

  You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

https://app.codesignal.com/arcade/intro/level-2/2mxbGwLzvkTCKAJMG

这里需要注意的是： 1.删除数组中的一个元素，第二次再使用的话，还是得从数组中删除另外的元素，而不是使用 pop() ，把数组中的元素真正删除掉。 2.如果条件符合，即删除一个元素后，数组中的其余元素是按照严格升序的，那么这个函数就判定为 True 3.删除一个元素后，可以使用 sorted() 来判断是否严格升序，两个数组进行比较就可以了。

def solution(sequence):
	result = False
	# 使用拷贝的方式，保留住传进来的数组
	# 这里换成 sequence.copy() 就通过了 
	origin = sequence[0:]
	index = 0
	while index < len(origin):
		del origin[index]
		print('origin:',origin,'seq:',sequence)
		if origin == sorted(set(origin)):
			result = true
			break
		else:
			# 如果非严格升序，那么就处理下一个数据，同时将序列归整为初始的全部元素
			index += 1
			origin = sequence[0:]
	return result

现在的问题是，测试通过了，但是说时间超时，是里面的数组拷贝占用了大量的时间么？搞不太清楚，不过从google查询的结果来看，在各大刷题网站上，类似的问题还真不少。 估计是部分测试用例的数据量较小，体现不出问题来，如果是部分测试的数据量较大，是不是会出现问题？在此网站上，报错的测试用例，还是加锁的，我也看不到。 注意：把 sequence[:] 拷贝数组换成 sequence.copy() 就没什么问题了。

第2题 房间选择，避开小鬼

1.题目描述： after becoming famous, the codebots decided to move into a new building together. each of the rooms has a different cost, and some of them are free, but there’s a rumour that all the free rooms are haunted! since the codebots are quite superstitious, they refuse to stay in any of the free rooms, or any of the rooms below any of the free rooms. 成名之后，codebots决定一起搬进一栋新大楼，每个房间都有不同的费用，其中一些是免费的，但有传言说，所有免费的房间都闹鬼！由于 codebots 非常迷信，他们拒绝入住任何免费房间，以及任何免费房间下方的任何房间。

given matrix, a rectangular matrix of integers, where each value represents the cost of the room, your task is to return the total sum of all rooms that are suitable for the codebots (ie: add up all the values that don’t appear below a 0) . 给定一个矩阵，一个整数矩形矩阵，其中每个值代表房间的成本，你的任务是返回适合 codebots 居住的所有房间的总和（费用的总和？） 用矩阵来描述的话，就是：

matrix = [[0, 1, 1, 2], 
          [0, 5, 0, 0], 
          [2, 0, 3, 3]]

其输出的结果应该为：

solution(matrix) = 9

再来一个例子看看输出结果：

matrix = [[1, 1, 1, 0], 
          [0, 5, 0, 1], 
          [2, 1, 3, 10]]

注意一下这个例子中的最后房间，其价格为10，已经超出了所租住其它房间的价格之和，因此，也是不适宜租住的。 上图的最终答案应该是：1 + 1 + 1 + 5 + 1 = 9

matrix = [[1, 0, 3],
		  [0, 2, 1], 
		  [1, 2, 0]]

上面的这个也没通过测试，预期答案是 1 + 3 + 1 =5 ，为什么没有加上最末一行的2呢？选取的标准是什么呢？这个有点搞不太懂了。我得到的答案是 1 + 3 + 1 +2 = 7 ，是不对的。 最末一行的2为什么不能加进去呢？取用的标准是什么？搞不太清楚。。。

看这名话，note that the free room in the final column makes the full column unsuitable for bots(not just the room directly beneath it).是不是可以这样理解，如果第一行的某列为0，那么这一列的数据都不能添加进去。

解决方案：

def solution(matrix):
	val = 0
	for i in range(0,len(matrix)):
		for j in range(0,len(matrix[0])):
			if matrix[0][j] != 0:
				if i == 0 and matrix[i][j] != 0:
					val += matrix[i][j]
				elif i > 0 and matrix[i-1][j] != 0:
					val += matrix[i][j]
return val
 

第3题 最长的共用子串

1.描述：

给定两个字符串，找出两者共有子串的个数 given two strings, find the number of common characters between them

2.思路：

找出每个字符串的所有子串，然后找其交集即可

3.代码：

def solution(s1, s2):
	set1 = set(s1[i:i+k]for i in range(len(s1)) for k in range(1,len(s1)+1))
	set2 = set(s2[i:i+k]for i in range(len(s2)) for k in range(1,len(s2)+1))
	print('s1:',set1,'s:',set2)
	s = set1 & set2
	print('s:',s)
	return len(s)

这其中比较关键的是求子串，比如给定：

s1 = 'aabcc'
s2 = 'adcaa'

那么其子串是多少呢？这里子串是有要求的，即必须是连续的，比如说 aacc 就不能算子串。

求子串的是两层循环，外边儿的一层是从 0 开始到 len(s) - 1，里边儿的一层是 1开始到 len(s) ，然后分别截取 i 到 i+k 之间的内容作为子串的结果。

s1: {'abc', 'bc', 'b', 'aa', 'ab', 'aab', 'c', 'aabc', 'a', 'abcc', 'bcc', 'aabcc', 'cc'}
s2: {'ad', 'adc', 'aa', 'ca', 'dc', 'caa', 'adcaa', 'dca', 'c', 'a', 'd', 'dcaa', 'adca'}
其交集：
s: {'c', 'a', 'aa'}
也就是说，题目的结论是交集的长度，即等于 3

上面的这个答案通过了测试，但是应该是有没通过的地方，看不到更严格的测试。那么这个算是不太正确的。通过在网上查找，找到了一个可以，这个是完全没问题的（可以拿到300分），我做的那个只能拿到280分。

def solution(s1, s2):
	common_char = ""
	for i in s1:
		if i not in common_char:
			i_in_s1 = s1.count(i)
			i_in_s2 = s2.count(i)
			comm_num = []
			comm_num.append(i_in_s1)
			comm_num.append(i_in_s2)
			comm_i = min(comm_num)
			new_char = i * comm_i
			common_char += new_char
	print(common_char)
	return len(common_char)

得到的应该是 公共串 (Common string) 在长度，返回这个长度即可，得空儿得好好看看这个实现的过程 。

第4题 括号内字串反转

1.描述：

Write a function that reverses chracters in (possibly nested) parentheses in the input string.

Input strings will always be well-formed with maching () s. 所有的括号都是匹配的。

2.举例：

• inputString = '(bar)', the result is solution(inputString) = 'rab'
• inputString = "foo(bar)baz",the result should be solution(inputString) = "foorabaz"
• inputString = "foo(bar)baz(blim)", the result should be solution(inputString) = "foorabbazmilb"
• inputString = "foo(bar(baz))blim",the result should be solution(inputString) = "foobazrabblim"

3.实现

最直接的想法是用Stack，当然真正实现起来也是这样来处理的。2023-04-16 21:51:45 不过我的方案差了很多，可以通过基本的测试，但更多的、更严格的测试没有通过。 先上 StackOverFlow 上面的大神的方案：

stack = [[]] # accumulate letters in stack[0]
for l in s:
    if l == '(':
        stack.append([])        # start a new level
    elif l == ')':
        sub = stack.pop()[::-1] # pop the last level and reverse
        stack[-1].extend(sub)   # add to current 
        print(stack)
    else:
        stack[-1].append(l)     # add to current
        print(stack)

这其中的打印语句还是我加的，人家只是用了很少量的几个语句，就完全实现了这个功能。只能说牛B！！！

大体的意思是：如果是左括号，那么就住堆栈里面添加一个空白列表， 如果是右括号，那么首先是临时串，此临时串反转，同时再压入栈中 否则的话，既不是左括号，也不是右括号，即正常的字符，那么就添加到最后一个列表的后面。附上一个运行测试的结果：

s = "foo(bar(baz))blim" 
[['f']]
[['f', 'o']]
[['f', 'o', 'o']]
[['f', 'o', 'o'], ['b']]
[['f', 'o', 'o'], ['b', 'a']]
[['f', 'o', 'o'], ['b', 'a', 'r']]
[['f', 'o', 'o'], ['b', 'a', 'r'], ['b']]
[['f', 'o', 'o'], ['b', 'a', 'r'], ['b', 'a']]
[['f', 'o', 'o'], ['b', 'a', 'r'], ['b', 'a', 'z']]
[['f', 'o', 'o'], ['b', 'a', 'r', 'z', 'a', 'b']]
[['f', 'o', 'o', 'b', 'a', 'z', 'r', 'a', 'b']]
[['f', 'o', 'o', 'b', 'a', 'z', 'r', 'a', 'b', 'b']]
[['f', 'o', 'o', 'b', 'a', 'z', 'r', 'a', 'b', 'b', 'l']]
[['f', 'o', 'o', 'b', 'a', 'z', 'r', 'a', 'b', 'b', 'l', 'i']]
[['f', 'o', 'o', 'b', 'a', 'z', 'r', 'a', 'b', 'b', 'l', 'i', 'm']]
 

实现的关键元素在于，在堆栈当中，使用了列表，思路清晰、明了，结果完美无缺！

4.我的实现

我的实现是这样的：

stack = ''
result = ''
in_stack = False
for ch in inputString:
    # in_stack = True if ch == '(' else False if ch==')' else ch
    if ch == '(':
        stack += ch
        in_stack = True
    elif ch == ')':
        if stack.rfind('(') == 0:
            result += stack[:0:-1]
            stack = ''
            in_stack = False
        else:
            in_stack = True
            rpos = stack.rfind('(')
            print('rpos:', rpos)
            stack = stack[:rpos] + stack[-1:-rpos:-1]
    else:
        stack += ch * bool(in_stack)
        result += ch * bool(not in_stack)
    print('ch:',ch,'--','in_stack:',in_stack, '--', bool(in_stack) * ch)
    print(result,'--',stack) 

想法也是，遇到“（”那么就入栈，同时设置入栈操作为 True 如果遇到“）”，那么就出栈，这里分为两种情况处理，一个是只有一层括号的情况，那么就反转，并清空堆栈，以待下一个需要反转的串入栈 还有一个就是多层括号的情况，那么找出最近一个左括号的位置，将栈内元素与此括号之后的内容拼接成一个新的字符串，并继续保留在栈中 其它情况，则分为两种，一种是入栈的，一种正常连接的字符串 最后的情况是把结果反馈出来即可。 同样也附一下运行结果：

inputString = "foo(bar(baz))blim"
 
ch: f -- in_stack: False -- 
f -- 
ch: o -- in_stack: False -- 
fo -- 
ch: o -- in_stack: False -- 
foo -- 
ch: ( -- in_stack: True -- (
foo -- (
ch: b -- in_stack: True -- b
foo -- (b
ch: a -- in_stack: True -- a
foo -- (ba
ch: r -- in_stack: True -- r
foo -- (bar
ch: ( -- in_stack: True -- (
foo -- (bar(
ch: b -- in_stack: True -- b
foo -- (bar(b
ch: a -- in_stack: True -- a
foo -- (bar(ba
ch: z -- in_stack: True -- z
foo -- (bar(baz
rpos: 4
ch: ) -- in_stack: True -- )
foo -- (barzab
ch: ) -- in_stack: False -- 
foobazrab -- 
ch: b -- in_stack: False -- 
foobazrabb -- 
ch: l -- in_stack: False -- 
foobazrabbl -- 
ch: i -- in_stack: False -- 
foobazrabbli -- 
ch: m -- in_stack: False -- 
foobazrabblim -- 

觉得这个思路也可以，但实现的很费劲，也体现对于堆栈的应用认识还是太浅薄😡

5.JavaScript的实现

网上还有另外一个帖子讨论了这个问题： [url]https://medium.com/fun-with-algorithms/codesignal-reverse-in-parentheses-6b08fe296f26[/url] The code starts with an empty function, which recieves a string. 代码以一个空函数开始，该函数接收一个字符串。

function reverseInParentheses(inputString) {
  // TODO
}

Let us see what we actually need to do: 让我们看看我们实际需要做什么：

1. Find the pairs of parentheses

2. 找出括号对

3. Find the part of the string we need to reverse 2.找到我们需要反转的字符串部分

4. Reverse the string 3.反转字符串

5. Repeat until all parentheses are replaced

6. 重复直到所有括号都被替换

Find the pairs 找到对 Seems simple enough, so for the first part we can do 2 things, either loop over it as an array of characters, or use Regular Expression (regex) since we are working on a string, lets start with the regex part — I love using https://regexr.com when I need to use regex, because honestly… Who remembers all the regex rules by heart 😅 ?? 看起来很简单，所以对于第一部分，我们可以做两件事，要么将其作为字符数组循环，要么使用正则表达式 (regex)，因为我们正在处理字符串，让我们从正则表达式部分开始——我喜欢使用 https://regexr.com 当我需要使用正则表达式时，因为老实说…谁会记住所有正则表达式规则？？

Regexr will allow us to test and will inform us what each part of the regex is doing: Regexr 将允许我们测试并告知我们正则表达式的每个部分在做什么：

( : will match a starting parenthesis “(” ( ：将匹配起始括号“(”

[a-zA-Z] : will match english letters [a-zA-Z] : 匹配英文字母

*? : will match any number of characters, but the question mark will match the shortest amount of characters, got when there are a few pairs that need to be matched individually. *？ : 将匹配任意数量的字符，但问号将匹配最短的字符数，当有几对需要单独匹配时得到。

( : will match an ending parenthesis “(” ( ：将匹配结束括号“(”

In order to implement it by code, we can execute the regex we made on the string, if we didn’t get anything then there is no parenthesis to match, if we did, we can get the startIndex which indicate the open parenthesis, and the end index which indicates the location of the closing parenthesis. 为了通过代码实现它，我们可以在字符串上执行我们制作的正则表达式，如果我们没有得到任何东西那么就没有括号可以匹配，如果我们得到了，我们可以得到表示左括号的startIndex，和指示右括号位置的结束索引。

 
function getStartAndEndIndexes(inputString) {
  const regularExpression = /\([a-zA-Z]*?\)/;
  const execData = regularExpression.exec(inputString);
  if(!execData) {
    return null;
  }
  const startIndex = execData.index;
  const endIndex = execData.index + execData[0].length - 1;
  return {startIndex, endIndex}
}

The other option will be for us to use a loop — honestly, in an interview, I would rather use a loop since I do not trust my knowledge of regex, all we want to do is the same thing, but with a loop, I will not use array functions, to keep the code simple and also because I will be using a break which doesn’t exist in the array functions. 另一种选择是我们使用循环——老实说，在一次采访中，我宁愿使用循环，因为我不相信我对正则表达式的了解，我们想要做的是同一件事，但是有了循环，我不会使用数组函数，以保持代码简单，也因为我将使用数组函数中不存在的中断。

We are initiating variables, startIndex will indicate the location of the open parenthesis, and the endIndex will indicate the location of the closing parenthesis, do notice we keep updating the start until we meet the first end because in case of something like foo(bar(baz))blim we want to first reverse (baz), and only then reverse the (bar(baz)) part. 我们正在启动变量，startIndex 将指示左括号的位置，endIndex 将指示右括号的位置，请注意我们不断更新开始，直到遇到第一个结束，因为在类似 foo(bar( baz))blim 我们想先反转 (baz)，然后才反转 (bar(baz)) 部分。

Once we find a closing parenthesis we can break out of the loop, and make sure we found a parenthesis, if we didn’t we can just return the string with no changes. 一旦我们找到一个右括号，我们就可以跳出循环，并确保我们找到了一个括号，如果我们没有找到，我们可以直接返回没有变化的字符串。

 
function getStartAndEndIndexes(inputString) {
  let startIndex = null;
  let endIndex = null;
  const chars = inputString.split('');
  for(let i = 0; i < chars.length; i++) {
    const c = chars[i];
     if(c === '(') {
       startIndex = i;
     }
     if(c === ')') {
       endIndex = i;
       break;
     }
  }
  if(startIndex === null || endIndex === null) {
    return null
  }
  return {startIndex, endIndex}
}

Find the part of the string we need to reverse 找到我们需要反转的字符串部分 This one is simple, we just need to use a substring to get the parts that we wish to replace, we can also remove the parenthesis at this point since we don’t need them (that is why we add +1 to the start and end indexes). 这个很简单，我们只需要使用子字符串来获取我们想要替换的部分，我们也可以在这一点上删除括号，因为我们不需要它们（这就是为什么我们在开头添加 +1 和结束索引）。

 
function reverseParentheses(startIndex, endIndex, inputString) {
  // before the parenthesis
  const startSegmant = inputString.substring(0, startIndex);
  // the parenthesis
  const parenthesisSegmant = 
  inputString.substring(startIndex +1, endIndex);
  // after the parenthesis
  const endSegmant = 
  inputString.substring(endIndex + 1, inputString.length);
  return startSegmant + reverse(parenthesisSegmant) + endSegmant;
}

Reverse the string 反转字符串 To reverse a string in javascript we can simply do this: 要在 javascript 中反转字符串，我们可以简单地这样做：

 
function reverse(string) {
  return string.split('').reverse().join('');
}

That being said, in lots of interviews the interviewers don’t like you using native functions 🙄, so here is a solution with a loop… these two code snippets will work the same way. 也就是说，在很多面试中，面试官不喜欢你使用原生函数🙄，所以这里有一个带循环的解决方案……这两个代码片段的工作方式相同。

function reverse(string) {
  let newString = '';
  for (let i = string.length - 1; i >= 0; i--) {
    newString += string[i];
  }
  return newString;
}

Repeat until all parentheses are replaced 重复直到替换所有括号 Here is where we are kind of at the mercy of the interviewer, we can either use a loop or a recursion, I for once hate recursions, I believe it can cause confusion, but pretty much anyone who studied computer science in college just loves it so much… 这是我们有点受面试官支配的地方，我们可以使用循环或递归，我曾经讨厌递归，我相信它会引起混淆，但几乎所有在大学学习计算机科学的人都喜欢它非常…

So let’s start with the recursion, we are simply calling the functions we already created, we introduce the break statement when we check if there are indexes, and we keep calling the same function with the new value until it will hit the break statement. 所以让我们从递归开始，我们简单地调用我们已经创建的函数，当我们检查是否有索引时我们引入 break 语句，并且我们用新值继续调用同一个函数直到它遇到 break 语句。

function reverseInParentheses(inputString) {
  const indexes = getStartAndEndIndexes(inputString);
  if(!indexes) {
    return inputString;
  }
  const {startIndex, endIndex} = indexes; 
  const newString = 
  reverseParentheses(startIndex, endIndex, inputString);
  return reverseInParentheses(newString);
}

And the loop version of this would be using a while loop to achieve the same thing. 而循环版本将使用 while 循环来实现相同的目的。

function reverseInParentheses(inputString) {
  let indexes = getStartAndEndIndexes(inputString);
  while(indexes) {
    const {startIndex, endIndex} = indexes; 
    const newString = 
    reverseParentheses(startIndex, endIndex, inputString);
    inputString = reverseInParentheses(newString);
    indexes = getStartAndEndIndexes(inputString);
  }
  return inputString;
}

Wrapping it up 总结起来 This test is quite nice, it can be solved in multiple ways, it’s not very complicated but not too easy either, it shows an understanding of working with strings and arrays. 这个测试很好，可以通过多种方式解决，不是很复杂但也不太容易，它显示了对使用字符串和数组的理解。

I have made the solution quite long, it is on purpose, even if I can write it all in 3 lines I do not want to, I rather have the code simple and organized rather than short, complex, and confusing. 我把解决方案做得很长，这是故意的，即使我可以用我不想写的 3 行来写，我宁愿让代码简单和有条理，而不是简短、复杂和混乱。

Full solution: 完整解决方案： https://gist.github.com/liron-navon/2e6a05aa80a6121c23dbb6a832eb15a8

// 1. Find the pairs of parentheses
function getStartAndEndIndexes(inputString) {
  const regularExpression = /\([a-zA-Z]*?\)/;
  const execData = regularExpression.exec(inputString);
  if(!execData) {
    return null;
  }
  const startIndex = execData.index;
  const endIndex = execData.index + execData[0].length - 1;
  return {startIndex, endIndex}
}
 
// 2. Find the part of the string we need to reverse
function reverseParentheses(startIndex, endIndex, inputString) {
  // before the parenthesis
  const startSegmant = inputString.substring(0, startIndex);
  // the parenthesis
  const parenthesisSegmant = 
  inputString.substring(startIndex +1, endIndex);
  // after the parenthesis
  const endSegmant = 
  inputString.substring(endIndex + 1, inputString.length);
  return startSegmant + reverse(parenthesisSegmant) + endSegmant;
}
 
// 3. Reverse the string
function reverse(string) {
  return string.split('').reverse().join('');
}
 
// 4. Repeat until all parentheses are replaced
function reverseInParentheses(inputString) {
  let indexes = getStartAndEndIndexes(inputString);
  while(indexes) {
    const {startIndex, endIndex} = indexes; 
    const newString = 
    reverseParentheses(startIndex, endIndex, inputString);
    inputString = reverseInParentheses(newString);
    indexes = getStartAndEndIndexes(inputString);
  }
  return inputString;
}

6.这个最牛，只用四行代码完成

还有一个更牛B的，只用了一个语句就解决了，哈哈

function solution(inputString) {
  let str = inputString
  const re = /\([A-Za-z]*\)/g
  
  while (re.test(str)) {
    str = str.replace(re, (substr) => substr.slice(1, substr.length - 1).split('').reverse().join(''))
  }
  return str
}

第5题 相似数组

1. 定义:

Two arrays are called similar if one can be obtained from another by swapping at most one pair of elements in one of the arrays.

如果第二个数组只交换不超过一对元素，就能和第一个数组相同，那么这两个数组就被称之为：相似数组。

2. 举例

• For a = [1, 2, 3] and b = [1, 2, 3], the output should be
  solution(a, b) = true.

  The arrays are equal, no need to swap any elements. 两个数组相等，不需要交换任何元素。

• For a = [1, 2, 3] and b = [2, 1, 3], the output should be
  solution(a, b) = true.

  We can obtain b from a by swapping 2 and 1 in b. 通过在 b 数组交换 2 和 1 ，从 a 得到 b

• For a = [1, 2, 2] and b = [2, 1, 1], the output should be
  solution(a, b) = false.

  Any swap of any two elements either in a or in b won’t make a and b equal.

3.实现

官方的实现还是相当牛B的，只是简单的一句：

from collections import Counter as C
def solution(a, b):
   return C(a) == C(b) and sum(a != b for a, b in zip(a, b)) < 3

前面引用了一下 collections 当中的计数函数 Counter，然后首先判断 a 数组与 b 数组的元素个数相同，并且值是一样的，隐藏的条件就是两个数组相似，只是位置发生了变化，其内容是完全一样的。 再者将两个数组合并起来，并取合并后的每一对值，计算其不同的个数，如果小于3，也就是说，如果这些成对的数据里面，只有两个不同的话，通过调整位置是可以完成题目要求的。 两个条件都成立的情况下，返回 True 的结果。

我的想法也是计算两个数组相同位置，或者说相同的索引下，不同的值的个数，如果大于2就是不成立的，另外还要对其进行排序，比如有这样的数组：

a: [2, 3, 9]
b: [10, 3, 2]

对于 b 数组而言，即使调整了 2 与 10 之间的位置，也不是相似数组。

我写的程序只是通过了部分基础测试，因为看不到高阶测试的内容，反正是没有通过完整测试。

看了人家的标准答案，才知道真的是天外有天，人外有人。

另外，也说明，如果平时多看一些高手的作品，对自己的思路打开也是大有裨益的！

第6题 判断IP4地址合法性

1. 描述

An IP address is a numerical label assigned to each device (e.g., computer, printer) participating in a computer network that uses the Internet Protocol for communication. There are two versions of the Internet protocol, and thus two versions of addresses. One of them is the [IPv4 address](keyword://ipv4-address).

Given a string, find out if it satisfies the IPv4 address naming rules.

2.举例

道理上并不复杂，IP4地址也比较常见，主要是一些特殊情况，需要进行分析判断。

通常情况下，都是用正则表达式也对IP4地址的正确性与否进行判定，这里采用比较直接的字符串方法来实现之。

return True if len([x for x in inputString.split('.') 
	if x.isdigit() and \
	0<=int(x)<=255 and \
	len(inputString.split('.'))==4 and \
	not (len(x)>1 and x[0]=='0')]) == 4 \
	else False 

简单来分析一下比较长的表达式：

1. 按点号进行分离
2. 必须是数字，因为测试里面会有 1a 、a1 等类似的出现；还有一种情况，就是要避免 '' 的出现，如果出现了 '' 会在后面的 int() 中出现错误
3. 数值的范围
4. 分离的长度为4，因为有 .. 的出现，那么 split('.') 就会形成多于4个的子串
5. 处理前导0。分离后的子串，长度只有1、2、3个长度，单个0，是允许的；长度为2、3的话须保证第0位非0
6. 这样处理之后，留在列表中的均为符合要求的数值，然后判断其长度，如果是4个话，就说明是合理地址，否则就不是。

下面看一些测试结果：

 inputString: "172.16.254.1"
 处理结果：['172', '16', '254', '1']

inputString: "172.316.254.1"
result: ['172', '254', '1']，其中的316被处理掉了

inputString: ".254.255.0"
result: inputString: ".254.255.0"，其中最前面应该是个''，那么处理掉了

inputString: "1.1.1.1a"
result : ['1', '1', '1']，1a被处理掉了

第 7 题最少步数跳过数组元素

1. 描述

You are given an array of integers representing coordinates of obstacles situated on a straight line.
您将获得一个整数数组，表示位于直线上的障碍物的坐标。

Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.
假设你是从坐标为 0 的点向右跳。您只能进行由某个整数表示的相同长度的跳跃。

Find the minimal length of the jump enough to avoid all the obstacles.
找到足以避开所有障碍物的最小跳跃长度。

2. 例子

单纯这样来讲，可能会不太清楚，如果有一个例子来描述的话，就会清楚许多。比如对于这样的一个数组：inputArray = [5, 3, 6, 7, 9] ，其输出应该是：4

什么意思呢？就是说从 0 开始，每次按 4 进行跳跃的话：

• 第一次，到 4，跳过了数组中的 [3]
• 第二次，到 8，跳过了数组中的[5，6，7]
• 第三次，到 12，则路过了数组中的[9]

如果是选 3 呢，那么就二次跳跃的时候就卡在了 6 上面，是不正确的。

3. 思路

一开始的时候，我还想着要把数组进行排序，然后把非数组元素要组成一个元组，然后从最小的数组开始进行判断，看递增的序列能否落在这个范围之内。如果在若干个元组当中，都恰巧合适，那么就得出答案。

后来又分析了一下，发现如果跳动的步数如果被数组的元素整除的话，是不符合要求的，那么就要寻找下一个数，直到不能被所有的数组元素整除。这样的话，解题就豁然开朗，就是找到不能数组元素整除的最小数即可。

再来一个比较明显的例子，inputArray = [999,1000]，那么我们来简单判断一下：

1. 2，不行，能被 1000 整除
2. 3，不行，能被 999 整除
3. 4，不行，能被 1000 整除，4 × 250
4. 5，不行，能被 1000 整除
5. 6，最小的就是 6 号，均不能被 999 和 1000 整除，那么最终的答案就是 6

现在看来，数学的分析还是最重要的，哈哈。

4. 代码

既然知道了原理，代码实现起来就很简单了。

def solution(inputArray):
	index, number = 0, 2  
	while index < len(inputArray):  
		if inputArray[index] % number == 0:  
			number += 1  
			index = 0  
			continue  
		else:  
			index += 1
	return number

第 8 题子矩阵

1. 描述

Last night you partied a little too hard. Now there’s a black and white photo of you that’s about to go viral! You can’t let this ruin your reputation, so you want to apply the box blur algorithm to the photo to hide its content.
昨晚你聚会有点过火了。现在有一张你的黑白照片即将走红！你不能让这毁了你的声誉，所以你想对照片应用框模糊算法来隐藏它的内容。

The pixels in the input image are represented as integers. The algorithm distorts the input image in the following way: Every pixel x in the output image has a value equal to the average value of the pixel values from the 3 × 3 square that has its center at x, including x itself. All the pixels on the border of x are then removed.
输入图像中的像素表示为整数。该算法以下列方式扭曲输入图像：输出图像中的每个像素 x 的值等于中心位于 x 的 3 × 3 正方形像素值的平均值，包括 @3 # 本身。然后删除 x 边界上的所有像素。

Return the blurred image as an integer, with the fractions rounded down.
将模糊图像作为整数返回，分数向下舍入。

2. 例子

1. For

image = [[1, 1, 1], 
         [1, 7, 1], 
         [1, 1, 1]]

the output should be solution(image) = [[1]].

To get the value of the middle pixel in the input 3 × 3 square: (1 + 1 + 1 + 1 + 7 + 1 + 1 + 1 + 1) = 15 / 9 = 1.66666 = 1. The border pixels are cropped from the final result.

2. For

image = [[7, 4, 0, 1], 
         [5, 6, 2, 2], 
         [6, 10, 7, 8], 
         [1, 4, 2, 0]]

the output should be

solution(image) = [[5, 4], 
                   [4, 4]]

There are four 3 × 3 squares in the input image, so there should be four integers in the blurred output. To get the first value: (7 + 4 + 0 + 5 + 6 + 2 + 6 + 10 + 7) = 47 / 9 = 5.2222 = 5. The other three integers are obtained the same way, then the surrounding integers are cropped from the final result.

3. 思路

程序并不复杂，也比较好理解，就是求给定二维数组的子数组，或者称之为给定矩阵的子矩阵。如果可以使用 numpy 的话，可能就会简单了。如果只使用 Python 的列表来处理的话，就比较复杂了。

通常的遍历有两种模式，一种是按行、列下标，用双层循环处理，一种是使用列表推导式，当然，在 Python 的环境下，还是推荐列表推导式最牛逼。

1. 先看一些简单的例子：

numList = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for r in numList:
	for c in r:
		print(c, end=' ')
	print()
 
i = j = 0
while numList[i][j] ! = 5:
	# 记录当前所在行并判断是否前进到下一行
	# 其依据是当前列是否到达该行的结尾
	i = (i if j != len(numList[i])-1 else i+1)
	# 记录当前所在列判断是否继续前进还是加到列头
	# 依据是是否到达该行的结尾
	j = (j+1 if j != len(numList[i])-1 else 0)
	print(numList[i][j], end=' ')

这种判断行、列的方法还是很少见到的，特此记录一下。

2. 按行取元素比较常见，看看一些按列取元素的，也可以称之为转置：

a = [[1,2],[3,4]]
b = list(zip(*a))
print(b)
[(1, 3), (2, 4)]

3. 二维变一维数组，因为在题目当中要对二维数组进行求和计算，如果转成一维数据的话，一个 sum 语句就能解决问题。

rows =3
columns= 2
mylist = [[0 for x in range(columns)] for x in range(rows)]
for i in range(rows):
    for j in range(columns):
        mylist[i][j] = '%s,%s'%(i,j)
print mylist

其内容为：

[['0,0', '0,1'], ['1,0', '1,1'], ['2,0', '2,1']]

from itertools import chain
l = list(chain.from_iterable(zip(*l)))
['0,0', '1,0', '2,0', '0,1', '1,1', '2,1']

这个地方比较特殊，一下子实现了两个功能，一个是转置，一个是变成了一维数组。

4. 还有一个最牛逼的，就是用 lambda 实现的按行、列取元素，就一句话：

sl = lambda r1,c1,r2,c2,lst:\
	[lst[r][c1:c2] for r in range(r1,r2)]

写出来之后，其实就是：列表 lst 的第 r 行的第[c 1 到 c 2]的元素。 现在我们来看一下这个题目： 首先确定的是 3×3 的子矩阵，那么相当于我们用一个 3×3 的框子去套大矩阵里面的数据，你会发现（针对 4×4 的矩阵）结果是这样的：

[0,0]~[2,2] [0,1]~[2,3]
[1,0]~[3,2] [1,1]~[3,3]

看行列的变化，行的变化是从 0 到 1，同样道理，列的变化也是从 0 到 1，这是一个 4×4 的矩阵，亦即说明，水平方向上包括了两个子矩阵，垂直方向也包含了两个子矩阵，故而我们可以很轻易地行出，行列循环的范围：

max_r = len(image) - 3 + 1
max_c = len(image[0]) - 3 + 1

然后定义一个存放结果的空矩阵：

m = [[] for _ in range(0, max_r)]

注意：这里只是定义了行数个空，相当于定义了 max_r 个空行。想定义空元素不能使用 m = [ []*2 ] ，这样表示不了[ [ ]，[ ] ]。 因为后面会把子矩阵的计算结果放到 m 里面。

4. 代码

max_r = len(image) - 3 + 1
max_c = len(image[0]) - 3 + 1
m = [[] for _ in range(0, max_r)]
sl = lambda r1,c1,r2,c2,lst:[lst[r][c1:c2] for r in range(r1,r2)]
for r in range(0,max_r):
	for c in range(0,max_c):
		sub_m = sl(r,c,r+3,c+3,image)
		m[r].append(int(sum(list(chain.from_iterable \(zip(*sub_m)))) / 9))
 return m

这个题目解得不错！2023-04-20 15:05:59，应该值得表扬，首先思路没错，同时对二维数据的遍历有了更深的理解!

第 9 题检查整数的各位是否为偶数

1. 描述

Check if all digits of the given integer are even.

2. 思路

一开始就想到了用集合，把各个数位取出来，然后判断是否是偶数，集合不添加重复的元素，当然在这个题目里面也涉及不到，比如有两个 2，或者是两个 3，对结果都没什么影响。

3. 代码

s = set()
while n != 0:
	s.add(n % 10)
	n //= 10
for item in s:
	if not item % 2==0:
		return False
return True

还有一个思路就是用 lambda，我现在只要是 Python 的题目，我就想能否用 Lambda 去实现，觉得得在实践中充分应用 Python 的一些特性才好。 Lambda 实现只有一句代码：

return all(list(map(lambda x: x %2==0,[int(ch) for ch in str(n)])))

首先是把给定的参数 n 转成字符串，并遍历之，得到各个数位的字符串列表，并转成整数；然后对这个列表进行遍历，看是否被 2 整除。这里用到了 Lambda 函数。最终的结果是一个 Bool 型的列表，用 all 函数来判断，如果全 True，即说明所有的数位都是偶数，如果有一个为 False，就说明其中的某位数字非偶，就返回结果 False。

第 10 题转换为下一个字母

1. 描述

Given a string, your task is to replace each of its characters by the next one in the English alphabet; i.e. replace a with b, replace b with c, etc (z would be replaced by a).

2. 例子

For inputString = "crazy", the output should be solution(inputString) = "dsbaz".

3. 思路

程序比较简单，需要判断的只有一个地方，如果是字母 z，那么就转换成字母 a。其它的按照 ord (ch)加一即可。

4. 代码

先上一段正常代码：

result = ''
for ch in inputString:
	if ord(ch) == 122:
		# 这里也可以直接写成'a'，不用97替代也行
		result += chr(97)
	else:
		result += chr(ord(ch)+1)
return result

利用 Lambda 来实现的代码：

return ''.join((map(lambda x:chr(ord(x)+1) if x!='z' else 'a' ,[x for x in inputString])))

首先是生成 inputString 的字符列表，然后利用 map 函数把业务逻辑应用到这个列表的每个元素上面。其中就一句话的事儿，如果元素不是 z，那么就是加 1 取下一个字符，如果是 z 呢，就变成 a。逻辑上很清晰。 最后用 ''.join() 函数连接起这些字符就可以了。

第 11 题最小绝对值的和

1. 描述

Given a sorted array of integers a, your task is to determine which element of a is closest to all other values of a. In other words, find the element x in a, which minimizes the following sum:

abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x)

(where abs denotes the absolute value)

If there are several possible answers, output the smallest one.

2. 例子

• For a = [2, 4, 7], the output should be solution(a) = 4.

  • for x = 2, the value will be abs(2 - 2) + abs(4 - 2) + abs(7 - 2) = 7.
  • for x = 4, the value will be abs(2 - 4) + abs(4 - 4) + abs(7 - 4) = 5.
  • for x = 7, the value will be abs(2 - 7) + abs(4 - 7) + abs(7 - 7) = 8.

  The lowest possible value is when x = 4, so the answer is 4.

• For a = [2, 3], the output should be solution(a) = 2.

  • for x = 2, the value will be abs(2 - 2) + abs(3 - 2) = 1.
  • for x = 3, the value will be abs(2 - 3) + abs(3 - 3) = 1.

  Because there is a tie, the smallest x between x = 2 and x = 3 is the answer.

3. 思路

题目不复杂，还是想着能用 Lambda 来解决，最初的想法是这样，求出每个值与数组其它元素之绝对值之和，然后比较得到最小的值，见下面的代码：

maxium = float('inf')
result = 0
for k,v in enumerate(a):
	tmp = sum(list(map(lambda x:abs(x-v),a)))
	if tmp < maxium:
		result = k
		maxium = tmp
return a[result]

这里需要注意的是，可以用到 Python 的最大值，是这样来用的：maxium = float('inf')

另外一个思路，是想用到字典，记录下数组中的每个元素的统计结果，按照绝对值的和进行排序，返回最小元素的下标即可。

这里用到一个把 List 转 Dictionary 的简单方法，就是直接用 collections. Counter 方法即可。同样，代码要比上一个简单一些，见下面：

count = Counter(a)
for k,v in enumerate(a):
	count[v] = sum(list(map(lambda x:abs(x-v),a)))
return sorted(count.items(), key=lambda x:x[1])[0][0]

最后一句排序后的字典，其 [0]个代表的列表中的第一个元素，第二个代表[0]代表的是下标索引值。X[1]代表的是按照累计和进行排序。

第 12 题去掉一位数字得到最大数

1、描述

Given some integer, find the maximal number you can obtain by deleting exactly one digit of the given number.

2. 例子

• For n = 152, the output should be
  solution(n) = 52;
• For n = 1001, the output should be
  solution(n) = 101. 我一开始想到的的 110，后来琢磨过来了，110 是不对的，数字的次序是不对的，只能是去掉中间的两个 0 中的一个，怎么可能会出现 110 呢？

3. 思路

还是得利用组合公式，生成不同的排列组合，然后对这些组合进行取最大值运算就可以了。

4. 代码

这次比较高效，直接一行代码解决：

maxium = 0
 
return max(list(map(lambda x:max(int(''.join(x)), maxium), list(combinations(str(n),len(str(n))-1)))))

这里有必要解释五下，itertools. Combinations 生成的不同的数位组合，转变成一个列表，然后用 map 将 max 取最大值函数应用到排列组合的列表上面，最后取这些值中的最大值，是不是可以不用比较啊，对呀，我取最大值了，比较什么呢？

还有更简单的一句代码，这次应该是真的一次性代码了：

max(list(map(lambda x:int(''.join(x)), list(combinations(str(n), len(str(n))-1)))))

第 13 题生成不重复的文件名

1. 描述

You are given an array of strings names representing filenames. The array is sorted in order of file creation, such that names[i] represents the name of a file created before names[i+1] and after names[i-1] (assume 0-based indexing). Because all files must have unique names, files created later with the same name as a file created earlier should have an additional (k) suffix in their names, where k is the smallest positive integer (starting from 1) that does not appear in previous file names. 你拿到一个字符串数组用以表示文件名。这个数组按照文件创建的次序来排序，比如说 names[i] 表示这个文件名是在 names[i+1] 之前，及 name[i-1] 之后创建（假如从 0 开始索引）。因为所有的文件必须拥有唯一的名字，后创建的文件如果重名，那么就需要加上 (k) 后缀来区别。k 为最小的非负整数（从 1 开始）在前面的文件名中。 来一段机器翻译，您将获得一个表示文件名的字符串数组 names 。该数组按文件创建顺序排序，例如 names[i] 表示在 names[i+1] 之前和 names[i-1] 之后创建的文件的名称（假设从 0 开始索引）。因为所有的文件都必须有唯一的名字，后面创建的和前面创建的文件同名的文件应该在名字中多一个 (k) 后缀，其中 k 是没有出现的最小正整数（从 1 开始）在以前的文件名中。 我觉得人家机器翻译得比我这个还要正规，将来人工智能可能首先要淘汰掉的，就是翻译行业了。语言类的方向最适合大数据统计领域了。

Your task is to iterate through all elements of names (from left to right) and update all filenames based on the above. Return an array of proper filenames. 您的任务是遍历 names 的所有元素（从左到右）并根据上述内容更新所有文件名。返回正确文件名的数组。

2. 例子

For names = ["doc", "doc", "image", "doc(1)", "doc"], the output should be solution(names) = ["doc", "doc(1)", "image", "doc(1)(1)", "doc(2)"].

1. Since names[0] = "doc" and names[1] = "doc", update names[1] = "doc(1)"
2. Since names[1] = "doc(1)" and names[3] = "doc(1)", update names[3] = "doc(1)(1)"
3. Since names[0] = "doc", names[1] = "doc(1)", and names[4] = "doc", update names[4] = "doc(2)"

3. 思路

一开始把问题想简单了，认为要添加重复的文件名直接添加后缀就可以，但是看了测试条件就知道，还挺麻烦的。 如果有需要重命名的文件名，则需要对基本名进行判断，而这里还涉及到 k 的问题，k 是会递增，而且会在未来的情况下，有可能已经存在了相对应的 k 值，那么就需要跳过这个 k 值，取下一个。 后来琢磨明白了，实际上是要处理基本文件名的匹配问题，如果是在基本文件名字典中没有出现过的文件名，那么就要新加进去，当出现基本文件名的时候，就需要针对这个增加 k 值。

4. 代码

def solution(names):
	if names==[]:
		return []
	# 如果文件名中含有()，那么取基本的文件名
	stack = [names[0]]
	base=dict()
	base_name = names[0][0:names[0].find('(')] if '(' in names[0] else names[0]
	# 如果文件名中含有()，那么要取这个文件名的k值
	base[base_name] = int(names[0][names[0].find('(')+1:names[0].find(')')]) if '(' in names[0] else 0
	print(base)
	for fn in names[1:]:
		if fn in stack:
			if fn in base:
				base[fn] += 1
				tmp_fn = fn + '({})'.format(base[fn])
				while tmp_fn in stack:
					base[fn] += 1
				tmp_fn = fn + '({})'.format(base[fn])
				stack.append(fn + '({})'.format(base[fn]))
			else:
				stack.append(fn + '(1)')
				base.update({fn:1})
		else:
			base[fn] = 0
			stack.append(fn)
	return stack

首先要在堆栈中添加第一个文件名，同时要建立一个 base 的字典，要解析出第一个文件名的基本名，即如果含有 (，就取 ( 之前的内容做基本名，也就是 base 字典的 key，然后取 k 值。没有括号的话，也得把这个文件名加入进去，因为这属于基本文件名，后面的 names[] 数组肯定会有重复的文件名存在。

然后从 names[1:] 开始循环取值，如果不在堆栈当中，这个简单，直接在 base 中添加基础信息，并同时在堆栈当中添加文件名就可以，因为没有重复嘛。

如果在堆栈当中存在了，那么说明重复了，就需要看是不是在 base 字典当中，如果在，那么就 k 加 1，形成新的 tmp_fn，接着循环检查生成的这个临时文件名是否在堆栈当中，在呢，就基本文件名中的 k 继续加 1，不在就退出循环，认可这个 tmp_fn，最终形成真正可以加入到堆栈当中的文件名，这里主要是 k 的变化。

如果不在基本文件名当中，那说明这是一个新的基本名，那么就执行两个动作，一个是在基本文件名字典中要添加键值对，并且把 k 赋成为 1，同时也把这个文件名加入到堆栈当中。

最终返回的是这个 stack，里面放的就是我们想要的结果。