计算三个矩形相交的面积

输入数据:左上角x坐标 y坐标 矩形宽 矩形高

思路就是
写一个矩形类, 类里写和另一个矩形比较重叠的方法, 这个方法返回的是重叠的矩形 ,
类里要有坐标信息字段,判断自身是不是一个矩形,然后类里写一个方法计算自身面积

  1. array = []#一个空数组
  2. for i in range(3):#三个矩形 插入三次
  3.     array.append([int(n) for n in input().split()])
  4.     #input()输入进来强制字符串类型,split()切片得到字符串列表,也可以理解成一维数组
  5.     #for 方法把列表中的元素一个单独取出来,取出来的同时使用int()方法给转成整形
  6.     #最后用[]把内容框起来成为一个一维数组插入到array数组里
  7. class Rec:#矩形类
  8.     @classmethod #实例化对象用 可以用来调用类的属性，类的方法，实例化对象等。
  9.     def initByWH(cls, x, y, w, h):#cls是这个类本身 左上x 左上y 宽 高
  10.         x2 = x + w
  11.         y2 = y - h
  12.         return cls(x, y, x2, y2)#返回左上x 左上y 右下x 右下y
  14.     def __init__(self, x1, y1, x2, y2):#初始化方法
  15.         self.x1 = x1
  16.         self.y1 = y1
  17.         self.x2 = x2
  18.         self.y2 = y2
  19.         self.w = x2 - x1
  20.         self.h = y1 - y2
  22.     def getSize(self):#计算面积
  23.         return self.w * self.h
  25.     def valid(self):#认可函数,如果左上x小于等于右下x 且左上y大于等于右下y
  26.         return self.x1 <= self.x2 and self.y1 >= self.y2
  28.     def getOverlap(self, rec):#比较后,获取重叠矩形的四个点
  29.         resultX1 = rec.x1 if rec.x1 > self.x1 else self.x1#左上x选 x值大的那个
  30.         resultX2 = rec.x2 if rec.x2 < self.x2 else self.x2#右下x选 x值小的那个
  31.         resultY1 = rec.y1 if rec.y1 < self.y1 else self.y1#左上y选 y值小的那个
  32.         resultY2 = rec.y2 if rec.y2 > self.y2 else self.y2#右下y选 y值大的那个
  34.         result = Rec(resultX1, resultY1, resultX2, resultY2)
  35.         if result.valid():#如果新的矩形四个点符合逻辑就返回参数,不符合return None程序结束
  36.             return result
  37.         return None
  38. rec1 = Rec.initByWH(array[0][0],array[0][1],array[0][2],array[0][3])#实例化三个矩形
  39. rec2 = Rec.initByWH(array[1][0],array[1][1],array[1][2],array[1][3])
  40. rec3 = Rec.initByWH(array[2][0],array[2][1],array[2][2],array[2][3])
  41. temp = rec1.getOverlap(rec2)#获取第一个和第二个矩形得到的重叠的矩形
  42. result = temp.getOverlap(rec3)#把得到的重叠矩形和第三个矩形继续重叠
  43. print(result.getSize())#计算最后的重叠面积

实现金字塔输出 奇数行正序输出 偶数行逆序输出 不足四位需要用*补位

具体思路:
首先是一个外循环-控制行数,并准备一个空列表记录该行要输出的内容
接着内循环,输出该行的相应个数的数据,从第一行开始,是第几行就输出几个数据,利用一个全局变量s,记录目前输出的数据,需要输出就自增1,并且如果s不足4位要执行补位,为了,每生成完一个数就插入到空列表里
做完该行要输出的所有数据后,为了实现金字塔输出需要在最前面插入空格,空格的数量由目标行数减去当前行数决定
最后根据行数是奇数还是偶数决定列表是正序输出还是逆序输出

  1. count = int(input())
  2. sum = 0
  3. for i in range(1,count+1):#i的意义是该行的输出个数
  4.     list = []
  5.     for j in range(i): #这行输出多少个
  6.         sum += 1 #sum是输出的数字
  7.         s = str(sum).ljust(4,"*")  #处理不足4位补位 
  8.         #ljust() 方法返回一个原字符串左对齐,并使用空格填充至指定长度的新字符
  9.         s = s
  10.         list.append(s) #添加到list
  11.         if i != count:  #不是最后一行
  12.             for time in range(count-i): #输出前的空格个数
  13.                 print('    ',end='')  #end='' 为不换行输出
  14.                 if i%2==1:  #奇数行正序输出
  15.                     for s in list:
  16.                         print(s,end = '    ')
  17.                     else:  #偶数行逆序输出
  18.                         for s in list[::-1]:
  19.                             print(s,end = '    ')
  20.     print()#换行

贪吃蛇

思路:
首先获取操作,然后生成地图,然后往地图上放东西,然后才开始找起点,遍历操作,计算结果 判断结果

  1. package Huawei;
  3. import java.util.LinkedList;
  4. import java.util.Scanner;
  6. /**
  7.  * @description:
  8.  * @author: Polaris
  9.  * @date: 2022/3/31 19:53
  10.  */
  11. public class no9 {
  12.     static char[][] arr =null;#二维数组
  13.     public static void main(String[] args) {#主函数
  14.         Scanner sc = new Scanner(System.in)
  15.         #Scanner sc = new Scanner(System.in);此句 表示从控制台获取数据，
  16.         #sc.hasNext() 表示你是否有输入数据，
  17.         #while语句块 表示当你输入数据的时候，就执行输出sc.next()（输出内容）
  18.         #所以只要你输入数据了，它就可以执行，
  19.         #具体的输入:
  20.         #GGG  #G上U下D左L右 G当前方向前进
  21.         #33  #行 列
  23.         #FFF  #H起始位置,F食物,E为空
  24.         #FFH
  25.         #EFE
  26.         #结局向左走了两步,吃到两个食物 第三步撞墙了,最后的长度为3
  27.         while (sc.hasNext()){
  28.             char[] ch = sc.nextLine().replaceAll(" ","").toCharArray();#ch是操作
  29.             int N = sc.nextInt();#NM生成地图
  30.             int M = sc.nextInt();
  31.             arr = new char[N][M];
  32.             for(int i =0;i<arr.length;i++){#往地图上塞东西
  33.                 for(int j = 0;j<arr[i].length;j++){
  34.                     arr[i][j] = sc.next().charAt(0);
  35.                 }
  36.             }
  37.             fun(arr,ch);#fun方法先是找到蛇的起点
  38.         }
  39.     }
  41.     static void fun(char[][] arr,char[] ch){#fun方法先遍历地图找到蛇的起点
  42.         LinkedList<int[]> snake = new LinkedList<>();?
  43.         int[] start = new int[2];
  44.         //先遍历地图找到蛇的起点
  45.         for(int i=0;i<arr.length;i++){
  46.             for(int j=0;j<arr[i].length;j++){
  47.                 if(arr[i][j] == 'H'){
  48.                     start[0]=i;
  49.                     start[1]=j;
  50.                     break;
  51.                 }
  52.             }
  53.         }
  54.         //起点入队
  55.         snake.add(start);
  56.         //遍历操作列表
  57.         for(int i =0;i<ch.length;i++){
  58.             int flag = 0;
  59.             if(ch[i]=='U'){
  60.                 flag=1;#flag只是用来区分不同操作的
  61.                 continue;
  62.             }else if(ch[i]=='D'){
  63.                 flag=-1;
  64.                 continue;
  65.             }else if(ch[i]=='L'){
  66.                 flag=-2;
  67.                 continue;
  68.             }else if(ch[i]=='R'){
  69.                 flag=2;
  70.                 continue;
  71.             }else if(ch[i]=='G'){
  72.                 switch (flag){
  73.                     case 1:
  74.                         start[0]++;#start 起点位置
  75.                         break;
  76.                     case -1:
  77.                         start[0]--;
  78.                         break;
  79.                     case 2:
  80.                         start[1]++;
  81.                         break;
  82.                     case -2:
  83.                         start[1]--;
  84.                         break;
  85.                 }
  86.                 if(isEnd(snake,start)){#根据flag就是对应的操作,来移动蛇的头,就是start
  87.                     #isEnd类判断是否结束
  88.                     break;
  89.                 }
  90.                 //吃到，只加不减#然后判断是撞墙了终结了 还是吃到东西了,还是没吃也没死
  92.                               #吃到就只加头到那个位置,没吃到还要把尾巴减一个
  95.                 if(arr[start[0]][start[1]]=='F'){
  96.                     snake.addFirst(start);
  97.                 }else{
  98.                     //没吃到，加头去尾
  99.                     snake.addFirst(start);#snake是个二维数组的list
  100.                     snake.removeLast();
  101.                 }
  102.             }
  103.         }
  104.         System.out.println(snake.size());
  109.     }
  111.     static boolean isEnd(LinkedList<int[]> list,int[] a){#判断结束的方法,就是判断撞墙和撞自己
  112.         //撞墙了
  113.         if(a[0]>=arr.length||a[1]>=arr[0].length)
  114.             return true;
  115.         //撞到自己了
  116.         for(int[] i:list){
  117.             if(i[0]==a[0]&&i[1]==a[1])
  118.                 return true;
  119.         }
  120.         return false;
  121.     }
  122. }

8皇后

具体的思路:

步骤1

第一个皇后先放在第一行第一列


步骤2

第二个皇后放在第二行第一列,然后判断是否与约束条件冲突,如果冲突,继续放在第二列,第三列直到找到一个合适的位置

步骤3

继续第三个皇后,同样是第一列,第二列直到第八个皇后也能放在一个不冲突的位置,算是找到一个正确解

步骤4

然后就开始回溯,一直到把第一个皇后放在第一列的所有正确解全都得到

步骤5

然后回头继续第把第一个皇后放在第二列,循环执行一到四,四个步骤

每次为下一个皇后，寻找合适的位置，就是试探。每次试探不到合理的位置，回头去改变前一个皇后的位置，就是回溯；排除没意义的试探，就是剪枝。上诉的解题过程，就是一个回溯法的思路。

  1. #!/usr/bin/env python 
  2. # -*- coding:utf-8 -*-
  3. __author__ = 'C2TR'
  4. def conflict(state, nextColumn):
  5.  """
  6.  判断下一行皇后位置是否与之前皇后的位置冲突
  7.  因为坐标是从0开始的，所以state的长度代表了下一行的行坐标
  8.  :param state:（7，4，6，0，2） 标记每行皇后所在的位置 （0，7）一行八列 （2，4） （3，6） （4，0） （5，2）
  9.  :param nextColumn:下一行的列坐标
  10.  :return:
  11.  """
  12.  nextRow = rows = len(state) # 5----下一行 = 行数 =state的长度
  13.  for row in range(rows):   #  0,1,2,3,4
  14.   # 获取当前行的列
  15.   column = state[row]
  16.   """
  17.   如何判断是否冲突：
  18.       1. 如果列的差值为0，说明两皇后在同一列
  19.       2. 如果列的差值等于行的差值，说明两皇后在对角线上
  20.   """
  21.   if abs(column - nextColumn) in [0, nextRow - row]:
  22.    return True
  23.  return False
  25. # 采用生成器的方式来产生每一个皇后的位置，并用递归来实现下一个皇后的位置
  26. def queens(num, state=()):#采用生成器的方式来产生每一个皇后的位置，并用递归思想实现回溯法计算出每一种结果的皇后的位置
  27.  """
  28.  基于递归采用回溯算法，算出每一种结果
  30.  :param num: 皇后的数量  8
  31.  :param state: 列坐标。初始为空。参数为元组不为列表，因为参数只能为不可变数据类型
  32.  :return:
  33.  """
  34.  # 每一行的列坐标都是从0:7的
  35.  # 0,1,2,3,4,5,6,7
  36.  for pos in range(num):#----循环8次
  37.   # 默认state为空。长度为0，但是是不冲突的
  38.   # 判断是否冲突，state为空时不冲突
  39.   if not conflict(state, pos): # 回溯法的体现----如果位置冲突判断函数返回值为false
  40.    # 如果state的长度为7，即到达了倒数第二行，也就是前7行皇后都已经找到了位置，最后一行又没有冲突，返回最后一行的列坐标
  41.    if len(state) == num - 1:#
  42.     # 最后一行的（pos,）=最后一行的result，然后再递归回去求倒数第二行的result
  43.     yield (pos,)
  44.    else:
  45.     for result in queens(num, state + (pos,)):
  46.      """
  47.      递归实现求state：
  48.          1. 向下递归
  49.          第一次（行）： pos=0，刚开始不会进入if len(state) == num - 1，进入执行else，会执行queens(num, state + (pos, ))，
  50.          第二次（行）： 进入else，再调用queens(num, state + (pos, )),递归执行queens(num, state + (pos,) + (pos,))
  51.          第三次（行）： 进入else，再调用queens(num, state + (pos,) + (pos,),递归执行queens(num, state + (pos,) + (pos,) + (pos,))
  52.          ...
  53.          第七次（行）： 执行和上面的一样，不过此时state的长度为7
  54.          第八次（行）： 执行f len(state) == num - 1:求出最后一行的列坐标(pos,)
  56.          2.向上递归
  57.          求出第八行的列坐标，就可以求出第七行的（pos,），返回的是第七行和第八行的列坐标（（pos，） + result）
  58.          根据下一行的结果依次求出上一行的结果；
  59.          ....
  60.          最后求出第一行的列坐标，返回整体结果
  61.      """
  62.      yield (pos,) + result#生成器,编写当前次数和
  64. def prettyprint(solution):#友好展示棋盘，画出每一种结果的皇后的位置
  65.  """
  66.  进行友好展示：为了至关表现棋盘，用X表示皇后的位置
  67.  :param solution:
  68.  :return:
  69.  """
  70.  def line(pos, length=len(solution)):
  71.   return '.' * (pos) + 'X' + '.' * (length - pos -1)
  73.  for pos in solution:
  74.   print(line(pos))
  77. if __name__ == '__main__':
  78.  solutions = queens(8)
  79.  for index, solution in enumerate(solutions):
  80.   print('第%d种解决方案：' %(index + 1), solution )
  81.   prettyprint(solution)
  82.   print('*' * 50)