LeetCode刷题
Type：Medium
https://leetcode-cn.com/problemset/all/
#8 字符串转换整数
需要注意几个测试用例
" +0 123"
" 0012"
"3.14"
先判断是否有正负号，然后循环数组，需要记得把 Character.isDigit(sc[i]) 加在循环条件里，保证只有当下一个字符是数字的时候才会把数值加起来。
class Solution {
public int myAtoi(String str) {
boolean isPos = true;
char[] sc = (str.trim() + " ").toCharArray();
int i = 0;
if (sc[0] == '-') {
isPos = false;
i++;
} else if (sc[0] == '+') {
isPos = true;
i++;
}
long value = 0;
while (i < sc.length && Character.isDigit(sc[i])) {
value = value * 10 + (sc[i] - '0');
i++;
if (value > Integer.MAX_VALUE) {
return isPos ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
}
value = isPos ? value : -value;
return (int) value;
}
}
#15 三数之和
首先对原数组进行排序。
最先想到的是三重循环，优化：
要满足 a + b + c = 0 ，则 a 一定是非正数，即 i 对应的数一定要小于等于 0 的，等于0的时候 a b c 都为 0 。同时 i 的循环应该是从 0 到 length - 3 的，即 0 <= i < length - 2 , 因为 j 要大于 i ，同理 k 要大于 j 。
实现如下：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
int v1;
int v2;
int v3;
for(int i = 0; i < nums.length-1 && nums[i] <= 0; ++i){
v1 = nums[i];
int j = i + 1;
int k = nums.length - 1;
while(k > j){
v2 = nums[j];
v3 = nums[k];
if(v1 + v2 + v3 > 0){
k--;
}else if(v1 + v2 + v3 < 0){
j++;
}
else if(v1 + v2 + v3 == 0){
List<Integer> tmp = new ArrayList<>();
tmp.add(v1);
tmp.add(v2);
tmp.add(v3);
if(!res.contains(tmp)){a
res.add(tmp);
}
j++;
k--;
}
}
}
return res;
}
}
上面这种写法虽然能满足题目，但是会超时，时间主要会消耗在 res.add() 之前的去重上。所以想通过 HashSet 来辅助去重（Hash表的查询时间O（1）因为查询的是每个元素的hashcode）。
想要可以自动拓展的数组 => List
想要元素不重复的数组 => Set
set内部排序由每个元素的hashcode决定
双重循环，v3 = -(v1 + v2) , 借助 HashMap 来判断原数组是否有 v3 这个值同时下标必须在 v2 之后，满足的话就可以放进 Set 中。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> res = new HashSet<>();
Map<Integer,Integer> map = new HashMap<>();
Arrays.sort(nums);
for(int i = 0;i < nums.length;++i){
map.put(nums[i],i);
}
int v1;
int v2;
int v3;
for(int i = 0; i < nums.length - 2 && nums[i] <= 0; ++i){
for(int j = i + 1; j < nums.length - 1 && j > i; ++j){
v1 = nums[i];
v2 = nums[j];
v3 = -(v1 + v2);
if(map.containsKey(v3) && map.get(v3) > j){
res.add(Arrays.asList(v1,v2,v3));
}
}
}
return new ArrayList<>(res);
}
}
#701 二叉搜索树中的插入操作
current 为当前结点，如果当前结点为 null ，那么就记录下 current 对应的 parent 结点，插入值小于 parent 结点的值，插入在左子树，反之插入在右子树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
root = new TreeNode(val);
return root;
}
boolean isLeft = false;
TreeNode current = root;
TreeNode parent = root;
while(current != null){
parent = current;
if(val < current.val){
current = current.left;
isLeft = true;
}else{
current = current.right;
isLeft = false;
}
}
TreeNode vNode = new TreeNode(val);
if(isLeft == true){
parent.left = vNode;
}else{
parent.right = vNode;
}
return root;
}
}
#2 两数相加
不能将链表中的每个元素一次性全部取出然后相加，然后把计算后的数值每一位都插入到链表中，因为可能会超出int整数范围。所以只能同时遍历两个链表对每一个元素依次相加。
需要用到的是一个进位符号，如果当前位置加和大于等于10，进位置为1；还需要一个curNode，作为辅助指针，指向当前应该插入的位置。
需要注意的测试用例是：
[9],[9]
输出的结果应该是[8,1]，首先当两数相加大于等于10的时候，sum应该等于对10取余。同时如果 l1 和 l2 如果都计算完了，但是进位标识是1的话还需要再添加一个元素进去。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0; // 进位
ListNode head = new ListNode(0);
ListNode curNode = head; // 辅助指针
while(l1 != null || l2 != null){
int sum = tmp;
if(l1 != null){
sum += l1.val;
}
if(l2 != null){
sum += l2.val;
}
ListNode tmpNode;
if(sum >= 10){
carry = 1;
tmpNode = new ListNode(sum % 10);
}else{
carry = 0;
tmpNode = new ListNode(sum);
}
curNode.next = tmpNode;
curNode = curNode.next;
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
if(carry == 1){
ListNode tmpNode = new ListNode(1);
curNode.next = tmpNode;
}
return head.next;
}
}
#120 三角形最小路径和
从最后一层往上计算，当前一层的值等于下一层相邻的两个数取最小再加上当前一层的数，不断网上，一直到第一层。
第一种方式：借助一个 n + 1 大小的数组，记录每一层的值，（最后一层是初始化的过程），然后输出数组第一个值就是最小路径和。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null || triangle.size() == 0){
return 0;
}
int[] res = new int[triangle.size()+1];
for(int i = triangle.size() - 1; i >= 0; --i){
for(int j = 0; j < triangle.get(i).size(); ++j){
res[j] = Math.min(res[j],res[j+1]) + triangle.get(i).get(j);
}
}
return res[0];
}
}
第二种方式：从倒数第二层开始计算，计算出当前位置的最小值后，直接重新赋值，不需要新的空间
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null || triangle.size() == 0){
return 0;
}
for(int i = triangle.size() - 2; i >= 0; --i){
for(int j = 0; j < triangle.get(i).size(); ++j){
Integer re = Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j+1)) + triangle.get(i).get(j);
triangle.get(i).set(j,re);
}
}
return triangle.get(0).get(0);
}
}
#220 存在重复元素Ⅲ
跟 #217 #219 关联性不大，#217 是找到重复元素，#219是找到重复元素并且是在一定范围内。这道题是要保证在一定的范围内（k），两个值的差的绝对值要不大于某个数（t）。
前面的 #217 可以使用双重循环运行完所有的测试用例，但是 #220 使用双重循环就会超时，所以使用 treeset 来辅助计算，二叉树的插入、删除、搜索都是O（logN）。总的时间复杂度降为O（N * logN）。
修改前：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(nums.length == 0 || k <= 0)
return false;
for(int i = 0; i < nums.length; ++i){
for(int j = i+1; j <= i + k; ++j){
if(j >= nums.length)
break;
long val = 0; // 用 long 是为了避免 int 超出范围
val = Math.abs((long)nums[i] - (long)nums[j]) > val ? Math.abs((long)nums[i] - (long)nums[j]) : val;
if(val <= t)
return true;
}
}
return false;
}
}
修改后：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(nums.length < 2 || k < 1 || t < 0)
return false;
TreeSet <Long> set = new TreeSet<Long>();
for(int i = 0; i < nums.length; ++i){
// set.subSet() 返回的类型是 SortedSet，返回值的范围是 [(long)nums[i]-t,(long)nums[i]+t+1))
SortedSet <Long> subSet = set.subSet((long)nums[i]-t,(long)nums[i]+t+1);
if(!subSet.isEmpty())
return true;
if(i >= k)
set.remove((long)nums[i-k]);
set.add((long)nums[i]);
}
return false;
}
}
#881 救生艇
贪心（双指针）
思路
如果最重的人可以与最轻的人共用一艘船，那么就这样安排。否则，最重的人无法与任何人配对，那么他们将自己独自乘一艘船。
这么做的原因是，如果最轻的人可以与任何人配对，那么他们也可以与最重的人配对。
算法
令 people[i] 指向当前最轻的人，而 people[j] 指向最重的那位。
然后，如上所述，如果最重的人可以与最轻的人共用一条船（即 people[j] + people[i] <= limit），那么就这样做；否则，最重的人自己独自坐在船上
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int i = 0;
int j = people.length - 1;
int boat = 0;
while(i <= j){
boat++;
if(people[i] + people[j] <= limit){
i++;
}
j--;
}
return boat;
}
}
#35 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
二分查找
class Solution {
public int searchInsert(int[] nums, int target) {
if(target < nums[0]){
return 0;
}else if(target > nums[nums.length - 1]){
return nums.length;
}else {
int low = 0;
int high = nums.length - 1;
while(low <= high){
int mid = (low + high) / 2;
if(target < nums[mid]){
high = mid - 1;
}else if(target == nums[mid]){
return mid;
}else {
low = mid + 1;
}
}
return low;
}
}
}
#74 搜索二维矩阵
先查找符合的行，然后下标从 1 … matrix[0].length - 2 通过二分查找来查找元素
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0){
return false;
}
int low = 0;
int high = matrix.length - 1;
while(low <= high){
int mid = (low + high) / 2;
if(target < matrix[mid][0]){
// 在 1 3 5 7 中查询
high = mid - 1;
}else if(target == matrix[mid][0] || target == matrix[mid][matrix[0].length - 1]){
return true;
}else if(target > matrix[mid][matrix[0].length - 1]){
// 在 23 30 34 50 中查询
low = mid + 1;
}else {
// 在 10 11 16 20 中查询
int l = 1; // 已经排除 10 和 20 不可能了
int h = matrix[0].length - 2;
while(l <= h){
int m = (l + h) / 2;
if(target < matrix[mid][m]){
h = m - 1;
}else if(target == matrix[mid][m]){
return true;
}else {
l = m + 1;
}
}
// 缺少这个 return 的话，会一直死循环
return false;
}
}
return false;
}
}
#240 搜索二维矩阵Ⅱ
矩阵具有以下特性：
1.每行的元素从左到右升序排列。
2.每列的元素从上到下升序排列。
从左下或者右上开始判断都可以，按台阶形状进行判断
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0){
return false;
}
// 从左下开始判断
// int i = matrix.length - 1;
// int j = 0;
// while(i >= 0 && j < matrix[0].length){
// if(matrix[i][j] == target){
// return true;
// }else if(matrix[i][j] < target){
// j = j + 1;
// }else {
// i = i - 1;
// }
// }
// 从右上开始判断
int i = 0;
int j = matrix[0].length - 1;
while(i < matrix.length && j >= 0){
if(matrix[i][j] == target){
return true;
}else if(matrix[i][j] > target){
j = j - 1;
}else {
i = i + 1;
}
}
return false;
}
}
#11 盛最多水的容器
Area = Max ( min ( height[i], height[j] ) * ( j-i ) ) { 其中 0 <= i < j < height.size() }
使用两个指针，值小的指针向内移动，这样就减小了搜索空间。因为面积取决于指针的距离与值小的值乘积，如果值大的值向内移动，距离一定减小，而求面积的另外一个乘数一定小于等于值小的值，因此面积一定减小，而我们要求最大的面积，因此值大的指针不动，而值小的指针向内移动遍历。
class Solution {
public int maxArea(int[] height) {
int i = 0;
int j = height.length - 1;
int area = 0;
while(i < j){
int h = Math.min(height[i], height[j]);
area = Math.max(area, (j - i) * h);
if(h == height[i])
i++;
else
j--;
}
return area;
}
}