前言

最近繁琐的事情比较多，所以没有连续学习（好吧我也懒，没有在当天补回来，所以今天还是来一点简单题吧，所以今天的题目可能比较水，基本上没有难度）

题目

day09

最大子数组和（经典）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1] 输出：1 示例 3：

输入：nums = [5,4,-1,7,8] 输出：23

这个题目第一个最先想到的就是暴力求解嘛 N的平方复杂度。
找出所有子串，然后返回最大值，但是这样的复杂度不管是时间还是空间，那个都不低。所以这里使用 Dp 思想去做。

那么为什么这里可以使用这个dp的思想呢，其实也很好解释。我们可以取个巧，首先我们还是老样子我们需要得到子数组，但是这个子数组有个特点，那就是这些数组里面一定有以当前数字作为子数组右边界的数组，并且我门字需要求最大值，当前为右边界为最大的值的子数组之间进行比较，还是举个例子吧。

现在状态方程都给出来了，那不就简单了。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) return digits;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

这个没啥好说的，直接上。

二进制求和

题目就不给了，就是叫你写一个二级制加法器。

输入: a = “11”, b = “1” 输出: “100”

这里注意输入的是字符串。

第一个方法直接偷懒。

class Solution {
    public String addBinary(String a, String b) {
        return Integer.toBinaryString(
            Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
        );
    }
}

第二个方法其实和我们先前做的两数相加是一样的，只不过现在换成了字符串，然后没有逆序，没有对位补0.

class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }
}

二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

这种类型的太多了，其实和前面的那个求深度的类似，只是这次要考虑到特殊情况。

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if(root.left == null && root.right == null){
            //是否为叶子节点是就直接返回1
            return 1;}

        int left = this.minDepth(root.left);

        int right = this.minDepth(root.right);

        if(root.left==null || root.right==null){
            //这里主要是有特殊情况 就是 左边或者右边只有一边有节点的情况
            return left+right+1;
        }

        return Math.min(left, right) + 1;
    }
}

同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = “egg”, t = “add”

输出：true

字符长度一样。
这个没什么好说的，和先前的模式串是一样的。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> Saskey = new HashMap<Character, Character>();
        Map<Character, Character> Taskey = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((Saskey.containsKey(x) && Saskey.get(x) != y) || (Taskey.containsKey(y) && Taskey.get(y) != x)) {
                return false;
            }
            Saskey.put(x, y);
            Taskey.put(y, x);
        }
        return true;
    }
}

day08(补）

反转链表

这里注意这里的链表是带头节点的单链表。

把后面的改成前面的不就好了。

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

存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1] 输出：true 示例 2：

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

一看到这个，你肯定知道很多种解法，这里就提供最简便的解法。

直接使用集合，也就是hash。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }
}

什么叫我手写一个hash函数，可以给钱我就写，给你好好分析分析set,hashmap源码，手把手教你修改java hash函数（好吧，这些都是基础）。

存在重复元素二

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j]
且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3 输出：true 示例 2：

输入：nums = [1,0,1,1], k = 1 输出：true 示例 3：

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

这个的话一方面还是可以直接使用

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                if(Math.abs(i-map.get(nums[i]))<=k){
                    return true;
                }
            }
            map.put(nums[i],i);

        }
        return false;
    }
}

还有一个就是，这里的话指定了一个长度，所以我们这里可以考虑使用滑动窗口，这个只需要扫一次。当然map也是，因为查找的时间复杂度为O(1),按道理。

但是滑动的话是这样的，就相当于圈地嘛，在圈的地方里面有没有重复的，有就ok，没有就FALSE，直到滑动完了。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (i > k) {
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }
}

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty
这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 ,
只要是标准的队列操作即可。 示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2],[], [], []]

输出： [null, null, null, 2, 2, false]

解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2);
myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回
False

这个没啥好说的，偷个懒（来个简单题水一水）
下面是python3.9的语法

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue1 = collections.deque()
        self.queue2 = collections.deque()


    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
        self.queue1, self.queue2 = self.queue2, self.queue1


    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.queue1.popleft()


    def top(self) -> int:
        """
        Get the top element.
        """
        return self.queue1[0]


    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.queue1

好吧还是给到java吧

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

用栈实现队列

这个题目类似，就是反过来了（没错水上瘾了）

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

你们可不能说我水就说这个简单呀（虽然这个确实是Letcode给初学者准备的（包括我））

day03（补）

这个day03其实就是我去送表姐的时候欠下的，但是我补了3题，所以这里补两题。（今天2022/1/19是我刷的第十天讲道理是50道Letcode或者蓝桥杯）

汇总区间

给定一个无重复元素的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
“a->b” ，如果 a != b
“a” ，如果 a == b
示例 1：
输入：nums = [0,1,2,4,5,7]
输出：[“0->2”,“4->5”,“7”]
解释：区间范围是：
[0,2] --> “0->2”
[4,5] --> “4->5”
[7,7] --> “7”
示例 2：
输入：nums = [0,2,3,4,6,8,9]
输出：[“0”,“2->4”,“6”,“8->9”]
解释：区间范围是：
[0,0] --> “0”
[2,4] --> “2->4”
[6,6] --> “6”
[8,9] --> "8->9"

这个没啥好说的

class Solution39 {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<String>();
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int low = i;
            i++;
            while (i < n && nums[i] == nums[i - 1] + 1) {
                i++;
            }
            int high = i - 1;
            StringBuilder temp = new StringBuilder(Integer.toString(nums[low]));
            if (low < high) {
                temp.append("->");
                temp.append(Integer.toString(nums[high]));
            }
            res.add(temp.toString());
        }
        return res;
    }
}

2的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

这个直接有一个取巧的方法。就是直接通过位运算。

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
}

如果你是符合的，那么你就会满足这个关系。不然你就使用循环去做…

day04（补）

mad 哭了，怎么做了那么久！！！

两个数组的交集

就是求交集（再水一水）

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4]

如果这个是python的话，我当时就笑了

[val for val in a if val in b]

或者直接转成set

set(a)&set(b)

当然没办法谁叫我选的是java。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {


        HashSet<Integer> set = new HashSet<>();
        int len1 = nums1.length;
        int len2 = nums2.length;
        ArrayList<Integer> list = new ArrayList<>();

        // 先把数组1的值全部加进去
        for (int i = 0; i < len1; i++) {
            set.add(nums1[i]);
        }
        int count = 0;
        // 跟数组2 比较
        for (int i = 0; i < len2; i++) {
            if (set.contains(nums2[i])) {
                list.add(nums2[i]);
                set.remove(nums2[i]);
            }
        }
        int size = list.size();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = list.get(i);
        }
        return a;
    }
}

两个数组的交集二

这个其实也一样，但是要考虑相同次数了

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]

但是这里的话就稍微复杂一点了，我们需要存储相同元素的个数

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

猜数字大小

猜数字游戏的规则如下：
每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

这个一看就知道是二分查找嘛【狗头】真不想水，赶进度…

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (guess(mid) <= 0) {
                right = mid; 
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

赎金信

题目：

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false
示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false
示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true

我怎么感觉我做了好多直接用hash的题目。

这个没什么好说的。我也不想解释了，但是如果直接这样

    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character,Integer> map1 = new HashMap<>();
        HashMap<Character,Integer> map2 = new HashMap<>();

        for(char c:magazine.toCharArray()){
            if(map1.containsKey(c)){
                map1.put(c,map1.get(c)+1);
            }else
                map1.put(c,1);
        }
        for(char c:ransomNote.toCharArray()){
            if(map2.containsKey(c)){
                map2.put(c,map2.get(c)+1);
            }else
                map2.put(c,1);
        }
        for(char c:map2.keySet()){

            if(map1.containsKey(c)){
                if(map1.get(c)<map2.get(c)){
                    return false;
                }
            }else
                return false;

        }
        return true;
    }
}

内存消耗是很高的。所以我们可以取个巧，也是用哈希的思想

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
        	//每个字母只用一次，如果长度不够那就说明不行
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

思路都是一样的，但是这里直接使用了一个数组来存放26个字母

找不同

：
再来一个类似的吧，也是一样的。
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例 1：
输入：s = “abcd”, t = “abcde”
输出：“e”
解释：‘e’ 是那个被添加的字母。
示例 2：
输入：s = “”, t = “y”
输出："y"

直接给代码吧

class Solution {
    public char findTheDifference(String s, String t) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            cnt[ch - 'a']++;
        }
        for (int i = 0; i < t.length(); ++i) {
            char ch = t.charAt(i);
            cnt[ch - 'a']--;
            if (cnt[ch - 'a'] < 0) {
                return ch;
            }
        }
        return ' ';
    }
}

喵的总算不补完了，突然发现Letcode里面有好多简单题目都是用哈希来做的，尤其是字符串。还有双指针用的也不少。

最后

以上就是外向牛排为你收集整理的每日一练（day09补08，03，04）前言题目day09day08(补）day03（补）day04（补）的全部内容，希望文章能够帮你解决每日一练（day09补08，03，04）前言题目day09day08(补）day03（补）day04（补）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。