剑指Offer

06 从尾到头打印链表

class Solution {
    int i;
    int j;
    int[] res;
    public int[] reversePrint(ListNode head) {
        solve(head);
        return res;
    }

    public void solve(ListNode head){
        if(head == null){
            res = new int[i];
            return;
        }
        i ++;
        solve(head.next);
        res[j] = head.val;
        j ++;
    }
}

15 二进制中1的个数

1. 位移法 时间复杂度O(N) N为二进制数的位数

   public class Solution {
       // you need to treat n as an unsigned value
       public int hammingWeight(int n) {
           int res = 0;
           for(int i = 0; i < 32; i ++){
               if((n & (1 << i)) != 0){
                   res ++;
               }
           }
           return res;
       }
   }

2. “与”操作法 【最优解法】时间复杂度O(K) K为二进制数中1的个数

   public class Solution {
       // you need to treat n as an unsigned value
       public int hammingWeight(int n) {
           int res = 0;
           while(n != 0){
               res ++;
               n = n & (n - 1);
               //n & (n-1)会将二进制代码中最后一位的1变成0
           }
           return res;
       }
   }

18 删除链表的节点

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        while(head != null){
            if(head.val != val){
                break;
            }
            head = head.next;
        } //找到第一个非空的头结点，用于返回和执行下步操作
        ListNode pre = head;
        ListNode cur = head;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}

24 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = head;
        while(next!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

35 复杂链表的复制

class Solution {
    Map<Node, Node> res = new HashMap<>();
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        if(!res.containsKey(head)){
            Node clone = new Node(head.val);
            res.put(head, clone);
            clone.next = copyRandomList(head.next);
            clone.random = copyRandomList(head.random);
        }
        return res.get(head);
    }
}

65 不用加减乘除做加法

/*
思路：
      首先看十进制是如何做的： 5+7=12，三步走 第一步：相加各位的值，不算进位，得到2。
      第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
      第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。 同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 
      第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。 
      第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。 
      第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。 继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
*/
public class Solution {
    public int Add(int num1,int num2) {
        while (num2!=0) {
            int temp = num1^num2;
            num2 = (num1&num2)<<1;
            num1 = temp;
        }
        return num1;
    }
}