Algorithms 🔗
小tips 🔗
字符串的加法 🔗
从低位到高位，逐位相加（带进位）
public String add(String num, int startF, int endF, int startS, int endS){ //字符串的加法
StringBuffer third = new StringBuffer();
int carry = 0, cur = 0; //进位和当前的和
while(endF >= startF || endS >= startS || carry != 0){
cur = carry; // 进位先赋值给当前和
if(endF >= startF){
cur += num.charAt(endF) - '0';
endF--;
}
if(endS >= startS){
cur += num.charAt(endS) - '0';
endS--;
}
carry = cur/10;
cur %= 10;
third.append((char)(cur+'0'));
}
return third.reverse().toString();
}
栈的应用 🔗
运行中动态的改变栈中的内容，以达到逐步计算的效果
class Solution {
public boolean parseBoolExpr(String expression) {
int n = expression.length();
Deque<Character> deque = new ArrayDeque<>();
// Deque<Character> deque_logic = new ArrayDeque<>();
for(int i = 0; i < n; i++){
char ch = expression.charAt(i);
if(ch == ',')
continue;
else if(ch == ')'){
int t = 0, f = 0;
while(deque.peekFirst() != '('){
char temp = deque.pollFirst();
if(temp == 't')
t++;
else
f++;
}
deque.pollFirst();
char expr = deque.pollFirst();
if(expr == '!'){
deque.addFirst(t == 0 ? 't' : 'f');
}else if(expr == '&'){
deque.addFirst(f > 0 ? 'f' : 't');
}else{
deque.addFirst(t > 0 ? 't' : 'f');
}
}else{
deque.addFirst(ch);
}
}
return deque.poll() == 't';
}
}
Peterson算法 🔗
该算法是一个实现互斥锁的并发程序设计算法，可以控制两个线程访问一个共享的单用户资源而不发生访问冲突
boolean flag[2];
int turn;
void procedure0()
{
while(true)
{
flag[0]=true;
turn=1;
while(flag[1]&&turn==1) /*若flag[1]为false，P0就进入临界区；若flag[1]为tureP0循环等待，只要P1退出临界区，P0即可进入*/
{
/* donothing*/
}
visit();/*访问临界区*/
flag[0]=false;/*访问临界区完成，procedure0释放出临界区*/
/*remainder section*/
}
}
void procedure1()
{
while(true)
{
flag[1]=true;
turn=0;
while(flag[0]&&turn==0)
{
/* donothing*/ ;
}
visit();/*访问临界区*/
flag[1]=false;/*访问临界区完成，procedure1释放出临界区*/
/*remainder section*/
}
}
void main()
{
flag[0]=flag[1]=false;
/*start procedure0 and procedure1*/ ;
}
该算法满足解决临界区问题的三个必须标准：互斥访问, 进入， 有限等待。
-
互斥访问
-
- P0与P1显然不会同时在临界区: 如果进程P0在临界区内，那么或者flag[1]为假(意味着P1已经离开了它的临界区)，或者turn为0(意味着P1只能在临界区外面等待，不能进入临界区).
-
进入
-
- 进入(Progress)定义为：如果没有进程处于临界区内且有进程希望进入临界区, 则只有那些不处于剩余区(remainder section)的进程可以决定哪个进程获得进入临界区的权限，且这个决定不能无限推迟。剩余区是指进程已经访问了临界区，并已经执行完成退出临界区的代码，即该进程当前的状态与临界区关系不大。
-
有限等待
Kadane算法 🔗
用于求最大的子数组和
算法描述：遍历数组，遍历过程中，将遍历到的元素依次累加起来（前缀和），当累加结果小于或等于0时，从下一个元素开始，重新开始累加。（该算法基于dp）
类似于dp，优化了空间复杂度。
位运算 🔗
计算二进制数中1的位数
n & n-1 //将n的最后一位1变为0
图论 🔗
前缀和+单调队列[862.和至少为k的最短子数组](862. 和至少为 K 的最短子数组 - 力扣（LeetCode）) 🔗
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] pre = new long[n+1];
for(int i = 0; i < n; i++){
pre[i+1] = pre[i] + nums[i]; //前缀和
}
int res = n+1;
Deque<Integer> queue = new ArrayDeque<>();
for(int i = 0; i <= n; i++){
long curSum = pre[i];
while(!queue.isEmpty() && curSum - pre[queue.peekFirst()] >= k){
res = Math.min(res, i - queue.pollFirst());
}
while(!queue.isEmpty() && pre[queue.peekLast()] >= curSum){ // 保持单调递增
queue.pollLast();
}
queue.offer(i);
}
return res < n+1 ? res : -1;
}
}
886. 可能的二分法 🔗
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) { // 求二分图
int m = dislikes.length;
List<Integer>[] lists = new List[n];
for(int i = 0; i < n; i++){
lists[i] = new ArrayList<>();
}
for(int i = 0; i < m; i++){ // 建图
lists[dislikes[i][0] - 1].add(dislikes[i][1] - 1);
lists[dislikes[i][1] - 1].add(dislikes[i][0] - 1);
}
int[] status = new int[n]; // 保存各个结点的状态 0 未使用 1/2 已使用
for(int i = 0; i < n; i++){
if(status[i] == 0 && !dfs(lists, status, i, 1)) // 逐一判断
return false;
}
return true;
}
public boolean dfs(List<Integer>[] lists, int[] status, int cur, int now){
status[cur] = now;
for(int next : lists[cur]){
if(status[next] != 0 && status[next] == status[cur])
return false;
if(status[next] == 0 && !dfs(lists, status, next, 3^now)) // 异或运算 改变状态
return false;
}
return true;
}
}
Dp 🔗
鸡蛋掉落 🔗
//暴力dp O(kn^2)
public int superEggDrop(int k, int n) {
int[][] dp = new int[k+1][n+1];
for (int i = 1; i <= n; ++i)
dp[1][i] = i; //1个蛋
for (int i = 1; i <= k; ++i)
dp[i][1] = 1; //1层楼
for (int i = 2; i <= k; ++i) {
for (int j = 2; j <= n; ++j) {
int ans = 100;
for (int v = 1; v <= j; ++v) {
ans = Math.min(ans, Math.max(dp[i-1][v-1], dp[i][j-v]));
}
dp[i][j] = ans + 1;
}
}
return dp[k][n];
}
//dp + 二分 (递归)
Map<Integer, Integer> map = new HashMap<>();
public int superEggDrop(int k, int n) {
return dp(k,n);
}
public int dp(int k, int n) {
if (!map.containsKey(n * 100 + k)) {
int ans = 0;
if (n == 0)
ans = 0;
else if (k == 1){
ans = n;
} else {
int l = 1, r = n;
while(l + 1 < r) {
int x = (l + r) / 2;
int t1 = dp(k-1, x-1);
int t2 = dp(k, n - x);
if (t1 < t2) {
l = x;
} else if (t1 > t2)
r = x;
else
l = r = x;
}
ans = 1 + Math.min(Math.max(dp(k-1,l-1), dp(k,n-l)), Math.max(dp(k-1,r-1), dp(k, n-r)));
}
map.put(n * 100 + k, ans);
}
return map.get(n * 100 + k);
}