牛客网编程题

二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

Solutions

从左下角开始判断，如果target小于当前，向右走；如果target大于当前，向左走。

# -*- coding:utf-8 -*-
class Solution:
    def Find(self, target, array):
        m = len(array)
        n = len(array[0])
        i = m-1
        j = 0
        while i>=0 and j<=n-1:
            if array[i][j] == target:
                return True
            elif array[i][j] > target:
                i -= 1
            else:
                j += 1
        return False

时间复杂度：O(m+n)

替换空格

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

Solutions

一开始就直接用python的replace()了

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        return s.replace(' ','%20')

但是很明显就不是考你这个。
翻了下《剑指offer》，因为从前往后每次插入都需要将后面的字符移动后两位，时间复杂度是O(n²)，采用从后面开始的话，一开始扫描空格数，计算好替换后的总长度，之后从后面替换。索性用了c++写，好久没写了。

class Solution {
public:
	void replaceSpace(char *str,int length) {
		int i = 0;
        int space = 0;
        while(str[i]!='\0')
        {
            if(str[i]==' ')
                space++;
            i++;
        }
        int newlength = length + 2 * space;
        while(space!=0 && newlength>length)
        {
            if(str[length]==' ')
            {
                str[newlength--]='0';
                str[newlength--]='2';
                str[newlength--]='%';
                length--;
            }
            else
            {
                str[newlength--]=str[length--];
            }
        }
	}
};

AC之后想了一下，其实也不是一定要从后面开始，只要扫描一遍之后，从前面也可以，只是判断条件就不像newlength>length这么好看易懂了。

从尾到头打印链表

题目描述

输入一个链表，从尾到头打印链表每个节点的值。

从头到尾遍历，每次存为list的第一个元素

class Solution:
    def printListFromTailToHead(self, listNode):
        l=[]
        while listNode:
            l.insert(0, listNode.val)
            listNode = listNode.next
        return l

跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

Solutions

找一下规律，f(1)=1，f(2)=2，f(3)=3，f(4)=5，可以发现当前等于前两个相加，举个例子，在6的时候，一种情况是跳到5时再跳1格；另外一种是跳到4时再跳2格。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        if number==1:
        	return 1
        if number==2:
        	return 2
        if number==3:
        	return 3
        s = 2
        t = 3
        for i in range(4, number+1):
            l = t
            t = s+t
            s = l
        return t

斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

Solutions

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        f = 0
        s = 1
        for i in range(2, n+1):
            l = s
            s = s + f
            f = l
        return s

重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

Solutions

函数容易写，比较难的是截取左子树和右子树的前序和中序，先取前序的第一个，然后在中序定位，该位置也是前序中左子树前序的终点。
如：
1 2 4 7 3 5 6 8
4 7 2 1 5 3 8 6
定位到1之后，说明前序中的第一位到第四位为左子树的前序

class Solution:
    def reConstructBinaryTree(self, pre, tin):
        if len(pre) == 0:
        	return None
       	if len(pre) == 1:
            return TreeNode(pre[0])
        t = TreeNode(pre[0])
        t.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1], tin[:tin.index(pre[0])])
        t.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:], tin[tin.index(pre[0])+1:])
        return t

用两个栈实现队列

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

Solutions

创建两个数组，stack1作为push的存放位置，当需要pop时先判断stack2中有没有元素，有就pop出来，没有再将stack1所有元素pop到stack2，再pop出来。

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, node):
        self.stack1.append(node)
        
    def pop(self):
        if self.stack2 == []:
            while self.stack1 != []:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
       	else:
            return self.stack2.pop()

变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

Solutions

根据上一题跳台阶的问题，因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+…+f(1)
因为f(n-1)=f(n-2)+f(n-3)+…+f(1)
所以f(n)=2*f(n-1)

看到牛客网上有人向上面这样优化，时间复杂度为O(n)，但是得到了f(n)=2*f(n-1)，其实便可以推出f(n)=2^(n-1)，这样直接用公式便可以将时间复杂度降为O(1)。

1
2
3

class Solution:
    def jumpFloorII(self, number):
        return 2**(number-1)

2333333333……

二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

Solutions

剑指offer上关于这道题有三种解法。

每次将末位和1做位运算，之后右移，但是会出现一个问题，负数在计算机里用补码表示，负数补码最左位为1，右移时，会将符号位再次右移，无限个1。看牛客上有人说可以将>>改为>>>，逻辑右移即可，测试了一下c++里貌似没有，估计是Java有。

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n)
         {
             if(n&1)
             	++count;
             n = n>>1;
         }
         return count;
     }
};

将右移数字改为左移与操作的位置数

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
		 unsigned int flag = 1;
         while(flag)
         {
             if(n&flag)
             	++count;
             flag = flag<<1;
         }
         return count;
     }
};

第三种真是佩服的五体投地，如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n)
         {
             ++count;
             n = (n-1) & n;
         }
         return count;
     }
};

另外有一个问题，我用Python做以上三种做法都会报错，本地倒不会。

旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

Solutions

采用二分法解答这个问题，
mid = low + (high - low)/2
需要考虑三种情况：
(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试，
high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid
注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1，就会产生错误，因此high = mid
但情形(1)中low = mid + 1就不会错误

看了一个牛客网上的高票回答，挺不错的，解决了原书的三个问题，而且代码简洁。

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        first = 0
        rear = len(rotateArray)-1
        while first<rear:
            mid = (first+rear)/2
            if rotateArray[mid] < rotateArray[rear]:
                rear = mid
            elif rotateArray[mid] > rotateArray[rear]:
                first = mid+1
            else:
                rear = rear-1
        return rotateArray[first]

链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

Solutions

这个题从头到尾遍历一遍，时间复杂度O(n)。

class Solution:
    def FindKthToTail(self, head, k):
        list = []
        while(head):
            list.append(head)
            head = head.next
        if k>len(list) or k<1:
            return
        return list[-k]

从时间上也没法再优化了，所以《剑指offer》里说了一种从空间上优化的方法，双指针，先让第一个指针跑k-1步，接着两个指针一起跑，当第一个指针到了最后一个时，第二个就到了倒数第k个。

class Solution:
    def FindKthToTail(self, head, k):
        p1 = head
        p2 = head
        if head==None or k==0:
            return
        for i in range(k-1):
            if p1.next:
            	p1 = p1.next
            else:
                return
        while p1.next:
            p1 = p1.next
            p2 = p2.next
        return p2

矩形覆盖

题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

Solutions

找下规律，飞不垃圾数列

class Solution:
    def rectCover(self, number):
        if number==0:
            return 0
        if number==1:
            return 1
        if number==2:
            return 2
        f = 1
        s = 2
        for i in range(3,number+1):
            t = s
            s = s+f
            f = t
        return s

反转链表

题目描述

输入一个链表，反转链表后，输出链表的所有元素。

Solutions

class Solution:
    def ReverseList(self, pHead):
        p2 = pHead
        if p2 == None:
            return
        p1 = pHead.next
        if p1 == None:
            return p2
        p2.next = None
        while p1.next:
            tmp = p1.next
            p1.next = p2
            p2 = p1
            p1 = tmp
        p1.next = p2
        return p1

修改p1.next，修改前需要存下一个结点，整体操作前需要判断下头结点和第二个结点是否为空，在这里wa了好几次……

调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

Solutions

这题和《剑指offer》上的有些不同，这里要求相对位置不变，按书里是可以头尾指针直接扫描的。这里的话，要么每次调整移动，时间复杂度为O(n²)，要么新建一个新数组，这样时间复杂度为O(n)，空间复杂度为O(n)。

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        newarray = []
        for i in array:
            if i%2:
                newarray.append(i)
        for i in array:
            if i%2 == 0:
                newarray.append(i)
        return newarray

数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

Solutions

用快速幂方法，将累乘优化成位数的乘积。其次还要对各种情况进行判断。

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        if exponent==0:
            return 1
        if base==0:
            if exponent<0:
                return
            return 0
        sym = exponent
        exponent = abs(exponent)
        r = 1
        while exponent:
            if exponent & 1:
                r *= base
            base *=base
            exponent >>= 1
        if sym < 0:
            return 1/r
        return r

合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

Solutions

两两比较，逐个后移。

class Solution:
    def Merge(self, pHead1, pHead2):
        res = head = ListNode(0)
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                head.next = pHead1
                pHead1 = pHead1.next
            elif pHead1.val >= pHead2.val:
                head.next = pHead2
                pHead2 = pHead2.next
            head = head.next
        head.next = pHead1 or pHead2
        return res.next

字符串最后一个单词的长度

题目描述

计算字符串最后一个单词的长度，单词以空格隔开。

输入描述:
一行字符串，非空，长度小于5000。

输出描述:
整数N，最后一个单词的长度。

示例1

输入
hello world
输出
5

Solutions

1 2	s = len(raw_input().split(' ')[-1]) print s

二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:

二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

Solutions

用递归做交换子树，注意递归做之前要将左右子树先交换，否则当做完左子树的递归时，会让右子树继续翻转原右子树。

class Solution:
    def Mirror(self, root):
        if root == None:
            return
        t = root.left
        root.left = root.right
        root.right = t
        if root.right:
            root.right = self.Mirror(root.right)
        else:
            root.right = None
        if root.left:
            root.left = self.Mirror(root.left)
        return root

树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

Solutions

凡是树的结构总是可以很简单地用递归做，子结构主要判断结点值是否相同，如果相同就递归左子树和右子树，直至B到了叶子结点。

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        result = False
        if not pRoot2:
            return False
        if pRoot1 and pRoot2:
            if pRoot1.val == pRoot2.val:
                result = self.DoesSametree(pRoot1, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.left, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.right, pRoot2)
        return result
    
    def DoesSametree(self, pRoot1, pRoot2):
        if not pRoot2:
            return True
        if not pRoot1:
            return False
        if pRoot1.val != pRoot2.val:
            return False
        return self.DoesSametree(pRoot1.left, pRoot2.left) and self.DoesSametree(pRoot1.right, pRoot2.right)

明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

Input Param 
     n               输入随机数的个数     
 inputArray      n个随机整数组成的数组 
     
Return Value
     OutputArray    输出处理后的随机整数

注：测试用例保证输入参数的正确性，答题者无需验证。测试用例不止一组。

输入描述:
输入多行，先输入随机整数的个数，再输入相应个数的整数
输出描述:
返回多行，处理后的结果
示例1
输入

输出

Solutions

牛客上一个很厉害的小哥用hash做，超级厉害，太佩服了。就是不知道为啥以下代码本地跑正确，牛客上总是跑不出结果，最后还是放了别人的交了算了。

num = input()
l = [0 for i in range(1001)]
for i in range(num):
    x = input()
    l[x]=1
for i in range(1001):
    if l[i]:
        print i

顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

Solutions

前几天看左神讲过，先定义出一个打印一圈的函数，打完一圈之后将左上右下斜着走一步，所以在总函数里控制外面端点即可。只是特殊情况比较多，比如单行、单列、双行双列有可能因为走了之后走到原来各自的行或列。

# -*- coding:utf-8 -*-
import math
class Solution:
    def printMatrix(self, matrix):
        lena = 0
        lenb = 0
        lenc = len(matrix)
        lend = len(matrix[0])
        L = []
        if lenc == 1:
            for i in matrix[0]:
                L.append(i)
            return L
        if lend == 1:
            for i in matrix:
                L.append(i[0])
            return L
        for i in range(int(math.ceil(len(matrix)/2.0))):
            L = self.printSon(matrix, lena, lenb, lenc, lend, L)
            lena += 1
            lenb += 1
            lenc -= 1
            lend -= 1
            if lena>=lenc or lenb>=lend:
                return L
        return L
        
    def printSon(self, matrix, a, b, c, d, L):
        for i in range(b, d):
            L.append(matrix[a][i])
        for i in range(a+1, c):
            L.append(matrix[i][d-1])
        if a==c-1:
            return L
        for i in range(d-2, b-1, -1):
            L.append(matrix[c-1][i])
        for i in range(c-2, a, -1):
            L.append(matrix[i][b])
        return L

包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

Solutions

建立一个辅助栈，每次push的时候比较当前的最小值，保存为最小值即可。

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, node):
        self.stack1.append(node)
        try :
            if self.stack2[-1] > node:
                self.stack2.append(node)
            else:
                self.stack2.append(self.stack2[-1])
        except IndexError:
            self.stack2.append(node)

    def pop(self):
        self.stack2.pop()
        return self.stack1.pop()
    
    def top(self):
        return self.stack1[-1]
        
    def min(self):
        return self.stack2[-1]

计算字符个数

题目描述

写出一个程序，接受一个有字母和数字以及空格组成的字符串，和一个字符，然后输出输入字符串中含有该字符的个数。不区分大小写。

输入描述:
输入一个有字母和数字以及空格组成的字符串，和一个字符。
输出描述:
输出输入字符串中含有该字符的个数。

示例1
输入

ABCDEF
A

输出

Solutions

s = list(raw_input())
c = raw_input()
count = 0
for i in s:
    if c.lower() == i.lower():
        count += 1
print count

栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

Solutions

建立一个栈，存放直到栈顶和出栈序列的首个相同，接着弹出，继续压栈，知道压栈序列为空，将栈所有元素弹出。这个过程中一旦有元素不同，返回False。

class Solution:
    def IsPopOrder(self, a, b):
        L1 = []
        while True:
            if len(b) == 0:
                return True
            while (len(L1) == 0 or L1[-1] != b[0]) and len(a) >= 1:
                L1.append(a.pop(0))
            if len(a) == 0:
                while True:
                    if L1.pop() != b.pop(0):
                        return False
                    else:
                        if len(b) == 0:
                            return True
            if L1[-1] == b[0]:
                L1.pop()
                b.pop(0)

从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

Solutions

建立一个队列，每次对结点的左结点和右结点放入队列，访问完当前结点，队列弹出一个结点，作为下次访问的结点。

class Solution:
    def PrintFromTopToBottom(self, root):
		queue = []
		l = []
		if root is None:
			return []
		queue.append(root)
		while True:
			node = queue.pop(0)
			l.append(node.val)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
			if len(queue) == 0:
				return l

二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

Solutions

二叉搜索树的特点，左子树所有元素比当前结点小，右子树所有元素比当前结点大。递归判断即可。

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if len(sequence) == 0:
            return False
        if len(sequence) == 1:
        	return True
        root = sequence.pop()
        flag = 0
        while flag < len(sequence) and sequence[flag] < root:
            flag += 1
        if flag == len(sequence):
            return True
        for i in range(flag, len(sequence)):
            if sequence[i] < root:
                return False
        if flag == 0:
        	return self.VerifySquenceOfBST(sequence[flag:])
        elif flag == len(sequence)-1:
        	return self.VerifySquenceOfBST(sequence[0:flag])
        else:
        	return self.VerifySquenceOfBST(sequence[0:flag]) and self.VerifySquenceOfBST(sequence[flag:])

二叉树中和为某一值的路径

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

Solutions

import copy
class Solution:
	def FindPath(self, root, expectNumber):
		Solve = []
		Path = []
		if root == None:
			return []
		Path.append(root)
		self.FindAdd(expectNumber, Path, Solve)
		return Solve

	def FindAdd(self, expectNumber, Path, Solve):
		node = Path[-1]
		if node.left == None and node.right == None:
			if sum([i.val for i in Path]) == expectNumber:
				Solve.append([i.val for i in Path])
		else:
			tmp = copy.deepcopy(Path)
			if node.left != None:
				tmp.append(node.left)
				self.FindAdd(expectNumber, tmp, Solve)
			tmp = copy.deepcopy(Path)
			if node.right != None:
				tmp.append(node.right)
				self.FindAdd(expectNumber, tmp, Solve)

合法IP

题目描述

现在IPV4下用一个32位无符号整数来表示，一般用点分方式来显示，点将IP地址分成4个部分，每个部分为8位，表示成一个无符号整数（因此不需要用正号出现），如10.137.17.1，是我们非常熟悉的IP地址，一个IP地址串中没有空格出现（因为要表示成一个32数字）。
现在需要你用程序来判断IP是否合法。

输入描述:

输入一个ip地址

输出描述:

1	返回判断的结果YES or NO

示例1
输入

1	10.138.15.1

输出

YES

Solutions

用c++的流可以很容易地控制.的间隔，还可以直接取流中的int类型。
假设这个字符串是已经知道的，不用输入，那也可以用c++的流转换。代码注释部分。

#include<iostream>
#include <sstream>
#include<string>
using namespace std;
 
int main()
{
    int ip[4]={0};
    char ch[3];
	//string s = "10.138.15.1";
    //istringstream istr;
    //istr.str(s);
    //istr>>num[0]>>c[0]>>num[1]>>c[1]>>num[2]>>c[2]>>num[3];
    while(cin>>ip[0]>>ch[0]>>ip[1]>>ch[1]>>ip[2]>>ch[2]>>ip[3])
    {
        if(ch[0]=='.'&&ch[1]=='.'&&ch[2]=='.')
        {
            if((ip[0]>=0&&ip[0]<=255)&&(ip[1]>=0&&ip[1]<=255)&&(ip[2]>=0&&ip[2]<=255)&&(ip[3]>=0&&ip[3]<=255))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else
            cout<<"NO"<<endl;
         
    }
    return 0;
}

longest-substring-without-repeating-characters最长不重复子数组

题目描述

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Solutions

一开始是想用hash记忆化一个struct，存放是否已经是否被读取和位置。主要思想是滑动窗口。不过悟空这种做法简直不要太赞，是否被读取可以直接用位置来判断，pre每次遇到重复又会往下走，在这里给悟空一个大大的赞！

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> book;
        int i,Max=0,pre=-1;
        for(i=0;i<s.length();i++) book[s[i]]=-1;
        for(i=0;i<s.length();i++)
        {
            pre=max(pre,book[s[i]]);
            Max=max(Max,i-pre);
            book[s[i]]=i;
        }
        return Max;
    }
};