一道算法题

aimisiyou

农夫约翰的奶牛场有很多奶牛，奶牛有黑白两种颜色。现在奶牛们排成整齐的一列去参加镇上的**活动。
约翰希望白色奶牛都排在前面，黑色的奶牛都排在后面。但现在队列中奶牛的颜色是混乱的，并且奶牛们都不愿意改变位置。
幸运的是，约翰有一根魔法棒，每挥舞一次魔法棒就可以改变一头奶牛的颜色。
请问，约翰至少要挥舞多少次魔法棒，才能将队列改成他希望的状态。注意，可以将所有的奶牛都变成白色，或者都变成黑色。

输入格式
第一行一个正整数n，表示奶牛的头数。(1<=n<=200000)。
第二行n个正整数，均为1或2，1表示白色奶牛，2表示黑色奶牛。
输出格式
一个正整数，表示挥舞魔法棒的最少次数。
输入样例
7
2 2 1 1 1 2 1
输出样例
3
提示
可以把1和2号奶牛变成1,7号奶牛变成2，或者全部奶牛变成1，最少需要3次。

aimisiyou

实质就是列表长度减去最长递增序列长度。复杂度O(n).

aimisiyou

采取什么算法？

aimisiyou

求最大乘积子序列。

aimisiyou

给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。为了减少他的工作量，请求出最少可以切成多少个子数组。

示例 1：

输入：nums = [2,3,3,2,3,3]

输出：2

解释：最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 ，第二个子数组头尾数字的最大公约数为 3 。

示例 2：

输入：nums = [2,3,5,7]

输出：4

解释：只有一种可行的切割：[2], [3], [5], [7]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qie-fen-shu-zu
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

aimisiyou

aimisiyou 发表于 2020-4-26 11:16
给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的 ...

_$  (defun p (llst k)
(setq llst (reverse llst))
(repeat k
   (setq llst (cdr llst))
)
(reverse llst)
)
(defun f (lst)
  (if (null lst)
      (setq va 0)
          (progn
               (setq i (+ (length lst) 1))
                   (setq alst (mapcar '(lambda (x) (list (setq i (- i 1)) x)) lst))
               (setq blst (vl-remove nil (mapcar '(lambda (x) (if (> (gcd (cadr x) (last lst)) 1) (car x) nil)) alst)))
           (setq va (+ 1 (apply 'min (mapcar '(lambda (y) (f (p lst y))) blst ))))
          )
   )
)
P
F
_$  (f '(7 11 7 19 11 13 7 13 19))
2
_$ (f '(7 11 7 19 11 13 7 13))
2
_$ (f nil)
0
_$ (f '(3))
1
_$  (f '(3 6 9))
1
_$ (f '(2 3 3 2 3 3))
2
_$ (f '(2 3 5 7))
4
_$

aimisiyou

n=31,m=45,最少需要多少个正方形？

aimisiyou

aimisiyou 发表于 2020-4-24 11:16
求最大乘积子序列。

_$ (defun f (lst)
  (setq alst (list (car lst)) sum1 (car alst))
  (foreach ea (cdr lst)
     (if (= ea 0)
             (setq alst (cons 0 alst) sum1 1)
         (setq alst (cons (* ea sum1) alst) sum1 (car alst))
          )
  )
(apply 'max alst)
)
(setq lst '(2 4 0 -1 9))
(max (f lst) (f (reverse lst)))
F
(2 4 0 -1 9)
9
_$ (setq lst '(2 3 -2 4))
(max (f lst) (f (reverse lst)))
(2 3 -2 4)
6
_$  (setq lst '(-2 0 -1))
(max (f lst) (f (reverse lst)))
(-2 0 -1)
0
_$

aimisiyou

aimisiyou 发表于 2020-4-26 11:16
给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的 ...

(defun zs (n)
   (setq i 3 lst nil)
   (while (<= i n)
          (setq lst (cons i lst))
          (setq i (+ i 2))
   )
  (setq llst (cons (list 2) (reverse lst)))
  (while (and (< (car (car llst)) (sqrt n) )   (< (cadr llst) (sqrt n))   )
        (setq flst (cons (cadr llst) (car llst)))
        (setq plst (vl-remove-if '(lambda (x) (= (rem x (car flst)) 0)) (cdr llst)))
        (setq llst (cons flst plst))   
   )
  (setq alst (car llst) blst (cdr llst))
  (mapcar '(lambda (e) (setq blst (cons e blst))) alst)
   blst
)
;;;(setq xlst '(14 10 24 15 13 11))
(defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (n)
(+ 3 (* 8 (fix (* n (rnd)))))
)
(defun pd (xlst ylst)
  (apply 'or (mapcar '(lambda (z) (member z xlst)) ylst))
)
(setq xlst nil)
(repeat 10
  (setq xlst (cons (rnd_n 100) xlst))
)
(setq num_max (apply 'max xlst))
(setq zs_lst (zs num_max))
(setq fflst (mapcar '(lambda (x) (vl-remove nil (mapcar '(lambda (y) (if (= (rem x y) 0) y nil)) zs_lst))) xlst))
(setq lst1 (mapcar '(lambda (x) 1) fflst))
(setq jj 1 ii -1)
(while (cdr lst1)
       (setq lst1 (mapcar '(lambda (x y)   
                              (if (pd (nth (setq ii (+ ii 1)) fflst) (nth (+ ii jj) fflst))
                                                                1
                                                                        (+ 1 (min x y))
                              )
                                                        )        
                           (reverse (cdr (reverse lst1)))
                           (cdr lst1)
             )
         )
                (setq jj (+ 1 jj) ii -1)
)
(progn (car lst1))

aimisiyou

在给出的n*n个数组成的矩形中找出一个小矩形，使得这些数的和最大。
如
0 -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

和值最大为15.（9  2  -4  1  -1  8）

aimisiyou

  农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
   1、从X移动到X-1或X+1，每次移动花费一分钟
   2、从X移动到2*X，每次移动花费一分钟
   假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入
   两个整数，N和K
输出
   一个整数，农夫抓到牛所要花费的最小分钟数
样例输入
    5 17
样例输出
    4

aimisiyou

链接：https://ac.nowcoder.com/acm/problem/20565
来源：牛客网

小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。 小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。
输入描述:
第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。
接下来K行，每行第一个数为Ti，表示第i种彩珠的数目。接下来按升序给出Ti个非负整数，为这Ti个彩珠分别出现的位置。
输出描述:
应包含一行，为最短彩带长度。
示例1
输入
复制
6 3
1 5
2 1 7
3 1 3 8
输出
复制
3

aimisiyou

链接：https://ac.nowcoder.com/acm/problem/20565
来源：牛客网

小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。 小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。
输入描述:
第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。
接下来K行，每行第一个数为Ti，表示第i种彩珠的数目。接下来按升序给出Ti个非负整数，为这Ti个彩珠分别出现的位置。
输出描述:
应包含一行，为最短彩带长度。
示例1
输入
复制
6 3
1 5
2 1 7
3 1 3 8
输出
复制
3

aimisiyou

求一种快速指定区间内最大值的算法~
如题……有一组数字

编号 ： 1 2 3 4 5 6 7 8 9
值  ：   9 7 5 6 3 1 2 8 4

例如求闭区间

[3,7]的最大值为6

[4,8]的最大值为8

那么有没有一种时间复杂度少于o(n)的算法能快速得出结果?

aimisiyou

在n个连续的格子中只有0或1。你能修改格子任意次数。修改方法：把格子分成两部分，每部分内部前后颠倒
如：10110可以分成10和110，然后前后颠倒，变成01011。求修改任意次后，连续相邻的0和1交替的格子的最大长度.