2655 字
13 分钟
让算法落地：「编程思维与实践」课程笔记
2023-06-13
推理到跑通
课程笔记
/
学习笔记

数据范围#

数据类型范围（2^x^）最大范围（10^x^）格式化控制符
unsigned int[0,2^32^-1]10^9^%u
int[-2^31^,2^31^-1]10^9^%d
long long[-2^63^,2^63^-1]10^18^%lld
unsigned long long[0,2^64^-1]10^19^%llu

ASCII码#

DecCharDecCharDecCharDecCharDecCharDecChar
3248064@80P**96 **`112p
33!49165A81Q**97 **a113q
34”50266B82R**98 **b114r
35#51367C83S**99 **c115s
36$52468D84T100d116t
37%53569E85U101e117u
38&54670F86V102f118v
39’55771G87W103g119w
40(56872H88X104h120x
41)57973I89Y105i121y
42*58:74J90Z106j122z
43+59;75K91[107k123{
44,60<76L92\108l124|
45-61=77M93]109m125}
46.62>78N94^110n126~
47/63?79O95_111o

数组传参#

void f(char s[10]); // f(char *s)
int main() {
    char s[10] = "LeeHero";
    f(s);
    return 0;
}
void f(char s[][10]); // f(char (*s)[10])
int main() {
    char s[5][10] = {"Lee","Hero"};
    f(s);
    return 0;
}

代码模板#

GCD/LCM#

int gcd(int a, int b) { return b>0?gcd(b,a%b):a; }
int lcm(int a, int b) { return a/gcd(a,b)*b; }

排序#

一般模板#

int cmp(const void *a, const void *b) {
    int x1 = *(int *)a;
    int x2 = *(int *)b;
    return x1-x2;
}


int main() {
    int arr[] = {10, 5, 15, 12, 90, 80};
    int n = sizeof(arr) / sizeof(arr[0]), i;
    qsort(arr, n, sizeof(int), cmp); // <- QSORT
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

结构体排序#

typedef struct {
  char usr[20]; char dom[20];
} EMAIL;


int cmp(const void *a, const void *b) {
  EMAIL *A = (EMAIL *)a;
  EMAIL *B = (EMAIL *)b;
  if (strcmp(A -> dom, B -> dom) == 0) {
    return strcmp(B -> usr, A -> usr);
  } else {
    return strcmp(A -> dom, B -> dom);
  }
}


int main() {
  EMAIL *data = 0;
  int T; scanf("%d", &T);
    EMAIL *data = (EMAIL *)malloc(sizeof(EMAIL)*(T+10));
  for (int i = 0; i < T; i++) {
    char ads[50] = {0};
    scanf("%s", &ads);
    strcpy((data+i) -> usr, GetUsr(ads));
    strcpy((data+i) -> dom, GetDom(ads));
  }
  qsort(data, T, sizeof(EMAIL), cmp); // <- QSORT
  for (int i = 0; i < T; i++)
    printf("%s@%s\n", data[i].usr, data[i].dom);
  return 0;
}

二维定长数组排序#

int cmp(const void *a, const void *b) {
  char *n1 = (char *)a;
    char *n2 = (char *)b;
  return myStrCmp(n1, n2);
}


int main() {
    char c; int i = 0; char words[120][100] = {0};
    scanf("%s", words[i++]);
    while ((c = getchar()) != '\n') { scanf("%s", words[i++]); }
    qsort(words, i, sizeof(words[0]), cmp); // <- QSORT
    for (int j = 0; j < i; j++) printf("%s ", words[j]);
    printf("\n");
  return 0;
}

二维动态数组排序#

int cmp(const void *a, const void *b) {
  int *n1 = *((int **)a);
  int *n2 = *((int **)b);
  return *(n1+1) - *(n2+1); //cmp car[x][1] & car[y][1]
}                             //belike ((int *)a)[1]-((int *)b)[1]


int main() {
  int n, t; scanf("%d %d",&n,&t);
  int **car = (int **)malloc(n*sizeof(int*));
  for (int i = 0; i < n; i++) {
    int *p = (int *)malloc(3*sizeof(int));
    *(car+i) = p;
  }
    qsort(car, n, sizeof(car[0]), cmp); // <- QSORT
    return 0;
}
int cmp(const void *a, const void *b) {
    char *p1 = *((char **)a);
    char *p2 = *((char **)b);
    //通过 *(p1+i) *(p2+i) 操作就可以解析到[一级指针所指字符串]的每个字符
    //从而做进一步的比较处理
    /* 后续省略 */
    return ret;
}


int main() {
  int N; scanf("%d", &N); char **email;
    email = (char **)malloc(N * sizeof(char*))； //char *email[N]
    for (int i = 0; i < N; i++) {
        scanf("%s", s);
        LEN = strlen(s);
        p = (char *)malloc((LEN+1) * sizeof(char));
        strcpy(p, s);
        *(email + i) = p;
    }
    qsort(email, N, sizeof(email[0]), cmp); // <- QSORT
    for (int i = 0; i < n; i++) printf("%s\n",*(email+i));
    return 0;
}

大整数#

#include <stdio.h>
#include <string.h>


typedef struct {
  int cnt, v[1000];  //个位在前存储
} BIGINT;


BIGINT int2BIG(int x) { //int转BIGINT
  BIGINT r = {0, {0}};
  while (x > 0) {
    r.v[r.cnt++] = x % 10;
    x /= 10;
  }
  return r;
}


BIGINT char2BIG(char *s) {
  BIGINT R = {0, {0}};
  int len = strlen(s);
  int i;
  R.cnt = len;
  for (i = len - 1; i >= 0; i--) {
    R.v[len - 1 - i] = s[i] - '0';
  }
  return R;
}


void printBIG(BIGINT a) {
  if (a.cnt == 0) {
    printf("0\n");
    return;
  }
  int len = a.cnt, i;
  while (a.v[len - 1] == 0)
    len--;
  for (i = len - 1; i >= 0; i--)
    printf("%d", a.v[i]);
  printf("\n");
}


BIGINT mul(BIGINT S, BIGINT T) {  //两个大整数相乘
  if (S.cnt == 0 || T.cnt == 0)
    return int2BIG(0);
  BIGINT R = {S.cnt + T.cnt, {0}};
  for (int i = 0; i < T.cnt; i++) {
    int t, k, j;
    int carry = 0;
    for (j = 0; j < S.cnt; j++) {
      t = S.v[j] * T.v[i] + carry + R.v[i + j];
      R.v[i + j] = t % 10;
      carry = t / 10;
    }
    k = i + j;
    while (carry > 0) {
      t = carry + R.v[k];
      R.v[k] = t % 10;
      carry = t / 10;
      k++;
    }
  }
  if (R.v[S.cnt + T.cnt - 1] == 0)
    R.cnt--; //最高位0不统计在一个大整数的位数中
  return R;
}


BIGINT add(BIGINT S, BIGINT T) {  //两个大整数相加
  BIGINT R = {0, {0}};
  int i, carry = 0;
  for (i = 0; i < S.cnt && i < T.cnt; i++) {
    int temp = (S.v[i] + T.v[i] + carry);
    R.v[i] = temp % 10;
    carry = temp / 10;
  }
  while (i < S.cnt) {
    int temp = S.v[i] + carry;
    R.v[i++] = temp % 10;
    carry = temp / 10;
  }
  while (i < T.cnt) {
    int temp = T.v[i] + carry;
    R.v[i++] = temp % 10;
    carry = temp / 10;
  }
  if (carry) {
    R.v[i++] = carry % 10;
  }
  R.cnt = i;
  return R;
}


int cmp(BIGINT S, BIGINT T) {  //两个大整数的比较
  int n = (S.cnt > T.cnt) ? S.cnt : T.cnt;
  for (int i = n - 1; i >= 0; i--)
    if (*(S.v + i) > *(T.v + i))
      return 1;
    else if (*(S.v + i) < * (T.v + i))
      return -1;
  return 0;
}


void SUB(BIGINT *S, BIGINT *T, BIGINT *result) { //大数减小数
  int n = (S->cnt > T->cnt) ? S->cnt : T->cnt;
  result->cnt = n;
  int carry = 0, i;
  for (i = 0; i < n; i++) {
    if ((*(S->v + i) + carry) < (*(T->v + i))) {
      *(result->v + i) = 10 + *(S->v + i) + carry - *(T->v + i);
      carry = -1;
    } else {
      *(result->v + i) = *(S->v + i) + carry - *(T->v + i);
      carry = 0;
    }
  }
  for (int i = n - 1; i >= 0 && !result->v[i]; i--)
    result->cnt--;
}


BIGINT BIGSUB(BIGINT S, BIGINT T, int *sign) {
  BIGINT R = {0, {0}};
  *sign = 1;
  if (cmp(S, T) >= 0) {
    *sign = 1;
    SUB(&S, &T, &R);
  } else {
    *sign = -1;
    SUB(&T, &S, &R);
  }
  return R;
}


int main() {
  char s1[600], s2[600];
  BIGINT a = {0, {0}}, b = {0, {0}}, c = {0, {0}};
  int sign = 1;
  while (scanf("%s %s", s1, s2) != EOF) {
    a = char2BIG(s1);
    b = char2BIG(s2);
    c = BIGSUB(a, b, &sign);
    if (sign == -1)
      printf("-");
    printBIG(c);
  }
  return 0;
}

代码示例#

进制转换#

#include <stdio.h>
#include <string.h>


const char mod[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";


int A2dec(char *sol, int A) {
  int len = strlen(sol);
  int weight = 1;
  int ans = 0;
  for (int i = 0; i < len; i++) {
    if (sol[i] >= 'a' && sol[i] <= 'z') sol[i] -= 'a'-'A';
  }
  for (int i = len-1; i > -1; i--) {
    int j;
    for (j = 0; j < strlen(mod); j++) if (mod[j] == sol[i]) break;
    ans += j*weight;
    weight *= A;
  }
  return ans;
}


void dec2B(int dec,int B,char *ans) {
  char temp[50]; int i = 0;
  if (dec == 0) temp[i++] = '0';
  while (dec) {
    temp[i++] = mod[dec%B];
    dec /= B;
  }
  int k = 0;
  for (int j = i-1; j > -1; j--) {
    ans[k++] = temp[j];
  }
  ans[k] = '\0';
}


int main() {
  int A, B; // A为起始，B为目标
  char sol[50]; // 转换数据
  scanf ("%d %s %d", &A, &sol, &B);
  int dec;
  dec = A2dec(sol,A);
  char ans[50];
  dec2B(dec,B,ans);
  printf("%s", ans);
  return 0;
}

台阶走法#

#include <stdio.h>
#include <string.h>


typedef unsigned long long int ull;


#define SIZE 500


typedef struct {
  int cnt, v[SIZE];
} BIGINT;


void printBIG(BIGINT b) {
  for (int i = 0; i < b.cnt; i++)
    printf("%d", b.v[b.cnt - 1 - i]);
  printf("\n");
}


BIGINT int2BIG(int x) {
  BIGINT r = {0, {0}};
  int flag = 0; //对0特判，但是没做0的add和mul
  while (x) {
    r.v[r.cnt++] = x % 10;
    x /= 10;
    flag = 1;
  }
  if (flag == 0) r.cnt = 1;
  return r;
}


BIGINT string2BIG(char *s) {
  BIGINT r = {0, {0}};
  r.cnt = strlen(s);
  for (int i = 0; i < r.cnt; i++)
    r.v[r.cnt - 1 - i] = s[i] - '0';
  return r;
}
BIGINT mul(BIGINT S, BIGINT T) {
  if (S.cnt == 0 || T.cnt == 0)
    return int2BIG(0);
  BIGINT R = {S.cnt + T.cnt, {0}};
  for (int i = 0; i < T.cnt; i++) {
    int t, k, j;
    int carry = 0;
    for (j = 0; j < S.cnt; j++) {
      t = S.v[j] * T.v[i] + carry + R.v[i + j];
      R.v[i + j] = t % 10;
      carry = t / 10;
    }
    k = i + j;
    while (carry) {
      t = carry + R.v[k];
      R.v[k] = t % 10;
      carry = t / 10;
      k++;
    }
  }
  if (R.v[S.cnt + T.cnt - 1] == 0)
    R.cnt--;
  return R;
}


BIGINT add(BIGINT S, BIGINT T) {
  BIGINT R = {0, {0}};
  int i, carry = 0;
  for (i = 0; i < S.cnt && i < T.cnt; i++) {
    int temp = (S.v[i] + T.v[i] + carry);
    R.v[i] = temp % 10;
    carry = temp / 10;
  }
  while (i < S.cnt) {
    int temp = S.v[i] + carry;
    R.v[i++] = temp % 10;
    carry = temp / 10;
  }
  while (i < T.cnt) {
    int temp = T.v[i] + carry;
    R.v[i++] = temp % 10;
    carry = temp / 10;
  }
  if (carry)
    R.v[i++] = carry % 10;
  R.cnt = i;
  return R;
}


//ull hash[101] = {0};
BIGINT hash[101];


int main() {
  for (int i = 0; i < 101; i++) {
    if (i <= 1)
      //hash[i] = 1;
      hash[i] = int2BIG(1);
    else if (i == 2)
      //hash[i] = 2;
      hash[i] = int2BIG(2);
    else if (i == 3)
      //hash[i] = 4;
      hash[i] = int2BIG(4);
    else if (i == 4)
      //hash[i] = 8;
      hash[i] = int2BIG(8);
    else {
      //hash[i] = hash[i - 1] + hash[i - 2] + hash[i - 3] + hash[i - 4];
      BIGINT r1 = add(hash[i - 1], hash[i - 2]);
      BIGINT r2 = add(hash[i - 3], hash[i - 4]);
      hash[i] = add(r1, r2);
    }
  }
  int T;
  scanf("%d", &T);
  for (int i = 0; i < T; i++) {
    int ptA, ptB; //path A/B
    int stB, stS; //Start Building/Step
    int edB, edS; //End Building/Step
    scanf("%d %d %d %d %d %d", &ptA, &ptB, &stB, &stS, &edB, &edS);
    //ull ans;
    BIGINT ans = {0, {0}};
    if (stB == edB) {
      if (ptA < stS || ptB > edS) {
        ans = hash[edS - stS];
      } else {
        //ans = hash[edS - ptB] * hash[ptB - ptA] * hash[ptA - stS] + hash[edS - stS];
        BIGINT r1 = mul(hash[edS - ptB], hash[ptB - ptA]);
        BIGINT r2 = mul(r1, hash[ptA - stS]);
        ans = add(r2, hash[edS - stS]);
      }
    } else if (stB != edB) {
      if (ptA < stS && ptB > edS || ptA > edS || ptB < stS) {
      /*B走廊在起点下方；A走廊在终点上方；AB包夹起点和终点*/
        //ans = 0;
        ans = int2BIG(0);
      } else if (ptA < stS) {
        //ans = hash[ptB - stS] * hash[edS - ptB];
        ans = mul(hash[ptB - stS], hash[edS - ptB]);
      } else if (ptB > edS) {
        //ans = hash[ptA - stS] * hash[edS - ptA];
        ans = mul(hash[ptA - stS], hash[edS - ptA]);
      } else {
        //ans = hash[ptB - stS] * hash[edS - ptB] + hash[ptA - stS] * hash[edS - ptA];
        BIGINT r1 = mul(hash[ptB - stS], hash[edS - ptB]);
        BIGINT r2 = mul(hash[ptA - stS], hash[edS - ptA]);
        ans = add(r1, r2);
      }
    }
    //printf("case #%d:\n%llu\n", i, ans);
    printf("case #%d:\n", i); printBIG(ans);
  }
  return 0;
}

皇后问题#

#include <stdio.h>


void Danger(int i, int j, char map[][200], int n) {
  /*Q的可攻击路径标记为D，遇到另外的Q则停止，并且把Q变为O*/
  for (int k = i+1; k < n; k++) { // 下
    if (map[k][j] == 'E') map[k][j] = 'D';
    if (map[k][j] == 'Q') { map[k][j] = 'O'; break; }
  }
  for (int k = i-1; k > -1; k--) { // 上
    if (map[k][j] == 'E') map[k][j] = 'D';
    if (map[k][j] == 'Q') { map[k][j] = 'O'; break; }
  }
  for (int k = j+1; k < n; k++) { // 右
    if (map[i][k] == 'E') map[i][k] = 'D';
    if (map[i][k] == 'Q') { map[i][k] = 'O'; break; }
  }
  for (int k = j-1; k > -1; k--) { // 左
    if (map[i][k] == 'E') map[i][k] = 'D';
    if (map[i][k] == 'Q') { map[i][k] = 'O'; break; }
  }
  for (int k = i+1, l = j+1; k < n && l < n; k++, l++) { // 右下
    if (map[k][l] == 'E') map[k][l] = 'D';
    if (map[k][l] == 'Q') { map[k][l] = 'O'; break; }
  }
  for (int k = i-1, l = j+1; k > -1 && l < n; k--, l++) { // 右上
    if (map[k][l] == 'E') map[k][l] = 'D';
    if (map[k][l] == 'Q') { map[k][l] = 'O'; break; }
  }
  for (int k = i-1, l = j-1; k > -1 && l > -1; k--, l--) { // 左上
    if (map[k][l] == 'E') map[k][l] = 'D';
    if (map[k][l] == 'Q') { map[k][l] = 'O'; break; }
  }
  for (int k = i+1, l = j-1; k < n && l > -1; k++, l--) { // 左上
    if (map[k][l] == 'E') map[k][l] = 'D';
    if (map[k][l] == 'Q') { map[k][l] = 'O'; break; }
  }
}


void Safe(int i, int j, char map[][200], int n);
  /*q的移动路径上若为E，标记为S，遇到Q变为S后停止，遇到O直接停止*/


int SafeCnter(char map[][200], int n) {
  /*统计地图中S的数目*/
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) if(map[i][j] == 'S') cnt++;
  }
  return cnt;
}


void Show(char map[][200], int n)；


int main() {
  int n; char c;
  char map[200][200];
  int Qpos[20000][2]; int Qind = 0;
  int qpos[2];
  scanf("%d", &n);
  c = getchar();
  /*读取地图*/
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%c", &map[i][j]);
      if (map[i][j] == 'Q') {
        Qpos[Qind][0] = i; Qpos[Qind][1] = j;
        Qind++;
      }
      if (map[i][j] == 'q') {
        qpos[0] = i; qpos[1] = j;
      }
    }
    c = getchar();
  }
  //printf("Qind:%d\n", Qind);
  /*标记危险格子*/
  for (int i = 0; i < Qind; i++) {
    int Qi = Qpos[i][0], Qj = Qpos[i][1];
    //printf("Qi:%d Qj:%d\n",Qi, Qj);
    Danger(Qi, Qj, map, n);
  }
  Safe(qpos[0], qpos[1], map, n);
  printf("%d\n",SafeCnter(map, n));
  return 0;
}
让算法落地：「编程思维与实践」课程笔记
https://leehenry.top/posts/debug_2_deploy/notesarchive/编思小抄/
作者
伏枥 | Henry Lee
发布于
2023-06-13
许可协议
CC BY-NC-ND 4.0
抽象空间的秩序：「线性代数」课程笔记
指针、数组、字符串的恩怨，这有你想知道的一切
自 2025 年启程，本站已伴您走过 34 天 / 集 32 篇，合 88570 字
最后落笔于 2025-09-23 02:48:30 / 留存 0 枚足迹，您是第 0 位同行者
© 2025 - 2025 伏枥 / 琼ICP备2025060528号 / 本站已加入 BLOGS·CN