lintcode入门篇六

185. 矩阵的之字型遍历

给你一个包含 m x n 个元素的矩阵 (m 行, n 列), 求该矩阵的之字型遍历。

样例

样例 1:
    输入: [[1]]
    输出:  [1]

样例 2:
    输入:   
    [
    [1, 2,  3,  4],
    [5, 6,  7,  8],
    [9,10, 11, 12]
  ]

    输出:  [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]
class Solution:
    '''
    1.首先i,j都不能小于0,并且i<len(matrix) and j<len(matrix[0])
    2.一开始是往上右,upright = True
    3.如果是upright = True的话,下一个值就是i-1,j+1,否则i+1,j-1
    4.如果i<0或者j<0,则代表需要转换方向,upright=False或者True:
    如果转换方向,此时的upright =True的话,此时得分情况:
    (1).一种是j在范围内(即j<=len(matrix)-1,那么需要往右边走,j+1,i不变(此时不仅要回退到原来的i和j,而且j需要再加1)
    (2).一种是j出范围(即j==len(matrix)),那么需要往下走,i+1(此时不仅需要回退到原来的i和j,而且i需要再加1)
    如果转换方向,此时的upright =True的话,此时得分情况:
    (1).和上述相反
    (2).和上述相反
    '''
    def printZMatrix(self,matrix):
        upright = True
        res=[]
        i,j=0,0
        IsOut = False
        while True:
            if upright == True:
                ##在此下运行的条件
                while i>=0 and j>=0 and i <= len(matrix)-1 and j<=len(matrix[0])-1:<br></br>                    ##终止条件
                    if i == len(matrix)-1 and j == len(matrix[0])-1:
                        IsOut = True
                        break
                    res.append(matrix[i][j])
                    print('upright=True:'+str(res[-1]))
                    i = i-1
                    j = j+1
                else:
                    if j == len(matrix[0]):
                        i = i+2
                        j = j-1
                    else:
                        i = i+1
                    upright = False
            print(upright)
            if upright == False:
                print('enter')
                while i>=0 and j>=0 and i <= len(matrix)-1 and j<=len(matrix[0])-1:
                    if i == len(matrix)-1 and j == len(matrix[0])-1:
                        IsOut = True
                        break
                    res.append(matrix[i][j])
                    i = i+1
                    j = j-1
                    print('upright=False:'+str(res[-1]))
                else:
                    if (i == len(matrix)):
                        i = i-1
                        j = j+2
                    else:
                        j = j+1
                    upright = True  
            if IsOut == True:
                res.append(matrix[-1][-1]) 
                break
        return res

![]()

大致解释:(折腾了两小时,终于搞定,略显累赘)

1.写入的顺序是先往右上,在往左下,在往右上,在往左下,依次写入,直到i=len(matrix)-1 and j = len(matrix[0])-1。

2.如果upright=True的话,取下一个元素是i-1,j+1

upright=True的时候,如果i<0或者j>len(matrix)-1的时候,说明需要进行转换(即换方向)。

(1).i<0,此时需要往右边走,i和j需要回退到原来的值,并且j需要再加1.

(2).j>len(matrix)-1,此时需要往下走,i和j需要回退到原来的值,并且i需要在加1

如果upright=False,和上述情况相反。

204. 单例

单例 是最为最常见的设计模式之一。对于任何时刻,如果某个类只存在且最多存在一个具体的实例,那么我们称这种设计模式为单例。例如,对于 class Mouse (不是动物的mouse哦),我们应将其设计为 singleton 模式。

你的任务是设计一个 getInstance 方法,对于给定的类,每次调用 getInstance 时,都可得到同一个实例。

样例

在 Java 中:

    A a = A.getInstance();
    A b = A.getInstance();

a 应等于 b

挑战

如果并发的调用 getInstance,你的程序也可以正确的执行么?

输入测试数据 (每行一个参数)如何理解测试数据? ```
class Solution:

@return: The same instance of this class every time

__instance = None
@classmethod
def getInstance(cls):
    # write your code here
    ##如果是__instance==None的话,说明是第一次创建实例
    if cls.__instance == None:
        ##第一次创建实例通过object.__new__方法来创建
        cls.__instance = object.__new__(cls)
        return cls.__instance
    else:
        ##返回上一个对象的引用
        return cls.__instance

注意这里是调用类,实现一个类仅有一个实例


### 209. 第一个只出现一次的字符

中文English

给出一个字符串,找出第一个只出现一次的字符。

### 样例

样例 1:
输入: "abaccdeff"
输出: 'b'

解释:
'b' 是第一个出现一次的字符

样例 2:
输入: "aabccd"
输出: 'b'

解释:
'b' 是第一个出现一次的字符

输入测试数据 (每行一个参数)如何理解测试数据?  第一种解法:

class Solution:
def firstUniqChar(self,str):
for i in range(len(str)):
if str.count(str[i]) == 1:
return str[i]


显示超时,改用第二种解法

class Solution:
"""
@param str: str: the given string
@return: char: the first unique character in a given string
"""
def firstUniqChar(self, str):

Write your code here

    str_dic = {}

    ##循环str,循环的str的字符i作为键,值为字符i出现的次数,每次循环加1
    for i in str:
        str_dic[i] = str_dic.get(i,0)+ 1 
    #例如:str为'abaccdeff',str_dic为{'a': 2, 'b': 1, 'c': 2, 'd': 1, 'e': 1, 'f': 2}
    for j in str:
        if str_dic[j] == 1:
            return j

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。