月度归档： 2021年8月

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

题解

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int otherNum = target-nums[i];
            if (map.containsKey(otherNum) && map.get(otherNum)!=i){
                res[0] = map.get(otherNum);
                res[1] = i;
            }
            map.put(nums[i], i);
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

8月23每日一题

力扣插件挂了，获取不到题面列表，我也拿不到题面的html代码了。。

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：

• nums[0] = 0
• nums[1] = 1
• 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
• 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的 最大 值。

示例 1：

输入：n = 7
输出：3
解释：根据规则：
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
因此，nums = [0,1,1,2,1,3,2,3]，最大值 3

示例 2：

输入：n = 2
输出：1
解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1

题解

emmm简单题，直接按照题意把代码撸一下

public int getMaximumGenerated(int n) {
    int[] nums = new int[n + 1];
    if (n == 0) {
        return nums[0];
    }
    nums[1] = 1;
    int maxNum = 1;
    for (int i = 1; 2 * i <= n || 2 * i + 1 <= n; i++) {
        nums[2 * i] = nums[i];
        maxNum = Math.max(maxNum, nums[2 * i]);
        if (2 * i + 1 <= n) {
            nums[2 * i + 1] = nums[i] + nums[i + 1];
            maxNum = Math.max(maxNum, nums[2 * i + 1]);
        }
    }
    return maxNum;
}

简单模拟计算。另外有个规律其实，最大值总是出现在奇数位上的。所以求max的操作只要在奇数位、即if (2 * i + 1 <= n)的判断体内部执行应该就可以了

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

题解

和之前一题LeetCode刷题 【83】 删除排序链表中的重复元素略有不同，这次需要删除的不再是多余的重复元素，而是所有有重复元素的都删除，只留下在原来链表中只出现过一次的节点。

和官方题解思路有点点点不一样的地方。。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {

        ListNode fakeHead = new ListNode();
        ListNode fakeCurrent = fakeHead;

        ListNode current = head;
        int sameVal;
        while (null != current){
            if (current.next!=null && current.val == current.next.val){
                sameVal = current.val;
                while (null!=current && current.val == sameVal){
                    current = current.next;
                }
            }else{
                fakeCurrent.next = current;
                current = current.next;
                fakeCurrent = fakeCurrent.next;
            }
        }
        fakeCurrent.next = null;
        return fakeHead.next;
    }
}

新建了一个fakeHead,和对应这个fakeHead往后遍历的fakeCurrent，然后在遍历原链表的时候，用这个fakeCurrent串起来需要的不重复的节点，最终需要把fakeCurrent的next置空。串珠子的意思。。。

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

题解

如果不限条件的话，额外申请一个hash表，遍历数组，记录每个在遍历过程中遇到的数字，遍历完成后，再从1开始自增到hash中查询，第一个查不到的即为结果。

代码简单

class SolutionByHashSet {
        Set<Integer> set;
        public int firstMissingPositive(int[] nums) {
            set = new HashSet<>();
            for (int num : nums) {
                if (num>=0 && num<=num){
                    set.add(num);
                }
            }
            for (int i = 1; i <= nums.length; i++) {
                if (!set.contains(i)){
                    return i;
                }
            }
            return nums.length+1;
        }
    }

但是题目要求，常数级别额外空间，就需要再想想了，题目提供的是数组，而数组组和连续正数相关的话，自然会想到数组索引下标，那么依次遍历，把对应的值放到对应下标位置上是不是可行呢？不过不同的是，把数字1放在下标0的位置，数字2，放在下标1的位置……这样的方法。

拿用例想一下试试【3,4,-1,1】

• 下标0位置得到数字3，那么3应该把他放到下标2的位置，所以两个下标上面的值进行交换得到新的数组【-1,4,3,1】
• 此时下标0位置的值为-1，-1这个值找不到对应的下标下标上去放置，那么我们再去处理下标1位置的值
• 到了下标1之后，这个位置的值是4，把它和对应下标3位置的值交换，得到新的排序【-1,1,3,4】。
• 此时下标1位置的值为1，继续把这个值和对应下标0的位置值交换，新的数组排序是【1,-1,3,4】
• 此时下标1位置的值为-1，那么去处理下一个下标位置上的值，后面略过，因为对应位置的值都是对应的

最终再从头开始遍历一遍判断对应下标置上的值是否是+1的数字

代码

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i]!= i+1){
                //终止条件
                //当前位置上的值再不能对应到nums的索引0到nums.length-1上
                //即，nums[i]的值在1-nums.length之间，包含区间
                if (nums[i] < 1 || nums[i]>nums.length){
                    break;
                }
                //有重复值
                if (nums[i] == nums[nums[i]-1]){
                    break;
                }
                swap(nums,i,nums[i]-1);
                //当前位置的值等于对应值，即nums[i]== i+1这个发生在交换之后
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]!= i+1){
                return i+1;
            }
        }
        return nums.length+1;
    }


    private void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}

最后提交的时候还是漏了一个里面有重复值的情况。于是再次加了个

if (nums[i] == nums[nums[i]-1]){
    break;
}

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

题解

8月20日每日一题，简单

转换成char数组，然后从下标0开始，往后k个，一次分段内翻转，一次调过不动作，如此循环。

最后一个循环如果需要翻转，且往后k个位置数组越界了，则取数组最后下标

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {


    public String reverseStr(String s, int k) {
        k--;
        char[] chars = s.toCharArray();
        boolean ifSkip = false;
        for (int i = 0; i < s.length(); i += k+1) {
            if (ifSkip){
                ifSkip = false;
            }else{
                ifSkip = true;
                reverseSubStr(chars,i, Math.min(i + k, chars.length - 1));
            }
        }
        return new String(chars);
    }


    public void reverseSubStr(char[] s,int left, int right){
        char tmp;
        while (left < right){
            tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

为啥我一开始要k–呢，因为下面每次遍历子分段边界的问题。

另外每次for循环的时候会差一个，所以额外需要再加1。

当然也可以每次移动2k个位置。然后运用双指针，把开头和到k位置的字符翻转

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

题解

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current!=null && current.next != null){
            if (current.val == current.next.val){
                current.next = current.next.next;
            }else{
                current = current.next;
            }
        }
        return head;
    }
}
//leetcode submit region end(Prohibit modification and deletion)