lc新手半个月的42道题 （带注解
原创
前言
在刷了这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 < 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<Character> stack = new Stack<>();
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);这些只是一些常见的反转字符串的方式，实际上还有其他一些方式，例如使用递归和位操作等。选择哪种方式取决于具体的需求和场景。
我正在参与2023腾讯技术创作特训营第二期有奖征文，瓜分万元奖池和键盘手表
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录