1. 算法：
字符串翻转
class Solution {
public void reverseString(char[] s) {
if (s == null || s.length <= 1) {
return ;
}
int i = 0;
int j = s.length - 1;
while(i < j) {
swap(s, i++, j--);
}
}
private void swap(char[] s, int i, int j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
冒泡、快排、选择
冒泡
public void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public int[] bubbleSort(int[] array) {
int n = array.length;
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n - i -1 ; j++) {
if (array[j] > array[j+1]) {
swap(array, j, j+1);
}
}
}
return array;
}
快排
static int partition(int[] unsorted, int low, int high)
{
int pivot = unsorted[low];
while (low < high)
{
while (low < high && unsorted[high] > pivot) high--;
unsorted[low] = unsorted[high];
while (low < high && unsorted[low] <= pivot) low++;
unsorted[high] = unsorted[low];
}
unsorted[low] = pivot;
return low;
}
static void quick_sort(int[] unsorted, int low, int high)
{
int loc = 0;
if (low < high)
{
loc = partition(unsorted, low, high);
quick_sort(unsorted, low, loc - 1);
quick_sort(unsorted, loc + 1, high);
}
}
选择排序
//选择排序的优化
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i; // 最小的值取a[i]
for(int j = k + 1; j < arr.length; j++){// 选最小的记录
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
翻转链表
https://www.cnblogs.com/byrhuangqiang/p/4311336.html
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
ListNode pCurr = head;
while( pCurr != null) {
ListNode pNext = pCurr.next;
pCurr.next = dummy.next;
dummy.next = pCurr;
pCurr = pNext;
}
return dummy.next;
}
斐波拉契数列
public int Fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int c = 2, b = 1, a = 0;
for (int i = 2; i <= n; i++) {
c = b + a;
a = b;
b = c;
}
return c;
}
限流算法
1. 令牌桶
令牌桶算法是一个存放固定容量令牌的桶，按照固定速率往桶里添加令牌。令牌桶算法的描述如下：
1. 假设限制2r/s，则按照500毫秒的固定速率往桶中添加令牌；
2. 桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝；
3. 当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上；
4. 如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。
2. 漏桶算法
漏桶作为计量工具（The Leaky Bucket Algorithm as a Meter）时，可以用于流量整形（Traffic Shaping）和流量控制（TrafficPolicing），漏桶算法的描述如下：
1. 一个固定容量的漏桶，按照常量固定速率流出水滴；
2. 如果桶是空的，则不需流出水滴；
3. 可以以任意速率流入水滴到漏桶；
4. 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。
令牌桶和漏桶对比：
令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；
漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；
令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；
漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；
令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率；
两个算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的。
3. 计数器限流算法
计数器限流算法也是比较常用的，主要用来限制总并发数，比如数据库连接池大小、线程池大小、程序访问并发数等都是使用计数器算法。
死锁
一般来说，要出现死锁问题需要满足以下条件：
1. 互斥条件：一个资源每次只能被一个线程使用。
2. 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
3. 不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。
4. 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。
只要破坏死锁 4 个必要条件之一中的任何一个，死锁问题就能被解决。
解决死锁的方式：
1. 以确定的顺序加锁
2. 超时放弃
网友评论