1 两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

思路

这个题最简单的思路就是遍历，通过一个复杂度为 $n^2$ 的遍历，但要注意每次遍历只需要从选定的下标的下一个开始寻找，因为之前的都已经尝试过，不需要再次验证。
第二种解法始于对于 $n^2$ 的复杂度的优化，这时可以利用哈希表，快速的找到是否存在对应的下标变量

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; ++i) {
        if (hashtable.containsKey(target - nums[i])) {
            return new int[]{hashtable.get(target - nums[i]), i};
        }
        hashtable.put(nums[i], i);
    }
    return new int[0];
    }

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

---

21 合并两个有序链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

其思路类似于大小个两排排队，每次两排中大个先出列，一排为空时直接接上另一排，可使用递归的思想解决问题。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //判断是否有一队为空
    if (l1 == null) {   
        return l2;
    } else if (l2 == null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }

}

---

705 设计哈希集合

题目

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

• void add(key) 向哈希集合中插入值 key 。
• bool contains(key) 返回哈希集合中是否存在这个值 key 。
• void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

思路

要解决这个题目的前提是明白哈希是什么，以我的理解就是很多个桶，拿到值后先算出hash值，然后就知道要放进哪个桶里，有这个理解后，就可以写出初步题解。

链地址法

class MyHashSet {
	private static final int BASE = 769;
	private LinkedList<Integer>[] list;

	public MyHashSet() {
		// 初始化
		list = new LinkedList[BASE];
		for (int i = 0; i < BASE; i++) {
			list[i] = new LinkedList<Integer>();
		}
	}

	public void add(int key) {
		int hash = hash(key);
		if (!list[hash].contains(key)) {
			list[hash].push(key);
		}
	}

	public void remove(int key) {
		int hash = hash(key);
		if (list[hash].contains(key)) {
			list[hash].remove((Integer) key);
		}
	}

	public boolean contains(int key) {
		int hash = hash(key);
		return list[hash].contains(key);
	}

	private static int hash(int key) {
		return key % BASE;
	}
}

需要注意这里相当于取了 769 个桶，这是一个素数，取这个数的原因是利用了同余的概念：当元素是个有规律的等差数列时，并且和基数（数组大小）最大公约数不为 1 时，就会造成哈希映射时冲突变高（数组某些位置永远不会有值）。
比如数列 0,6,12,18,24,30...，base为 10，取模(0,6,2,8,4,0...)后，放入哈希表中位置将只能在 0,2,4,6,8 这几个数组位置上； 但我们如果把 base 取 7（数组大小甚至比 10 小），同样数列取模后(0,6,5,4,3,2,1,0,...)，可以分布在哈希表中的 0,1,2,3,4,5,6 所有位置上；

改进

有了初步的思路以后，想要改进就要考虑如果大量值的hash值重复，会造成一个桶里东西太多，到头还还是等同于遍历，可以优化哈希算法，包括开放地址法、再哈希法等等。

---

706 设计哈希映射

题目

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类。

思路

这题与705相差不多，代码热热还能用。
上代码

class MyHashMap {

	class Pair {
		private int key;
		private int value;

		public Pair(int key, int value) {
			this.key = key;
			this.value = value;
		}

		public int getKey() {
			return this.key;
		}

		public void setValue(int value) {
			this.value = value;
		}
	}

	private LinkedList[] list;
	private static final int BASE = 769;

	public MyHashMap() {
		list = new LinkedList[BASE];
		for (int i = 0; i < BASE; i++) {
			list[i] = new LinkedList<Pair>();
		}
	}

	public void put(int key, int value) {
		int hash = hash(key);
		Iterator<Pair> it = list[hash].iterator();
		while (it.hasNext()) {
			Pair existed = it.next();
			if (existed.getKey() == key) {
				existed.setValue(value);
				return;
			}
		}
		list[hash].add(new Pair(key, value));
	}

	public int get(int key) {
		int hash = hash(key);
		Iterator<Pair> it = list[hash].iterator();
		while (it.hasNext()) {
			Pair existed = it.next();
			if (existed.getKey() == key) {
				return existed.value;
			}
		}
		return -1;
	}

	public void remove(int key) {
		int hash = hash(key);
		Iterator<Pair> it = list[hash].iterator();
		while (it.hasNext()) {
			Pair existed = it.next();
			if (existed.getKey() == key) {
				list[hash].remove(existed);
                return;
			}
		}
	}

	private static int hash(int key) {
		return key % BASE;
	}
}

54 螺旋矩阵

题目

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序 ，返回矩阵中的所有元素。

思路

第一次拿到这个题我的想法是循环套循环，外层循环判断是否上下左右可以前进，内层循环按照先向右走到头，下、左、上同理的顺序来保证顺时针螺旋顺序，这里用一个boolean列表用来记录是否走过对应的格子

	private boolean[][] printed;
	private int rowNow = 0, colNow = 0;

    //判断是否能向对应方向走
	private boolean up() {
		if (rowNow == 0)
			return false;
		if (!printed[rowNow - 1][colNow])
			return true;
		return false;
	}

	private boolean down() {
		if (rowNow == printed.length - 1)
			return false;
		if (!printed[rowNow + 1][colNow])
			return true;
		return false;
	}

	private boolean left() {
		if (colNow == 0)
			return false;
		if (!printed[rowNow][colNow - 1])
			return true;
		return false;
	}

	private boolean right() {
		if (colNow == printed[0].length - 1)
			return false;
		if (!printed[rowNow][colNow + 1])
			return true;
		return false;
	}

	public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> list = new ArrayList<Integer>();
		int rows = matrix.length;
		int cols = matrix[0].length;
		printed = new boolean[rows][cols]; // 初始化都为false
		list.add(matrix[rowNow][colNow]); // 第一个
		printed[rowNow][colNow] = true;

		while (right()) {
			// 有路可走
			while (right()) {
				// 能向右走
				colNow++;
				list.add(matrix[rowNow][colNow]);
				printed[rowNow][colNow] = true;
			}

			while (down()) {
				// 能向下走
				rowNow++;
				list.add(matrix[rowNow][colNow]);
				printed[rowNow][colNow] = true;
			}

			while (left()) {
				// 能向左走
				colNow--;
				list.add(matrix[rowNow][colNow]);
				printed[rowNow][colNow] = true;
			}

			while (up()) {
				// 能向上走
				rowNow--;
				list.add(matrix[rowNow][colNow]);
				printed[rowNow][colNow] = true;
			}
		}
		return list;
	}

59 螺旋矩阵II

题目

给你一个正整数 $n$ ，生成一个包含 $1$ 到 $n^2$ 所有元素，且元素按 顺时针顺序螺旋排列 的 $n \times n$ 正方形矩阵 matrix 。

思路

思路同54
上代码

public int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n];
    int left = 0, right = n - 1, top = 0, bottom = n - 1;
    int count = 1;
    while (count <= n * n) {
        // 右
        for (int col = left; col <= right; col++) {
            matrix[top][col] = count++;
        }
        // 下
        for (int row = top + 1; row <= bottom; row++) {
            matrix[row][right] = count++;
        }
        if (left < right && top < bottom) {
            // 左
            for (int col = right - 1; col >= left; col--) {
                matrix[bottom][col] = count++;
            }
            // 上
            for (int row = bottom - 1; row > top; row--) {
                matrix[row][left] = count++;
            }
        }
        top++;
        bottom--;
        right--;
        left++;
    }
    return matrix;
}

基本思路大同小异，下面提供一种官方更简洁的方法：

class Solution {
    public int[][] generateMatrix(int n) {
        int maxNum = n * n;
        int curNum = 1;
        int[][] matrix = new int[n][n];
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
        int directionIndex = 0;
        while (curNum <= maxNum) {
            matrix[row][column] = curNum;
            curNum++;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {
                directionIndex = (directionIndex + 1) % 4; // 顺时针旋转至下一个方向
            }
            row = row + directions[directionIndex][0];
            column = column + directions[directionIndex][1];
        }
        return matrix;
    }
}

115 不同的子序列

题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

思路

这个题目很明显是一个动态规划的题目，利用空间保存之前的计算结果，通过状态转移公式得到下一状态的结果并保存。

假设字符串 s(sentence) 和 t(target) 的长度分别为 m 和 n。 建立一个(m+1)*(n+1)的数组dp：

通过dp[i][j]来保存s[i:]的子序列中 t[j:] 出现的个数

其中下表为m,n的分别表示最后为空字符串""的结果。

首先考虑几个初始状态，并初始化：

• 当 j=n 时，t[j:] 为空字符串，由于空字符串是任何字符串的子序列，因此对任意 0≤i≤m，有 dp[i][n] = 1；

• 当 i=m 且 j<n 时，s[i:] 为空字符串，t[j:] 为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意 0≤j<n，有 dp[m][j] = 0。

得到状态转移方程

于是可得到代码：

 public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length(); //便于之后使用
        //不可能情况
        if (m < n) {
            return 0;
        }
        //dp
        int[][] dp = new int[m + 1][n + 1];
        //初始化边界情况
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }
        
        for (int i = m - 1; i >= 0; i--) {
            char sChar = s.charAt(i);
            for (int j = n - 1; j >= 0; j--) {
                char tChar = t.charAt(j);
                if (sChar == tChar) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }

206 反转列表

题目

反转一个单列表

思路

最一般的方法是使用迭代将每一个指针指向前一个。
这种链表的题最容易想错的地方是改变了指向后忘记把原来存在的指针删除，导致思路出错。通俗来想是把这个节点的指向“掰”向另一个节点。
所以做链表的题应该先沉下心来，把思路完全想清楚了，然后用几行代码解决问题，而不是修修补补。

• 第一种迭代的思路： 共使用三个指针，一个记录当前节点curr，一个记录前一个节点prev，一个记录下一个节点next。每一次将当前节点的next指向前一个节点，直至当前节点为null。
  每次迭代的开始先记录下一个节点（块内变量），prev的初始值为null，刚好作为返还后的结束，之后每次迭代后要将prev的值改为curr。

    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode prev = null;   //初始值为null作为结束的指向
            ListNode curr = head;
            while (curr != null) {
                ListNode next = curr.next; //可在每次迭代时再声明临时变量保存
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    }

• 第二种递归的思路：
  这种思路比较难理解，但设计非常巧妙。其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？
  主要难以理解的地方在于：真正修改指向的操作在递归之后，也就是说是在回溯的阶段从后往前修改指向的， 上代码理解：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) { //包括一个节点的情况
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;  //后面的节点转向
        head.next = null;   //前面的节点指向null
        return newHead; //新的head依次传递回来
    }
}

191 位1的个数

题目

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

思路

解法1：
最简单直接的、不用位运算的思路就是使用Integer.toBinaryString(n)将十进制整数 n 转换成二进制字符串，然后遍历串的每一位检查是否为 1。

public int hammingWeight(int n) {
    String a = Integer.toBinaryString(n);   //Integer内置函数
    int count = 0;
    for(int i = 0; i < a.length(); i++){
        if(a.charAt(i)=='1') {
            count++;
        }
    }
    return count;
}

但这样效率比较低，如果可以直接操作二进制数，效率会高很多。
解法2：
使用位操作符，循环i从0到31，利用 n&(1<<i) 对比是否第i位上为1。

public int hammingWeight(int n) {
    int count = 0;
    for(int i = 0;i<32;i++) {
        if((n&(1<<i))!=0) {
            count++;
        }
    }
    return count;
}

解法3：
对于位运算的优化——注意到 n&(n-1) 可以让 n 最后一位 1 变为 0，于是循环直至 n==0。

public int hammingWeight(int n) {
    int count = 0;
    while(n!=0) {
        n = n&(n-1);
        count++;
    }
    return count;
}

73 矩阵置零

题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

思路

这是我第一次听说原地算法，说白了就是不利用或只利用固定的少量空间来完成题解，对于这个题，就是在原矩阵中做出标记完成理解。
对于这个题来说，如果某行某列是0，那么该行该列都要置为0，那么我们可以利用**第一行（第一列）**来保存是否该行（该列）要置为0。
其原理就在于反正这一块要被污染，就利用他来保存需要的标记。
存在的问题是需要额外的变量来保存是否第一行（第一列）本身需要被全部置零。可用[0,0]来保存是否第一行要被置零，这样就只需要一个额外的变量来保存是否第一列要被置零。

public void setZeroes(int[][] matrix) {
    boolean ifCol1Z = false; // 用来记录第一列是否需要置空
    int m = matrix.length, n = matrix[0].length;
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            // 第一列为0
            ifCol1Z = true;
        }
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[0][j] = matrix[i][0] = 0;
            }
        }
    }
    // 填充
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 1; j <= n - 1; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
        if (ifCol1Z) {
            matrix[i][0] = 0;
        }
    }
}

456 132模式

题目

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

进阶：很容易想到时间复杂度为 O(n^2) 的解决方案，你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？

思路

如题所说，很容易想到时间复杂度为O(n^2)的思路，以i, j, k标识，即遍历j，i保存为j以前最小的数，每一次遍历j都内部循环j右侧次大的数k（或比i最大的数中最小的那个）。
这样的算法问题出在每次求k都需要遍历，所以想到改进得到O(nlogn)的算法：使用平衡树记录j右边的数每次通过logn的复杂度获得j右侧次大的数k（或比i最大的数中最小的那个）。

这里用到的数据结构是TreeMap。用到的方法有：

• put
• ceilingKey
• remove
• getOrDefault

public boolean find132pattern(int[] nums) {
    int n = nums.length;
    if (n < 3)
        return false;

    // 至少3个
    int leftMin = nums[0];
    TreeMap<Integer, Integer> right = new TreeMap<Integer, Integer>();

    // 扫描从2开始右侧的所有，建立
    for (int k = 2; k < n; k++) {
        right.put(nums[k], right.getOrDefault(nums[k], 0) + 1);
    }

    for (int j = 1; j < n - 1; j++) {
        if (leftMin < nums[j]) {
            Integer tmp = right.ceilingKey(leftMin + 1);
            if (tmp != null && tmp < nums[j])
                return true;
        }
        // 为下一次循环更新
        // 计数减一
        right.put(nums[j + 1], right.get(nums[j + 1]) - 1);
        if (right.get(nums[j+1]) == 0)
            right.remove(nums[j+1]);
        leftMin = Math.min(leftMin, nums[j]);
    }
    return false;
}

61 旋转链表

题目

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
注意k可能大于链表的长度。

思路

解法1：
对于链表的循环，我初步的想法是因为链表循环 n 次会回到初始情况，所以实际上只需要移动 k%n 个位置，这样我第一遍得到链表的长度 n，之后通过几个变量移动 k%n 次即可。

public ListNode rotateRight(ListNode head, int k) {
    ListNode header = new ListNode(0,head);
    ListNode pre = header,pio = header;
    int count = 0;
    while(head!=null){
        head = head.next;
        count++;
    }
    if(count == 0 || count == 1) return header.next;

    for(int i = 0; i<k%count;i++){
        pio = pio.next;
    }
    while(pio.next!=null){
        pio = pio.next;
        pre = pre.next;
    }
    pio.next = header.next;
    header.next = pre.next;
    pre.next = null;
    return header.next;
}

解法2：
后来看到官方题解闭合为环，觉得很有意思，在这里分享一下。
首先遍历到链表尾部，顺便得到链表的长度 n，这样便只需要移动 k%n 次。
新的头部则在原头部 n-k%n 处，若 n-k%n 等于 n，则返回原头部。

    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || head == nullptr || head->next == nullptr) {
            return head;
        }
        int n = 1;
        ListNode* iter = head;
        while (iter->next != nullptr) {
            iter = iter->next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter->next = head;
        while (add--) {
            iter = iter->next;
        }
        ListNode* ret = iter->next;
        iter->next = nullptr;
        return ret;
    }

这里还有一个很有意思的循环 a 次的方法 while(a-- > 0)

190 颠倒二进制位

题目

颠倒给定的 32 位无符号整数的二进制位。

思路

在刚拿到这个题时本想偷个懒，利用Integer.toBinaryString得到字符串再乘加权简单通过，然后发现当使用Math.pow数字太大（比如2^31）时，java的double会变得不够精确，会有1的偏差，导致得到的结果会有差距而失败。只能通过位运算。
除了基本的解题方法（见代码）外，题解中的位运算分治方法思路比较清奇，在这里都贴出来。

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res |= (n&1)<<31-i;
        n>>=1;
    }
    return res;
}

方法2（位运算分治）：

class Solution {
private:
    const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
    const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
    const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111

public:
    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};