1. 数组异或操作

image-20200623173137501

2. 左旋转字符串

image-20200623172910698

3. 删除中间节点

image-20200623175320130
思路：

题目中链表只给了要删除的节点，我们通过已知节点可以删除他的下一个节点，但是无法删除他本身

我们可以将他下一个节点的值赋给当前节点，那么该节点就变得和下一个节点一样了，此时我们只需删除下一个节点即可。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

4. 二进制求和

image-20200624175005659
不全对的一个想法：

通过Java自带的函数，将给出的两个字符串转化为十进制数相加，相加后的结果再转回二进制数的字符串

1
2
3
4
5
6
7
class Solution {
    public String addBinary(String a, String b) {
    
        return Integer.toBinaryString(Integer.parseInt(a,2) + Integer.parseInt(b,2));
    
    }
}

然而在 Java 中：

  • 如果字符串超过 3333 位，不能转化为 Integer
  • 如果字符串超过 6565 位，不能转化为 Long
  • 如果字符串超过 500000001500000001 位，不能转化为 BigInteger

因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。

更健壮的算法：

我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。

具体的，我们可以取 n=max{∣a∣,∣b∣}，循环 nn 次，从最低位开始遍历。我们使用一个变量 carry 表示上一个位置的进位，初始值为 0。记当前位置对其的两个位为 a_i 和 b_i ，则每一位的答案为 (carry + a_i + b_i) mod 2，下一位的进位为 (carry + a_i + b_i) / 2。重复上述步骤，直到数字 a 和 b 的每一位计算完毕。最后如果 carry 的最高位不为 0，则将最高位添加到计算结果的末尾。

注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。当然你也可以直接把 a 和 b 中短的那一个补 0 直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。这里的代码给出第一种的实现。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String addBinary(String a, String b) {

        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(),b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 -i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 -i) - '0') : 0;
            ans.append((char)(carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();
    
        return ans.toString();
    }
}