头像

Hasity




离线:1天前


最近来访(1595)
用户头像
bug制造者
用户头像
次饭
用户头像
A_Miao
用户头像
Shockblade
用户头像
肥肠煎蛋
用户头像
HUSTzyk
用户头像
彩虹狗
用户头像
thunder005
用户头像
我要当猛1
用户头像
Fernweh_5
用户头像
Amazing168
用户头像
潮鸣
用户头像
平安_4
用户头像
bre
用户头像
selfknow
用户头像
hqyang
用户头像
无条件_0
用户头像
jaaa
用户头像
sheppard
用户头像
厉飞雨


Hasity
6天前

git 地址: https://github.com/Li-CW/kob。欢迎star。全部给出了详细注释。


核心文件及注释

AcGameObject.js

/*
    渲染引擎。AGO中的所有对象,再调用一次start函数之后,会每秒会每秒调用60次 update 函数。
*/

const AC_GAME_OBJECT = [];

export class AcGameObject {
  constructor() {
    //   将对象放入 AGO数组
    AC_GAME_OBJECT.push(this);
    // 时间差
    this.timedelta = 0;
    // 是否执行start函数
    this.has_called_start = false;
  }
  // 只执行一次
  start() {}
  // 每帧执行一次
  update() {}

  on_destroy() {}
  destroy() {
    this.on_destroy();
    for (let i in AC_GAME_OBJECT) {
      const obj = AC_GAME_OBJECT[i];
      if (obj === this) {
        AC_GAME_OBJECT.splice(i);
        break;
      }
    }
  }
}

let last_timestamp;
const step = (timestamp) => {
  // AGO中的对象,按照放入顺序执行,对于同一个对象的操作,后放入的会覆盖先放入的
  for (let obj of AC_GAME_OBJECT) {
    //   首先执行start函数
    if (!obj.has_called_start) {
      obj.has_called_start = true;
      obj.start();
    }
    // 之后指向update函数
    else {
      obj.timedelta = timestamp - last_timestamp;
      obj.update();
    }
  }
  last_timestamp = timestamp;
  requestAnimationFrame(step);
};
requestAnimationFrame(step);


Wall.js

/*
    Wall 类继承 AGO 类。首先执行 start 函数,然后每秒执行60次 update 函数。

    函数:
        构造函数接收一个墙块坐标与地图对象(地图对象中,保存了地图和画布)
        render 函数:在画布中画出墙体。

    注:创建 GameMap 对象的时候,在构造函数中,先将 GameMap 对象放入 AGO 中,
        然后在 create_walls 函数中创建墙体,在 Wall 构造的时候,将对象放入 AGO 中。
        GameMap 对象位于 Wall 对象前面,所以会先画背景,然后画墙体。
        符合正常逻辑。     
*/
import { AcGameObject } from "./AcGameObject";
export class Wall extends AcGameObject {
  constructor(r, c, gamemap) {
    // 将对象放入ACG数据
    super();
    this.r = r;
    this.c = c;
    this.gamemap = gamemap;
    this.color = "#B37226";
  }

  update() {
    this.render();
  }

  render() {
    // 获得单位长度
    const L = this.gamemap.L;
    // 获取画布
    const ctx = this.gamemap.ctx;
    // 设置颜色
    ctx.fillStyle = this.color;
    // 画出一块墙体
    ctx.fillRect(this.c * L, this.r * L, L, L);
  }
}

GameMap.js

/* 
    GameMap 类继承 AGO 类。首先执行 start 函数,然后每秒执行60次 update 函数。

    函数:
        构造函数接收地图dom对象和地图中的画布dom对象。
        check_connectivity 函数:检查地图的起点和终点是否联通
        create_walls 函数:创建地图中的墙体,并保证起点终点联通。
        start 函数:调用 create_walls, 创建地图中的墙体。
        update_size 函数:就算画布单位长度(一个小正方形的长度),更新画布边长。
        render 函数:画地图背景。(草地部分)
        update 函数:调用 update_size 函数,然后调用 render 。每秒60次渲染地图背景。

    注:创建 GameMap 对象的时候,在构造函数中,先将 GameMap 对象放入 AGO 中,
        然后在 create_walls 函数中创建墙体,在 Wall 构造的时候,将对象放入 AGO 中。
        GameMap 对象位于 Wall 对象前面,所以会先画背景,然后画墙体。
        符合正常逻辑。 
*/

import { AcGameObject } from "./AcGameObject";
import { Wall } from "./Wall";
export class GameMap extends AcGameObject {
  // GameMap.vue 组件中创建了这个类的对象,
  // 传入了canvas 的ctx, 和 background
  constructor(ctx, parent) {
    //   通过super函数,将该对象放入ACG数组。
    super();
    this.ctx = ctx;
    this.parent = parent;
    this.L = 0;
    this.rows = 13;
    this.cols = 13;

    this.inner_walls_count = 80;
    this.walls = [];
  }
  // 检测g的起点和终点是否联通
  check_connectivity(g, sx, sy, tx, ty) {
    if (sx == tx && sy == ty) return true;
    //  标记当前点已经走过,不用恢复现场
    g[sx][sy] = true;
    //   上下左右四个方向
    let dx = [-1, 0, 1, 0],
      dy = [0, 1, 0, -1];
    for (let i = 0; i < 4; i++) {
      let x = sx + dx[i],
        y = sy + dy[i];
      // 递归检测相邻点。因为四周墙,不用做越界检查
      if (!g[x][y] && this.check_connectivity(g, x, y, tx, ty)) {
        return true;
      }
    }
    return false;
  }
  // 创建地图中的墙
  create_walls() {
    //   g中保存的所有墙
    const g = [];
    // 地图四周画墙
    for (let r = 0; r < this.rows; r++) {
      g[r] = [];
      for (let c = 0; c < this.cols; c++) {
        g[r][c] = false;
      }
    }
    // 去除起点和终点的墙
    for (let r = 0; r < this.rows; r++) {
      g[r][0] = g[r][this.cols - 1] = true;
    }
    for (let c = 0; c < this.cols; c++) {
      g[0][c] = g[this.rows - 1][c] = true;
    }

    //填充中间的墙,对称填充。一次循环填两个墙体
    for (let i = 0; i < this.inner_walls_count / 2; i++) {
      // 每次随机一个位置,如过已经有墙,再次随机,直到找到没墙的点
      for (let j = 0; j < 1000; j++) {
        let r = parseInt(Math.random() * this.rows);
        let c = parseInt(Math.random() * this.cols);
        // 已经有墙了,就再次随机
        if (g[r][c] || g[c][r]) continue;
        // 如果是起点或者终点,不能画墙,再次随机
        if ((r == this.rows - 2 && c == 1) || (r == 1 && c == this.cols - 2))
          continue;
        // 对称画墙
        g[r][c] = g[c][r] = true;
        break;
      }
    }
    //   检查地图是否联通。复制一份地图,防止原地图被修改。
    const copy_g = JSON.parse(JSON.stringify(g));
    if (!this.check_connectivity(copy_g, this.rows - 2, 1, 1, this.cols - 2))
      return false;
    //   地图连通,画出墙体
    for (let r = 0; r < this.rows; r++) {
      for (let c = 0; c < this.cols; c++) {
        //   该位置有墙
        if (g[r][c]) {
          // 创建墙
          this.walls.push(new Wall(r, c, this));
        }
      }
    }
    return true;
  }
  // 初始化函数,只执行一次
  start() {
    //   这里最好也计算下地图的长宽和单位长度
    this.update_size();
    //   尝试创建地图,在1000次尝试过程中,出现合法地图则停止。
    for (let i = 0; i < 1000; i++) {
      if (this.create_walls()) break;
    }
  }
  // 更新地图长宽
  update_size() {
    //   计算单位长度
    this.L = parseInt(
      Math.min(
        this.parent.clientWidth / this.cols,
        this.parent.clientHeight / this.rows
      )
    );
    // 设置画布长宽
    this.ctx.canvas.width = this.L * this.cols;
    this.ctx.canvas.height = this.L * this.rows;
  }
  // 更新地图,每一帧执行一次。
  update() {
    //   先更新地图大小
    this.update_size();
    // 重新画地图
    this.render();
  }

  render() {
    // 画地图背景
    const color_even = "#AAD751",
      color_odd = "#A2D149";
    for (let r = 0; r < this.rows; r++) {
      for (let c = 0; c < this.cols; c++) {
        if ((c + r) % 2 == 0) {
          this.ctx.fillStyle = color_even;
        } else {
          this.ctx.fillStyle = color_odd;
        }
        this.ctx.fillRect(c * this.L, r * this.L, this.L, this.L);
      }
    }
  }
}

GameMap.vue

<!-- 
    地图组件。
    地图与背景大小相等(背景是矩形,地图就是矩形,背景是正方形,地图就是正方形)。
    地图中方法canvas(画布)。canvas(画布)竖直水平居中
    画布大小、画布内容在 GameMap 对象中进行填充。
    GameMap 创建时传入:地图dom对选对象和画布dom对象。
-->
<template>
    <!-- 地图里放个画布 -->
    <!-- ref作用:与当前dom元素关联 -->
    <div ref="parent" class="gamemap">
        <!-- 画布 -->
        <canvas ref="canvas"></canvas>
    </div>
</template>

<script>
import { GameMap } from "../assets/scripts/GameMap";
import { ref, onMounted } from "vue";
export default {
    setup() {
        const parent = ref(null);
        let canvas = ref(null);
        // 创建页面时执行该函数
        onMounted(() => {
            // 创建游戏地图,将画布与地图dom传入地图对象
            new GameMap(canvas.value.getContext('2d'), parent.value);
        });

        return {
            parent,
            canvas,
        }
    }
}
</script>

<style scoped>
/* 地图的大小和位置 */
div.gamemap {
    width: 100%;
    height: 100%;
    /* 竖直水平居中 */
    display: flex;
    justify-content: center;
    text-align: center;
}
</style>



Hasity
6天前

git 地址: https://github.com/Li-CW/kob。欢迎star。全部给出了详细注释。


核心文件及注释

AcGameObject.js

/*
    渲染引擎。AGO中的所有对象,再调用一次start函数之后,会每秒会每秒调用60次 update 函数。
*/

const AC_GAME_OBJECT = [];

export class AcGameObject {
  constructor() {
    //   将对象放入 AGO数组
    AC_GAME_OBJECT.push(this);
    // 时间差
    this.timedelta = 0;
    // 是否执行start函数
    this.has_called_start = false;
  }
  // 只执行一次
  start() {}
  // 每帧执行一次
  update() {}

  on_destroy() {}
  destroy() {
    this.on_destroy();
    for (let i in AC_GAME_OBJECT) {
      const obj = AC_GAME_OBJECT[i];
      if (obj === this) {
        AC_GAME_OBJECT.splice(i);
        break;
      }
    }
  }
}

let last_timestamp;
const step = (timestamp) => {
  // AGO中的对象,按照放入顺序执行,对于同一个对象的操作,后放入的会覆盖先放入的
  for (let obj of AC_GAME_OBJECT) {
    //   首先执行start函数
    if (!obj.has_called_start) {
      obj.has_called_start = true;
      obj.start();
    }
    // 之后指向update函数
    else {
      obj.timedelta = timestamp - last_timestamp;
      obj.update();
    }
  }
  last_timestamp = timestamp;
  requestAnimationFrame(step);
};
requestAnimationFrame(step);


Wall.js

/*
    Wall 类继承 AGO 类。首先执行 start 函数,然后每秒执行60次 update 函数。

    函数:
        构造函数接收一个墙块坐标与地图对象(地图对象中,保存了地图和画布)
        render 函数:在画布中画出墙体。

    注:创建 GameMap 对象的时候,在构造函数中,先将 GameMap 对象放入 AGO 中,
        然后在 create_walls 函数中创建墙体,在 Wall 构造的时候,将对象放入 AGO 中。
        GameMap 对象位于 Wall 对象前面,所以会先画背景,然后画墙体。
        符合正常逻辑。     
*/
import { AcGameObject } from "./AcGameObject";
export class Wall extends AcGameObject {
  constructor(r, c, gamemap) {
    // 将对象放入ACG数据
    super();
    this.r = r;
    this.c = c;
    this.gamemap = gamemap;
    this.color = "#B37226";
  }

  update() {
    this.render();
  }

  render() {
    // 获得单位长度
    const L = this.gamemap.L;
    // 获取画布
    const ctx = this.gamemap.ctx;
    // 设置颜色
    ctx.fillStyle = this.color;
    // 画出一块墙体
    ctx.fillRect(this.c * L, this.r * L, L, L);
  }
}

GameMap.js

/* 
    GameMap 类继承 AGO 类。首先执行 start 函数,然后每秒执行60次 update 函数。

    函数:
        构造函数接收地图dom对象和地图中的画布dom对象。
        check_connectivity 函数:检查地图的起点和终点是否联通
        create_walls 函数:创建地图中的墙体,并保证起点终点联通。
        start 函数:调用 create_walls, 创建地图中的墙体。
        update_size 函数:就算画布单位长度(一个小正方形的长度),更新画布边长。
        render 函数:画地图背景。(草地部分)
        update 函数:调用 update_size 函数,然后调用 render 。每秒60次渲染地图背景。

    注:创建 GameMap 对象的时候,在构造函数中,先将 GameMap 对象放入 AGO 中,
        然后在 create_walls 函数中创建墙体,在 Wall 构造的时候,将对象放入 AGO 中。
        GameMap 对象位于 Wall 对象前面,所以会先画背景,然后画墙体。
        符合正常逻辑。 
*/

import { AcGameObject } from "./AcGameObject";
import { Wall } from "./Wall";
export class GameMap extends AcGameObject {
  // GameMap.vue 组件中创建了这个类的对象,
  // 传入了canvas 的ctx, 和 background
  constructor(ctx, parent) {
    //   通过super函数,将该对象放入ACG数组。
    super();
    this.ctx = ctx;
    this.parent = parent;
    this.L = 0;
    this.rows = 13;
    this.cols = 13;

    this.inner_walls_count = 80;
    this.walls = [];
  }
  // 检测g的起点和终点是否联通
  check_connectivity(g, sx, sy, tx, ty) {
    if (sx == tx && sy == ty) return true;
    //  标记当前点已经走过,不用恢复现场
    g[sx][sy] = true;
    //   上下左右四个方向
    let dx = [-1, 0, 1, 0],
      dy = [0, 1, 0, -1];
    for (let i = 0; i < 4; i++) {
      let x = sx + dx[i],
        y = sy + dy[i];
      // 递归检测相邻点。因为四周墙,不用做越界检查
      if (!g[x][y] && this.check_connectivity(g, x, y, tx, ty)) {
        return true;
      }
    }
    return false;
  }
  // 创建地图中的墙
  create_walls() {
    //   g中保存的所有墙
    const g = [];
    // 地图四周画墙
    for (let r = 0; r < this.rows; r++) {
      g[r] = [];
      for (let c = 0; c < this.cols; c++) {
        g[r][c] = false;
      }
    }
    // 去除起点和终点的墙
    for (let r = 0; r < this.rows; r++) {
      g[r][0] = g[r][this.cols - 1] = true;
    }
    for (let c = 0; c < this.cols; c++) {
      g[0][c] = g[this.rows - 1][c] = true;
    }

    //填充中间的墙,对称填充。一次循环填两个墙体
    for (let i = 0; i < this.inner_walls_count / 2; i++) {
      // 每次随机一个位置,如过已经有墙,再次随机,直到找到没墙的点
      for (let j = 0; j < 1000; j++) {
        let r = parseInt(Math.random() * this.rows);
        let c = parseInt(Math.random() * this.cols);
        // 已经有墙了,就再次随机
        if (g[r][c] || g[c][r]) continue;
        // 如果是起点或者终点,不能画墙,再次随机
        if ((r == this.rows - 2 && c == 1) || (r == 1 && c == this.cols - 2))
          continue;
        // 对称画墙
        g[r][c] = g[c][r] = true;
        break;
      }
    }
    //   检查地图是否联通。复制一份地图,防止原地图被修改。
    const copy_g = JSON.parse(JSON.stringify(g));
    if (!this.check_connectivity(copy_g, this.rows - 2, 1, 1, this.cols - 2))
      return false;
    //   地图连通,画出墙体
    for (let r = 0; r < this.rows; r++) {
      for (let c = 0; c < this.cols; c++) {
        //   该位置有墙
        if (g[r][c]) {
          // 创建墙
          this.walls.push(new Wall(r, c, this));
        }
      }
    }
    return true;
  }
  // 初始化函数,只执行一次
  start() {
    //   这里最好也计算下地图的长宽和单位长度
    this.update_size();
    //   尝试创建地图,在1000次尝试过程中,出现合法地图则停止。
    for (let i = 0; i < 1000; i++) {
      if (this.create_walls()) break;
    }
  }
  // 更新地图长宽
  update_size() {
    //   计算单位长度
    this.L = parseInt(
      Math.min(
        this.parent.clientWidth / this.cols,
        this.parent.clientHeight / this.rows
      )
    );
    // 设置画布长宽
    this.ctx.canvas.width = this.L * this.cols;
    this.ctx.canvas.height = this.L * this.rows;
  }
  // 更新地图,每一帧执行一次。
  update() {
    //   先更新地图大小
    this.update_size();
    // 重新画地图
    this.render();
  }

  render() {
    // 画地图背景
    const color_even = "#AAD751",
      color_odd = "#A2D149";
    for (let r = 0; r < this.rows; r++) {
      for (let c = 0; c < this.cols; c++) {
        if ((c + r) % 2 == 0) {
          this.ctx.fillStyle = color_even;
        } else {
          this.ctx.fillStyle = color_odd;
        }
        this.ctx.fillRect(c * this.L, r * this.L, this.L, this.L);
      }
    }
  }
}

GameMap.vue

<!-- 
    地图组件。
    地图与背景大小相等(背景是矩形,地图就是矩形,背景是正方形,地图就是正方形)。
    地图中方法canvas(画布)。canvas(画布)竖直水平居中
    画布大小、画布内容在 GameMap 对象中进行填充。
    GameMap 创建时传入:地图dom对选对象和画布dom对象。
-->
<template>
    <!-- 地图里放个画布 -->
    <!-- ref作用:与当前dom元素关联 -->
    <div ref="parent" class="gamemap">
        <!-- 画布 -->
        <canvas ref="canvas"></canvas>
    </div>
</template>

<script>
import { GameMap } from "../assets/scripts/GameMap";
import { ref, onMounted } from "vue";
export default {
    setup() {
        const parent = ref(null);
        let canvas = ref(null);
        // 创建页面时执行该函数
        onMounted(() => {
            // 创建游戏地图,将画布与地图dom传入地图对象
            new GameMap(canvas.value.getContext('2d'), parent.value);
        });

        return {
            parent,
            canvas,
        }
    }
}
</script>

<style scoped>
/* 地图的大小和位置 */
div.gamemap {
    width: 100%;
    height: 100%;
    /* 竖直水平居中 */
    display: flex;
    justify-content: center;
    text-align: center;
}
</style>



Hasity
19天前

题意翻译

在数组中,在当前数右侧,找出比当前数小,且距离最远的数字。输出下标距离。

因此,核心在:找出比当前数小且最右的数字。

解题思路

启发:如果数组中最右侧有这个一个序列:a,b,c,8,d,e,f,6。8肯定不是任何一个数x的答案。因为如果8比x小,那个在8右侧的6,肯定比x小,且位于更右侧。6是更佳答案。

从左到右扫描数组,生成一个单调递增栈(栈中保存下标),任何一数 x 的答案,一定在栈中。

单调栈中保存的是数组下标,且下标对应的数组中的数字递增。所以,对于数组中的数字 x ,可以用二分法找到答案。

答案就是:下标对应数字比x小,且最接x的那个数。(类似于在递增数组中,二分找出比 x 小的最大数)。

#include<iostream>
using namespace std;
int a[100010];//保存身高
int st[100010];//单调栈
int top = -1;//栈顶
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        //栈顶比当前元素大,栈顶出栈
        while(top >= 0 && a[i] <= a[st[top]]){
            top--;
        }
        //当前元素入栈
        st[++top] = i;
    }

    //找出每一个数的答案
    for(int i = 0; i < n; i++){
        int x = a[i];
        //二分法
        int l = 0, r = top;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(a[st[mid]] >= x){
                r = mid -1;
            }
            else{
                l = mid;
            }
        }
        //根据下标输出结果
        //在 i 右侧,且比a[i] 小
        if(st[l] > i && a[st[l]] < x)
        {
            cout << st[l] - i - 1 << " ";
        }
        //右侧没有比a[i] 小的数字。
        else{
            cout << -1  << " "; 
        }
    }

    return 0;

}

n * logn




Hasity
24天前

题意解读

题目给一个无序数组,要输出将这个数组排好序后,数组第k个数字。

思路分析

快速选择算法:

  • 选取一个基准(参考快排),将数组分成左右两个部分,右边部分大于等于左边部分。
  • 根据数组分界位置与k的大小关系,判断要找的数字是在左半部分还是右半部分。
  • 对存在要找数字的那半部分数组递归处理,直到待处理的数组中只剩下一个数,这个数字就是要找的那个。

举例

对于数组:2 4 1 5 3 找排序后第3个数字。(数组元素下标从1开始)

  • 选基准,分数组:选基准2,将数组分成:2 ,1 | 4,5,3 两部分。
  • 判断分界线与3的关系:分界线在数组的第 2和3个元素之间,因为划分后数组右半部分大于等于左边部分,因此,排序后,第3个数字一定在右半部分数组。
  • 选基准,划分右半部分数组:选基准4,划分后整个数组的情况为:2,1| 4 , 3 | 5
  • 判断上一步分界线与3的关系:分界线在数组的第4和5个元素之间,因为划分后数组右半部分大于等于左边部分,因此,排序后,第3个数字一定在左半部分数组。也就是在2,1| 4 , 3 | 5 粗体部分中。
  • 选基准,划分粗体部分数组:选基准4,划分后整个数组的情况为:2,1| 3 | 4 | 5。
  • 判断上一步分界线与3的关系:分界线在数组的第3和4个元素之间,因为划分后数组右半部分大于等于左边部分,因此,排序后,第3个数字一定在左半部分数组。也就是在2,1| 3 | 4 | 5。 粗体部分中。
  • 此时,粗体部分就一个数字,就是要找的:将这个数组排好序后,数组第3个数字。

代码

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int n, k;

int findK(int a[], int l, int r, int k){
    //数组中就剩一个数了,就是要找的那个数字
    if(l >= r) return a[l];
    //选分界线,划分数组。这里选的是中间的数字
    int x = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        while(a[++i] < x);
        while(a[--j] > x);
        if(i < j){
            swap(a[i], a[j]);
        }
    }
    //判断分界线与k的关系,
    //如果k在分界线左边,处理左半部分数组
    //注意:这里j是数组下标从0开始,k是从1开始编号的,
    //j指向的是第 j + 1 个元素。
    if(j + 1 >= k)
        return findK(a, l, j, k);
    //否则k在分界线右边,处理左半部分数组
    else 
        return findK(a, j + 1, r, k);
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int res = findK(a, 0, n - 1, k);
    cout << res;
}



Hasity
24天前

排序算法千千万,快排虐我千万遍!!!能够完成这道题的排序算法很多,这里主要学习快速排序。

我爱思考

  • 有一个特殊的数组,他由左右两部分组成,并且右边部分的数字都大于等于左边数组中的数字。如下图:

若果分别将数组的左半部分排好序,右半部分排好序,整个数组就有序了。

  • 可以得出一个结论:将一个无需数组分成左右两部分,右边部中的每个树大于等于左边部分中的每个数。将左右部分分别排好序,整个数组就有序了。
  • 可以得出这样一个排序算法:这个算法会先将数组分成左右两部分,保证右半部分中的每个数大于等于左半部分中的每个数,然后分别对左右部分数组使用该算法排好序,那么整个数组就排好序了。

快排思路

  1. 首先设定一个分界值(基准值),通过该分界值将数组分成左右两部分。
  2. 将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
  3. 左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
  4. 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

代码

/*
快排写法千千万,
边界处理难又难,
大神算法背下来,
乐无边呀乐无边
*/
#include<iostream>
using namespace std;
int a[100010];
int n;
void quickSort(int a[], int l, int r){
    //如果数组中就一个数,就已经排好了,直接返回。
    if(l >= r) return;
    //选取分界线。这里选数组中间那个数
    int x = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    //划分成左右两个部分
    while(i < j){
        while(a[++i] < x);
        while(a[--j] > x);
        if(i < j){
            swap(a[i], a[j]);
        }
    }
    //对左部分排序
    quickSort(a, l, j);
    //对右部分排序
    quickSort(a, j + 1, r);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    quickSort(a, 0, n - 1);
    for(int i = 0; i < n; i++){
        cout << a[i] << " ";
    }
}

重要的建议:快排算法划分的边界处理很很麻烦,找一个神的写好的,背下来。




Hasity
25天前

思路

一个数的约数是由这个数的几个质因子相乘得到的。

例如:12 的质因子有 2,3。12的约数有:1,2,3,4,6,12。

  • 约数1 是由 0 个 2, 0 个3相乘得到的。
  • 约数2 是由 1 个 2, 0 个3相乘得到的。
  • 约数3 是由 0 个 2, 1 个3相乘得到的。
  • 约数4 是由 2 个 2, 0 个3相乘得到的。
  • 约数6 是由 1 个 2, 1 个3相乘得到的。
  • 约数12 是由 2 个 2, 1 个3相乘得到的。

12 可以分解为:2^2*3^1。所以2可以取 0 ~ 2个,3种取法。3可以取 0~1 个,2种取法。12的质因子一共:2 * 3 = 6个。

也就是:把一个数N 写成:N = (p1^x1^)(p^x2)(p3^x3)…(pk^xk),其中pi为质数。则N的约数个数为:(x1+1)(x2+1)(x3+1)…(xk+1)

理论点的证明

写了也没人看。

代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int mod = 1e9+7 ;
int main()
{
    int T; 
    cin >> T;
    unordered_map<int, int> h;
    while(T--)
    {
        int n; cin >> n;
        //依次求出指数
        for(int i = 2; i <= n / i; i++)
        {
            while(n % i == 0)
            {
                //指数+1
                h[i] ++;
                n = n / i;
            }
        }
        //如果有剩余,也是一个质因子
        if(n > 1) h[n]++;
    }

    long long  res = 1;
    for(auto iter = h.begin(); iter != h.end(); iter++)
    {
        //res = (x1+1)(x2+1)(x3+1)…(xk+1)
        res = res * (iter->second + 1) % mod ;
    }
    cout << res;
}



Hasity
25天前

思路

什么是约数:如果一个数a除以另一个数b的余数为0,即 a%b == 0, 则b是a的约数。

如何求一个数x的所有约数

  • 用 x 除以 1 到 x 的所有数,如果余数是0,则把除数加到答案中。

可以优化吗?

  • 如果 a / b = c···0,则一定有 a % c = b····0。所以一个数 x 的约数肯定是成对存在的,对称轴是 根号x。
  • 因此,只需要用 x 除以 1 到 根号x 之间的数,如果余数是0,则把除数以及x / 除数加到答案中。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        vector<int> res;
        //因为约数成对出现,所以只需要循环到根号x
        // 不要是用 i *i <= n,因为可能溢出
        for(int i = 1; i <= n /i; i++)
        {
            if(n % i == 0)
            {
                res.push_back(i);
                //如果i * i = x,添加i即可,不用添加 x / i
                if(n / i != i)
                    res.push_back(n / i);
            }
        }
        sort(res.begin(), res.end());
        for(auto x : res) cout << x << " ";
        cout << endl;

    }
}



Hasity
25天前

什么是最大公约数

最大公约数(Greatest Common Divisor)指两个或多个整数共有约数中最大的一个。也称最大公因数、最大公因子,a, b的最大公约数记为(a,b),同样的,a,b,c的最大 公约数记为(a,b,c),多个 整数的最大公约数也有同样的记号。求最大公约数有多种 方法,常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。

辗转相减法求最大公约数

用(a,b)表示a和b的最大公因数:有结论(a,b)=(a,ka+b),其中a、b、k都为自然数。

也就是说,两个数的最大公约数,将其中一个数加到另一个数上,得到的新数,其公约数不变,比如(4,6)=(4+6,6)=(4,6+2×4)=2.

要证明这个原理很容易:如果p是a和ka+b的公约数,p整除a,也能整除ka+b.那么就必定要整除b,所以p又是a和b的公约数,从而证明他们的最大公约数也是相等的.

基于上面的原理,就能实现我们的迭代相减法:(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2

基本上思路就是大数减去小数,一直减到能算出来为止,在作为练习的时候,往往进行到某一步就已经可以看出得值.

辗转相减到辗转相除

迭代相减法简单,不过步数比较多,实际上我们可以看到,在上面的过程中,由(78,14)到(8,14)完全可以一步到位,因为(78,14)=(14×5+8,14)=(8,14),由此就诞生出我们的辗转相除法.

即:(a, b) = (a % b, b) = (b, a %b)

相当于每一步都把数字进行缩小,等式右边就是每一步对应的缩小结果。

对(a, b)连续使用辗转相除,直到小括号内右边数字为0,小括号内左边的数就是两数最大公约数。

代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int a, b;
        cin >> a >> b;
        //辗转相除,直到小括号内右边数为0
        while(b)
        {
            //c 一定小于 b
            int c = a % b;
            //小括号左边放除数,右边放约数
            a = b;
            b = c;
        }
        //小括号内左边数为最大公约数
        cout << a << endl;
    }
}

聊胜于无的优化

对于(a, b),如果 a % b == 0, 则b就是最大公约数,可以提前结束循环。

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int a, b;
        cin >> a >> b;
        //a % b == 0, 则b就是最大公约数,可以提前结束循环。
        while(a % b)
        {
            int c = a % b;
            a = b;
            b = c;
        }
        cout << b << endl;
    }

}


新鲜事 原文

Hasity
2个月前
AcWing《SpringBoot框架课》拼团优惠!https://www.acwing.com/activity/content/introduction/1877/group_buy/91454/


新鲜事 原文

Hasity
2个月前
AcWing《SpringBoot框架课》拼团优惠!https://www.acwing.com/activity/content/introduction/1877/group_buy/91454/