【Java】力扣刷题笔记（一）_class solution {

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        // 双重循环 循环极限为(n^2-n)/2
        for(int i = 0; i < nums.length; i++){
            for(int j = nums.length - 1; j > i; j --){
                if(nums[i]+nums[j] == target){
                    indexs[0] = i;
                    indexs[1] = j;
                    return indexs;
                }
            }
        }
        return indexs;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        // 建立k-v ，一一对应的哈希表
        HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
        for(int i = 0; i < nums.length; i++){
            if(hash.containsKey(nums[i])){
                indexs[0] = i;
                indexs[1] = hash.get(nums[i]);
                return indexs;
            }
            // 将数据存入 key为补数 ，value为下标
            hash.put(target-nums[i],i);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(1)hash.containsKey()检查 hashMap 中是否存在指定的 key 对应的映射关系。
hash.containsValue()检查 hashMap 中是否存在指定的 value 对应的映射关系。
(2)hash.put()将键/值对添加到 hashMap 中
hash.get()获取指定 key 对应对 value
(3)hash.isEmpty()判断 hashMap 是否为空
hash.size()计算 hashMap 中键/值对的数量
hash.replace(K key, V oldValue, V newValue)替换 hashMap 中是指定的 key 对应的 value。
(4)keySet()返回 hashMap 中所有 key 组成的集合视图。
values()返回 hashMap 中存在的所有 value 值。

2.两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        int val = l1.val + l2.val;
        ListNode next = addTwoNumbers(l1.next, l2.next);
        if (val >= 10) {
            val -= 10;
            next = addTwoNumbers(next, new ListNode(1));
        }
        return new ListNode(val, next);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

167.两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。

class Solution {//双指针
    public int[] twoSum(int[] numbers, int target) {
        int n=numbers.length;
        for(int i=0,j=n-1;i<j;){
            int sum=numbers[i]+numbers[j];
            if(sum==target) return new int[] {i+1,j+1};
            else if(sum>target) j--;
            else i++;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

278.第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int i = 1, j = n;
        while (i < j) { // 循环直至区间左右端点相同
            int mid = i + (j - i) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                j = mid; // 答案在区间 [left, mid] 中
            } else {
                i = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return i;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

不能用（left+right）/2形式，当left和right都是int，两个值的初始值都超过int限定大小的一半，那么left+right就会发生溢出，所以应该用left+(right-left)/2来防止求中值时候的溢出。

189.轮转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

我的代码： 未考虑k>nums.length的情况

class Solution {
    public void rotate(int[] nums, int k) {
        int[] arr = new int[nums.length];
        for(int i=k;i>0;i--){
            arr[k-i] = nums[nums.length-i];
        }
        for(int j=0;j<nums.length-k;j++){
            arr[k+j] = nums[j];
        }
        System.arraycopy(arr, 0, nums, 0, nums.length);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

题解方法：采用翻转
该方法基于如下的事实：当我们将数组的元素向右移动 kk 次后，尾部 k\bmod nkmodn 个元素会移动至数组头部，其余元素向后移动 k\bmod nkmodn 个位置。
该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 k mod n个元素就被移至数组头部，然后我们再翻转 [0, k mod n-1] 区间的元素和 [k mod n, n-1]区间的元素即能得到最后的答案。

class Solution {
    private void reverse(int[] nums, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
    }
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

public class Solution {
    public int squareSum(int n) {
        int sum = 0;
        while(n > 0){
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow = n, fast = squareSum(n);
        while (slow != fast){
            slow = squareSum(slow);
            fast = squareSum(squareSum(fast));
        };
        return slow == 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

get新知识点：快慢指针
定义快慢指针fast和slow，起始都位于链表头部。规定fast每次后移两个位置，slow每次后移一个位置。
若链表无环，则fast遇到null节点时，立刻返回。
如果链中有环，fast和slow一定会再次相遇。
当fast和slow相遇时，额外使用指针ptr，并指向链表头部。ptr和slow每次都后移一个位置，最终它们会在入环点相遇。
时间复杂度：O(N)，N为链表节点数量，通过问题2和问题3的分析可知，slow与fast相遇时，slow不会绕环超过一周，寻找入环点时，也只走了环外距离a。因此，总的执行时间为：O(N)+O(N)=O(N)

496. 下一个更大元素

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1; //或者k>=n ? -1:nums2[k]
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1. boolean empty() 测试堆栈是否为空。
2. Object peek( )查看堆栈顶部的对象，但不从堆栈中移除它。
3. Object pop( )移除堆栈顶部的对象，并作为此函数的值返回该对象。
4. Object push(Object element)把项压入堆栈顶部。
5. int search(Object element)返回对象在堆栈中的位置，以 1 为基数。