package com.dominic;
import edu.princeton.cs.algs4.StdRandom;
public class Sort {
private static boolean less(Comparable x, Comparable y)
{ return x.compareTo(y) < 0; }
private static void exchange(Comparable[] a, int i, int j)
{ Comparable t = a[i]; a[i] = a[j]; a[j] = t;}
public static void show(Comparable[] a){
for (Comparable comparable : a)
System.out.print(comparable + " ");
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for (int i = 1;i < a.length;i++)
if(less(a[i],a[i-1]))
return false;
return true;
}
public static void selection(Comparable[] a){
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i + 1; j < N; j++)
if (less(a[j], a[min])) min = j;
exchange(a,i,min);
}
}
public static void insertion(Comparable[] a){
int N = a.length;
for (int i=1;i<N;i++){
for (int j = i;j>0&&less(a[j],a[j-1]);j++)
exchange(a,j,j-1);
}
}
public static void shell(Comparable[] a){
int N = a.length;
int h = 1;
while (h < N/3)
h = 3*h+1;
while (h >= 1){
for (int i = h;i < N;i++){
for(int j = i;j>=h && less(a[j],a[j-h]);j-=h)
exchange(a,j,j-h);
}
h = h/3;
}
}
public static void merge(Comparable[] a){
Comparable[] aux = new Comparable[a.length];
_merge_sort(a, aux,0, a.length-1);
}
private static void _merge_sort(Comparable[] a, Comparable[] aux, int lo, int hi){
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
_merge_sort(a, aux, lo, mid);
_merge_sort(a, aux, mid+1, hi);
_merge(a, aux, lo, mid, hi);
}
private static void _merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi){
int i = lo, j = mid + 1;
if (hi + 1 - lo >= 0) System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
for (int k = lo; k <= hi; k++){
if (i>mid) a[k]=aux[j++];
else if (j>hi) a[k]=aux[i++];
else if (less(aux[j],aux[i])) a[k]=aux[j++];
else a[k]=aux[i++];
}
}
public static void quick(Comparable[] a){
StdRandom.shuffle(a);
_quick_sort(a, 0, a.length-1);
}
private static void _quick_sort(Comparable[] a, int lo, int hi){
if (hi <= lo) return;
int j = _partition(a, lo, hi);
_quick_sort(a, lo, j-1);
_quick_sort(a, j+1, hi);
}
private static int _partition(Comparable[] a, int lo, int hi){
int i = lo, j = hi + 1;
Comparable v = a[lo];
while(true){
while(less(a[++i],v)) if(i==hi) break;
while(less(v,a[--j])) if(j==lo) break;
if(i >= j) break;
exchange(a, i, j);
}
exchange(a, lo, j);
return j;
}
public static void quick3way(Comparable[] a){
StdRandom.shuffle(a);
_quick3way_sort(a, 0, a.length-1);
}
private static void _quick3way_sort(Comparable[] a, int lo, int hi){
if (hi<=lo) return;
int lt = lo, i = lo + 1, gt = hi;
Comparable v = a[lo];
while(i <= gt){
int cmp = a[i].compareTo(v);
if (cmp<0) exchange(a, lt++, i++);
else if (cmp > 0) exchange(a, i, gt--);
else i++;
}
_quick3way_sort(a, lo, lt-1);
_quick3way_sort(a, gt+1, hi);
}
}
博客
-
排序算法学习
-
第一棵完全二叉树与树的输入
啊，仿照数据结构上的二叉树递归写法根本实现不了，最后发现原来是要传递指针的呀，该死！还要注意形参与实参的区别，用于统计的数应该以指针的形式直接访问内存修改数据，而不是用形参。
无论如何，我实现了自己的第一棵完全二叉树及树的输入，嘻嘻嘻。下面放上代码（很烂）。
#include <stdio.h> #include <string.h> #include <stdlib.h> #define status int typedef struct Tree{ char data; struct Tree *lchild; struct Tree *rchild; }Tree,*tree; tree CreatBiTree(char * string,int *p,tree t){ if(*p>=strlen(string)) return NULL; if(string[*p]==' ') return NULL; else{ t=(Tree*)malloc(sizeof(Tree)); t->data=string[*p]; (*p)++; t->lchild=CreatBiTree(string, p, t->lchild); (*p)++; t->rchild=CreatBiTree(string, p, t->rchild); } return t; } status printTree(tree t){ if(t==NULL) { printf("null "); return 0; } printf("%c ",t->data); printTree(t->lchild); printTree(t->rchild); return 0; } int main() { tree root; int *p; p=(int*)malloc(sizeof(int)); *p=0; char * test; test=(char*)malloc(100* sizeof(char)); gets(test); root=CreatBiTree(test,p,root); printf("root: %c \nfull tree: ",root->data); printTree(root); printf("\np's trace: %d",*p); return 0; } -
Java关键字
下面列出了 Java 关键字。这些保留字不能用于常量、变量、和任何标识符的名称。
类别 关键字 说明 访问控制 private 私有的 protected 受保护的 public 公共的 类、方法和变量修饰符 abstract 声明抽象 class 类 extends 扩充,继承 implements 实现（接口） interface 接口 native 本地，原生方法（非 Java 实现） new 新,创建 static 静态 strictfp 严格,精准 synchronized 线程,同步 transient 短暂 volatile 易失 程序控制语句 break 跳出循环 case 定义一个值以供 switch 选择 continue 继续 default 默认 do 运行 else 否则 for 循环 if 如果 instanceof 实例 return 返回 switch 根据值选择执行 while 循环 错误处理 assert 断言表达式是否为真 catch 捕捉异常 finally 有没有异常都执行 throw 抛出一个异常对象 throws 声明一个异常可能被抛出 try 捕获异常 包相关 import 引入 package 包 基本类型 boolean 布尔型 byte 字节型 char 字符型 double 双精度浮点 float 单精度浮点 int 整型 long 长整型 short 短整型 变量引用 super 父类,超类 this 本类 void 无返回值 保留关键字 goto 是关键字，但不能使用 const 是关键字，但不能使用 null 空 -
136. 只出现一次的数字
- 交换律：a ^ b ^ c <=> a ^ c ^ b
- 任何数于0异或为任何数 0 ^ n => n
- 相同的数异或为0: n ^ n => 0
var a = [2,3,2,4,4]2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3这个异或法我真的没想到，还是基础不扎实呀！
int singleNumber(int* nums, int numsSize){ int n=nums[0]; for(int i=1;i<numsSize;i++) n=n^nums[i]; return n; } -
C语言printf输出的小玩法
在输出时候加上 “\033[ ; m …… \033[0m ” 即可使得输出的字体和背景是有颜色的。下面是颜色的定义：
字背景颜色范围:40 – 49
40:黑
41:深红
42:绿
43:黄色
44:蓝色
45:紫色
46:深绿
47:白色
字颜色:30 – 39
30:黑
31:红
32:绿
33:黄
34:蓝色
35:紫色
36:深绿
37:白色
下面看一下：ANSI控制码的说明
\33[0m 关闭所有属性
\33[1m 设置高亮度
\33[4m 下划线
\33[5m 闪烁
\33[7m 反显
\33[8m 消隐
\33[30m — \33[37m 设置前景色
\33[40m — \33[47m 设置背景色
\33[nA 光标上移n行
\33[nB 光标下移n行
\33[nC 光标右移n行
\33[nD 光标左移n行
\33[y;xH设置光标位置
\33[2J 清屏
\33[K 清除从光标到行尾的内容
\33[s 保存光标位置
\33[u 恢复光标位置
\33[?25l 隐藏光标
\33[?25h 显示光标
-
一个去除字符串空格的小函数
void removeBlanks(char * string) { int len = (int) strlen(string), count = 0; for (int i = 0; i < len; i++) { if (string[i] == ' ') { count++; continue; } string[i - count] = string[i]; } string[len-count]=0; }用了几种复杂的方法，最后才回归本质😅。
-
实现了代码很烂的KMP算法
先是看算法导论和数据结构
后来又自己又上YouTube看视频
就是这个视频，讲得很清晰 然后附上代码做纪念：
int KMP(char * string, char * pattern){ int len=(int)strlen(pattern), l=(int)strlen(string), *next; next=(int*)malloc((len+1)*sizeof(int)); for(int i=1,j=0;i<len;i++){ if(pattern[i]==pattern[j]) { next[i]=j+1; j++; continue; } if(j==0) continue; i--; j=(next[j]==0)?0:(next[j]-1); } for(int i=0,j=0;i<l;i++){ if(string[i]==pattern[j]){ j++; if(j==len) return i+1-len; continue; } if(j==0) continue; i--; j=next[j-1]; } return -1; }以后再改进吧！继续努力💪！
