高阶面试-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();}
}