文章/答案/技术大牛

发布

社区首页 >专栏 >lc新手半个月的42道题（带注解

lc新手半个月的42道题（带注解

原创

汪汪想变强

发布于 2023-10-05 09:24:45

3499

文章被收录于专栏：汪汪想变强汪汪想变强

前言

在刷了这42题后，感觉简单题都很ok了，现在开始死磕中等题。。

学习目的

按章节来刷先理解了会写就好，不用管什么复杂度最优解

数组/字符串

删除有序数组中的重复项

快慢指针

public static int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {//* 注意这种长度的都是while
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }

合并区间 -中

排序

public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {//非空判断
            return new int[0][2];
        }
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);//升序排序

        List<int[]> merged = new ArrayList<int[]>(); //二维数组
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];//定义左右边界
            //前元素右边界 与 后元素左边界 比较
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {//第一轮循环 || 边界不重叠
                merged.add(new int[]{L, R});//* 书写方式
            } else {//边界重叠
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);//* 书写方式
    }

大数相减

package bs;

/**
 * [4399-大数相减]
 * 大数相减
 * 以字符串的形式读入两个数字a,b(a>=b),编写一个函数计算它们的差(a-b),以字符串形式返回。
 * 数据范围：每个数字的长度均为1<=len<=10000
 * 要求：时间复杂度O(n)
 * 示例输入：
 * 1001
 * 输出：
 * 99
 */
import java.util.Arrays;

public class SubtractLargeNumbers {

    public static String subtract(String a, String b) {
        // 将两个字符串用字符数组表示，反转方便从低位到高位相减
        //1.使用StringBuilder反转、转字符数组
        char[] num1 = new StringBuilder(a).reverse().toString().toCharArray();
        char[] num2 = new StringBuilder(b).reverse().toString().toCharArray();

        //2.初始化各长度和最大长度
        int len1 = num1.length;
        int len2 = num2.length;
        int maxLen = Math.max(len1, len2);

        //3.初始化result数组和borrow
        char[] result = new char[maxLen];
        int borrow = 0; // 初始化借位为0

        //4.对每位上数做减法
        for (int i = 0; i < maxLen; i++) {
            //取每位上数，并转为int
            int digit1 = (i < len1) ? (num1[i] - '0') : 0;
            int digit2 = (i < len2) ? (num2[i] - '0') : 0;

            //减法
            int diff = digit1 - digit2 - borrow;
            //判断是否借位
            if (diff < 0) {
                diff += 10; // 借位
                borrow = 1;
            } else {//不可能存在>10情况
                borrow = 0;
            }

            //再由int转char
            result[i] = (char) (diff + '0');
        }

        //5.去掉结果中前导零
        int leadingZeros = 0;
        for (int i = maxLen - 1; i >= 0; i--) {
            if (result[i] == '0') {
                leadingZeros++;
            } else {
                break;
            }
        }
        // 如果结果全是零，则返回 "0"
        if (leadingZeros == maxLen) {
            return "0";
        }
        // 构建最终结果字符串，删去高位上的0
        char[] finalResult = Arrays.copyOf(result, maxLen - leadingZeros);
        // 最后再反转回去，构造成string
        return new StringBuilder(String.valueOf(finalResult)).reverse().toString();
    }

    public static void main(String[] args) {
        String a = "1001";
        String b = "99";
        String result = subtract(a, b);
        System.out.println(result);
    }
}

无重复字符的最长子串 -中

package common.string;

import java.util.HashSet;
import java.util.Set;

/**
 * 滑动窗口 -debug就懂了
 */
public class T1 {
    public static void main(String[] args) {
        int length = lengthOfLongestSubstring("abcabcbb");
        System.out.println(length);
    }
    public static int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1;
        //最长长度计步器
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针i向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;//* 别忘了移动rk
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

两数之和

public static int[] twoSum(int[] nums, int target) {
        //1.创建哈希表
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>(); //* ()注意别忘了
        //2.开始遍历
        for (int i = 0; i < nums.length; i++) {
            //* 注意：要先判断再存储
            //开始判断
            if (hashMap.containsKey(target - nums[i])){
                return new int[]{hashMap.get(target - nums[i]), i};//* new别忘了
            }

            //先数组转哈希表
            hashMap.put(nums[i], i);
        }
        return new int[0];
    }

三数之和

寻找文件副本

set集合

class Solution {
    public int findRepeatDocument(int[] documents) {
        Set<Integer> hmap = new HashSet<>();
        for(int doc : documents) {
            if(hmap.contains(doc)) return doc;
            hmap.add(doc);
        }
        return -1;
    }
}

杨辉三角

public static List<List<Integer>> generate(int numRows) {
        //1.建立杨辉三角数组
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        //2.去生成每层中的元素
        for (int i = 0; i < numRows; ++i) {//i：行    j：列
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));//* add对象是ret
                }
            }
            ret.add(row);
        }
        return ret;
    }

合并两个有序数组

for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);

移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

字符串相加

public static String addStrings(String num1, String num2) {
        //1.初始化num1、num2的最大下标，还有借位add，和构造器ans
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        //2.开始相加
        while (i >= 0 || j >= 0 || add != 0) {
            //分别取数 *对于无数的位上置零
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            //相加
            int result = x + y + add;
            //就算ans和add
            ans.append(result % 10);
            add = result / 10;
            //i、j分别--
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        
        return ans.toString();
    }

两个数组的交集

    public static int[] intersection(int[] nums1, int[] nums2) {
        //1.声明set1、set2、list
        Set<Integer> set1 = new HashSet<>(),set2 = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        //2.添加元素到set中
        for(int i:nums1){
            set1.add(i);
        }
        for(int i:nums2){
            set2.add(i);
        }
        //2.做保留操作
//        set1.retainAll(set2);
        Set<Integer> intersectionSet = new HashSet<Integer>();
        for (int num : set1) {
            if (set2.contains(num)) {
                intersectionSet.add(num);
            }
        }
        //3.转化为int数组返回
        return intersectionSet.stream().mapToInt(i->i).toArray();
    }

数学/位运算

x 的平方根

方法一：袖珍计算器算法

由于计算机无法存储浮点数的精确值（浮点数的存储方法可以参考 IEEE 754，这里不再赘述），因此在得到结果的整数部分 ans\textit{ans}ans 后，我们应当找出 ans\textit{ans}ans 与 ans+1\textit{ans} + 1ans+1 中哪一个是真正的答案。

    public static int mySqrt(int x) {
        //减少算力
        if (x == 0) {
            return 0;
        }
        //换底公式
        //* 注意要转为int类型
        int ans = (int) Math.exp(0.5 * Math.log(x));
        //判断返回ans还是ans+1
        //* 注意返回的是long类型
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }

递归/回溯

当递归函数执行到达递归基（即传递给函数的字符串满足某个终止条件）时，就会开始返回。递归过程可以看成是入栈的过程，返回的过程就是出栈的过程。

动态规划

动态规划是一种更加系统和高效的问题解决方法，特别适用于那些可以分解为子问题并且有最优子结构性质的问题

买卖股票的最佳时机

一次遍历

public static int maxProfit(int prices[]) {
        //1.初始化
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        //2.开始计算
        for (int i = 0; i < prices.length; i++) {
            //小：获取minprice
            if (prices[i] < minprice) {
                minprice = prices[i];

            //大：获取maxprofit
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }

买卖股票的最佳时机 II

使用最小花费爬楼梯

原始版本

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

使用滚动数组思想，将空间复杂度优化到 O(1)O(1)O(1)

//1.初始化n、prev、curr
        int n = cost.length;
        int prev = 0,curr = 0;
        //2.n>2的情况
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i-1],prev + cost[i-2]);
            prev = curr;
            curr = next;
        }
        //3.遍历完返回curr值
        return curr;

最大子数组和

f(i)=max{f(i−1)+numsi,numsi}

public static int maxSubArray(int[] nums) {
        int max = nums[0]; //* 设置第一个元素为最大值,减少一次遍历
        int pre = 0;
        for (int x : nums) {
            pre = Math.max(pre + x,x);
            max = Math.max(max,pre);
        }
        return max;
    }

爬楼梯

f(x)=f(x−1)+f(x−2) + 滚动数组的方法

public static int climbStairs(int n) {
        int pre=0,cur=0,next=1;
        while (n-- != 0){
            pre = cur;
            cur = next;
            next = pre + cur;
        }
        return next;
    }

链表

合并两个有序链表

迭代法

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) { //* 用while
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // *合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

回文链表

双指针法

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {//* 用while
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}

反转链表

思路

 /**
     * 整体思路：每次迭代将当前节点的next指针指向前一个节点，然后更新指针的位置，最终实现链表的反转
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        //先一个指向头一个指向尾
        ListNode prev = null; //反转要指向的节点
        ListNode curr = head; //当前遍历节点
        while (curr != null) {
            //这里和数组交换完全没有关系
            ListNode next = curr.next; //先保存好curr的next
            curr.next = prev; //核心：实现当前节点的反转
            prev = curr; //将反转后部分 连接上完整的反转链表
            curr = next; //进行遍历下一个节点
        }
        return prev;
    }

环形链表

哈希表

 public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();//* 存的类型是ListNode
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;//* 要后移啊
        }
        return false;
    }

链表中倒数第k个节点

自己写出来

public static ListNode getKthFromEnd(ListNode head, int k) {
        //倒数改成正数 - 正数n=len-倒数k
        //1.计算len
        int len = 1;
        ListNode pre = head;//记录头结点
        while (pre!=null){
            len++;
            pre = pre.next;
        }
        int n = len - k;

        pre = head;//再次指向头结点
        while (n-- != 1){
            pre = pre.next;
        }
        return pre;
    }

相交链表

自己写出来

//有相同节点且第一个相同节点就是答案
        HashSet<ListNode> hashSet = new HashSet<>();

        //把两个链表分别加入hashset中，第一个加入不成功的节点就是答案
        //1.先加入headA
        while (headA!=null){
            hashSet.add(headA);
            headA = headA.next;
        }

        while (headB!=null){
            if (!hashSet.add(headB)){
//                return headB;
                break;
            }
            headB = headB.next;
        }
        return headB;

环形链表 II -中

public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }

复制带随机指针的链表 -中

哈希表

if(head == null){
            return null;
        }
        Node cur = head;
        HashMap<Node,Node> map = new HashMap<>();
        while(cur!=null){//新链表节点的构建
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur=head;
        while(cur!=null){//新链表指向的构建
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);//* 注意返回值

合并 K 个升序链表 -难

顺序合并

public static ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public static ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode prehead = new ListNode(-1); //初始化头指针
        ListNode prev = prehead;//用于遍历的指针
        while (a!=null && b!=null){
            if (a.val >= b.val){
                prev.next = b;
                b = b.next;
            } else {
                prev.next = a;
                a = a.next;
            }
            prev = prev.next;
        }
        // *合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = a == null ? b : a;

        return prehead.next;

    }

K 个一组翻转链表 -难

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
        dummy.next = head; //* 忘记

        ListNode pre = dummy;
        ListNode end = dummy;
        
        while (end.next != null){
            //1.设置
            for (int i=0;i<k && end!=null;i++) end = end.next;
            if (end == null) break; //* 老是忘记写
            ListNode start = pre.next;//开始翻转部分
            ListNode next = end.next;//未翻转部分

            //2.开始翻转
            end.next = null; pre.next = reverse(start);

            //3.跳跃到下一个分组
            start.next = next; //* 跳跃对象是next

            //4.重置
            pre = start;
            end = pre;
        }
        return dummy.next;
}

private ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

LRU 缓存 -中

栈

有效的括号

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n % 2 == 1){
            return  false;
        }
        Map<Character, Character> map = new HashMap<Character, Character>() {{
            // 将 })] 作为key
            put('}', '{');
            put(']', '[');
            put(')', '(');
        }};
        // 新建一个栈
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 如果c是 })], 则判断， 否则说明是({[ , 直接入栈
            if(map.containsKey(c)){
                // stack.peek() 获取栈顶元素
                if(stack.isEmpty() || stack.peek() != map.get(c)){
                    return false;
                }
                else{// 将栈顶移除(先进后出，栈顶是最接近 c 的左括号)
                stack.pop();
                }
            }else{
                // 说明c是({[ , 直接入栈
            stack.push(c);
        }
        }
        return stack.isEmpty();
    }
}

综合题

反转字符串

反转字符串有多种方式可以实现，以下是几种常见的方式：

1.使用StringBuilder或StringBuffer的reverse方法：

  String str = "Hello, World!";
   StringBuilder sb = new StringBuilder(str);
   String reversedString = sb.reverse().toString();
   System.out.println(reversedString);

2.使用字符数组：

  String str = "Hello, World!";
   char[] charArray = str.toCharArray();
   int left = 0;
   int right = charArray.length - 1;
   while (left &lt; right) {
       char temp = charArray[left];
       charArray[left] = charArray[right];
       charArray[right] = temp;
       left++;
       right--;
   }
   String reversedString = new String(charArray);
   System.out.println(reversedString);

3.使用递归：

 public String reverseString(String str) {
       if (str.isEmpty()) {
           return str;
       }
       return reverseString(str.substring(1)) + str.charAt(0);
   }

   String str = "Hello, World!";
   String reversedString = reverseString(str);
   System.out.println(reversedString);

4.使用栈：

  import java.util.Stack;

   String str = "Hello, World!";
   Stack&lt;Character&gt; stack = new Stack&lt;&gt;();
   for (char c : str.toCharArray()) {
       stack.push(c);
   }
   StringBuilder sb = new StringBuilder();
   while (!stack.isEmpty()) {
       sb.append(stack.pop());
   }
   String reversedString = sb.toString();
   System.out.println(reversedString);