高阶面试-hw算法整理

坚持最近一个星期把每道题搞熟悉

1154一年中的第几天

public int dayOfYear(String date) {
	// format YYYY-MM-DD
	int 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;
}

125. 验证回文串

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;
    }
}

344. 反转字符串

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--;
        }
    }
}

20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        // map {} 栈
        // check
        if(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();
    }
}

392. 判断子序列

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;
    }
}

409. 最长回文串

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()){
            // 当前字符出现次数向下取偶数，并计入res
            int count = kv.getValue();
            int rem = count % 2;
            res += count - rem;

            // 如果当前字符出现次数是奇数，将odd置位1
            if(rem == 1){
                odd = 1;
            }
        }
        return res+odd;
    }
}

859. 亲密字符串

class Solution {
    public boolean buddyStrings(String s, String goal) {
        //check len
        if (s.length() != goal.length()){
            return false;
        }

        // equal
        if (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 second
            int 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));
        }
    }
}

14. 最长公共前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // check
        if(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;
    }
}

1694. 重新格式化电话号码

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();
    }
}

551. 学生出勤记录 I

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

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // cache
        Map<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[]{};
    }
}

169. 多数元素

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

53. 最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
	    //check
        if(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;
    }
}

1502. 判断能否形成等差数列

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;
    }
}

88. 合并两个有序数组

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);
        }
        // 拷贝到nums1
        System.arraycopy(newNums,0,nums1,0,m+n);
    }
}

594. 最长和谐子序列

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;
    }
}

643. 子数组最大平均数 I

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;
    }
}

463. 岛屿的周长

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;
    }
}

234. 回文链表

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null){
            return true;
        }

        // stack
        Deque<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;
    }
}

21. 合并两个有序链表

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;
    }
}

141. 环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        // check
        if(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;
    }
}

83. 删除排序链表中的重复元素

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;
    }
}

468. 验证IP地址

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 并且长度不为1
            if (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');
            }
            //数字超过255
            if (ans > 255) {
                return false;
            }
        }
        return true;
    }

    public boolean isIPv6(String queryIP) {
        String[] split = queryIP.split(":", -1);
        //数量不是8
        if (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;
    }
}

正则太难了…

692. 前K个高频单词

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;
        }

        @Override
        public int compareTo(WordFrequency wordFrequency) {
            if (this.frequency != wordFrequency.frequency) {
                return Integer.compare(this.frequency, wordFrequency.frequency);
            } else {
               return wordFrequency.word.compareTo(this.word);
            }
        }
    }
}

1764. 通过连接另一个数组的子数组得到一个数组

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;
    }
}

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        //check
        if(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()][]);
    }
}

229. 多数元素 II

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;
    }
}

347. 前 K 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // check
        if(nums.length==0 || k == 0){
            return new int[]{};
        }

        // hash
        Map<Integer,Integer> hash = new HashMap();
        for(int i=0;i<nums.length;i++){
            hash.put(nums[i],hash.getOrDefault(nums[i],0)+1);
        }

        // PriorityQueue
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k,(v1,v2)->{
            return hash.get(v1)-hash.get(v2);
        });

        // offer
        for(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);
                }
            }
        }

        // res
        int[] res = new int[k];
        int i = 0;
        for(int e: queue){
            res[i] = e;
            i++;
        }
        return res;
    }
}

93. 复原 IP 地址

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);
        }
    }
}

424. 替换后的最长重复字符

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;
    }
}

15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // check
        if(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;

    }
}

39. 组合总和

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);
        }
    }
}

90. 子集 II

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);// 撤销选择，回溯到上一层
        }
    }
}

46.全排列

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);
            }
        }
    }
}

78. 子集

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);
    }
}

417. 太平洋大西洋水流问题

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

class Solution {
    // right left up down
    private 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);//up
            dfs(heights,atlanticReachable,i,n-1);//down
        }
        for(int j = 0; j<n;j++){
            dfs(heights,pacificReachable,0,j);//left
            dfs(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);
            }
        }
    }
}

994. 腐烂的橘子

先遍历整个二维数组，统计新鲜橘子的数量并收集所有腐烂橘子的初始位置。然后，它使用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++;
            }
        }
        //如果还有没腐烂的，返回-1
        return freshOranges == 0?minutes:-1;
    }
}

385.迷你语法分析器

先检查输入字符串的第一个字符，以确定是直接解析整数还是进入解析嵌套列表的逻辑。对于嵌套列表的解析，它使用一个栈来维护当前解析的嵌套层次。遍历字符串时，遇到 [ 时入栈一个新的 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;
    }
}

713. 乘积小于 K 的子数组

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;
    }
}

16. 最接近的三数之和

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;
    }
}

150. 逆波兰表达式求值

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(); //最后剩下的就是表达式的结果
    }
}

70. 爬楼梯

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];
    }
}

64. 最小路径和

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];
    }
}

204. 计数质数

首先初始化一个布尔数组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;
    }
}

JAVA11 求最小公倍数

牛客网

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;
    }
}

HJ28 素数伴侣

为何需要重新寻找伴侣

当为某个奇数找到了一个偶数伴侣，并且这个偶数原先已经有伴侣时，我们实际上打破了原有的一个匹配对。为了保持匹配的最大化，我们需要确保被替换掉的奇数（原偶数的伴侣）也能找到一个新的匹配，这样才能保证整体匹配数的增加而不是简单的交换。

实现机制

在find函数中，当为奇数odd找到一个与之匹配的偶数，并且这个偶数之前已经有了伴侣（evensMatch[i] != 0），代码会递归调用find(evensMatch[i], evens, used, evensMatch)。这一步是为了尝试为那个被替换的奇数（evensMatch[i]）重新找到一个伴侣。如果成功，意味着原伴侣（evensMatch[i]）找到了新的匹配，释放了当前偶数与新奇数（odd）的匹配，整体的匹配对数得以增加。

保证最大匹配

通过这种方式，算法不断探索所有可能的匹配组合，确保了在每次为一个奇数找到匹配时，都能尽量维持或增加整体的匹配对数，避免了局部最优解，从而向全局最优解靠近。简言之，递归重找伴侣是为了在有限的资源（偶数）中，通过调整和优化，达到最多“素数伴侣”对的目的。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        //输入的数字先分为 奇数、偶数 两组
        List<Integer> evenList = new ArrayList<>();
        List<Integer> oddList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int j = sc.nextInt();
            if (isEven(j)) {
                evenList.add(j);
            } else {
                oddList.add(j);
            }
        }

        int size = evenList.size();
        int count = 0;

        //已经匹配的数的伴侣
        int[] evensMatch = new int[size];
        for (Integer odd : oddList) {
            //标记对应的数是否查找过
            int[] used = new int[size];
            if (find(odd, evenList, used, evensMatch)) {
                count++;
            }
        }
        System.out.println(count);

        sc.close();
    }

    private static boolean isPrime(int n) {
        // 除1和自身，不能被其他自然数整除
        if (n <= 1) {
            return false;
        } else {
            for (int i = 2; i < n; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean isEven(int n) {
        return (n %2 )==0;
    }

    private static boolean find(int odd, List<Integer> evens, int[] used, int[] evensMatch) {
        //便利偶数：检查当前传入的奇数是否与那些偶数匹配
        for (int i = 0; i < evens.size(); i++) {
            if (isPrime(odd + evens.get(i)) && used[i] == 0) {
                // 设置当前偶数匹配为true
                used[i] =1;
                //如果第 i 个偶数没有伴侣
                //或者第 i 个偶数原来有伴侣，并且该伴侣能重新找到伴侣
                // 奇数odd可被设置为第 i 个偶数的伴侣
                //采用匈牙利算法，能让就让
                if (evensMatch[i] == 0 || find(evensMatch[i], evens, used, evensMatch)) {
                    evensMatch[i] = odd;
                    return true;
                }
            }
        }
        //遍历完偶数都没有可以做伴侣的，奇数没有配对
        return false;
    }

HJ25 数据分类处理

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;  
}
}

HJ60 查找组成一个偶数最接近的两个素数

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;
    }
}

从上到下打印二叉树 III

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;
    }

剑指offer 32 从上到下打印二叉树 II

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

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(); // 换行，表示这一层打印完毕
        }
    }
}

HJ41 称砝码

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