回文序列

如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：
{1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列,
{1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。
现在给出一个数字序列，允许使用一种转换操作：
选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。
现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列。

输入描述

输入为两行，第一行为序列长度n ( 1 ≤ n ≤ 50)
第二行为序列中的n个整数item[i] (1 ≤ iteam[i] ≤ 1000)，以空格分隔。

输出描述

输出一个数，表示最少需要的转换次数

输入例子:

4
1 1 1 3

输出例子:

2

本题思路为：判断队首和队尾元素。若二者相等，则将这两个元素都弹出队列，将队列规模缩小2个，再对该问题进行判断；若二者不相等，则选择其中较小的一个，将该元素和与其相邻的元素都弹出队列，再将其和插入队列，从而将队列规模缩小1个，再对该问题进行判断。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def least_count(*item):
    count = 0
    deque = list(item)
    while len(deque) > 1:
        if deque[0] > deque[-1]:
            deque.append(deque.pop() + deque.pop())
            count += 1
        elif deque[0] < deque[-1]:
            deque.insert(0,deque.pop(0) + deque.pop(0))
            count += 1
        else:
            deque.pop()
            deque.pop(0)
    
    return count

l = least_count(1,1,1,3)
print(l)

优雅的点

小易有一个圆心在坐标原点的圆，小易知道圆的半径的平方。小易认为在圆上的点而且横纵坐标都是整数的点是优雅的，小易现在想寻找一个算法计算出优雅的点的个数，请你来帮帮他。

例如：半径的平方如果为25
优雅的点就有：(+/-3, +/-4), (+/-4, +/-3), (0, +/-5) (+/-5, 0)，一共12个点。

输入描述:

输入为一个整数，即为圆半径的平方,范围在32位int范围内。

输出描述:

输出为一个整数，即为优雅的点的个数

输入例子:

25

输出例子:

12

空间换时间 , 首先获取所有可能的候选值,然后使用左右双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def grace_point(lenght):
    candidate = [num** 2 for num in range(int(lenght**.5)+1)]
    
    left = 0
    right = len(candidate) - 1

    res = 0

    while left < right:
        temp = candidate[left] + candidate[right]
        if temp < lenght:
            left += 1
        elif temp > lenght:
            right -= 1
        else:
            res += 1
            left += 1
            right -= 1
    
    if not int(lenght**.5) == lenght**.5:
        return res * 8
    else:
        return res * 8 - 4


x =grace_point(26)
print(x)

跳石板

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3…….
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板
输入描述:
输入为一行，有两个整数N，M，以空格隔开。
(4 ≤ N ≤ 100000)
(N ≤ M ≤ 100000)

输出描述:
输出小易最少需要跳跃的步数,如果不能到达输出-1

输入例子:
4 24

输出例子:
5

这是一道考察动态规划的题目（因为下一个子阶段的求解是建立在上一个子阶段的解的基础上，且子问题之间非相互独立），关于动态规划算法：