高阶面试-hw算法整理

  • 开发
  • 27

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

文章目录

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);
            }
        }
    }
}
阅读全部

相关推荐

  1. 高阶面试-hw算法整理

    2024-07-21 00:16:03       28 阅读

  2. 高阶面试-mongodb

    2024-07-21 00:16:03       24 阅读

  3. 高阶面试-写缓存

    2024-07-21 00:16:03       34 阅读

  4. C++面试：堆排序、归并排序、二分查找等高阶算法

    2024-07-21 00:16:03       54 阅读

  6. kafka面试题（基础-进阶-高阶）

    2024-07-21 00:16:03       29 阅读

  10. 算法 Hw9

    2024-07-21 00:16:03       37 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 00:16:03       123 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 00:16:03       131 阅读

  9. 在Django里面运行非项目文件

    2024-07-21 00:16:03       109 阅读

  19. Python语言-面向对象

    2024-07-21 00:16:03       117 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-21 00:16:03       109 阅读

热门阅读

  1. 【系统架构设计师】论文：论行业应用软件系统的开发规划

    2024-07-21 00:16:03       33 阅读

  6. std::bind 简单实验

    2024-07-21 00:16:03       29 阅读

  7. 中电金信：语言服务游戏行业解决方案

    2024-07-21 00:16:03       29 阅读

  9. 数据库之数据类型

    2024-07-21 00:16:03       27 阅读

  12. 代码保存板块

    2024-07-21 00:16:03       30 阅读

  13. Git 代码管理面试59题（一）

    2024-07-21 00:16:03       29 阅读

  14. Kudu节点数规划

    2024-07-21 00:16:03       34 阅读

  18. Emacs

    2024-07-21 00:16:03       27 阅读

  20. 提升 Google 对网站兴趣的关键：颜值与内容并重

    2024-07-21 00:16:03       20 阅读

  23. 2024.07.20【读书笔记】|医疗科技创新流程（第二章 创新创造 Acclarent案例研究）

    2024-07-21 00:16:03       33 阅读

  28. 【js自学打卡8】filter / 类与原型链 / 转字符串

    2024-07-21 00:16:03       32 阅读

  30. 2024年交安安全员考试题库及答案

    2024-07-21 00:16:03       25 阅读