SouthLeetCode-打卡24年01月第2周

SouthLeetCode-打卡24年01月第2周

// Date : 2024/01/08 ~ 2024/01/14

001.数组中第三大的数

(1) 题目描述

给定一个nums[]数组，求出数组中第三大的数，注意数组中可能包含重复的元素，保证一定有第三大的数

(2) 题解代码

public class Question1 {static int thirdMax(int[] nums){int length = nums.length;if(length < 3) return -999;Arrays.sort(nums);int flag = 0;int index = 0;for(int i = nums.length-1 ; i > 0 ; i-- ){if (nums[i] != nums[i-1]){flag++;}if (flag < 3){index++;}}return nums[length-index-1];}public static void main(String[] args) {int nums1[] = new int[]{1,2,4,3,6,6};int res = thirdMax(nums1);System.out.println(res);int nums2[] = new int[]{3,2,1};int res2 = thirdMax(nums2);System.out.println(res2);}}

002.阶乘的取余

(1) 题目描述

给定一个整数n，求 (1!+2!+...+n!) % 10000

(2) 题解代码

public class Question2 {static int factorial ( int n ) {int r = 1;for ( int i = 1; i <= n; i++ ) {r*=i;}return r;}static int sumOfFactorials(int n){int sum = 0;int factorial = 1;for(int i=1 ; i<=n ; i++){factorial *= i;sum = (sum%10000 + factorial%10000) % 10000;}return sum;}public static void main(String[] args) {System.out.println(sumOfFactorials(1));System.out.println(sumOfFactorials(2));System.out.println(sumOfFactorials(3));System.out.println(sumOfFactorials(10));}
}

003.有效的括号

(1) 题目描述

给定一个字符串，字符串中只包含{}[]这四种字符，写一个程序判断字符串中是否包含有效的括号

(2) 题解代码

public class Question3 {static boolean isValidBrackets ( String s ){if(s.length()%2 == 0){Stack<Character> stack = new Stack<>();HashMap<Character,Character> hashmap = new HashMap<>();hashmap.put('[',']');hashmap.put('{','}');List<Character> list = new ArrayList<>();list.add('[');list.add('{');for(int i=0 ; i<s.length() ; i++){if (list.contains(s.charAt(i))){stack.push(hashmap.get(s.charAt(i)));} else if (stack.empty() || s.charAt(i) != stack.peek()) {return false;} else {stack.pop();}}return stack.empty();}else{return false;}}public static void main(String[] args) {System.out.println(isValidBrackets("{}")); // trueSystem.out.println(isValidBrackets("{[]}")); // trueSystem.out.println(isValidBrackets("{[}]")); // false}
}

004.二分查找

(1) 题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

(2) 题解代码

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;int mid =  (left + right)  / 2;while(left <= right){mid =  (left + right)  / 2;int number = nums[mid];if(number > target){right = mid-1;}else if(number < target){left = mid+1;}else{return mid;}}return -1;}
}

005.反转字符串

(1) 题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

(2) 题解代码

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;int mid =  (left + right)  / 2;while(left <= right){mid =  (left + right)  / 2;int number = nums[mid];if(number > target){right = mid-1;}else if(number < target){left = mid+1;}else{return mid;}}return -1;}
}

006.数字替换

(1) 题目描述

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

(2) 题解代码

007.有序数组的平方和

(1) 题目描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

(2) 题解代码

Version1.0

class Solution {public int[] sortedSquares(int[] nums){for(int i=0 ; i<nums.length; i++){nums[i] = nums[i]*nums[i];}Arrays.sort(nums);return nums;}
}

Version2.0

class Solution {public int[] sortedSquares(int[] nums){int length = nums.length;int left = 0;int right = length-1;int[] res = new int[length];int index = length-1;while(left <= right){if(nums[left] + nums[right] > 0){res[index] = nums[right]*nums[right];right--;}else{res[index] = nums[left]*nums[left];left++;}index--;}return res;}
}

Version3.0

class Solution {public int[] sortedSquares(int[] nums) {int length = nums.length;int left = 0;int right = length - 1;int[] res = new int[length];int index = length-1;while(left <= right){res[index] = nums[left]*nums[left] > nums[right]*nums[right] ? nums[left]*nums[left++] : nums[right]*nums[right--];index--;}return res;}
}

008.长度最小的子数组

(1) 题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**

如果不存在符合条件的子数组，返回 0 。

(2) 题解代码

暴力解法（用例通过16/21）

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int res = 0;for(int len = 1; len < nums.length ; len++){for(int i=0 ; i+len <= nums.length ; i++){for(int k=0; k < len ; k++){sum += nums[i+k];}if(sum >= target){if(res == 0){res = len;}else{res = Math.min(res,len);}}sum = 0;}}return res;}
}

暴力解法（用例通过18/21：超时）

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int res = 0;//把循环条件加上等号即可for(int len = 1; len <= nums.length ; len++){for(int i=0 ; i+len <= nums.length ; i++){for(int k=0; k < len ; k++){sum += nums[i+k];}if(sum >= target){if(res == 0){res = len;}else{res = Math.min(res,len);}}sum = 0;}}return res;}
}

Version3.0 滑动窗口

class Solution {public int minSubArrayLen(int target, int[] nums) {int length = nums.length;int sum = 0, res = 0;int left = 0, right = 0;int maxSum = 0;for( ; right < length ; right++){allSum += nums[right];sum += nums[right];while(sum >= target){res = res != 0 ? Math.min(res,right-left+1) : right-left+1;sum -= nums[left++];}}if(allSum < target){ res = 0; }return res;}
}

009.第三大的数

(1) 题目描述

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

(2) 题解代码

class Solution {public int thirdMax(int[] nums) {int length = nums.length;int flag = 1;Arrays.sort(nums);for(int i=length-2 ; i>=0 ; i--){if(nums[i] != nums[i+1]){flag++;}if(flag == 3){return nums[i];}}return nums[length-1];}
}

010.下一个排列

(1) 题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

(2) 题解代码

// 未做完…

011.环形链表Ⅱ

(1) 题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

(2) 题解代码

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;boolean flag = false;while(fast != null){slow = slow.next;fast = fast.next;if(fast != null){fast = fast.next;}else{return null;}if(fast == slow){flag = true;break;}}if (flag) {fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return slow;} else {return null;}}
}

012.相交链表

(1) 题目描述

(2) 题解代码

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode secA = headA;ListNode curB = headB;ListNode secB = headB;while(curA != null && curB != null){curA = curA.next;curB = curB.next;}if(curA == null){while(curB != null){curB = curB.next;secB = secB.next;}curA = headA;while(curA != secB){curA = curA.next;secB = secB.next;}return curA;}if(curB == null){while(curA != null){curA = curA.next;secA = secA.next;}curB = headB;while(curB != secA){curB = curB.next;secA = secA.next;}return curB;}return null;}
}