做题勿忘剪枝

无论是哪种题型，剪枝都不能忘

所谓剪枝就是在执行逻辑之前先把必然、显然不成立不满足的部分直接判断并去除，避免浪费不必要的时间

多轮遍历之取余%

有一个数组或集合我们需要多次遍历，

假设这个数组的长度是size，要遍历两次，代码如下：（利用余数获取二次遍历的下标，减少空间的开销）

for(int i = 0; i < 2*size; i++) {
    while(!st.empty() && nums[i % size] > nums[st.peek()]) {
        result[st.peek()] = nums[i % size];//更新result
        st.pop();//弹出栈顶
    }
    st.push(i % size);
}

动态规划难题常用的双层for循环累加技巧

参考：

说白了，其实是一种不定长参数的累加求和技巧

例1：

for(int i = 3; i <= n; i++) {
    for(int j = 1; j <= i-j; j++) {
        // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
        //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
        //j 最大到 i-j,就不会用到 dp[0]与dp[1]
        dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
        // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
        //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
    }
}

dp[i] = Math.max(dp[i], Math.max(j*(i-j),中取最大值的dp[i]就是中间拿个累加状态

例2：

for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
        //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
        dp[i] += dp[j - 1] * dp[i - j];
    }
}

dp[i] += dp[j - 1] * dp[i - j];使用+=，我们取的是最后的d[i]

位移运算替代乘除（2的幂）

左移（<<）和右移（>>/>>>）是位运算中用于调整数值大小的操作。左移一位相当于将数值乘以2，右移一位相当于将数值除以2。这些操作通常比使用乘法和除法运算符更快，因为它们是直接在二进制级别上操作的。
左移（<<）的例子：

int a = 3; // 二进制表示：0011
int b = a << 1; // 结果是 6，二进制表示：0110
// 相当于 a * 2

在这个例子中，a 的值左移一位，相当于将 a 乘以2。
右移（>>）的例子：

int a = 10; // 二进制表示：1010
int b = a >> 1; // 结果是 5，二进制表示：0101
// 相当于 a / 2

在这个例子中，a 的值右移一位，相当于将 a 除以2。
无符号右移（>>>）的例子：

int a = -2; // 二进制表示：11111111 11111111 11111111 11111110（符号位为1）
int b = a >>> 1; // 结果是 128，二进制表示：01111111 11111111 11111111 11111100（符号位变为0）
// 相当于 a / 2，不考虑符号位

在这个例子中，a 的值无符号右移一位，相当于将 a 除以2，并且结果的符号位变为0。
这些位运算在处理数值大小的调整时非常方便和高效，特别是当你需要频繁地乘以或除以2的幂时。它们可以直接操作内存中的位，避免了高级算术运算的复杂性和性能开销。

变量交换

面试官：请说出4种不使用第三方变量交换两个变量值的方法 - 知乎 (zhihu.com)

遇到交换变量值的问题，通常我们的做法是：定义一个新的变量，借助它完成交换。

t = a;
a = b; 
b = t;

但问题的重点是“不使用第三方变量”，那就变得“可爱”起来了。思考过后，抛出以下四种方法来解决该问题：

变量本身交换数值；
算术运算；
指针地址操作；
位运算；
以上四种方法均实现了不借助第三方变量来完成两个变量值的交换：
算术运算和位运算计算量相当，只能进行整形数据的交换；
地址运算中计算较复杂，可以很轻松的实现大类型（比如自定义的类或结构）的交换；
理论上重载 “^” 运算符，也可以实现任意结构的交换；

变量本身交换数值

b = (a + b) - (a = b);

首先执行 a + b 操作，然后将 b 赋值给 a，则 b = a + b - b = a，这就完成了 ab 的互换操作。

算术运算

综上所述，我们的步骤为

int a = 10;
int b = 15;
a = b - a; //b=15;a=5;
b = b - a; //b=10;a=5;
a = b + a; //b=10;a=15;

该算法只能用于整型类型。

异或运算

简单介绍一下异或的规则：

如果a、b两个值不相同，则异或结果为1；
如果a、b两个值相同，异或结果为0。

代码如下

int a=10, b=12;//二进制：a=1010;b=1100;
a = a^b;//a=0110;b=1100
b = a^b;//a=0110;b=1010
a = a^b;//a=1100;b=1010
System.out.println("a="+ a +",b="+ b);

执行结果

a=12,b=10

异或运算能够使数据中的某些位翻转，其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次，值不变。