高阶面试-hw算法整理

public int dayOfYear(String date) {// format YYYY-MM-DDint year = Integer.parseInt(date.substring(0, 4));int month = Integer.parseInt(date.substring(5, 7));int day = Integer.parseInt(date.substring(8));int[] daysOfMonthList = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 闰月if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {daysOfMonthList[1]++;}int daysBeforeThisMonth = 0;if (month > 1){for (int i = 0; i < month - 1; i++) {daysBeforeThisMonth += daysOfMonthList[i];}}return day+daysBeforeThisMonth;
}

class Solution {public boolean isPalindrome(String s) {int n = s.length();int left = 0;int right = n-1;while(left < right){while(left < right && !Character.isLetterOrDigit(s.charAt(left))){left++;}while(left < right && !Character.isLetterOrDigit(s.charAt(right))){right--;}if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){return false;}left++;right--;}return true;}
}

class Solution {public void reverseString(char[] s) {// 双指针int left = 0;int right = s.length-1;while(left < right){char temp = s[left];s[left] = s[right];s[right] = temp;left++;right--;}}
}

class Solution {public boolean isValid(String s) {// map {} 栈// checkif(s.isEmpty()){return true;}Map<Character,Character> map = new HashMap();map.put(']','[');map.put('}','{');map.put(')','(');Stack<Character> stack = new Stack();for(Character c: s.toCharArray()){if(map.containsKey(c)){// 说明有括号Character topElement = stack.isEmpty()?'#':stack.pop();if(map.get(c) != topElement){return false;}}else{stack.push(c);}}return stack.isEmpty();}
}

class Solution {public boolean isSubsequence(String s, String t) {// 贪心 双指针int n = s.length();int m = t.length();int i =0, j=0;while(i<n && j<m){if(s.charAt(i) == t.charAt(j)){i++;}j++;}return i == n;}
}

class Solution {public int longestPalindrome(String s) {// hash 偶数++ 奇数放中间只能1个Map<Character,Integer> counter = new HashMap();for( int i = 0; i< s.length(); i++){counter.merge(s.charAt(i),1,(a,b)->(a+b));}// 统计构造回文串的最大长度int res = 0, odd = 0 ;for(Map.Entry<Character,Integer> kv: counter.entrySet()){// 当前字符出现次数向下取偶数，并计入resint count = kv.getValue();int rem = count % 2;res += count - rem;// 如果当前字符出现次数是奇数，将odd置位1if(rem == 1){odd = 1;}}return res+odd;}
}

class Solution {public boolean buddyStrings(String s, String goal) {//check lenif (s.length() != goal.length()){return false;}// equalif (s.equals(goal)){int[] count = new int[26];for (int i = 0; i < s.length(); i++) {int assicCount = s.charAt(i)-'a';count[assicCount]++;//对应字母的频率if (count[assicCount] > 1){// 有重复，只要换重复的就一定相等return true;}}return false;}else {// first secondint first = -1;int second = -1;for (int i = 0; i < s.length(); i++) {// 只能有两个相同位置的字符不一样if (s.charAt(i) != goal.charAt(i)){if (first==-1){first = i;}else if (second==-1){second = i;}else {// 超过两个return false;}}}return (second != -1 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first));}}
}

class Solution {public String longestCommonPrefix(String[] strs) {// checkif(strs.length ==0){return "";}// 先排序 再比较头尾Arrays.sort(strs);int n = strs.length;String ans = "";for(int i = 0; i< strs[0].length();i++){if(strs[0].charAt(i) == strs[n-1].charAt(i)){ans += strs[0].charAt(i);}else{break;}}return ans;}
}

class Solution {public String reformatNumber(String number) {StringBuilder digits = new StringBuilder();for(int i = 0; i < number.length(); i++){char c = number.charAt(i);if(Character.isDigit(c)){digits.append(c);}}int n = digits.length();int currPt = 0;StringBuilder ans = new StringBuilder();while(n > 0){if(n > 4){ans.append(digits.substring(currPt,currPt+3)+"-");n -=3;currPt += 3;}else{if(n==4){ans.append(digits.substring(currPt,currPt+2)+"-"+digits.substring(currPt+2,currPt+4));}else {ans.append(digits.substring(currPt,currPt+n));}break;}}return ans.toString();}
}

class Solution {public boolean checkRecord(String s) {return s.indexOf('A') == s.lastIndexOf('A') && !s.contains("LLL");}
}

class Solution {public int[] twoSum(int[] nums, int target) {// cacheMap<Integer,Integer> cache = new HashMap();for(int i=0;i<nums.length;i++){if(cache.containsKey(target-nums[i])){return new int[]{cache.get(target-nums[i]),i};}cache.put(nums[i],i);}return new int[]{};}
}

class Solution {public int majorityElement(int[] nums) {// checkif(nums.length <=2){return nums[nums.length-1];}// 排序后中间元素Arrays.sort(nums);return nums[nums.length/2];}
}

class Solution {public int maxSubArray(int[] nums) {//checkif(nums == null || nums.length==0){return 0;}int maxCurrent = nums[0]; // 当前元素的子数组和int maxGlobal = nums[0]; // 全局最大子数组和for(int i=1;i<nums.length;i++){// 人生的每个阶段，如果前一个阶段是负积累，及时抛弃，开启新篇章，否则持续积累// 选择当前元素作为新子数组的开始，或者将其添加到前一个元素的子数组中maxCurrent = Math.max(nums[i],maxCurrent+nums[i]);// 每个阶段都要做下总结，是否全局最优// 更新全局最大子数组和maxGlobal = Math.max(maxGlobal,maxCurrent);}return maxGlobal;}
}

class Solution {public boolean canMakeArithmeticProgression(int[] arr) {if(arr.length ==2){return true;}Arrays.sort(arr);int res = arr[1]-arr[0];for(int i=2;i<arr.length;i++){if((arr[i]-arr[i-1]) != res){return false;}}return true;}
}

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {// 双指针int[] newNums = new int[m+n];int i = 0;int j = 0;int p = 0;while(i<m && j<n){if(nums1[i]<nums2[j]){newNums[p] = nums1[i];p++;i++;}else{newNums[p] = nums2[j];p++;j++;}}if(i<m){// 复制从i到m的元素过去System.arraycopy(nums1,i,newNums,p,m-i);}if(j<n){System.arraycopy(nums2,j,newNums,p,n-j);}// 拷贝到nums1System.arraycopy(newNums,0,nums1,0,m+n);}
}

class Solution {public int findLHS(int[] nums) {Map<Integer,Integer> map = new HashMap();for(int i = 0;i < nums.length;i++){map.put(nums[i],map.getOrDefault(nums[i],0)+1);}int ans = 0;for(int i: map.keySet()){if(map.containsKey(i-1)){ans = Math.max(ans,map.get(i)+map.get(i-1));}}return ans;}
}

class Solution {public double findMaxAverage(int[] nums, int k) {int sum = 0;int n = nums.length;for(int i=0;i<k;i++){sum += nums[i];}int maxSum = sum;for(int i=k;i<n;i++){sum = sum - nums[i-k] + nums[i];maxSum = Math.max(maxSum, sum);}return maxSum * 1.0/k;}
}

class Solution {public int islandPerimeter(int[][] grid) {int perimeter = 0;int rows = grid.length;int cols = grid[0].length;for(int i=0;i<rows;i++){for(int j = 0; j< cols;j++){// 四个位置，水 或者 越界 再++if(grid[i][j] == 1){// 上方if(i==0 || grid[i-1][j] == 0){perimeter++;}// 下方if(i==rows-1 || grid[i+1][j]==0){perimeter++;}// 左侧if(j==0|| grid[i][j-1]==0){perimeter++;}// 右侧if(j==cols-1 || grid[i][j+1]==0){perimeter++;}}}}return perimeter;}
}

class Solution {public boolean isPalindrome(ListNode head) {if(head.next == null){return true;}// stackDeque<ListNode> stack = new ArrayDeque();ListNode newHead = head;while(head!=null){stack.push(head);head = head.next;}while(newHead != null){if(newHead.val != stack.pop().val){return false;}newHead = newHead.next;}return true;}
}

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dummy = new ListNode(-1);ListNode head = dummy;while(list1!=null && list2!=null){if(list1.val>list2.val){head.next = list2;head = head.next;list2 = list2.next;}else{head.next = list1;head = head.next;list1 = list1.next;}}while(list1!=null){head.next = list1;head = head.next;list1 = list1.next;}while(list2!=null){head.next = list2;head = head.next;list2 = list2.next;}return dummy.next;}
}

public class Solution {public boolean hasCycle(ListNode head) {// checkif(head == null){return false;}// 双指针ListNode fast = head;ListNode slow = head;while(fast.next != null && fast.next.next!= null){fast = fast.next.next;slow = slow.next;if(fast == slow ){return true;}}return false;}
}

class Solution {public ListNode deleteDuplicates(ListNode head) {if(head == null){return head;}ListNode cur = head;while(cur.next != null){if(cur.val == cur.next.val){cur.next = cur.next.next;}else{cur = cur.next;}}return head;}
}

class Solution {public String validIPAddress(String queryIP) {if (queryIP.indexOf(".") >= 0) {return isIPv4(queryIP) ? "IPv4" : "Neither";} else {return isIPv6(queryIP) ? "IPv6" : "Neither";}}private boolean isIPv4(String queryIP) {// 加-1防止出现空字符串无法计数 如192.168.1.1，后面多了个点，不加-1会被忽略后面的空串String[] split = queryIP.split("\\.",-1);//个数不是4个if (split.length != 4) {return false;}for (String s : split) {// 每个长度不在1-3之间if (s.length() > 3 || s.length() == 0) {return false;}// 有前导0 并且长度不为1if (s.charAt(0) == '0' && s.length() != 1) {return false;}// 计算数字int ans = 0;for (int j = 0; j < s.length(); j++) {char c = s.charAt(j);if (!Character.isDigit(c)) {return false;}ans = ans * 10 +(c - '0');}//数字超过255if (ans > 255) {return false;}}return true;}public boolean isIPv6(String queryIP) {String[] split = queryIP.split(":", -1);//数量不是8if (split.length != 8) {return false;}for (String s : split) {// 每个串 长度不是1-4之间if (s.length() > 4 || s.length() == 0) {return false;}for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);//不是数字且字母不在a-f之间if (!Character.isDigit(c) && !('a' <= Character.toLowerCase(c) && Character.toLowerCase(c) <= 'f')) {return false;}}}return true;}
}

正则太难了…

class Solution {public List<String> topKFrequent(String[] words, int k) {Map<String, Integer> frequencyMap = new HashMap<>();for (String word : words) {frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);}// 小顶堆PriorityQueue<WordFrequency> minHeap = new PriorityQueue<>();for (Map.Entry<String, Integer> entry : frequencyMap.entrySet()) {minHeap.offer(new WordFrequency(entry.getKey(), entry.getValue()));if (minHeap.size() > k) {minHeap.poll();}}List<String> result = new ArrayList<>();while (!minHeap.isEmpty()) {result.add(minHeap.poll().word);}Collections.reverse(result);return result;}public static class WordFrequency implements Comparable<WordFrequency> {String word;int frequency;public WordFrequency(String word, int frequency) {this.word = word;this.frequency = frequency;}@Overridepublic int compareTo(WordFrequency wordFrequency) {if (this.frequency != wordFrequency.frequency) {return Integer.compare(this.frequency, wordFrequency.frequency);} else {return wordFrequency.word.compareTo(this.word);}}}
}

class Solution {public boolean canChoose(int[][] groups, int[] nums) {//滑动窗口int n = nums.length;int gIndex = 0;int windowStart = 0;while(gIndex < groups.length && windowStart < n){boolean found = false;// 在nums中查找与当前groups[gIndex] 匹配的子序列for(int i=windowStart; i<= n-groups[gIndex].length;i++){boolean match = true;for(int j = 0; j< groups[gIndex].length;j++){if(nums[i+j] != groups[gIndex][j]){match = false;break;}}if(match){found = true;windowStart = i+groups[gIndex].length;break;}}if(!found){return false;}gIndex++;}return gIndex == groups.length;}
}

class Solution {public int[][] merge(int[][] intervals) {//checkif(intervals.length <= 1){return intervals;}// 排序Arrays.sort(intervals, (a,b)->a[0] - b[0]);List<int[]> mergedIntervals = new ArrayList();int[] currentInterval = intervals[0];mergedIntervals.add(currentInterval);for(int i=1;i<intervals.length;i++){int[] nextInterval = intervals[i];// current end > next start, 重叠if(currentInterval[1] >= nextInterval[0]){currentInterval[1] = Math.max(currentInterval[1],nextInterval[1]);}else{currentInterval = nextInterval;mergedIntervals.add(currentInterval);}}return mergedIntervals.toArray(new int[mergedIntervals.size()][]);}
}

class Solution {public List<Integer> majorityElement(int[] nums) {int threshold = nums.length / 3;Map<Integer,Integer> counts = new HashMap();for(int num: nums){counts.put(num, counts.getOrDefault(num,0)+1);}List<Integer> result = new ArrayList();for(Map.Entry<Integer,Integer> entry: counts.entrySet()){if(entry.getValue() > threshold){result.add(entry.getKey());}}return result;}
}

class Solution {public int[] topKFrequent(int[] nums, int k) {// checkif(nums.length==0 || k == 0){return new int[]{};}// hashMap<Integer,Integer> hash = new HashMap();for(int i=0;i<nums.length;i++){hash.put(nums[i],hash.getOrDefault(nums[i],0)+1);}// PriorityQueuePriorityQueue<Integer> queue = new PriorityQueue<Integer>(k,(v1,v2)->{return hash.get(v1)-hash.get(v2);});// offerfor(int key:hash.keySet()){if(queue.size() < k){queue.offer(key);}else{if(hash.get(key) > hash.get(queue.peek())){queue.poll();queue.offer(key);}}}// resint[] res = new int[k];int i = 0;for(int e: queue){res[i] = e;i++;}return res;}
}

class Solution {public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList();backtrace(s,0,new ArrayList(),result);return result;}private void backtrace(String s,int start,List<String> currentPath,List<String> result){//如果已经分割了4部分，并且到达了字符串的末尾if(start == s.length() && currentPath.size() == 4){result.add(String.join(".", currentPath));return;}if(currentPath.size() > 4){return;}//从当前起始位置开始，尝试分割长度为1到3的片段for(int end = start;end < Math.min(start+3,s.length()); end++){String segment = s.substring(start, end+1);if((segment.length() > 1 && segment.startsWith("0")) || Integer.parseInt(segment) > 255){continue;}currentPath.add(segment);backtrace(s,end+1,currentPath,result);// 回溯：移除刚加入的片段，尝试其他分割方式currentPath.remove(currentPath.size() -1);}}
}

class Solution {public int characterReplacement(String s, int k) {int left = 0, right = 0;int maxLength = 0;Map<Character,Integer> charFrequency = new HashMap();while(right < s.length()){charFrequency.put(s.charAt(right), charFrequency.getOrDefault(s.charAt(right),0)+1);// 当前窗口需要替换的最大次数int maxFreqCharCount = getMaxFrequency(charFrequency);// 当前窗口大小 - 窗口内出现次数最多的字符数量＜k，说明还有替换机会while(right-left+1 -maxFreqCharCount > k){//缩小窗口charFrequency.put(s.charAt(left), charFrequency.get(s.charAt(left))-1);left++;}//更新最长子串长度maxLength = Math.max(maxLength,right-left+1);right++;}return maxLength;}private int getMaxFrequency(Map<Character,Integer> frequencyMap){int maxFreq = 0;for(int freq: frequencyMap.values()){maxFreq = Math.max(maxFreq,freq);}return maxFreq;}
}

class Solution {public List<List<Integer>> threeSum(int[] nums) {// checkif(nums == null || nums.length < 3){return null;}List<List<Integer>> result = new ArrayList<>();// 排序Arrays.sort(nums);// 双指针夹逼for(int i = 0; i< nums.length-2;i++){int j = i+1;int k = nums.length-1;if(nums[i]>0){break;}if(i>0 && nums[i]==nums[i-1]){continue;}while(j < k){int a = nums[i];int b = nums[j];int c = nums[k];if(a+b+c < 0){j++;}else if(a+b+c > 0){k--;}else{List<Integer> list = new ArrayList<>();list.add(a);list.add(b);list.add(c);result.add(list);while(j<k && nums[j+1] == nums[j]){j++;}while(j<k && nums[k-1] == nums[k]){k--;}j++;k--;}}}return result;}
}

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList();if(candidates == null || candidates.length == 0){return result;}List<Integer> currentCombination = new ArrayList();backtrace(candidates,target,0,currentCombination, result);return result;}private void backtrace(int[] candidates,int target,int start,List<Integer> currentCombination, List<List<Integer>> result){if(target < 0){// 小于0，此路不通，直接返回return;}if(target == 0){//刚好为0，找到合法组合，加入结果集result.add(new ArrayList<>(currentCombination));return;}//start 开始遍历，允许重复使用同一个元素for(int i = start; i < candidates.length;i++){//选择当前元素currentCombination.add(candidates[i]);backtrace(candidates,target-candidates[i],i,currentCombination,result);//撤销选择，尝试下一个元素currentCombination.remove(currentCombination.size()-1);}}
}

class Solution {public List<List<Integer>> subsetsWithDup(int[] nums) {List<List<Integer>> result = new ArrayList();Arrays.sort(nums);List<Integer> temp = new ArrayList();backtrace(result,temp,nums,0);return result;}private void backtrace(List<List<Integer>> result,List<Integer> temp,int[] nums, int start){result.add(new ArrayList<>(temp)); // 添加当前组合到结果集for(int i = start; i < nums.length; i++){// 如果当前元素和前一个相同，并且前一个已经被用了（在同一个层级的循环中）// 跳过当前元素，避免生成重复的子集if(i> start && nums[i] == nums[i-1]){continue;}temp.add(nums[i]);backtrace(result,temp,nums,i+1); //递归生成当前选择为基础的子集temp.remove(temp.size()-1);// 撤销选择，回溯到上一层}}
}

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList();List<Integer> currentPermutation = new ArrayList();boolean[] used = new boolean[nums.length];// 递归进行全排列generatePermutation(nums,result,currentPermutation,used);return result;}private void generatePermutation(int[] nums,List<List<Integer>> result,List<Integer> currentPermutation,boolean[] used){if(currentPermutation.size() == nums.length){//排列已满，添加到结果集result.add(new ArrayList<>(currentPermutation));return;}for(int i=0;i<nums.length;i++){if(!used[i]){used[i] = true;currentPermutation.add(nums[i]);//递归生成剩余元素的全排列generatePermutation(nums,result,currentPermutation,used);//回溯，撤销选择used[i] = false;currentPermutation.remove(currentPermutation.size()-1);}}}
}

class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> result = new ArrayList();// 添加空集为起始result.add(new ArrayList());List<Integer> currentSubset = new ArrayList();generateSubsets(nums,0,currentSubset,result);return result;}private void generateSubsets(int[] nums, int index, List<Integer> currentSubset,List<List<Integer>> result){if(index == nums.length){return;}// 选择当前元素currentSubset.add(nums[index]);result.add(new ArrayList<>(currentSubset));generateSubsets(nums,index+1,currentSubset,result);//不选择当前元素，从子集移除当前元素currentSubset.remove(currentSubset.size()-1);//递归生成不包含当前元素的子集generateSubsets(nums,index+1,currentSubset,result);}
}

定义了四个方向，然后分别对矩阵的上下左右边界执行深度优先搜索，标记出能够流向太平洋和大西洋的单元格。之后遍历整个矩阵，找出同时标记为可达太平洋和大西洋的单元格，将其坐标添加到结果列表中

class Solution {// right left up downprivate int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};private int m,n;public List<List<Integer>> pacificAtlantic(int[][] heights) {m = heights.length;n = heights[0].length;boolean[][] pacificReachable = new boolean[m][n];boolean[][] atlanticReachable = new boolean[m][n];//分别从边界出发，进行DFS，标记能到达太平洋和大西洋的点for(int i=0; i<m; i++){dfs(heights,pacificReachable,i,0);//updfs(heights,atlanticReachable,i,n-1);//down}for(int j = 0; j<n;j++){dfs(heights,pacificReachable,0,j);//leftdfs(heights,atlanticReachable,m-1,j);//right}// 找出同时能到达太平洋和大西洋的点List<List<Integer>> result = new ArrayList();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(pacificReachable[i][j] && atlanticReachable[i][j]){result.add(Arrays.asList(i,j));}}}return result;}private void dfs(int[][] heights,boolean[][] reachable, int r,int c){reachable[r][c] = true;for(int[] dir: directions){int newRow = r+dir[0];int newCol = c+dir[1];if(newRow >=0 && newRow < m && newCol >= 0 && newCol < n && !reachable[newRow][newCol] && heights[newRow][newCol]>=heights[r][c]){dfs(heights,reachable,newRow,newCol);}}}
}

先遍历整个二维数组，统计新鲜橘子的数量并收集所有腐烂橘子的初始位置。然后，它使用BFS逐步腐烂新鲜橘子，同时跟踪经过的总分钟数。如果所有橘子都能腐烂，则返回分钟数；否则，若仍有新鲜橘子剩余，则返回-1

class Solution {public int orangesRotting(int[][] grid) {int m = grid.length;//行数int n = grid[0].length;//列数int freshOranges = 0;Queue<int[]> rottenQueue = new LinkedList<>(); //腐烂橘子的队列// 初始化for(int i=0; i<m;i++){for(int j = 0; j<n;j++){if(grid[i][j] == 1){freshOranges++;}else if(grid[i][j]==2){rottenQueue.offer(new int[]{i,j});}}}int minutes = 0; int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};while(!rottenQueue.isEmpty() && freshOranges > 0){// 当前轮次待处理的腐烂橘子数int queueSize = rottenQueue.size();for(int i=0; i< queueSize;i++){int[] rotten = rottenQueue.poll();for(int[] direction: directions){int newX = rotten[0] + direction[0];int newY = rotten[1] + direction[1];// 检查新位置是否在网格内且是新鲜橘子if(newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1){grid[newX][newY] = 2;freshOranges--;rottenQueue.offer(new int[]{newX,newY});}}}//如果这一轮有橘子腐烂，增加一分钟if(!rottenQueue.isEmpty()){minutes++;}}//如果还有没腐烂的，返回-1return freshOranges == 0?minutes:-1;}
}

先检查输入字符串的第一个字符，以确定是直接解析整数还是进入解析嵌套列表的逻辑。对于嵌套列表的解析，它使用一个栈来维护当前解析的嵌套层次。遍历字符串时，遇到 [ 时入栈一个新的 NestedInteger 实例，遇到 ] 时出栈，表示当前子列表完成。对于数字，连续读取直到遇到非数字字符，然后将其转换为 NestedInteger 并添加到当前栈顶的列表中。最后返回最外层的 NestedInteger 对象，即整个字符串解析的结果。

/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* public interface NestedInteger {*     // Constructor initializes an empty nested list.*     public NestedInteger();**     // Constructor initializes a single integer.*     public NestedInteger(int value);**     // @return true if this NestedInteger holds a single integer, rather than a nested list.*     public boolean isInteger();**     // @return the single integer that this NestedInteger holds, if it holds a single integer*     // Return null if this NestedInteger holds a nested list*     public Integer getInteger();**     // Set this NestedInteger to hold a single integer.*     public void setInteger(int value);**     // Set this NestedInteger to hold a nested list and adds a nested integer to it.*     public void add(NestedInteger ni);**     // @return the nested list that this NestedInteger holds, if it holds a nested list*     // Return empty list if this NestedInteger holds a single integer*     public List<NestedInteger> getList();* }*/
class Solution {public NestedInteger deserialize(String s) {if(s.charAt(0)!='[') {return new NestedInteger(Integer.valueOf(s));}Queue<Character> q=new LinkedList<>();for(char c:s.toCharArray()){q.offer(c);}// 弹出第一个'['q.poll();return dfs(q);}public NestedInteger dfs(Queue<Character> q){NestedInteger res=new NestedInteger();int sign=1;int num=0;while(!q.isEmpty()){char c=q.poll();if(c==','){continue;}else if(c=='['){res.add(dfs(q));}else if(c=='-'){sign=-1;}else if(c==']'){return res;}else {num=10*num+sign*(c-'0');if(q.peek()==','||q.peek()==']'){ res.add(new NestedInteger(num));num = 0;sign = 1;}}}return res;}
}

class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {if(k <=1){return 0;}int left = 0,product = 1, count = 0;for(int right = 0;right < nums.length;right++){product *= nums[right];while(product >= k){product /= nums[left++];}count+= right-left+1;//当前窗口的子数组个数}return count;}
}

class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);// 初始化int closestSum = nums[0]+nums[1]+nums[2];int minDiff = Math.abs(closestSum-target);for(int i = 0; i<nums.length -2; i++){// 跳过重复元素，避免重复计算if(i > 0 && nums[i] == nums[i-1]){continue;}int left = i+1, right = nums.length-1;while(left < right){int sum = nums[i]+nums[left]+nums[right];int diff = Math.abs(sum-target);//更新最接近的和、差值if(diff < minDiff){minDiff = diff;closestSum = sum;}//移动指针if(sum < target){left++;}else if(sum > target){right--;}else{//正好相等return sum;}}}return closestSum;}
}

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new ArrayDeque();for(String token: tokens){switch(token){case "+":stack.push(stack.pop() + stack.pop());break;case "-":int right = stack.pop();int left = stack.pop();stack.push(left-right);break;case "*":stack.push(stack.pop() * stack.pop());break;case "/":right = stack.pop();left = stack.pop();stack.push(left/right);//整除，自动向零截断break;default:stack.push(Integer.parseInt(token));break;}}return stack.pop(); //最后剩下的就是表达式的结果}
}

class Solution {public int climbStairs(int n) {if(n<=2){return n;}//初始化int[] dp = new int[n+1];dp[1] = 1;dp[2] = 2;for(int i=3;i<=n;i++){// 当前阶的方法数 = 前一阶的 + 前两阶的dp[i] = dp[i-1]+dp[i-2];}return dp[n];}
}

class Solution {public int minPathSum(int[][] grid) {int m = grid.length; //网格的行数int n = grid[0].length;//网格的列数//初始化int[][] dp = new int[m][n];//初始化第一行和第一列dp[0][0] = grid[0][0];for(int i=1;i<m;i++){dp[i][0] = dp[i-1][0]+grid[i][0];//第一列的值依赖上方的值}for(int j = 1;j<n;j++){dp[0][j] = dp[0][j-1]+grid[0][j];//第一行的值依赖左侧的值}//填充其余部分for(int i=1;i<m;i++){for(int j=1;j<n;j++){// 到达(i,j) 的最小路径和 = 上方和左侧的最下路径和 + 当前位置的值dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}// 右下角即为所求的最小路径和return dp[m-1][n-1];}
}

首先初始化一个布尔数组isPrime，用于标记从2到n-1的每个数是否为质数。初始时，假设所有数都是质数。然后，从2开始，对于每个标记为质数的数i，将其所有的倍数标记为非质数（因为它们肯定不是质数）。这个过程一直进行到sqrt(n)，因为大于sqrt(n)的非质数在其平方根之前已经被标记过了。最后，遍历数组，统计标记为true的元素个数，即为小于n的质数数量

class Solution {public int countPrimes(int n) {if(n<=2){return 0;}int count = 0;boolean[] isPrime = new boolean[n];Arrays.fill(isPrime,true);isPrime[0] = isPrime[1] = false;for(int i=2;i*i<n;i++){if(isPrime[i]){for(int j=i*i;j<n;j+=i){isPrime[j] = false;}}}//直接累加计数，而不是再次遍历for(int i=2;i<n;i++){if(isPrime[i]){count++;}}return count;}
}

牛客网

import java.util.*;public class Main {public static void main(String[] args) {Scanner console = new Scanner(System.in);int m = console.nextInt();int n = console.nextInt();int result = getCM(m, n);System.out.println(result);}public static int getCM(int m, int n){if(m == 0 || n == 0){return 0; //任何数和0 的最小公倍数是0}return Math.abs(m*n) / gcd(m,n);}// 计算最大公约数（GCD）的欧几里得算法private static int gcd(int a,int b){while(b != 0){int temp = b;b = a % b;a = temp;}return a;}
}

1. 读取输入数据：程序首先使用Scanner类从标准输入读取数据。首先读取一个整数I，表示序列I的长度；接着读取I个整数，填充到数组arrI中，这是整数序列I。随后读取一个整数r，表示序列R的长度；最后读取r个整数，这些整数将构成序列R，但首先会放入一个TreeSet（红黑树实现的集合）中以自动排序并去重。

2. 数据处理：

   • 使用TreeSet<Integer> treeSet来存储序列R中的整数，确保它们是去重且排序的。
   • 对于treeSet中的每个整数integer，执行以下操作：
     • 初始化一个计数器count用于记录有多少个整数I满足条件（即包含当前R中的整数）。
     • 创建一个临时列表temp，用于存储满足条件的I的索引和值。
     • 遍历数组arrI，将每个整数转换成字符串形式，并检查是否包含当前的integer（通过String.contains()方法）。
       • 如果包含，增加count计数，并将索引和该整数值加入到temp列表中。
     • 当前integer对应的处理结束后，如果count大于0，说明有满足条件的I，此时将integer、满足条件的个数count以及temp列表的内容添加到最终结果列表list中。

3. 整理输出：

   • 在输出之前，先在list的最前方添加一个元素，表示后续整数序列的个数（不包括这个计数本身）。
   • 最后，遍历list，将所有元素打印出来，每个元素后面跟一个空格。

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {  Scanner sc = new Scanner(System.in);  while (sc.hasNext()) {  // I 的个数  int countI = sc.nextInt();  int[] arraysI = new int[countI];//序列I  for (int i = 0; i < countI; i++) {  arraysI[i] = sc.nextInt();  }  int countR = sc.nextInt();  TreeSet<Integer> treeSetR = new  TreeSet<>();//序列R,对R序列进行排序去重  for (int i = 0; i < countR; i++) {  treeSetR.add(sc.nextInt());  }  ArrayList<Integer> result = getResult(treeSetR, arraysI);  //输出结果  for (Integer integer : result) {  System.out.print(integer + " ");  }  }  
}  private static ArrayList<Integer> getResult(TreeSet<Integer> treeSetR, int[] arraysI) {  ArrayList<Integer> result = new ArrayList<>();//保存最终结果  for (Integer integer : treeSetR) { //查找是否有满足条件的I  int count = 0;//统计满足个数  ArrayList<Integer> temp = new ArrayList<>();//临时列表，保存索引，以及对应值  for (int i = 0; i < arraysI.length; i++) {  String str = String.valueOf(arraysI[i]);//I整数对应的数字需要连续包含R<i>对应的数字  if (str.contains(String.valueOf(integer))) { //只要有一个满足条件就保存R<i>，保存个数，索引，具体I  count++;  temp.add(i);  temp.add(arraysI[i]);  }  }  if (count > 0) { //按顺序保存对应数据  result.add(integer);  result.add(count);  result.addAll(temp);  }  }  //统计序列总个数  result.add(0, result.size());  return result;  
}
}

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while(scanner.hasNextInt()){int targetNum = scanner.nextInt();if(targetNum <=2 || targetNum %2 != 0){System.out.println("输入应该为大于2的偶数");continue;}int lowerBound = targetNum/2;int upperBound = targetNum/2;while(lowerBound > 2 && upperBound< targetNum-2){if(isPrime(lowerBound) && isPrime(upperBound) && lowerBound+upperBound == targetNum){break;}else{lowerBound--;upperBound++;}}System.out.println(lowerBound);System.out.println(upperBound);}scanner.close();}private static boolean isPrime(int number){if(number <=2){return false;}//平方根 因为一个数的所有可能除数都不会超过其平方根for(int i=2;i<Math.sqrt(number);i++){if(number % i ==0){return false;} }return true;}
}

leetcode没有版权了，找不到，暂时先在csdn看吧

接受一个二叉树的根节点作为输入，然后返回一个二维列表，其中每个子列表代表二叉树每一层的节点值，且根据之字形顺序排列。这里使用了两个栈来实现层次遍历，并通过leftToRight布尔变量来控制当前层遍历时的方向（从左到右或从右到左）。在遍历过程中，根据当前层的遍历方向决定如何将孩子节点压入栈中，以实现之字形遍历的效果

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> currentLevel = new Stack<>();Stack<TreeNode> nextLevel = new Stack<>();currentLevel.push(root);boolean leftToRight = true; // 标记当前层的遍历方向while (!currentLevel.isEmpty()) {List<Integer> levelValues = new ArrayList<>();while (!currentLevel.isEmpty()) {TreeNode node = currentLevel.pop();levelValues.add(node.val);// 根据当前层的遍历方向来决定孩子节点的入栈顺序if (leftToRight) {if (node.left != null) {nextLevel.push(node.left);}if (node.right != null) {nextLevel.push(node.right);}} else {if (node.right != null) {nextLevel.push(node.right);}if (node.left != null) {nextLevel.push(node.left);}}}result.add(levelValues);// 交换两个栈，准备下一层的遍历Stack<TreeNode> temp = currentLevel;currentLevel = nextLevel;nextLevel = temp;// 改变遍历方向leftToRight = !leftToRight;}return result;}

使用了一个队列来保存每一层的节点，初始时将根节点入队。进入循环后，首先获取当前层的节点数量，然后遍历这一层的每个节点，打印节点值，并将其左右孩子节点（如果存在）入队。每完成一层的遍历后，通过换行来区分不同层的输出

public class SolutionJZ32two {public static void main(String[] args) {// 示例创建二叉树，实际使用时可以通过读取输入动态生成TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);printTreeByLevel(root);}public static void printTreeByLevel(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();for (int i = 0; i < levelSize; i++) {TreeNode currentNode = queue.poll();System.out.print(currentNode.val + " ");if (currentNode.left != null) {queue.offer(currentNode.left);}if (currentNode.right != null) {queue.offer(currentNode.right);}}System.out.println(); // 换行，表示这一层打印完毕}}
}

• 使用两层循环遍历每一种砝码及其数量。外层循环遍历砝码种类，内层循环则基于当前砝码的数量生成所有可能的累加重量。
• 对于每种砝码，通过一个临时的HashSet newWeights来收集新生成的所有可能总重量，这一步是为了避免直接修改正在迭代的集合而引发的并发修改异常。
• 内部还有一个循环遍历allWeights中已有的所有重量，并将当前砝码的每个可能累加重量（从1倍到其数量倍）都加到这些已知重量上，然后将结果加入到newWeights中。
• 每处理完一种砝码后，将newWeights的内容替换到allWeights中，准备处理下一种砝码

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int n = in.nextInt();int[] weights = new int[n];int[] counts = new int[n];for (int i = 0; i < n; i++) {weights[i] = in.nextInt();}for (int i = 0; i < n; i++) {counts[i] = in.nextInt();}Set<Integer> allWeights = new HashSet<>();allWeights.add(0); // 包含重量0// 直接通过循环构建所有可能的重量组合for (int i = 0; i < n; i++) {Set<Integer> newWeights = new HashSet<>(allWeights); // 避免修改原集合导致并发修改异常for (int count = 1; count <= counts[i]; count++) {for (int existingWeight : allWeights) {newWeights.add(existingWeight + weights[i] * count);}}allWeights = newWeights;}System.out.println(allWeights.size());}in.close();}
}