之旅"/>
力扣做题之旅
2022/12/4——数组专题
题目(完成)：1.两数之和
我的解答：
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int nums_len=end(nums)-begin(nums);int i,j;int result_sum;int result_numpy[2];for(i=0;i<nums_len;i++){for(j=0;j<nums_len;j++){result_sum=nums[i]+nums[j];if(result_sum==target&&i!=j){result_numpy[0]=i;result_numpy[0]=j;return {i,j};}}}return {i,j};}
};经验：
1.求数组长度：
int nums_len=end(nums)-begin(nums)2.嵌套for循环
3.定义数组：
int numpy1[5] = { 0,1,2,3,4 } //注意数组的表达形式{}//java
class Solution {public int[] twoSum(int[] nums, int target) {int sums = 0 ;int []result = new int[2];for(int i = 0;i<nums.length;i++){for(int j = 0;j<nums.length;j++){if(nums[i]+nums[j]==target && i!=j){result[0]=i;result[1]=j;break;}}}return result;}
}2022/12/5
题目(未做出)26：删除有序数组中的重复项
我的解答(二刷):
class Solution {
public:int removeDuplicates(vector<int>& nums) {int i=1;int j=1;while(i<nums.size()){if(nums[j]!=nums[i-1]){i++;j++;}else{j++;if(nums[i-1]!=nums[j]){nums[i]=nums[j];i++;j=i;}}}return i;}
};答案解答(思维有进步，但是还不够)
class Solution {
public:// j// i // 0 1 2 1 2 2 3 4int removeDuplicates(vector<int>& nums) {int i = 1, j = 1;while(j < nums.size()){if(nums[i - 1] != nums[j]){nums[i] = nums[j];++i;}++j;}return i;}
};三刷做的答案和第一次做的答案一模一样 真服了
class Solution {public int removeDuplicates(int[] nums) {int i = 1;int j = 1;while(j<nums.length){if(nums[i-1]!=nums[j]){nums[i]=nums[j];i++;//j=i;}else{j++;}}return i;}
}2022/12/6
题目(做出一半)：27.移除元素
我的解答：
class Solution {
public:int removeElement(vector<int>& nums, int val) {int i;int j;int k;for(i=0;i<(nums.size())/2;i++){if(nums[i]==val){for(j=nums.size()-1;j>=(nums.size())/2;j--){if(nums[j]!=val){k=nums[i];nums[i]=nums[j];nums[j]=k;break;}}}}return i;}
};经验：
我的思路是用双指针分别从左右遍历，答案有相同的思路，但是我写的不太好。
第二次解答 依托答辩
class Solution {
public:int removeElement(vector<int>& nums, int val) {int i,j=1;int a=0;while(j<nums.size()){if(nums[i-1]!=val){i++;j++;}else{j++;if(nums[j]!=val){a=nums[i-1];nums[i-1]=nums[j];nums[j]=a;i++;j=i;}}}return i;}
};非常简单直接的解题思路
class Solution {
public:int removeElement(vector<int>& nums, int val) {int i;int j=0;for(i=0;i<nums.size();i++){if(nums[i]!=val){nums[j]=nums[i];j++;}}return j;}
};2022/12/7
题目(未做出)：35.搜索插入位置
题目中若要求算法的时间复杂度是O(logn)，那么这个算法基本上就是二分法。
我的解答：超时 第二次
我的解答
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int i=0;int a;while(i<nums.size()){if(nums[i]<=target&&target<=nums[i+1]){if(nums[i]==target){a=i;}else if(nums[i+1]==target){a=i+1;}else{a=i+1;}}else{i++;}}return a;}
};
答案
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size()-1;int mid = 0;while(left <= right){mid = left + (right - left)/2;if(nums[mid] == target){return mid;}if(nums[mid] >target){right = mid-1;}else{left = mid+1;}}return left;}
};
2022/12/8
题目(基本完成)：66.加一
我的解答
class Solution {
public:vector<int> plusOne(vector<int>& digits) {int length=digits.size()-1;digits[length]++;int i=digits.size()-1;while(i>0){if(digits[i]==10){digits[i]=0;digits[i-1]++;}i--;}if(digits[0]==10){vector<int>ans(digits.size()+1);ans[0]=1;return ans;}return digits;}
};经验：
可以自己定义一个新的数组并返回；定义一个全为0的数组：
vector<int>ans(digits.size()+1);二刷 和第一遍做的一模一样 服了 一点进步没有啊
class Solution {
public:vector<int> plusOne(vector<int>& digits) {int i = digits.size() - 1;digits[i]++;while(i>=0){if(digits[i]==10){digits[i]=0;digits[i-1]++;}i--;}return digits;}
};class Solution {public int[] plusOne(int[] digits) {int n = digits.length -1;digits[n]++;while(n>0){if(digits[n]==10){digits[n]=0;digits[n-1]++;}n--;}if(digits[0]==10){int []result = new int[digits.length+1];result[0]=1;for(int j=1;j<n+1;j++){result[j]=0;}return result;}return digits;}
}
更简洁的思维
public int[] plusOne(int[] digits) {for (int i = digits.length - 1; i >= 0; i--) {if (digits[i] == 9) {digits[i] = 0;} else {digits[i] += 1;return digits;}}//如果所有位都是进位，则长度+1digits= new int[digits.length + 1];digits[0] = 1;return digits;}2022/12/9
题目(超时)：88.合并两个有序数组
我的解答
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i;int j=0;for(i=m;i<m+n;i++){nums1[i]=nums2[j];j++;}int k=m+n;int i_1;int j_1;int test;int times=0;while(k>2){for(i_1=0;i_1<k;i_1++){for(j_1=0;j_1<k;j_1++){if(nums1[i_1]>=nums1[j_1]){times++;}if(times==k){test=nums1[i_1];nums1[i_1]=nums1[k-1];nums1[k-1]=test;k--;// i_1=0;// j_1=0;}}}}}
};
答案
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int r=nums1.size();while(n>0){if(m>0&&nums1[m-1]>nums2[n-1]){nums1[r-1]=nums1[m-1];m--;r--;}else{nums1[r-1]=nums2[n-1];n--;r--;}}}
};经验：
1.感觉自己写的逻辑上应该没问题，但是超时了。
2.因为两个数组都是非递减顺序的，所以从后往前比较两个数组的值大小然后插入。
二刷 未作出 还不如第一次 好歹还有点思路
2022/12/10
题目(未做出)：118.杨辉三角
答案
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>>nums(numRows);int i;int j;int m;for(i=0;i<numRows;i++){nums[i].resize(i+1);nums[i][i]=1;nums[i][0]=1;}for(m=2;m<numRows;m++){for(j=1;j<m;j++){nums[m][j]=nums[m-1][j-1]+nums[m-1][j];}}return nums; }
};经验：
1.nums.resize()
2.nums[i][j]
2023/2/15
题目(我感觉没问题，但是答案也没有类似的解答)：136.只出现一次的数字
我的解答
class Solution {
public:int singleNumber(vector<int>& nums) {int i,j;int times=0;int a=0;for(i=0;i<nums.size();i++){for(j=0;j<nums.size();j++){if(nums[i]==nums[j]){times++;}}if(times==1){return nums[i]; }}return 0;}
};异或运算有两种特性：
- x ^ x = 0，任意相同数字 x 异或的结果为 0；
- x ^ 0 = x，任意非零数字与 0 异或的结果为其本身。
- 异或运算满足交换律和结合律。
class Solution {public int singleNumber(int[] nums) {int result = 0;for(int num:nums){result ^=num;}return result;}
}2023/3/27
题目(未做出)121：买卖股票的最佳时机
参考答案
class Solution {
public:int maxProfit(vector<int>& prices) {int cost=INT_MAX,profit=0;for(int price : prices){cost=min(cost,price);profit=max(profit,price-cost);}return profit;}
};class Solution {public int maxProfit(int[] prices) {int cost = 100000;int profit = 0;for(int price:prices){cost=Math.min(cost,price);profit=Math.max(profit,price-cost);}return profit;}
}
//正无穷
print(float("inf"))
print(float("inf")+1)
//负无穷
print(float("-inf"))
print(float("-inf")+1)Java中最大值函数：Math.max
Java中最小值函数：Math.min
2023/3/29
题目(完成)169：多数元素
sort(nums.begin(),nums.end());class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return(nums[(nums.length)/2]);}
}Java中的排序函数：Arrays.sort(数组名)
题目(完成)217：存在重复元素
参考答案
class Solution {
public:bool containsDuplicate(vector<int>& nums) {sort(nums.begin(), nums.end());for (int i = 1; i < nums.size(); i++) if (nums[i-1] == nums[i]) return true;return false;}
};class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> set;for (int num: nums) {if (set.find(num) != set.end()) return true;set.insert(num); }return false;}
};class Solution {
public:bool containsDuplicate(vector<int>& nums) {if(nums.size() <= 1) return false;unordered_map<int,int> map;for(int num : nums) {map[num]++;if(map[num] >= 2) return true;}return false;}
};unordered_set find(key):查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器
Java哈希表：
class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> set = new HashSet<Integer>();for (int x : nums) {if (!set.add(x)) {return true;}}return false;}
}
个人感觉下面这个更好，能和C++版本对应上理解
class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> set = new HashSet<>();for (int num: nums) {if (set.contains(num)) {return true;}set.add(num);}return false;}
}
2023/3/30
题目(C++写未完成，用Java写的时候通过了)219:存在重复元素2
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,int> map;for(int i=0;i<nums.size();i++){if(!map.empty() && map.count(nums[i])>0){if(i-map[nums[i]]<=k){return true;}}map[nums[i]]=i;} return false;}
};map和set两种容器的底层结构都是红黑树，所以容器中不会出现相同的元素，因此count()的结果只能为0和1，可以以此来判断键值元素是否存在(当然也可以使用find()方法判断键值是否存在)。
Java
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Set<Integer> set= new HashSet<>();for(int i=0;i<nums.length;i++){if(set.contains(nums[i])){// int k = 0;for(int j=0;j<nums.length;j++){if(nums[j]==nums[i]&&i!=j){if(Math.abs(i-j)<=k){return true;}}}}set.add(nums[i]);}return false;}
}答案
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {HashSet<Integer> set = new HashSet<>();for(int i = 0; i < nums.length; i++) {if(set.contains(nums[i])) {return true;}set.add(nums[i]);if(set.size() > k) {set.remove(nums[i - k]);}}return false;}
}
答案采用的是是类似滑动窗口的一种方法 一直维护一个大小为K的滑动窗口一直往前走，判断窗口内是否有重复元素，所以与我考虑的存在哈希表内的数据是否有序无关，这里注意哈希表不保证集合中元素的顺序，在某些特定情况下可能是有序的。
2023/4/2
题目(思路正确，做出来一半)228：汇总区间
我的解答
class Solution {
public:vector<string> summaryRanges(vector<int>& nums) {vector<string>ans;int i=1;int j=1;string s;while(j<nums.size()){if(nums[j]-nums[i-1]>1){s = to_string(nums[i-1]);ans.push_back(s);i++;j++;}else{if(j==nums.size()-1){s=to_string(nums[i-1]) + "->" + to_string(nums[j]);ans.push_back(s);}int times = 1;j++;if(nums[j]-nums[i]==times){j++;times++;}if(nums[j]-nums[i]>times){// map[k]="nums[i-1],nums[j-1]]";// s += to_string(nums[l]) + "->" + to_string(nums[r - 1]);s=to_string(nums[i-1]) + "->" + to_string(nums[j-1]);ans.push_back(s);if(j==nums.size()-1){s=to_string(nums[j]);ans.push_back(s);}i=j+1;j=i;}}}return ans;}
};// s = to_string(nums[l]);
// ans.push_back(s);答案
class Solution {
public:vector<string> summaryRanges(vector<int>& nums) {int n = nums.size();vector<string> ans;if(n == 0) {return {};}//nums是个空数组int l = 0;while(l < n) {string s;int r = l + 1;if(r == n) { //mums数组中只有一个元素s = to_string(nums[l]);ans.push_back(s);break;}while(r < n && nums[r] == nums[r - 1] + 1) {++r;}if(r == l + 1) {s = to_string(nums[l]);} if(r > l + 1) {s += to_string(nums[l]) + "->" + to_string(nums[r - 1]);}l = r;ans.push_back(s);}return ans;}
};push_back()函数将一个新元素加到vector的最后，位置为当前最后一个元素的下一个元素
Java
class Solution {public List<String> summaryRanges(int[] nums) {List<String> res = new ArrayList<>();// i 初始指向第 1 个区间的起始位置int i = 0;for (int j = 0; j < nums.length; j++) {// j 向后遍历，直到不满足连续递增(即 nums[j] + 1 != nums[j + 1])// 或者 j 达到数组边界，则当前连续递增区间 [i, j] 遍历完毕，将其写入结果列表。if (j + 1 == nums.length || nums[j] + 1 != nums[j + 1]) {// 将当前区间 [i, j] 写入结果列表StringBuilder sb = new StringBuilder();sb.append(nums[i]);if (i != j) {sb.append("->").append(nums[j]);}res.add(sb.toString());// 将 i 指向更新为 j + 1，作为下一个区间的起始位置i = j + 1;}}return res;}
}List<String> res = new ArrayList<>();定义一个长度可变的数组
参考文章：(92条消息) Java如何向数组里添加元素_java数组添加元素的方法_zhangvalue的博客-CSDN博客
StringBuilder sb = new StringBuilder();可编辑的字符串
参考文章：
(92条消息) Java：StringBuilder的基本使用_java stringbuilder用法_Rex Chou的博客-CSDN博客
2023/4/3
题目(完成)268：消失的数字
我的解答
我的解答
class Solution {
public:int missingNumber(vector<int>& nums) {int n = nums.size();sort(nums.begin(),nums.end());int r = 0;if(nums[0]!=0){return r;}if(n == r + 1){return r+1;}while((r+1<n) && nums[r+1] == nums[r] + 1){r++;}return r+1;}
};2023/4/4
题目(完成)283：移动零
暴力解法
class Solution {
public:void moveZeroes(vector<int>& nums) {int times=0;int j = 0;// if(nums.size()==0){// return nums// }for(int i=0;i<nums.size();i++){if(nums[i]!=0){nums[j]=nums[i];j++;times++;}}for(times;times<nums.size();times++){nums[times]=0;}// return nums;}
};
双指针
class Solution {
public:void moveZeroes(vector<int>& nums) {int left = 1;int right = 1;while(right<nums.size()){if(nums[left - 1]== 0){if(nums[right]!=0){nums[left-1]=nums[right];nums[right]=0;left++;right=left;}else{right++;}}else{left++;right++;}}}
};答案
class Solution {
public:void moveZeroes(vector<int>& nums) {int leftIndex = 0;int rightIndex = 0;/*** 还是两个指针，如果nums[rightIndex]不等于0的时候才交换，并且对left进行加*/while(rightIndex < nums.size()){if(nums[rightIndex]){int t = nums[rightIndex];//很简洁 双指针自己和自己换的思想需要好好理解一下nums[rightIndex] = nums[leftIndex];nums[leftIndex] = t;++leftIndex;}++rightIndex;}}
};2023/4/5
题目(完成一半)303：区域和检索-数组不可变
对题目和函数的理解没到位
class NumArray {vector<int>test;//全局变量
public:NumArray(vector<int>& nums) {test.resize(nums.size()+1);for(int i=0;i<nums.size();i++){test[i+1]=test[i]+nums[i];}}int sumRange(int left, int right) {return test[right+1]-test[left];}
};class NumArray {private int[] res;public NumArray(int[] nums) {res = new int[nums.length + 1];for(int i = 0;i < nums.length;i++){res[i+1] = res[i] + nums[i];}}public int sumRange(int left, int right) {return res[right + 1] - res[left];}
}为什么要这么写，而不是按照自己一开始比较直接的思路，需要好好理解，想不明白就看看解析
2023/4/6
题目(未完成)349：两个数组的交集
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {/* 存放结果，之所以用set是为了给结果集去重 */unordered_set<int> result;/* 由于输出的元素唯一不重复因此可以将nums1转化为unordered_set哈希表 */unordered_set<int> nums1_set(nums1.begin(),nums1.end());for(int i = 0; i < nums2.size(); i++){/* 判断nums1_set中是否有nums2的元素，若有将此值插入到result */if(nums1_set.find(nums2[i]) != nums1_set.end())result.insert(nums2[i]);}return vector<int> (result.begin(),result.end());}
};我的解答
class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> hashset= new HashSet<Integer>();Set<Integer> hashset1= new HashSet<Integer>();for(int num1:nums1){hashset.add(num1);}for(int num2:nums2){if(hashset.contains(nums2)){hashset1.add(num2);}hashset.add(num2);}int [] resArr=new int[hashset1.size()];int index = 0;for(int i:hashset1){resArr[index++] = i;}return resArr;// int[] result = new int[hashset1.size()];// int i = 0;// for (int integer : hashset1) {// result[i++] = integer;// }// return result;// return int[] result = new int(hashset1);}
}
答案
class Solution {public int[] intersection(int[] nums1, int[] nums2) {if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {return new int[0];}Set<Integer> set = new HashSet<Integer>();Set<Integer> result = new HashSet<Integer>(); // 结果哈希表// 遍历nums1加入set哈希表for ( int i : nums1) {set.add(i);}// 遍历nums2,如果set哈希表中存在就加入到结果哈希表中for ( int i : nums2) {if (set.contains(i)) {result.add(i);}set.add(i);}int[] resArr = new int[result.size()]; // 结果数组int index = 0;// 把哈希表的值传入数组for (int i : result) {resArr[index++] = i;}return resArr;}
}有运用哈希表的思维了，而且自己写的语言逻辑感觉和答案没差呀，不知道为什么就是不对(Java)
2023/4/7
题目(完成一半)350：两个数组的交集2
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int>map1;unordered_map<int,int>map2;unordered_set<int>set;//vector是动态空间,随着新元素的加入，内部机制会自动扩充空间容纳新元素。vector<int>ans;for(int num1:nums1){map1[num1]++;}for(int num2:nums2){map2[num2]++;}for(int num3:nums1){if(map2.find(num3)!=map2.end()){int times = min(map1[num3],map2[num3]);for(int i=0;i<times/2;i++){ans.push_back(num3);}}}return ans;}
};class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int>Hash;vector<int> ans;for (auto &i : nums1){++Hash[i];}for (auto &i : nums2){if (Hash.find(i) != Hash.end() && Hash[i] > 0){ans.emplace_back(i);--Hash[i];}}return ans;}
};class Solution {public int[] intersect(int[] nums1, int[] nums2) {//总是让nums1指向短的呢个数组if(nums1.length > nums2.length){return intersect(nums2.nums1);}Map<Integer,Integer>map = new HashMap<Integer,Integer>();for(int num:nums1){int count = map.getOrDefault(num,0)+1;map.put(num,count);}int [] intersection = new int[nums1.length];int index = 0;for(int num:nums2){int count = map.getOrDefault(num,0);if(count >0){intersection[index++]=num;count--;if(count>0){map.put(num,count);}else{map.remove(num);}}}return Arrays.copyOfRange(intersection,0,index);}
}
2023/4/7
题目(C++未完成，Java完成)414：第三大的数
class Solution {
public:int thirdMax(vector<int>&nums) {sort(nums.begin(),nums.end());set<int>st;int result=0;if(nums.size()<3){int n=nums.size()-1;return nums[n];}int times=0;for(int num:nums){st.insert(num);}for(auto it=st.end();it!=st.begin();it--){times++;if(times==3){result=*it;break;}}return result;}
};class Solution {
public:int thirdMax(vector<int> &nums) {set<int> s;for (int i = 0; i < nums.size(); i++) {s.insert(nums[i]);if (s.size() > 3) {s.erase(s.begin());}}if (s.size() == 3)return *s.begin();return *s.rbegin();}
};class Solution {public int thirdMax(int[] nums) {Arrays.sort(nums);Map<Integer,Integer>map = new HashMap<Integer,Integer>();for(int num:nums){int count = map.getOrDefault(num,0)+1;map.put(num,count);}if(map.size()<3){return nums[nums.length-1];}else{int index = nums.length-1;int count_first=map.getOrDefault(nums[index],0);index=index-count_first;int count_second=map.getOrDefault(nums[index],0);index=index-count_second;return nums[index];}}
}这个解题思路不错
class Solution {public int thirdMax(int[] nums) {Set<Integer> set = new HashSet<>();for (int x : nums) set.add(x);List<Integer> list = new ArrayList<>(set);Collections.sort(list);return list.size() < 3 ? list.get(list.size() - 1) : list.get(list.size() - 3); }
}对去重后的set数组进行了排序
2023/4/13
题目(未完成)34：在排序数组中查找元素的第一个和最后一个位置
class Solution {public int[] searchRange(int[] nums, int target) {int x = Leftmost(nums,target);if(x == -1){return new int[]{-1,-1};}else{return new int[]{x,Rightmost(nums,target)};}}public int Leftmost(int[] nums, int target){int left = 0;int right = nums.length;int candidate = -1;// List<Integer> res = new ArrayList<Integer>();while(left <= right){int mid = (left+right) >>> 1;if(target < nums[mid]){right = mid - 1;}else if(target > nums[mid]){left = mid + 1;}else{candidate = mid;right = mid -1 ;}}return candidate;}public int Rightmost(int[] nums, int target){int left = 0;int right = nums.length;int candidate = -1;while(left <= right){int mid = (left+right) >>> 1;if(target < nums[mid]){right = mid - 1;}else if(target > nums[mid]){left = mid + 1;}else{candidate = mid;left = mid + 1 ;}}return candidate;}}题目(完成)9：回文数
class Solution {public boolean isPalindrome(int x) {int number = 0;int temp = x;//负数一定不是回文数if(x <0){return false;}while(x!=0){int unit = x % 10;x = x / 10;number = number * 10 + unit;}return (temp==number);}
}2023/4/14
题目(超时)448：找出所有数组中消失的数字
class Solution {public List<Integer> findDisappearedNumbers(int[] nums) {Arrays.sort(nums);// Set<Integer> set = new Hashset<Integer>();Set<Integer> set = new HashSet<Integer>();//根据题意数组中第一个元素一定是1int i = 1;while(i<nums.length){if(nums[i]!=nums[i-1]+1){set.add(nums[i]);}}List<Integer> result = new ArrayList<>(set);for(int number : set){result.add(number);}return result;// int [] result = new int[set.size()];// int index = 0;// for (int j : set) {// result[index++] = j;// }// return result;}
}答案
class Solution {public List<Integer> findDisappearedNumbers(int[] nums) {/*原地哈希：当看见数字范围为[1,n]恰好为等于数组索引长度时候，可以利用原数组压缩空间开销常规做法是设置一个数目容器，然后找出出现个数为0的但是这里可以利用原来数组作为数字容器，没枚举一共数字就将对应位置的数字变为对应的负数最后找出所有还是正数的数字的位置就是答案这样既能保留了原来的信息又可以进行标记时间复杂度：O(N) 空间复杂度：O(1)*/List<Integer> res = new ArrayList<>();int n = nums.length;for (int num : nums) {// 对应的索引int abs = Math.abs(num) - 1;nums[abs] = -Math.abs(nums[abs]);}for (int i = 0; i < n; i++) {if (nums[i] > 0) res.add(i + 1);}return res;}
}class Solution {public List<Integer> findDisappearedNumbers(int[] nums) {List<Integer> res = new ArrayList<>();int i = 0;while (i < nums.length) {if (nums[i] == i + 1) {i++;continue;}int idealIdx = nums[i] - 1;if (nums[i] == nums[idealIdx]) {i++;continue;}int tmp = nums[i];nums[i] = nums[idealIdx];nums[idealIdx] = tmp;}for (int j = 0; j < nums.length; j++) {if (nums[j] != j + 1) {res.add(j + 1);}}return res;}
}答案的两种思维都需要好好学习一下
题目(未完成)455：分发饼干
class Solution {public int findContentChildren(int[] g, int[] s) {int i = 0;int j = 0;int count = 0;Arrays.sort(g);Arrays.sort(s);if(s.length == 0 || g[0]>s[0]){return count;}else{while(i<g.length){if(g[i]<=s[j]){count++;i++;j++;}else{j++;if(j==s.length){break;}}}}return count;}
}答案
class Solution {public int findContentChildren(int[] g, int[] s) {int cookie = 0;int child = 0;Arrays.sort(g);Arrays.sort(s);while(cookie < s.length && child < g.length){if(s[cookie] >= g[child]){child++;}cookie++;}return child;}
}思路是正确的，怎么写的就乱七八糟的，和老太太的臭裹脚布一样！！！！
10/27 已经完成80%了
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);// if(s[0] < g[0]) return 0;int i = 0;int j = 0;int res = 0;while(i < g.length){for(int k = j;k < s.length;k++){if(i < g.length && s[k] >= g[i]){ j++;res++;break;}}i++;}return res;}
}2023/4/17
题目(完成)463:岛屿的周长
自己的思路
class Solution {public int islandPerimeter(int[][] grid) {int Perimeter = 0;int times = 0;int redundant = 0;int result = 0;for(int i = 0;i<grid.length;i++){for(int j = 0;j<grid[i].length;j++){if(grid[i][j]==1){times++;if(i>=1&&grid[i-1][j]==grid[i][j]){redundant++;}if(j>=1&&grid[i][j-1]==grid[i][j]){redundant++;}}}}result = times * 4 - redundant *2;return result;}
}题目(已完成)485:最大连续1的个数
class Solution {public int findMaxConsecutiveOnes(int[] nums) {int begin = 0;int times = 0;int temporary = 0;//还是卡在边界问题上了while(begin < nums.length){if(nums[begin]==1){begin++;times++;if(begin == nums.length){temporary = Math.max(temporary,times);break;}}else{temporary = Math.max(temporary,times);times=0;begin++;} }return temporary;}
}2023/4/18
题目(未完成)495:提莫攻击
class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int times = 0;int i = 0;while(i < timeSeries.length){if(i+1==timeSeries.length){times+=duration;break;}if(timeSeries[i]+duration-1 == timeSeries[i+1]){times+=(duration/2);i++;}else{times+=duration;i++;}}return times;}
}
答案
class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int ans = 0;int expired = 0;for (int i = 0; i < timeSeries.length; ++i) {if (timeSeries[i] >= expired) {ans += duration;} else {//本次中毒增加的持续中毒时间ans += timeSeries[i] + duration - expired;}expired = timeSeries[i] + duration;}return ans;}
}
2023/4/19
题目(完成)628:三个数的最大乘积
class Solution {public int maximumProduct(int[] nums) {Arrays.sort(nums);int n = nums.length;int number1 = nums[n-1] * nums[n-2] * nums[n-3];int number2 = nums[0] * nums[1] *nums [n-1];return number1 > number2 ? number1:number2;}
}题目(未完成)645:错误的集合
class Solution {public int[] findErrorNums(int[] nums) {Arrays.sort(nums);int [] result = new int[2];int i = 1;int n = nums.length;while(i<nums.length){if(nums[i]!=nums[i-1]){i++;}else{break;}}if(nums[i] == i+1){result[0]=nums[i];if(nums[0]!=1){result[1]=1;}else if(nums[n-1]!=n){result[1]=n;}else{result[1]=nums[i]-1;}}if(nums[i] != i+1){result[0]=nums[i];if(nums[0]!=1){result[1]=1;}else if(nums[n-1]!=n){result[1]=n;}else{result[1]=nums[i]+1;}}return result;}
}答案
class Solution {public int[] findErrorNums(int[] nums) {int[] errorNums = new int[2];int n = nums.length;Arrays.sort(nums);int prev = 0;for (int i = 0; i < n; i++) {int curr = nums[i];if (curr == prev) {errorNums[0] = prev;} else if (curr - prev > 1) {errorNums[1] = prev + 1;}prev = curr;}if (nums[n - 1] != n) {errorNums[1] = n;}return errorNums;}
}class Solution {public int[] findErrorNums(int[] nums) {int[] errorNums = new int[2];int n = nums.length;Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}for (int i = 1; i <= n; i++) {int count = map.getOrDefault(i, 0);if (count == 2) {errorNums[0] = i;} else if (count == 0) {errorNums[1] = i;}}return errorNums;}
}2023/4/20
题目(未完成)697：数组的度
class Solution {public int findShortestSubArray(int[] nums) {Map<Integer,Integer> map = new HashMap<Integer,Integer>();//将元素都放入哈希表中统计每个数字出现的个数for(int num:nums){map.put(num,map.getOrDefault(num,0) + 1);}//找到度的大小int count = 0;for(int num:nums){count = Math.max(count,map.getOrDefault(num,0));}HashSet<}
}答案
class Solution {public int findShortestSubArray(int[] nums) {Map<Integer, int[]> map = new HashMap<Integer, int[]>();int n = nums.length;for (int i = 0; i < n; i++) {if (map.containsKey(nums[i])) {map.get(nums[i])[0]++;map.get(nums[i])[2] = i;} else {map.put(nums[i], new int[]{1, i, i});}}int maxNum = 0, minLen = 0;for (Map.Entry<Integer, int[]> entry : map.entrySet()) {int[] arr = entry.getValue();if (maxNum < arr[0]) {maxNum = arr[0];minLen = arr[2] - arr[1] + 1;} else if (maxNum == arr[0]) {if (minLen > arr[2] - arr[1] + 1) {minLen = arr[2] - arr[1] + 1;}}}return minLen;}
}哈希表的映射不一定是映射一个值，还可以是一个数组
Map<Integer,int[]> map = new HashMap<Integer, int[]>();
哈希表的定义方式中，Integer是key的数据类型，int[]是value的数据类型
题目(完成)442：数组中重复的数据
//解法一 我的解答
class Solution {public List<Integer> findDuplicates(int[] nums) {List<Integer> res = new ArrayList<Integer>();Arrays.sort(nums);if(nums.length == 1){return res;}else{for(int i = 1;i<nums.length;i++){if(nums[i]==nums[i-1]){res.add(nums[i]);}}}return res;}
}//解法二 答案
class Solution {public List<Integer> findDuplicates(int[] nums) {List<Integer> duplicates = new ArrayList<Integer>();int n = nums.length;for (int i = 0; i < n; i++) {int num = nums[i];int index = Math.abs(num) - 1;if (nums[index] > 0) {nums[index] = -nums[index];} else {duplicates.add(index + 1);}}return duplicates;}
}给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内
类似的题目已经出现第二次了，解题的思维也大同小异
题目(未完成)41：缺失的第一个正数
我的解答
class Solution {public int firstMissingPositive(int[] nums) {//先找最小正整数1在不在Arrays.sort(nums);int result = 1;int index = 0;// if(nums.length == 1 && nums[0] != 1){// return result;// }else{// return nums[0]+1;// }for(int i = 0;i < nums.length;i++){if(nums[i] > 0 && nums[i] != 1){return result;}else if(nums.length == 1 && nums[nums.length-1]<=0){return result;}else if(nums[i] > 0 && nums[i] == 1){index = i;break;}}//index是1的下标if(index == nums.length -1){result = 2;return result;}while(index < nums.length){if(index + 1 == nums.length || nums[index+1] != nums[index] + 1){result = nums[index] + 1;break;}else{index++;}}return result;}
}这个题目的解题思维也挺类似>>>>>>给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内
2023/4/21
题目(未完成)274：H指数
我的解答
class Solution {public int hIndex(int[] citations) {// Map<Integer,Integer> map = new HashMap<Integer,Integer>();// //将代表第几篇论文的索引值以及对应引用次数做成键值对送入哈希表// for(int i = 0;i<citations.length;i++){// map.put(i+1,citations[i]);// }int Threshold = 0;int result = 0;int i = 0;if(citations.length == 1 && citations[0]!=0){result = 1;return result;}if(citations.length == 1 && citations[0]==0){return result;}while(i<citations.length){while(i<citations.length){if(citations[i] > 0){Threshold = citations[i];break;}else{i++;}}int count = 0;for(int j = 0;j<citations.length;j++){if(citations[j] >= Threshold){count++;}}if(Threshold == count && citations.length - count <= Threshold){result = Math.max(result,Threshold);}i++;}if(result == 0){result = citations[0];for(int m = 0;m < citations.length;m++){result = Math.min(result,citations[m]);}}return result;}
}
--------------------------------------------------------------------------
答案
class Solution {public int hIndex(int[] citations) {Arrays.sort(citations);int h = 0, i = citations.length - 1; while (i >= 0 && citations[i] > h) {h++; i--;}return h;}
}class Solution {public int hIndex(int[] citations) {int n = citations.length;int left = 0;int right = n - 1;Arrays.sort(citations);while (left < right) {int mid = left + (right - left) / 2;if (citations[mid] < n - mid) {left = left + 1;} else {right = mid;}}return citations[left] == 0 ? 0 : n - left;}
}public class Solution {public int hIndex(int[] citations) {int len = citations.length;int left = 0;int right = len;while (left < right) {// 猜论文篇数int mid = (left + right + 1) / 2;// 满足高引用的特点是：引用次数 >= 论文篇数// count 的含义是：大于等于 mid 的论文篇数int count = 0;for (int citation : citations) {if (citation >= mid) {count++;}}if (count >= mid) {left = mid;} else {right = mid - 1;}}return left;}
}二分查找没理解好
题目(未完成)453：最小操作次数使数组元素相等
求数组所有元素之和：Arrays.stream(arr1).sum();
求数组最大值/最小值：Arrays.stream(arr1).max.getAsInt();
Arrays.stream(arr1).min().getAsInt()
复制一个数组：int [] temparr = new int[n];
int [] resArr = Arrays.copyOf(temparr,temparr.length);
(101条消息) Arrays.stream()常用方法_now()的博客-CSDN博客
题目(完成)665：非递减数列
class Solution {public boolean checkPossibility(int[] nums) {// int i = 1;// int count = 0;// int index = 0;// while(i<nums.length){// if(nums[i]<nums[i-1]){// count++;// index = i;// // if(i+1<nums.length && Math.abs(nums[i]-nums[i-1])>Math.abs(nums[i]-nums[i+1])){// // return false;// // }// if(count > 1){// return false;// }// }// i++;// }// return true;int i = 1;int count1 = 0;int count2 = 0;// int index = 0;int variable = 0;while(i<nums.length){if(nums[i]<nums[i-1]){variable = nums[i];nums[i]=nums[i-1];for(int j = 1;j < nums.length;j++){if(nums[j]<nums[j-1]){count1++;}}nums[i]=variable;nums[i-1]=variable;for(int k = 1;k < nums.length;k++){if(nums[k]<nums[k-1]){count2++;}}if(count1 > 0 && count2 >0){return false;}// count++;// index = i;// if(count > 1){// return false;// }}i++;}return true;}
}答案
class Solution {
public:bool checkPossibility(vector<int> &nums) {int n = nums.size();for (int i = 0; i < n - 1; ++i) {int x = nums[i], y = nums[i + 1];if (x > y) {nums[i] = y;if (is_sorted(nums.begin(), nums.end())) {return true;}nums[i] = x; // 复原nums[i + 1] = x;return is_sorted(nums.begin(), nums.end());}}return true;}
};
答案和我的思路差不多，但是答案用了is_sorted函数(判断是否有序)，代码更简洁一些。
(101条消息) is_sorted() 函数---一个判断数组和容器是否有序的函数_辉小歌的博客-CSDN博客
2023/4/23
题目(已完成)118.杨辉三角1
class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<List<Integer>>();for(int i = 0;i < numRows; i++){List<Integer> row = new ArrayList<Integer>();for(int j = 0; j<=i; j++){if(i == j || j == 0){row.add(1);}else{row.add(ret.get(i - 1).get(j - 1) + ret.get(i-1).get(j));}}ret.add(row);}return ret;}
}二维List：(102条消息) 二维list的使用（java）_java 二维list_-Will-浩的博客-CSDN博客
ret.get(rowIndex);
题目(已完成)119.杨辉三角2
class Solution {public List<Integer> getRow(int rowIndex) {List<List<Integer>> ret = new ArrayList<List<Integer>>();// List <Integer> res = new ArrayList<Integer>();for(int i = 0;i < rowIndex + 1; i++){List<Integer> row = new ArrayList<Integer>();for(int j = 0; j<=i; j++){if(i == j || j == 0){row.add(1);}else{row.add(ret.get(i - 1).get(j - 1) + ret.get(i-1).get(j));}// if(i == rowIndex){// if(i == j || j == 0){// res.add(1);// }else{// res.add(ret.get(i - 1).get(j - 1) + ret.get(i-1).get(j));// }// }}ret.add(row);}return ret.get(rowIndex);}
}class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> row = new ArrayList<Integer>();row.add(1);for (int i = 1; i <= rowIndex; ++i) {row.add(0);for (int j = i; j > 0; --j) {row.set(j, row.get(j) + row.get(j - 1));}}return row;}
}2023/4/24
题目(未完成)661：图片平滑器--------------------------------------------------------------------------------第37题
//答案
class Solution {public int[][] imageSmoother(int[][] img) {int m = img.length, n = img[0].length;int[][] ret = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int num = 0, sum = 0;for (int x = i - 1; x <= i + 1; x++) {for (int y = j - 1; y <= j + 1; y++) {if (x >= 0 && x < m && y >= 0 && y < n) {num++;sum += img[x][y];}}}ret[i][j] = sum / num;}}return ret;}
}思维很简单，自己一开始想补一圈0，太复杂了，重新做的时候好好想一想，其实是可以想出来的
题目(完成一半)598：范围求和2
class Solution {public int maxCount(int m, int n, int[][] ops) {for(int[]op : ops){m = Math.min(m,op[0]);n = Math.min(n,op[1]);}return m*n;}
}傻逼题目看都看不懂
题目(完成一半)419：甲板上的战舰
自己做的，有瑕疵
class Solution {public int countBattleships(char[][] board) {int count = 0;int extra = 0;int x = 0;int y = 0;for(int i = 0;i < board.length;i++){for(int j = 0;j < board[i].length;j++){if(board[i][j] == 'X'){count++;if(x == i && Math.abs(j - y) == 1){extra++;}else if(y == j && Math.abs(x - i) == 1){extra++; }x = i;y = j;}}}return count - extra;}
}
自己做的改进一下了，通过了
class Solution {public int countBattleships(char[][] board) {int count = 0;int extra = 0;for(int i = 0;i < board.length;i++){for(int j = 0;j < board[i].length;j++){if(board[i][j] == 'X'){count++;if(i > 0 && board[i-1][j] == 'X'){extra++;}else if(j>0 &&board[i][j-1] == 'X'){extra++; }}}}return count - extra;}
}
答案
class Solution {public int countBattleships(char[][] board) {int count = 0;for(int i = 0;i<board.length;i++){for(int j =0;j<board[i].length;j++){if(board[i][j] == 'X'){if(i > 0 && board[i-1][j] == 'X'){//查找上一个是不是Xcontinue;//强制进入下一次循环}else if(j>0 &&board[i][j-1] == 'X'){//查找左边一个是不是Xcontinue;}else{count++;}}}}return count;}
}其实也不是做不出来，思维其实很像了，但是还是差一点
2023/4/25
题目(完成一半)189：轮转数组
//我的解答
class Solution {public void rotate(int[] nums, int k) {//k是几就循环几次 只把最后一位提出来，整体后移//超出时间限制// for(int i = 0;i < k; i++){// int target = nums[nums.length - 1];// for(int j = nums.length - 1;j > 0;j--){// nums[j] = nums[j - 1];// }// nums[0] = target;// }//arraycopyif(nums.length > 1){k %= nums.length;//关键int[] res = Arrays.copyOfRange(nums,nums.length - k,nums.length);System.arraycopy(nums,0,nums,k,nums.length-k);System.arraycopy(res,0,nums,0,k);}}
}
//答案
class Solution {public void rotate(int[] nums, int k) {k %= nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}public void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start += 1;end -= 1;}}
}Java复制（拷贝）数组的4种方法：arraycopy()方法、clone() 方法、copyOf()和copyOfRan (biancheng)
2023/4/27
题目(完成一半)396：旋转函数
我的解答
class Solution {public int maxRotateFunction(int[] nums) {int res = 0;for(int i = 0;i < nums.length;i++){int target = nums[nums.length - 1];for(int j = nums.length - 1;j > 0;j--){nums[j] = nums[j - 1];}nums[0] = target;int temp = 0;for(int k = 0;k < nums.length;k++){temp +=k*nums[k];}res = Math.max(res,temp);}return res;}
}题目(未完成)54：螺旋矩阵
class Solution {public List<Integer> spiralOrder(int[][] matrix) {//仿照答案写的List<Integer> res = new ArrayList<Integer>();int top = 0;int bottom = matrix.length - 1;int left = 0;int right = matrix[0].length - 1;int count = matrix.length * matrix[0].length;while(count >= 1){for(int i = left;i <= right && count >= 1;i++){res.add(matrix[top][i]);count--;}top++;for(int i = top;i <= bottom && count >= 1;i++){res.add(matrix[i][right]);count--;}right--;for(int i = right;i >= left && count >= 1;i--){res.add(matrix[bottom][i]);count--;}bottom--;for(int i = bottom;i >= top && count >= 1;i--){res.add(matrix[i][left]);count--;}left++;}return res;//答案LinkedList<Integer> result = new LinkedList<>();if(matrix==null||matrix.length==0) return result;int left = 0;int right = matrix[0].length - 1;int top = 0;int bottom = matrix.length - 1;int numEle = matrix.length * matrix[0].length;while (numEle >= 1) {for (int i = left; i <= right && numEle >= 1; i++) {result.add(matrix[top][i]);numEle--;}top++;for (int i = top; i <= bottom && numEle >= 1; i++) {result.add(matrix[i][right]);numEle--;}right--;for (int i = right; i >= left && numEle >= 1; i--) {result.add(matrix[bottom][i]);numEle--;}bottom--;for (int i = bottom; i >= top && numEle >= 1; i--) {result.add(matrix[i][left]);numEle--;}left++;}return result;}
}2023/4/28
题目(完成一半，因为思路和昨天的一个题完全一样)59：螺旋矩阵2
我的解答
class Solution {public int[][] generateMatrix(int n) {// int m = (int)Math.sqrt(n);int[][] res = new int[n][n];int top = 0;int bottom = res.length - 1;int left = 0;int right = res[0].length - 1;int count = 1;int numSum = n*n;while(count <= numSum){for(int i = left;i <= right;i++){res[top][i] = count;count++;}top++;for(int i = top;i <= bottom;i++){res[i][right] = count;count++;}right--;for(int i = right;i >= left;i--){res[bottom][i] = count;count++;}bottom--;for(int i = bottom;i >= top;i--){res[i][left] = count;count++;}left++;}return res;}
}答案
class Solution {public int[][] generateMatrix(int n) {int l = 0, r = n - 1, t = 0, b = n - 1;int[][] mat = new int[n][n];int num = 1, tar = n * n;while(num <= tar){for(int i = l; i <= r; i++) mat[t][i] = num++; // left to right.t++;for(int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.r--;for(int i = r; i >= l; i--) mat[b][i] = num++; // right to left.b--;for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.l++;}return mat;}
}题目(未完成)498：对角线的遍历
我的解答 思路想错了
class Solution {public int[] findDiagonalOrder(int[][] mat) {//两个循环 一个从左下到右上，一个从右上到左下// int numSum = mat.length * mat[0].length;// int[] res = new int[numSum];// int count = 0;// int first = 0;// int second = 0;// while(count <= numSum){// //第一个循环，从左下到右上// res[count] = mat[first][second];// count++;// while(first - 1 >= 0 && second + 1 <= mat[0].length - 1){// res[count] = mat[first - 1][second + 1];// count++;// first--;// second++;// }// second++;// res[count] = mat[first][second];// count++;// while(first + 1 <= mat.length - 1 && second - 1 >= 0){// res[count] = mat[first + 1][second - 1];// count++;// first++;// second--;// }// first++;// }// return res;int top = 0;int bottom = mat.length - 1;int left = 0;int right = mat[0].length - 1;int numSum = mat.length * mat[0].length;int[] res = new int[numSum];int count = 0;for(int i = left;i <= right;i++){res[count] = mat[top][i];count++;int first = top;int second = i;while(first + 1 <= bottom && 0 <= second - 1){res[count] = mat[first + 1][second - 1];first++;second--;count++;}}top++;for(int i = top;i <= bottom;i++){res[count] = mat[i][right];int first = top;int second = i;while(first + 1 <= bottom && 0 <= second - 1){res[count] = mat[first + 1][second - 1];first++;second--;if(second != bottom){count++;}}}return res;}
}2023/4/30
题目(完成)566：重塑矩阵
class Solution {public int[][] matrixReshape(int[][] mat, int r, int c) {if(r * c != mat.length * mat[0].length){return mat;}int left = 0;int right = 0;int[][] res = new int[r][c];for(int i = 0;i < mat.length;i++){for(int j = 0;j <mat[0].length;j++){res[left][right] = mat[i][j];right++;if(right == res[0].length){if(left < res.length){left++;right = 0;}}}}return res;}
}官方解答中的坐标映射似懂非懂
2023/4/30
题目(未完成) 48：旋转图像
只是看懂了答案，但是掌握的很不牢固
2023/5/1
题目(完成一半)73：矩阵置零
我的解答
class Solution {public void setZeroes(int[][] matrix) {for(int i = 0;i<matrix.length;i++){for(int j = 0;j<matrix[i].length;j++){if(matrix[i][j] == 0){for(int k = 0;k < matrix[i].length;k++){if(matrix[i][k] != 0){matrix[i][k] = -100;}}for(int q = 0;q < matrix.length;q++){if(matrix[q][j] != 0){matrix[q][j] = -100;}}}}}for(int i = 0;i<matrix.length;i++){for(int j = 0;j<matrix[i].length;j++){if(matrix[i][j] == -100){matrix[i][j] = 0;}}}}
}答案
class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length, n = matrix[0].length;boolean flagCol0 = false, flagRow0 = false;for (int i = 0; i < m; i++) {if (matrix[i][0] == 0) {flagCol0 = true;}}for (int j = 0; j < n; j++) {if (matrix[0][j] == 0) {flagRow0 = true;}}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][j] == 0) {matrix[i][0] = matrix[0][j] = 0;}}}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}}if (flagCol0) {for (int i = 0; i < m; i++) {matrix[i][0] = 0;}}if (flagRow0) {for (int j = 0; j < n; j++) {matrix[0][j] = 0;}}}
}按照我的思路 百分之99的用例可以通过，但是总有百分之1的特殊情况通过不了
答案的复杂度分析
2023/5/6
题目(完成)289：生命游戏
class Solution {public void gameOfLife(int[][] board) {int[][] res = new int[board.length][board[0].length];for(int i = 0;i < board.length;i++){for(int j = 0;j < board[0].length;j++){int count = 0;//统计活细胞的个数if(j - 1 >= 0){if(board[i][j-1] == 1){count++;}if(i - 1 >= 0 && board[i-1][j-1] == 1){count++;}if(i + 1 < board.length && board[i+1][j-1] == 1){count++;}}if(i - 1 >= 0 && board[i-1][j] == 1){count++;}if(i + 1 < board.length && board[i+1][j] == 1){count++;}if(j + 1 < board[0].length){if(board[i][j+1] == 1){count++;}if(i - 1 >= 0 && board[i-1][j+1] == 1){count++;}if(i + 1 < board.length && board[i+1][j+1] == 1){count++;}}if(board[i][j] == 1){if(count < 2 || 3 < count){res[i][j] = 0;}else{res[i][j] = 1;}}if(board[i][j] == 0){if(count == 3){res[i][j] = 1;}else{res[i][j] = 0;}}}}for(int i = 0;i < board.length;i++){for(int j = 0;j < board[0].length;j++){board[i][j] = res[i][j];}}}
}题目(完成)238：除自己以外数组的乘积
和官方的思路不一样
class Solution {public int[] productExceptSelf(int[] nums) {//时间复杂度O(n) 不能使用嵌套循环int[] res = new int[nums.length];int count = 0;int temp = 1;for(int i = 0;i < nums.length;i++){if(nums[i] != 0){temp = temp * nums[i]; }else{count++;}}for(int i = 0;i < res.length;i++){if(count >= 2){res[i] = 0;}else if(count == 1){if(nums[i] == 0){res[i] = temp;}else{res[i] = 0;}}else{res[i] = temp/nums[i];}}return res;}
}题目(未完成)304：二位区域检索-矩阵不可变
第二种解法更重要
2023/5/7——字符串专题
题目(完成)520：检测大写字母
class Solution {public boolean detectCapitalUse(String word) {boolean res = true;int count = 0;for(int i = 0;i < word.length();i++){char str = word.charAt(i);if(Character.isUpperCase(str)){count++;}}if(count == word.length() || count == 0){res = true;}else if(count == 1 && word.length() > 1){char temp = word.charAt(0);if(Character.isUpperCase(temp)){res = true;}else{res = false;}}else{res = false;}return res;}
}宫水三叶
class Solution {public boolean detectCapitalUse(String word) {if (word.toUpperCase().equals(word)) return true;if (word.toLowerCase().equals(word)) return true;int n = word.length(), idx = 1;if (Character.isUpperCase(word.charAt(0))) {while (idx < n && Character.isLowerCase(word.charAt(idx))) idx++;}return idx == n;}
}(111条消息) JAVA逻辑运算符示例详解：与、或、非、异或_java中或者_火石桥霍建华的博客-CSDN博客
.toUpperCase().equals() 先变成大写再比较
.equalsIgnoreCase() 忽略大小写
2023/5/7
题目(完成)125：验证回文串
class Solution {public boolean isPalindrome(String s) {// boolean res = true;if(s.length() == 1){return true;}StringBuilder sb_1 = new StringBuilder();StringBuilder sb_2 = new StringBuilder();// s = Character.toLowerCase(s);for(int i = s.length() - 1;i >= 0;i--){char temp_1 = Character.toLowerCase(s.charAt(i));if(temp_1 >= 'a' && temp_1 <= 'z'){sb_1.append(temp_1);}if(temp_1 >= '0' && temp_1 <= '9'){sb_1.append(temp_1);}}for(int i = 0;i < s.length();i++){char temp_2 = Character.toLowerCase(s.charAt(i));if(temp_2 >= 'a' && temp_2 <= 'z'){sb_2.append(temp_2);}if(temp_2 >= '0' && temp_2 <= '9'){sb_2.append(temp_2);}}//return sb_1 == sb_2;return sb_1.toString().equals(sb_2.toString());}
}StringBuilder比较是否相等：sb_1.toString().equals(sb_2.toString())；
答案
class Solution {public boolean isPalindrome(String s) {StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}StringBuffer sgood_rev = new StringBuffer(sgood).reverse();return sgood.toString().equals(sgood_rev.toString());}
}.isLetterOrDigit()：判断是否是字母或数字；
.reverse()：反转字符串；
2023/5/8
题目(未完成)14：最长公共前缀
class Solution {public String longestCommonPrefix(String[] strs) {if(strs.length == 0){return "";}StringBuilder res = new StringBuilder();String temp = strs[0];//数组中的第一个单词；boolean test = true;int i = 0;while(test){char temp_1 = temp.charAt(i); //取出来了ffor(int j = 1;j < strs.length;j++){char temp_2 = strs[j].charAt(i);if(temp_1 != temp_2){test = false;}}if(test){res.append(temp_1);}i++;//这里存在隐患}return res.toString();}
}答案
class Solution {public String longestCommonPrefix(String[] strs) {if(strs.length == 0) //特殊情况1return "";String ans = strs[0];for(int i =1;i < strs.length;i++) {int j=0;for(;j<ans.length() && j < strs[i].length();j++) {if(ans.charAt(j) != strs[i].charAt(j))break;}ans = ans.substring(0, j);if(ans.equals("")) //特殊情况2return ans;}return ans;}
}
注意处理特殊情况
String[] strs = {} strs.length() = 0;
String[] strs = {""} strs.length() = 1;
题目(未完成)434：字符串中的单词数
我写的
class Solution {public int countSegments(String s) {int i = 0;int count = 0;while(i < s.length()){if(Character.isLetter(s.charAt(i))){i++;if(i == s.length() && count == 0){count++;break;}}else{count++;i++;}}return count;}
}
答案
class Solution {public int countSegments(String s) {int n = s.length();int ans = 0;for (int i = 0; i < n; ) {if (s.charAt(i) == ' ' && i++ >= 0) continue;while (i < n && s.charAt(i) != ' ') i++;ans++;}return ans;}
}
感觉答案写成这样更好理解一点
class Solution {public int countSegments(String s) {int n = s.length();int ans = 0;for (int i = 0; i < n; ) {if (s.charAt(i) == ' '){i++;// System.out.println(i);continue;}while (i < n && s.charAt(i) != ' ') i++;ans++;}return ans;}
}
continue只是跳过continue所在循环体中continue后的语句
2023/5/9
题目(完成)58：最后一个单词的长度
class Solution {public int lengthOfLastWord(String s) {int count = 0;int i = s.length() - 1;while(s.charAt(i) == ' ' && i >= 0) i--;while(s.charAt(i) != ' ' && i >= 0){i--;if(i < 0){count++;break;}count++;}return count;}
}题目(完成)344：反转字符串
//解法1
class Solution {public void reverseString(char[] s) {StringBuilder res = new StringBuilder();for(int i = 0;i < s.length;i++){res.append(s[i]);}String res_1 = res.reverse().toString();for(int i = 0;i < res_1.length();i++){char c = res_1.charAt(i);s[i] = c;}}
}//解法2
class Solution {public void reverseString(char[] s) {int left = 0;int right = s.length - 1;while(left <= right){char c = s[left];s[left] = s[right];s[right] = c;left++;right--;}}
}题目(未完成)541：反转字符串2 写的又臭又长
我写的
class Solution {public String reverseStr(String s, int k) {// String res = "";// if(s.length() - 2*k < k){// res = s.reverse();// return res;// }// if(s.length() - 2*k >= k && s.length() - 2*k < 2k){// }int i = 0;StringBuilder res = new StringBuilder();if(s.length() < 2*k && s.length() >= k){res.append(s.substring(0,k)).reverse();res.append(s.substring(k,s.length()));return res.toString();}// StringBuilder temp = new StringBuilder();while(i < s.length()){if(s.length() - (i + 2*k) >= 2*k){res.append(s.substring(i,i + k)).reverse();res.append(s.substring(i + k,i + 2*k));i = i + 2*k;}else if(s.length() - (i + 2*k) < k){StringBuilder temp = new StringBuilder();res.append(s.substring(i,i + k)).reverse();res.append(s.substring(i + k,i + 2*k));temp.append(s.substring(i + 2*k,s.length())).reverse();res.append(temp.toString());break;}else{StringBuilder temp = new StringBuilder();res.append(s.substring(i,i + k)).reverse();res.append(s.substring(i + k,i + 2*k));temp.append(s.substring(i + 2*k,i + 2*k + k)).reverse();res.append(temp.toString());res.append(s.substring(i + 2*k + k,s.length()));break;}}return res.toString();}
}
答案
class Solution {public String reverseStr(String s, int k) {int n = s.length();char[] arr = s.toCharArray();for (int i = 0; i < n; i += 2 * k) {reverse(arr, i, Math.min(i + k, n) - 1);}return new String(arr);}public void reverse(char[] arr, int left, int right) {while (left < right) {char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}
}(116条消息) toCharArray()_java tochararray()_Technology9997的博客-CSDN博客
2023/5/10
题目(完成)151：反转字符串中的单词 循环条件是有先后顺序的
class Solution {public String reverseWords(String s) {StringBuilder res = new StringBuilder();int index = s.length() - 1;int left = 0;int right = 0;while(index >= 0 && left <= right){while(index >= 0 &&s.charAt(index) == ' '){index--;}right = index + 1;while(index >= 0 && s.charAt(index) != ' '){//这个循环条件有先后条件index--;}left = index + 1;if(right != left){res.append(s.substring(left,right));res.append(' ');}}res.deleteCharAt(res.length() - 1);//起作用了return res.toString();}
}.deleteCharAt()：删除某个位置的字符
题目(完成)557：反转字符串中的单词3
//有点像原地修改
class Solution {public String reverseWords(String s) {int index = 0;int left = 0;int right = 0;char[] res = s.toCharArray();while(index < s.length()){while(s.charAt(index) == ' ')index++;left = index;while(index < s.length() && s.charAt(index) != ' ')index++;right = index - 1;reverse(res,left,right);}// String res_test = new String(res);return new String(res);}public void reverse(char[] res,int left,int right){while(left <= right){char c = res[left];res[left] = res[right];res[right]= c;left++;right--; }}
}//第二种
class Solution {public String reverseWords(String s) {StringBuilder res = new StringBuilder();int index = 0;int begin = 0;int end = 0;while(index < s.length()){while(index < s.length() && s.charAt(index) == ' ')index++;end = index;while(index < s.length() && s.charAt(index) != ' ')index++;begin = index - 1;for(int i = begin;i >= end;i--){res.append(s.charAt(i));}res.append(' ');}res.deleteCharAt(res.length() - 1);return res.toString();}
}char类型数组和String相互转化
(116条消息) Java char[]数组转成String类型（char to String）详细介绍_java char数组转string_Smile sea breeze的博客-CSDN博客
题目(已完成，但是是用笨办法完成的)387：字符串中的第一个唯一的字符
我写的
class Solution {public int firstUniqChar(String s) {// int res = 0;int symbol = 0;for(int i = 0;i < s.length();i++){char temp = s.charAt(i);int j = 0;while(j < s.length()){if(temp == s.charAt(j) && i != j){break;}else{j++;if(j == s.length()){return i;}}}}return -1;}
}
答案
class Solution {public int firstUniqChar(String s) {int index = -1;int res = s.length();for(char ch = 'a'; ch<= 'z';ch++){index = s.indexOf(ch);//这个字符在字符串中第一次出现的位置 如果找不到 index = -1if(index != -1 && index == s.lastIndexOf(ch)){//这个字符在字符串中能找到 且第一次出现的位置和最后一次出现的位置相同res = Math.min(res,index);//找到第一个不重复的字符}}return res > s.length() - 1 ? -1 : res;}
}
哈希表1
class Solution {public int firstUniqChar(String s) {Map<Character,Integer> frequency = new HashMap<Character,Integer>();for(int i = 0;i < s.length();i++){char ch = s.charAt(i);frequency.put(ch,frequency.getOrDefault(ch,0) + 1);}for(int i = 0;i < s.length();i++){if(frequency.get(s.charAt(i)) == 1){return i;}}return -1;}
}
哈希表2
class Solution {public int firstUniqChar(String s) {Map<Character,Integer> position = new HashMap<Character,Integer>();int n = s.length();for(int i = 0;i < n;i++){char ch = s.charAt(i);if(position.containsKey(ch)){position.put(ch,-1);//覆盖}else{position.put(ch,i);}}int first = n;for(Map.Entry<Character,Integer> entry :position.entrySet()){//固定格式int pos = entry.getValue();if(pos != -1 && pos <first){first = pos;}}if(first == n){first = -1;}return first;}
}indexOf()：指定字符第一次出现的位置 lastIndexof()：指定字符最后一次出现的位置
(116条消息) Java中indexOf() 方法 总计及其日常使用_你若不离不弃，我必生死相依的博客-CSDN博客
HashSet 不允许集合中出现重复的值。HashSet 底层其实就是 HashMap，所有对 HashSet 的操作其实就是对 HashMap 的操作。所以 HashSet 也不保证集合的顺序。
HashMap不保证插入顺序，但是循环遍历时，输出顺序是不会改变的。
2023/5/11
题目(完成)389：找不同 答案的ASCII和位运算很简便
class Solution {public char findTheDifference(String s, String t) {if(s.length() == 0){return t.charAt(0);}Map<Character,Integer> res = new HashMap<Character,Integer>();char res_ch = ' ';for(int i = 0;i < s.length();i++){char ch = s.charAt(i);res.put(ch,res.getOrDefault(ch,0) + 1);}for(int j = 0;j < t.length();j++){char temp = t.charAt(j);if(!res.containsKey(temp)){res_ch = temp;break;}else{res.put(temp,res.get(temp) - 1);if(res.get(temp) == -1){res_ch = temp;break;}}}return res_ch;}
}题目(完成)383：赎金信
class Solution {public boolean canConstruct(String ransomNote, String magazine) {Map<Character,Integer> res = new HashMap<Character,Integer>();// char res_ch = ' ';for(int i = 0;i < magazine.length();i++){char ch = magazine.charAt(i);res.put(ch,res.getOrDefault(ch,0) + 1);}for(int j = 0;j < ransomNote.length();j++){char temp = ransomNote.charAt(j);if(!res.containsKey(temp)){return false;}else{res.put(temp,res.get(temp) - 1);if(res.get(temp) == -1){return false;}}}return true;}
}题目(完成)242：有效的字母异位词
我写的
class Solution {public boolean isAnagram(String s, String t) {if(s.length() != t.length()) return false;Map<Character,Integer> res = new HashMap<Character,Integer>();// char res_ch = ' ';for(int i = 0;i < s.length();i++){char ch = s.charAt(i);res.put(ch,res.getOrDefault(ch,0) + 1);}for(int j = 0;j < t.length();j++){char temp = t.charAt(j);if(!res.containsKey(temp)){return false;}else{res.put(temp,res.get(temp) - 1);if(res.get(temp) == -1){return false;}}}return true;}
}
答案
class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}char[] str1 = s.toCharArray();char[] str2 = t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);}
}将字符串转换成字符数组，再排序
2023/5/12
题目(未完成)49：字母异位词分组
class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMao<String, List<String>>();for(String str : strs){char[] array = str.toCharArray();Arrays.sort(array);String key = new String(array);List<String> list = map.getOrDefault(key,new ArrayList<Sting>());list.add(str);map.put(key,list);}return new ArrayList<List<Sting>>(map.values());}
}List<String> list = new ArrayList<String>();
List<String> list = map.getOrDefault(key,new ArrayList<String>());
题目(完成)451：根据字符出现频率排序
class Solution {public String frequencySort(String s) {Map<Character,Integer> res = new HashMap<Character,Integer>();for(int i = 0;i < s.length();i++){char ch = s.charAt(i);res.put(ch,res.getOrDefault(ch,0) + 1);}StringBuilder res_ch = new StringBuilder();char char_max = ' '; int char_max_times = 0;int count = s.length();while(count > 0){for(Map.Entry<Character,Integer> entry :res.entrySet()){char target = entry.getKey();int target_times = entry.getValue();if(target_times >= char_max_times){char_max = target;char_max_times = target_times;}}for(int i = 0;i < char_max_times;i++){res_ch.append(char_max);count--;}res.remove(char_max);char_max_times = 0;}return res_ch.toString();}
}唯一好理解的一个答案
class Solution {public String frequencySort(String s) {Map<Character, Integer> map = new HashMap<Character, Integer>();int length = s.length();for (int i = 0; i < length; i++) {char c = s.charAt(i);int frequency = map.getOrDefault(c, 0) + 1;map.put(c, frequency);}List<Character> list = new ArrayList<Character>(map.keySet());Collections.sort(list, (a, b) -> map.get(b) - map.get(a));StringBuffer sb = new StringBuffer();int size = list.size();for (int i = 0; i < size; i++) {char c = list.get(i);int frequency = map.get(c);for (int j = 0; j < frequency; j++) {sb.append(c);}}return sb.toString();}
}map.keySet():
将哈希表中的键按照其对应值的大小排序：
2023/5/14
题目(完成一半)423：从英文中重建数字 我写的处理不了重复的情况
class Solution {public String originalDigits(String s) {StringBuilder res = new StringBuilder();String[] Candidate_area = {"zero","one","two","three","four","five","six","seven","eight","nine"};for(int i = 0;i < Candidate_area.length;i++){char[] array = Candidate_area[i].toCharArray(); // zero int count = 0;//array.length();//one 3int times = 0;while(times < s.length()){char ch = s.charAt(times);//array[count];if(array[count] != ch){times++;}if(array[count] == ch){count++;times = 0;if(count == array.length){res.append(i);break;}}// times++;}}return res.toString();}
}class Solution {static String[] ss = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};public String originalDigits(String s) {int n = s.length();int[] cnts = new int[26];//将'a'放在cnts数组的第0个位置，记录26个字母在s字符串中的出现顺序for (int i = 0; i < n; i++) cnts[s.charAt(i) - 'a']++;StringBuilder sb = new StringBuilder();for (int i : priority) {int k = Integer.MAX_VALUE;//z e r o 找到ss[i]中在s字符串中出现频率最小的次数for (char c : ss[i].toCharArray()) k = Math.min(k, cnts[c - 'a']);for (char c : ss[i].toCharArray()) cnts[c - 'a'] -= k;while (k-- > 0) sb.append(i);}char[] cs = sb.toString().toCharArray();Arrays.sort(cs);return String.valueOf(cs);}
}
说明：System.out.println(array);这样是不行的，这样打印是的是数组的首地址。
(117条消息) Java数组的三种打印方式_打印数组用百分号_chenkaibsw的博客-CSDN博客
char[] 和 String相互转化。
(117条消息) Java char[]数组转成String类型（char to String）详细介绍_java char数组转string_Smile sea breeze的博客-CSDN博客
被Static修饰的变量，其参数被该类所有的对象共享。
(117条消息) Java static关键字详解_Cappuccinooo的博客-CSDN博客
2023/5/16
题目(完成)657：机器人能否返回原点
class Solution {public boolean judgeCircle(String moves) {// int left = 0;// int right = 0;// int up = 0;// int down = 0;// for(int i = 0;i < moves.length();i++){// char ch = moves.charAt(i);// if(ch == 'U') up++;// if(ch == 'D') down++;// if(ch == 'L') left++;// if(ch == 'R') right++;// }// if(up - down == 0 & left - right == 0){// return true;// }// return false;int left_right = 0;// int right = 0;int up_down = 0;// int down = 0;for(int i = 0;i < moves.length();i++){char ch = moves.charAt(i);if(ch == 'U') up_down++;if(ch == 'D') up_down--;if(ch == 'L') left_right++;if(ch == 'R') left_right--;}if(up_down == 0 & left_right == 0){return true;}return false;}
}题目(未完成)696：计数二进制子串 没抓住问题的关键
我写的
class Solution {public int countBinarySubstrings(String s) {char[] res = s.toCharArray();int count = 0;int i = 1;int signal = 0;while(i < res.length){if(res[i] != res[i-1]){count++;i++;// if(signal > 0){// count++;// signal = 0;// }}else if(res[i] == res[i-1]){i++;signal++;if(signal == 2){count++;signal--;}}}return count;}
}
答案
class Solution {public int countBinarySubstrings(String s) {List<Integer> counts = new ArrayList<Integer>();int ptr = 0, n = s.length();while (ptr < n) {char c = s.charAt(ptr);int count = 0;while (ptr < n && s.charAt(ptr) == c) {++ptr;++count;}counts.add(count);}int ans = 0;for (int i = 1; i < counts.size(); ++i) {ans += Math.min(counts.get(i), counts.get(i - 1));}return ans;}
}
答案改进
class Solution {public int countBinarySubstrings(String s) {int ptr = 0, n = s.length(), last = 0, ans = 0;while (ptr < n) {char c = s.charAt(ptr);int count = 0;while (ptr < n && s.charAt(ptr) == c) {++ptr;++count;}ans += Math.min(count, last);last = count;}return ans;}
}
题目(完成)551：学生出勤记录1
class Solution {public boolean checkRecord(String s) {int i = 0;int Absent = 0;int Late = 0;int temp = 0;char[] res = s.toCharArray();while(i < res.length){if(res[i] == 'A'){Absent++;i++;}else if(res[i] == 'L'){Late = 0;while(i < s.length() && res[i] == 'L'){Late++;i++;}temp = Math.max(temp,Late);}else{i++;}}if(Absent < 2 && temp < 3){return true;}else{return false;}}
}2023/5/18
题目(未完成)467：环绕字符串中唯一的子字符串
这个题具体解析推导过程没理解，直接记高手答案
自己写的 垃圾
class Solution {public int findSubstringInWraproundString(String s) {//只有z能和a挨着if(s.length() == 1 && s == " "){return 0;}if(s.length() == 1 && s != " "){return 1;}if(s.length() == 0){return 0;}char[] res = s.toCharArray();int i = 1;int j = 1;int count = 1;while(j < res.length){while(res[i] - res[i-1] == -25 || res[i] - res[i-1] == 1){i++;count++;if(i == res.length) break;}count++;j++;i = j;}return count;}
}
高手
class Solution {public int findSubstringInWraproundString(String _p) {char[] cs = _p.toCharArray();int n = cs.length, ans = 0;int[] max = new int[26];max[cs[0] - 'a']++;for (int i = 1, j = 1; i < n; i++) {int c = cs[i] - 'a', p = cs[i - 1] - 'a';if ((p == 25 && c == 0) || p + 1 == c) j++;else j = 1;max[c] = Math.max(max[c], j);}for (int i = 0; i < 26; i++) ans += max[i];return ans;}
}答案涉及一个专业词汇：线性DP
2023/5/22
题目(未完成)299：猜数字游戏 解题思路和上面呢个题很像
我写的
class Solution {public String getHint(String secret, String guess) {StringBuilder sb = new StringBuilder();// Map<Character,Integer> map = new HashMap<Character,Integer>();Map<Character,Integer> count = new HashMap<Character,Integer>();for(int i = 0;i < secret.length();i++){char ch = secret.charAt(i);// map.put(ch,i);count.put(ch,count.getOrDefault(ch,0) + 1);}int Bulls = 0;int Cows = 0;for(int i = 0;i < guess.length();i++){char ch_secret = secret.charAt(i);char ch_guess = guess.charAt(i);if(ch_secret == ch_guess && count.get(ch_guess) > 0){Bulls++;count.put(ch_guess,count.get(ch_guess) - 1);}else{if(count.containsKey(ch_guess) && count.get(ch_guess) > 0){Cows++;count.put(ch_guess,count.get(ch_guess) - 1);}}}sb.append(Bulls);sb.append('A');sb.append(Cows);sb.append('B');return sb.toString();}
}
宫水三叶
class Solution {public String getHint(String secret, String guess) {int n = secret.length();int a = 0, b = 0;int[] cnt1 = new int[10], cnt2 = new int[10];for (int i = 0; i < n; i++) {int c1 = secret.charAt(i) - '0', c2= guess.charAt(i) - '0';if (c1 == c2) {a++;} else {cnt1[c1]++;cnt2[c2]++;}}for (int i = 0; i < 10; i++) b += Math.min(cnt1[i], cnt2[i]);return a + "A" + b + "B";}
}2023/5/29
题目(完成)412：Fizz Buzz
class Solution {public List<String> fizzBuzz(int n) {List<String> res = new ArrayList<String>();for(int i = 1;i <= n;i++){if(i % 3 == 0 && i % 5 == 0){res.add("FizzBuzz");}else if(i % 3 == 0){res.add("Fizz");}else if(i % 5 == 0){res.add("Buzz");}else{res.add(String.valueOf(i));}}return res;}
}
宫水三叶
class Solution {public List<String> fizzBuzz(int n) {List<String> ans = new ArrayList<>();for (int i = 1; i <= n; i++) {String cur = "";if (i % 3 == 0) cur += "Fizz";if (i % 5 == 0) cur += "Buzz";if (cur.length() == 0) cur = i + "";ans.add(cur);}return ans;}
}将整数型转换成字符串
(125条消息) Java –将整数转换为字符串_cyan20115的博客-CSDN博客
题目(完成)506：相对名次
class Solution {public String[] findRelativeRanks(int[] score) {String[] res = new String[score.length];int[] paixu = Arrays.copyOf(score,score.length);Arrays.sort(paixu);for(int i = 0;i < score.length;i++){int k = 0;for(int j = 0; j< paixu.length;j++){if(score[i] == paixu[j]){k = j;break;}}if(k == score.length - 1){res[i] = "Gold Medal";}else if(k == score.length - 2){res[i] = "Silver Medal";}else if(k == score.length - 3){res[i] = "Bronze Medal";}else{res[i] = score.length - k + "";// res[i] = String.valueOf(i + 1);}}return res;}
}
宫水三叶
class Solution {String[] ss = new String[]{"Gold Medal", "Silver Medal", "Bronze Medal"};public String[] findRelativeRanks(int[] score) {int n = score.length;String[] ans = new String[n];int[] clone = score.clone();Arrays.sort(clone);Map<Integer, Integer> map = new HashMap<>();for (int i = n - 1; i >= 0; i--) map.put(clone[i], n - 1 - i);for (int i = 0; i < n; i++) {int rank = map.get(score[i]);ans[i] = rank < 3 ? ss[rank] : String.valueOf(rank + 1);}return ans;}
}
克隆数组：
int[] score = {1,2,3};
int[] clone = score.clone();
2023/5/31
题目(完成一半)539：最小时间差 我自己的思路和答案第一种解法相同，就是写法不同
我写的
class Solution {public int findMinDifference(List<String> timePoints) {int[] res_res = new int[timePoints.size() * 2];int i = 0;for(String s : timePoints){char[] res = s.toCharArray();if(Integer.parseInt(String.valueOf(res[0])) == 0 && Integer.parseInt(String.valueOf(res[1])) == 0 && Integer.parseInt(String.valueOf(res[3])) == 0 && Integer.parseInt(String.valueOf(res[4])) == 0){res_res[i] = 23 * 60 + 60;res_res[i + timePoints.size()] = 0;}else if(Integer.parseInt(String.valueOf(res[0])) == 0 && Integer.parseInt(String.valueOf(res[1])) == 0){res_res[i] = 23 * 60 + (Integer.parseInt(String.valueOf(res[3])) *10 + Integer.parseInt(String.valueOf(res[4])));res_res[i + timePoints.size()] = (Integer.parseInt(String.valueOf(res[3])) *10 + Integer.parseInt(String.valueOf(res[4])));}else{res_res[i] = (Integer.parseInt(String.valueOf(res[0])) *10 + Integer.parseInt(String.valueOf(res[1]))) * 60 + (Integer.parseInt(String.valueOf(res[3])) *10 + Integer.parseInt(String.valueOf(res[4])));}i++;}Arrays.sort(res_res);int res_min = Integer.MAX_VALUE;for(int k = 1; k < res_res.length;k++){res_min = Math.min(res_min,Math.abs(res_res[k] - res_res[k-1]));}return res_min;}
}
宫水三叶
class Solution {public int findMinDifference(List<String> timePoints) {int n = timePoints.size() * 2;int[] nums = new int[n];for (int i = 0, idx = 0; i < n / 2; i++, idx += 2) {String[] ss = timePoints.get(i).split(":");int h = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);nums[idx] = h * 60 + m;nums[idx + 1] = nums[idx] + 1440;}Arrays.sort(nums);int ans = nums[1] - nums[0];for (int i = 0; i < n - 1; i++) ans = Math.min(ans, nums[i + 1] - nums[i]);return ans;}
}
宫水三叶
class Solution {public int findMinDifference(List<String> timePoints) {int n = timePoints.size();if (n > 1440) return 0;int[] cnts = new int[1440 * 2 + 10];for (String s : timePoints) {String[] ss = s.split(":");int h = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);cnts[h * 60 + m]++;cnts[h * 60 + m + 1440]++;}int ans = 1440, last = -1;for (int i = 0; i <= 1440 * 2 && ans != 0; i++) {if (cnts[i] == 0) continue;if (cnts[i] > 1) ans = 0;else if (last != -1) ans = Math.min(ans, i - last);last = i;}return ans;}
}int的最大值：Integer.MAX_VALUE
数字，字符，字符串相互转化：(126条消息) Java数字、字符、字符串互相转换_java数字转字符串_有时候我也会的博客-CSDN博客
Java获取List元素：String s：timePoints
获取字符串中的数字（分割）：String[] ss = timePoints.get(i).split(":");
2023/6/1
题目(未完成)533：最优除法 脑筋急转弯
class Solution {public String optimalDivision(int[] nums) {StringBuilder res = new StringBuilder();for(int i = 0;i < nums.length;i++){if(nums.length >= 3){if(i < nums.length - 1){if(i == 1) res.append("(" + nums[i] + "/");else res.append(nums[i] + "/");}else{res.append(nums[i] + ")");}}else if(nums.length == 1){res.append(nums[i]);}else{if(i < nums.length - 1){res.append(nums[i] + "/");}else res.append(nums[i]);}}return res.toString();}
}
宫水三叶
class Solution {public String optimalDivision(int[] nums) {int n = nums.length;StringBuilder sb = new StringBuilder();for (int i = 0; i < n; i++) {sb.append(nums[i]);if (i + 1 < n) sb.append("/");}if (n > 2) {sb.insert(sb.indexOf("/") + 1, "(");sb.append(")");}return sb.toString();}
}indexOf：返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
题目(未完成)537：复数乘法 思路是对的，就是处理过程有问题 java.split
class Solution {public String complexNumberMultiply(String num1, String num2) {// a + bi c + di//(ac - bd) + (ad + bc)iStringBuilder res = new StringBuilder();char[] num1_char = num1.toCharArray();char[] num2_char = num2.toCharArray();int b,d = 0;int a = Integer.parseInt(String.valueOf(num1_char[0]));if(num1_char[2] == '-'){String temp = String.valueOf(num1_char[3]);b = -Integer.parseInt(temp);}else{b = Integer.parseInt(String.valueOf(num1_char[2]));}int c = Integer.parseInt(String.valueOf(num2_char[0]));if(num2_char[2] == '-'){String temp = String.valueOf(num2_char[3]);d = Integer.parseInt(temp);}else{d = Integer.parseInt(String.valueOf(num1_char[2]));}// int d = Integer.parseInt(String.valueOf(num2_char[2]));res.append(a*c - b*d);res.append('+');res.append(a*d + b*c);res.append('i');return res.toString();}
}
宫水三叶
class Solution {public String complexNumberMultiply(String num1, String num2) {String[] ss1 = num1.split("\\+|i"), ss2 = num2.split("\\+|i");int a = parse(ss1[0]), b = parse(ss1[1]);int c = parse(ss2[0]), d = parse(ss2[1]);int A = a * c - b * d, B = b * c + a * d;return A + "+" + B + "i";}int parse(String s) {return Integer.parseInt(s);}
}(126条消息) Java split方法详细讲解_一只光头猿的博客-CSDN博客
2023/6/7
题目(未完成)592：分数加减运算 我写的和答案思路是一样的 但是我处理方法想复杂了
我写的
class Solution {public String fractionAddition(String expression) {String[] test_1 = expression.split("\\d/\\d");// + - String[] test_2 = expression.split("\\+|-");//1/3 2/3 int fenzi = 0;int fenmu = 1;for(int i = 0;i < test_1.length;i++){char ch = test_1.charAt(i);//获取是正数还是负数char[] res = test_2[i].toCharArray();//将1/3中的分子和分母的数值提取出来int res_fenzi = Integer.parseInt(String.valueOf(res[0]));int res_fenmu = Integer.parseInt(String.valueOf(res[2]));if(ch == '-'){fenzi = (fenzi * res_fenmu) - (res_fenzi * fenmu);fenmu = fenmu * res_fenmu;}else{fenzi = (fenzi * res_fenmu) + (res_fenzi * fenmu);fenmu = fenmu * res_fenmu;}}}
}
答案
class Solution {public String fractionAddition(String expression) {long x = 0, y = 1; // 分子，分母int index = 0, n = expression.length();while (index < n) {// 读取分子long x1 = 0, sign = 1;if (expression.charAt(index) == '-' || expression.charAt(index) == '+') {sign = expression.charAt(index) == '-' ? -1 : 1;index++;}while (index < n && Character.isDigit(expression.charAt(index))) {x1 = x1 * 10 + expression.charAt(index) - '0';//处理32/65这种情况的index++;}x1 = sign * x1;index++;// 读取分母long y1 = 0;while (index < n && Character.isDigit(expression.charAt(index))) {y1 = y1 * 10 + expression.charAt(index) - '0';//处理32/65这种情况的index++;}x = x * y1 + x1 * y;y *= y1;}if (x == 0) {return "0/1";}long g = gcd(Math.abs(x), y); // 获取最大公约数return Long.toString(x / g) + "/" + Long.toString(y / g);}public long gcd(long a, long b) {long remainder = a % b;while (remainder != 0) {a = b;b = remainder;remainder = a % b;}return b;}
}long 数据类型用于保存 int 无法保存的较大整数。
字符转数字的快捷办法：expression.charAt(index) - '0'；
判断指定字符是否是数字：Character.isDigit(expression.charAt(index))；
2023/6/8
题目(感觉就差最后一点了) 640：求解方程 我写的感觉就差个x前多位系数的处理了
我写的
class Solution {public String solveEquation(String equation) {String[] res = equation.split("\\=");int left_x_final = 0;int left_num_final = 0;for(String s : res){int left_x = 0;int left_num = 0;int index = 0;int lengths = s.length();//x+5-3+xint sign = 1;while(index < lengths){if(index < lengths && s.charAt(index) == 'x'){if(index - 1 < 0){left_x++;}else if(index - 1 >= 0 && s.charAt(index - 1) == '+'){left_x++;}else if(index - 1 >= 0 && s.charAt(index - 1) == '-'){left_x--;}else if(index - 1 >= 0 && Character.isDigit(s.charAt(index - 1))){if(index - 2 < 0){left_x = left_x + (s.charAt(index - 1) - '0');}else if(index - 2 >= 0 && s.charAt(index - 2) == '+'){left_x = left_x + (s.charAt(index - 1) - '0');}else if(index - 2 >= 0 && s.charAt(index - 2) == '-'){left_x = left_x - (s.charAt(index - 1) - '0');}}index++;}if(index < lengths && (s.charAt(index) == '-' || s.charAt(index) == '+')){sign = s.charAt(index) == '-' ? -1 : 1;index++;}int temp = 0;while(index < lengths && Character.isDigit(s.charAt(index))){if(index + 1 < lengths && s.charAt(index + 1) == 'x'){index++;break;}else{temp = temp * 10 +(sign * (s.charAt(index) - '0'));// left_num += sign * (s.charAt(index) - '0');}index++;}left_num = left_num + temp;}if(left_x_final == 0 && left_num_final == 0){left_x_final = left_x;left_num_final = left_num;}else{if(left_x_final == left_x && left_num_final == left_num){return "Infinite solutions";}else{if(left_x_final > left_x){return "x=" + String.valueOf((left_num - left_num_final)/(left_x_final - left_x));}else if(left_x > left_x_final){return "x=" + String.valueOf((left_num_final - left_num)/(left_x - left_x_final));}}}}return "No solution";}
}
答案
class Solution {public String solveEquation(String equation) {int factor = 0, val = 0;int index = 0, n = equation.length(), sign1 = 1; // 等式左边默认系数为正while (index < n) {if (equation.charAt(index) == '=') {sign1 = -1; // 等式右边默认系数为负 相当于都移动到左边计算index++;continue;}int sign2 = sign1, number = 0;boolean valid = false; // 记录 number 是否有效if (equation.charAt(index) == '-' || equation.charAt(index) == '+') { // 去掉前面的符号sign2 = (equation.charAt(index) == '-') ? -sign1 : sign1;index++;}while (index < n && Character.isDigit(equation.charAt(index))) {number = number * 10 + (equation.charAt(index) - '0');index++;valid = true;}if (index < n && equation.charAt(index) == 'x') { // 变量factor += valid ? sign2 * number : sign2;//走这里说明是x的系数index++;} else { // 数值val += sign2 * number; //走这里说明是常量}}if (factor == 0) {return val == 0 ? "Infinite solutions" : "No solution";}return "x=" + (-val / factor); //再把常数项移回到右边 所以要再加负号}
}答案确实高明
2023/6/13
题目(完成)38：外观数列
class Solution {public String countAndSay(int n) {String res = "1";for(int i = 0;i < n - 1;i++){StringBuilder res_test = new StringBuilder();String temp = res;int k = 0;while(k < temp.length()){int times = 0;char s = temp.charAt(k);while(k < temp.length() && temp.charAt(k) == s){k++;times++;}res_test.append(times);res_test.append(s);}res = res_test.toString();}return res;}
}2023/6/15
题目(我觉得没问题说实话，但是未通过)443：压缩字符串
我和三叶姐的思路是一模一样的
我写的
class Solution {public int compress(char[] chars) {int k = 0;int res = 0;int pointer = 0;if(chars.length == 1){res = 1;return res;}while(k < chars.length){int times = 0;int times_copy = 0;char temp = chars[k];int times_times = 0;//统计一共有几位数int sentinel = 0;// pointer = k; //记录第一个字母的坐标while(k < chars.length && chars[k] == temp){k++;times++;}times_copy = times;//res负责记录整个数组最后的长度res++;res++;times_times++;while(times / 10 != 0){times = times / 10;res++; times_times++;}chars[pointer] = temp;pointer++;if(times_copy > 1){if(times_times == 1){chars[pointer] = Integer.toString(times_copy).charAt(0);pointer++;}else{sentinel = pointer + times_times - 1;chars[sentinel] = Integer.toString(times_copy % 10).charAt(0);//个位sentinel--;pointer++;while(times_copy / 10 != 0){chars[sentinel] = Integer.toString(times_copy / 10 % 10).charAt(0);times_copy = times_copy /10;sentinel--;pointer++;}}}}return res;}
}
宫水三叶
class Solution {public int compress(char[] cs) {int n = cs.length;int i = 0, j = 0;while (i < n) {int idx = i;while (idx < n && cs[idx] == cs[i]) idx++;int cnt = idx - i;cs[j++] = cs[i];if (cnt > 1) {int start = j, end = start;while (cnt != 0) {cs[end++] = (char)((cnt % 10) + '0');cnt /= 10;}reverse(cs, start, end - 1);j = end;}i = idx;}return j;}void reverse(char[] cs, int start, int end) {while (start < end) {char t = cs[start];cs[start] = cs[end];cs[end] = t;start++; end--;}}
}
2023/6/20
题目(完成)13：罗马整数转数字
class Solution {public int romanToInt(String s) {char[] res = s.toCharArray();int res_num = 0;int i = 0;while(i < res.length){if(res[i] == 'I'){if(i + 1 < res.length && res[i + 1] == 'V'){res_num = res_num + 4;i++;i++;if(i >= res.length) break;}else if(i + 1 < res.length && res[i + 1] == 'X'){res_num = res_num + 9;i++;i++;if(i >= res.length) break;}else{res_num = res_num + 1;i++;if(i >= res.length) break;}}if(res[i] == 'V'){res_num = res_num + 5;i++;if(i >= res.length) break;}if(res[i] == 'X'){if(i + 1 < res.length && res[i + 1] == 'L'){res_num = res_num + 40;i++;i++;if(i >= res.length) break;}else if(i + 1 < res.length && res[i + 1] == 'C'){res_num = res_num + 90;i++;i++;if(i >= res.length) break;}else{res_num = res_num + 10;i++;if(i >= res.length) break;}}if(res[i] == 'L'){res_num = res_num + 50;i++;if(i >= res.length) break;}if(res[i] == 'C'){if(i + 1 < res.length && res[i + 1] == 'D'){res_num = res_num + 400;i++;i++;if(i >= res.length) break;}else if(i + 1 < res.length && res[i + 1] == 'M'){res_num = res_num + 900;i++;i++;if(i >= res.length) break;}else{res_num = res_num + 100;i++;if(i >= res.length) break;}}if(res[i] == 'D'){res_num = res_num + 500;i++;if(i >= res.length) break;}if(res[i] == 'M'){res_num = res_num + 1000;i++;if(i >= res.length) break;}}return res_num;}
}题目(完成)12：整数转罗马数字
class Solution {public String intToRoman(int num) {StringBuilder res = new StringBuilder();while(0 < num){//处理千位及以上while(1000 <= num){num = num - 1000;res.append("M");if(num <= 0) break;}//处理百位if(900 <= num && num < 1000){num = num - 900;res.append("CM");if(num <= 0) break;}else if(500 <= num && num < 900){num = num - 500;res.append("D");if(num <= 0) break;}else if(400 <= num && num < 500){num = num - 400;res.append("CD");if(num <= 0) break;}else if(100 <= num && num < 400){while(100 <= num){num = num - 100;res.append("C");if(num <= 0) break;}}//处理十位if(90 <= num && num < 100){num = num - 90;res.append("XC");if(num <= 0) break;}else if(50 <= num && num < 90){num = num - 50;res.append("L");if(num <= 0) break;}else if(40 <= num && num < 50){num = num - 40;res.append("XL");if(num <= 0) break;}else if(10 <= num && num < 40){while(10 <= num){num = num - 10;res.append("X");if(num <= 0) break;}}//处理个位if(9 <= num && num < 10){num = num - 9;res.append("IX");if(num <= 0) break;}else if(5 <= num && num < 9){num = num - 5;res.append("V");if(num <= 0) break;}else if(4 <= num && num < 5){num = num - 4;res.append("IV");if(num <= 0) break;}else if(1 <= num && num < 4){while(1 <= num){num = num - 1;res.append("I");if(num <= 0) break;}}}return res.toString();}
}2023/6/25
题目(我尽力了，未完成)273：整数转换英文表示
我写的 又臭又长
class Solution {static String[] TheUnit = {"One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};static String[] TheTen = {"Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};static String[] TheTen_Integer = {"Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};public String numberToWords(int num) {StringBuilder res = new StringBuilder();String temp = String.valueOf(num);char[] res_ch = temp.toCharArray();if(0 <= res_ch.length && res_ch.length < 4){if(res_ch.length == 3){res.append(TheUnit[(res_ch[0] - '0') - 1]);res.append(" ");res.append("Hundred");res.append(" ");if(res_ch[1] == '1'){res.append(TheTen[res_ch[2] - '0']);// res.append(" ");}else if(res_ch[1] != '1' && res_ch[1] != '0'){res.append(TheTen_Integer[(res_ch[1] - '0') - 2]);res.append(" ");if(res_ch[2] != '0'){// res.appned(TheUnit[(res_ch[2] - '0') - 1]);res.append(TheUnit[(res_ch[2] - '0') - 1]);// res.append(" ");}}}else if(res_ch.length == 2){if(res_ch[0] == '1'){res.append(TheTen[res_ch[1] - '0']);// res.append(" ");}else{res.append(TheTen_Integer[(res_ch[0] - '0') - 2]);res.append(" ");if(res_ch[1] != '0'){res.append(TheUnit[(res_ch[1] - '0') - 1]);// res.append(" ");}}}else if(res_ch.length == 1){res.append(TheUnit[(res_ch[1] - '0') - 1]);// res.append(" ");}}else if(4 <= res_ch.length && res_ch.length < 7){int times = 0;if(res_ch.length == 6){times = 3;res.append(TheUnit[(res_ch[0] - '0') - 1]);res.append(" ");res.append("Hundred");res.append(" ");if(res_ch[1] == '1'){res.append(TheTen[res_ch[2] - '0']);res.append(" ");}else{res.append(TheTen_Integer[(res_ch[1] - '0') - 2]);res.append(" ");if(res_ch[2] != '0'){// res.appned(TheUnit[(res_ch[2] - '0') - 1]);res.append(TheUnit[(res_ch[2] - '0') - 1]);res.append(" ");}}}else if(res_ch.length == 5){times = 2;if(res_ch[0] == '1'){res.append(TheTen[res_ch[1] - '0']);res.append(" ");}else{res.append(TheTen_Integer[(res_ch[0] - '0') - 2]);res.append(" ");if(res_ch[1] != '0'){res.append(TheUnit[(res_ch[1] - '0') - 1]);res.append(" ");}}}else if(res_ch.length == 4){times = 1;res.append(TheUnit[(res_ch[0] - '0') - 1]);res.append(" ");}res.append("Thousand");res.append(" ");res.append(TheUnit[(res_ch[times] - '0') - 1]);res.append(" ");res.append("Hundred");res.append(" ");if(res_ch[times + 1] == '1'){res.append(TheTen[res_ch[times + 2] - '0']);// res.append(" ");}else{res.append(TheTen_Integer[(res_ch[times + 1] - '0') - 2]);res.append(" ");if(res_ch[times + 2] != '0'){// res.appned(TheUnit[(res_ch[2] - '0') - 1]);res.append(TheUnit[(res_ch[times + 2] - '0') - 1]);// res.append(" ");}}}else if(7 <= res_ch.length && res_ch.length < 10){if(res_ch.length == 9){res.append(TheUnit[(res_ch[0] - '0') - 1]);res.append(" ");res.append("Hundred");res.append(" ");if(res_ch[1] == '1'){res.append(TheTen[res_ch[2] - '0']);// res.append(" ");}else{res.append(TheTen_Integer[(res_ch[1] - '0') - 2]);// res.append(" ");if(res_ch[2] != '0'){// res.appned(TheUnit[(res_ch[2] - '0') - 1]);res.append(TheUnit[(res_ch[2] - '0') - 1]);// res.append(" ");}}}else if(res_ch.length == 8){if(res_ch[0] == '1'){res.append(TheTen[res_ch[1] - '0']);// res.append(" ");}else{res.append(TheTen_Integer[(res_ch[0] - '0') - 2]);res.append(" ");if(res_ch[1] != '0'){res.append(TheUnit[(res_ch[1] - '0') - 1]);// res.append(" ");}}}else if(res_ch.length == 7){res.append(TheUnit[(res_ch[1] - '0') - 1]);// res.append(" ");}res.append("Millon");res.append(" ");}else if(res_ch.length == 10){}return res.toString();}public void test(char[] res_ch){}}
宫水三叶
class Solution {static String[] num2str_small = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};static String[] num2str_medium = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};static String[] num2str_large = {"Billion", "Million", "Thousand", "",};String num2Str(int x) {String ans = "";if (x >= 100) {ans += num2str_small[x / 100] + " Hundred ";x %= 100;}if (x >= 20) {ans += num2str_medium[x / 10] + " ";x %= 10;}if (x != 0) ans += num2str_small[x] + " ";return ans;}public String numberToWords(int num) {if (num == 0) return num2str_small[0];StringBuilder sb = new StringBuilder();for (int i = (int)1e9, j = 0; i >= 1; i /= 1000, j++) {if (num < i) continue;sb.append(num2Str(num / i) + num2str_large[j] + " ");num %= i;}while (sb.charAt(sb.length() - 1) == ' ') sb.deleteCharAt(sb.length() - 1);return sb.toString();}
}while(sb.charAt(sb.length() - 1) == ' ') sb.deleteCharAt(sb.length() - 1);
2023/6/25
题目(我感觉我是完成了的，但是最后一个案例未通过，自己在idea试是可以的)165：比较版本号
class Solution {public int compareVersion(String version1, String version2) {String[] vers1 = version1.split("\\.");String[] vers2 = version2.split("\\.");int length = Math.min(vers1.length,vers2.length);// int temp = 0;// int i = 0;for(int i = 0;i < length;i++){if(vers1[i] == vers2[i]) continue;else{int vers1_num = 0;if(vers1[i].length() != 1 && vers1[i].charAt(0) == '0'){int k = 0;while(k < vers1[i].length() && vers1[i].charAt(k) == '0') k++;while(k < vers1[i].length()){vers1_num = vers1_num * 10 + (vers1[i].charAt(k) + '0');k++;}}else if(vers1[i].length() != 1 && vers1[i].charAt(0) != '0'){int k = 0;while(k < vers1[i].length()){vers1_num = vers1_num * 10 + (vers1[i].charAt(k) + '0');k++;}}else if(vers1[i].length() == 1){vers1_num = vers1[i].charAt(0) + '0';}int vers2_num = 0;if(vers2[i].length() != 1 && vers2[i].charAt(0) == '0'){int k = 0;while(k < vers2[i].length() && vers2[i].charAt(k) == '0') k++;while(k < vers2[i].length()){vers2_num = vers2_num * 10 + (vers2[i].charAt(k) + '0');k++;}}else if(vers2[i].length() != 1 && vers2[i].charAt(0) != '0'){int k = 0;while(k < vers2[i].length()){vers2_num = vers2_num * 10 + (vers2[i].charAt(k) + '0');k++;}}else if(vers2[i].length() == 1){vers2_num = vers2[i].charAt(0) + '0';}if(vers1_num == vers2_num) continue;else if(vers1_num > vers2_num){return 1;}else if(vers1_num < vers2_num){return -1;}}}//走到这有两种情况 一种是真的是只能返回0 另一种是两个长度不一样if(vers1.length > vers2.length){for(int j = vers2.length;j < vers1.length;j++){if(vers1[j].length() == 1 && vers1[j].charAt(0) != '0') return 1;else if(vers1[j].length() > 1){for(int m = 0;m < vers1[j].length();m++){if(vers1[j].charAt(m) != '0') return 1;}}}return 0;}if(vers2.length > vers1.length){for(int j = vers1.length;j < vers2.length;j++){if(vers2[j].length() == 1 && vers2[j].charAt(0) != '0') return -1;else if(vers2[j].length() > 1){for(int m = 0;m < vers2[j].length();m++){if(vers2[j].charAt(m) != '0') return -1;}}// else return -1;}return 0;}return 0;}
}宫水三叶
class Solution {public int compareVersion(String v1, String v2) {String[] ss1 = v1.split("\\."), ss2 = v2.split("\\.");int n = ss1.length, m = ss2.length;int i = 0, j = 0;while (i < n || j < m) {int a = 0, b = 0;if (i < n) a = Integer.parseInt(ss1[i++]);if (j < m) b = Integer.parseInt(ss2[j++]);if (a != b) return a > b ? 1 : -1;}return 0;}
}还得是三叶姐
2023/6/26
题目(完成)481：神奇字符串 不知道为什么突然就成功了，本来还以为不行
class Solution {public int magicalString(int n) {if(n <= 3) return 1;int res = 1;String s = "122";String s_guide = "122";int length = s.length(); //初始的长度// int s_pointer = 2;int s_guide_pointer = 2;char temp = '1';while(length < n){int times = s_guide.charAt(s_guide_pointer) - '0';for(int i = 0;i < times;i++){if(length < n){s += temp;if(temp == '1') res++;length++;}else{break;} }s_guide = s;s_guide_pointer++;if(s_guide_pointer % 2 == 0){temp = '1';}else{temp = '2';}}return res;}
}2023/6/27
题目(完成)392：判断子序列 第85道
我写的
class Solution {public boolean isSubsequence(String s, String t) {//s是否为t的子序列int i = 0;int k = 0;int k_pointer = -1;while(i < s.length()){char temp = s.charAt(i);while(k < t.length() && t.charAt(k) != temp) k++;if(k == t.length()) return false;if(k > k_pointer){k_pointer = k;k++;//最后一个案例一直没通过的原因在于少了这行}else{return false;}i++;}return true;}
}
答案
class Solution {public boolean isSubsequence(String s, String t) {int n = s.length(), 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;}
}题目(未完成)524：通过删除字母匹配到字典里最长单词 没有理解并处理好字典序
类似Map、Set、List等集合中元素排序，想想Collections.sort()
我写的
class Solution {public String findLongestWord(String s, List<String> dictionary) {int length = 0;String res = "";int length_pointer = 0;// int Alphabetical_order_temp = 0;//存储上一个符合要求的字符序for(String str : dictionary){int i = 0 , j = 0;//str是短的 s是长的int Alphabetical_order = 0;//如果答案不止一个，返回长度最长且字母序最小while(i < str.length() && j < s.length()){if(str.charAt(i) == s.charAt(j)){if(Alphabetical_order == 0){char first_AlAlphabetical = str.charAt(i);}i++;// Alphabetical_order += j;}j++;if(i == str.length()){if(str.length() > length){//如果答案不止一个，返回长度最长且字母序最小length = str.length();res = str;}else if(str.length() == length){// if(Alphabetical_order < Alphabetical_order_temp){// res = str;// }}// Alphabetical_order_temp = Alphabetical_order;}}}return res;}
}
最好理解的答案
class Solution {public String findLongestWord(String s, List<String> dictionary) {String res = "";for (String t : dictionary) {int i = 0, j = 0;while (i < t.length() && j < s.length()) {if (t.charAt(i) == s.charAt(j)) {++i;}++j;}if (i == t.length()) {if (t.length() > res.length() || (t.length() == res.length() && tpareTo(res) < 0)) {res = t;}}}return res;}
}
宫水三叶
class Solution {public String findLongestWord(String s, List<String> list) {Collections.sort(list, (a,b)->{if (a.length() != b.length()) return b.length() - a.length();return apareTo(b);});int n = s.length();for (String ss : list) {int m = ss.length();int i = 0, j = 0;while (i < n && j < m) {if (s.charAt(i) == ss.charAt(j)) j++;i++;}if (j == m) return ss;}return "";}
}什么是字典序：(132条消息) 字典序_兰亭落雪的博客-CSDN博客
compareTo方法：Java compareTo() 方法 | 菜鸟教程 (runoob)
Collections.sort(list, (a,b)->{
if (a.length() != b.length()) return b.length() - a.length();
return apareTo(b);
});
* 升序排的话就是第一个参数pareTo(第二个参数);
* 降序排的话就是第二个参数pareTo(第一个参数);
b.length() - a.length() 倒叙 a.length() - b.length() 正叙
2023/6/28
题目(未完成)521：最长特殊序列1 脑筋急转弯
class Solution {public int findLUSlength(String a, String b) {return a.equals(b) ? -1 : Math.max(a.length(), b.length());}
}当两字符串不同时，我们总能选择长度不是最小的字符串作为答案，而当两字符串相同时，我们无法找到特殊序列。
题目(未完成)522：最长特殊序列2 答案想不到
2023/7/9
题目(完成)66：加一
class Solution {public int[] plusOne(int[] digits) {int n = digits.length -1;digits[n]++;while(n>0){if(digits[n]==10){digits[n]=0;digits[n-1]++;}n--;}if(digits[0]==10){int []result = new int[digits.length+1];result[0]=1;for(int j=1;j<n+1;j++){result[j]=0;}return result;}return digits;}
}public int[] plusOne(int[] digits) {for (int i = digits.length - 1; i >= 0; i--) {if (digits[i] == 9) {digits[i] = 0;} else {digits[i] += 1;return digits;}}//如果所有位都是进位，则长度+1digits= new int[digits.length + 1];digits[0] = 1;return digits;}题目(完成)67：二进制求和
class Solution {public String addBinary(String a, String b) {String res = "";String res_refer = "";if(a.length() >= b.length()){res = a;res_refer = b;}else{res = b;res_refer = a;}int length_res = res.length() - 1;int length = res_refer.length() - 1;int sign = 0;int length_Difference = res.length() - res_refer.length();while(length >= 0 || length_res >= 0){char[] res_char = res.toCharArray();int res_ch = res.charAt(length_res) - '0';int res_refer_ch = 0;if(length >= 0){res_refer_ch = res_refer.charAt(length) - '0';}if(res_ch + res_refer_ch + sign == 2){//res.charAt(length + length_Difference) = '0';res_char[length_res] = '0';}else if(res_ch + res_refer_ch + sign == 3){res_char[length_res] = '1';//res.charAt(length + length_Difference) = '1';}else if(res_ch + res_refer_ch + sign == 1){res_char[length_res] = '1';//res.charAt(length + length_Difference) = '1';sign = 0;}if(res_ch + res_refer_ch == 2){sign = 1;}length--;length_res--;res = String.valueOf(res_char);if(length_res < 0 && sign == 1){res = '1' + res;break;}}return res;}
}2023/7/10
题目(完成)415：字符串相加
class Solution {public String addStrings(String a, String b) {String res = "";String res_refer = "";if(a.length() >= b.length()){res = a;res_refer = b;}else{res = b;res_refer = a;}int length_res = res.length() - 1;int length = res_refer.length() - 1;int sign = 0;while(length >= 0 || length_res >= 0){char[] res_char = res.toCharArray();int res_ch = res.charAt(length_res) - '0';int res_refer_ch = 0;if(length >= 0){res_refer_ch = res_refer.charAt(length) - '0';}if(res_ch + res_refer_ch + sign < 10){res_char[length_res] = Integer.toString(res_ch + res_refer_ch + sign).charAt(0);sign = 0;}else{res_char[length_res] = Integer.toString(res_ch + res_refer_ch + sign - 10).charAt(0);sign = 1;}length--;length_res--;res = String.valueOf(res_char);if(length_res < 0 && sign == 1){res = '1' + res;break;}}return res;}
}2023/7/14
题目(完成一半)43：字符串相乘 我写的直接将思路里每一步的结果相加，所以就处理不了太长的结果；答案是一步步往上加的，就很好的避免了我的问题。
class Solution {public String multiply(String a, String b) {String res = "";String res_refer = "";if(a.length() >= b.length()){res = a;res_refer = b;}else{res = b;res_refer = a;}int length_res = res.length() - 1;int length = res_refer.length() - 1;long times = 0;long temp = 0;long res_num = 0;for(int i = length;i >= 0 ;i--){int sign = 0;int beishu = 1;int res_refer_ch = res_refer.charAt(i) - '0';int length_res_temp = length_res;// System.out.println("res_refer_ch:" + res_refer_ch);char[] res_char = res.toCharArray();while(length_res_temp >= 0){int res_ch = res.charAt(length_res_temp) - '0';// System.out.println("res_ch:" + res_ch);if(res_ch * res_refer_ch + sign < 10){res_char[length_res_temp] = Integer.toString(res_ch * res_refer_ch + sign).charAt(0);sign = 0;}else{res_char[length_res_temp] = Integer.toString(res_ch * res_refer_ch + sign).charAt(1);sign = Integer.toString(res_ch * res_refer_ch + sign).charAt(0) - '0';}// System.out.println("res_char[length_res_temp]:" + res_char[length_res_temp]);// System.out.println("sign:" + sign);length_res_temp--;}if(sign != 0){temp = Integer.parseInt(sign + String.valueOf(res_char));}else{temp = Integer.parseInt(String.valueOf(res_char));}// System.out.println("temp:" + temp);
// System.out.println("temp:" + temp);// System.out.println("times:" + times);for(int k = 0;k < times;k++){beishu = beishu * 10;}// System.out.println("beishu:" + beishu);res_num = res_num + temp * beishu;// System.out.println("res_num:" + res_num);times++;}// if(sign != 0){// System.out.println(sign + "" + res_num + "");// }// System.out.println("sign2:" + sign);// System.out.println(res_num + "");return res_num + "";}
}class Solution {/*** 计算形式* num1* x num2* ------* result*/public String multiply(String num1, String num2) {if (num1.equals("0") || num2.equals("0")) {return "0";}// 保存计算结果String res = "0";// num2 逐位与 num1 相乘for (int i = num2.length() - 1; i >= 0; i--) {int carry = 0;// 保存 num2 第i位数字与 num1 相乘的结果StringBuilder temp = new StringBuilder();// 补 0 for (int j = 0; j < num2.length() - 1 - i; j++) {temp.append(0);}int n2 = num2.charAt(i) - '0';// num2 的第 i 位数字 n2 与 num1 相乘for (int j = num1.length() - 1; j >= 0 || carry != 0; j--) {int n1 = j < 0 ? 0 : num1.charAt(j) - '0';int product = (n1 * n2 + carry) % 10;temp.append(product);carry = (n1 * n2 + carry) / 10;}// 将当前结果与新计算的结果求和作为新的结果res = addStrings(res, temp.reverse().toString());}return res;}/*** 对两个字符串数字进行相加，返回字符串形式的和*/public String addStrings(String num1, String num2) {StringBuilder builder = new StringBuilder();int carry = 0;for (int i = num1.length() - 1, j = num2.length() - 1;i >= 0 || j >= 0 || carry != 0;i--, j--) {int x = i < 0 ? 0 : num1.charAt(i) - '0';int y = j < 0 ? 0 : num2.charAt(j) - '0';int sum = (x + y + carry) % 10;builder.append(sum);carry = (x + y + carry) / 10;}return builder.reverse().toString();}
}
2023/7/19
题目(完成)482：密钥格式化
class Solution {public String licenseKeyFormatting(String s, int k) {StringBuilder res = new StringBuilder();int length = s.length() - 1;int count = 0;while(length >= 0){if(length >= 0 && s.charAt(length) != '-'){res.append(s.charAt(length));count++;if(count == k){res.append('-');count = 0;}}length--;}if(res.length() - 1 >= 0 && res.charAt(res.length()- 1) == '-'){res.deleteCharAt(res.length() - 1);}return res.reverse().toString().toUpperCase();}
}题目(完成)6：N字形转换
class Solution {public String convert(String s, int numRows) {StringBuilder res = new StringBuilder();if(numRows == 1) return s;int multiple = (numRows - 1) * 2;int rows = 0;int temp = 0;while(rows < numRows){temp = rows;if(rows == 0 || rows == numRows - 1){// res.append(s.charAt(temp));while(temp < s.length()){res.append(s.charAt(temp));temp = temp + multiple;}}else{// int temps = rows;int temp_extra = multiple - temp;while(temp< s.length()){res.append(s.charAt(temp));if(temp_extra < s.length()){res.append(s.charAt(temp_extra));}temp = temp + multiple;temp_extra = temp_extra + multiple;}}rows++;}return res.toString();}
}2023/7/20
题目(完成)28：找出字符串中第一个匹配的下标
class Solution {public int strStr(String a, String b) {int a_length = a.length();int b_length = b.length();int a_pointer = 0;int b_pointer = 0;int a_pointer_replace = 0;int b_pointer_replace = 0;// int res = a_length;while(a_pointer < a_length){if(a.charAt(a_pointer) == b.charAt(b_pointer)){a_pointer_replace = a_pointer;b_pointer_replace = b_pointer;while(a_pointer_replace < a_length && b_pointer_replace < b_length && a.charAt(a_pointer_replace) == b.charAt(b_pointer_replace)){a_pointer_replace++;b_pointer_replace++;}if(b_pointer_replace == b_length) return a_pointer;}a_pointer++;}return -1;}
}2023/8/25——二叉树专题
二叉树基础知识
java中map的key是有序的，因为其底层实现逻辑是二叉平衡搜索树
深度优先法则：前中后序遍历
广度优先法则：层序遍历
深度： 二叉树中任意一个节点到根节点的距离 从上往下计数 用前序遍历
高度：二叉树中任意一个节点到叶子节点的距离 从下往上计数 用后序遍历
叶子节点:自己下面不再连接有节点的节点
二叉搜索树：根节点的值比其左子树的都要大，比其右子树的都要小，子树也是这样
二叉搜索树按照中序遍历的顺序得到的结果是单调递增的
题目(学习)144：二叉树的前序遍历
//递归法
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();preorder(root, result);//root:根节点 result:存储结果的数组return result;}public void preorder(TreeNode root,List<Integer> result){if(root == null) return;result.add(root.val); //中preorder(root.left,result); //左preorder(root.right,result); //右}
}
//迭代法
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if(root == null) return result;Stack<TreeNode> stack = new Stack<>();//栈stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);//栈 先进后出 前序 中左右if(node.right != null){stack.push(node.right);}if(node.left != null){stack.push(node.left);}}return result;}
}题目(学习)145：二叉树的后序遍历
//递归法
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();postorder(root,result);return result;}public void postorder(TreeNode root,List<Integer> list){if(root == null) return;postorder(root.left, list);//左postorder(root.right,list);//右list.add(root.val);//中}
}
//迭代法
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if(root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if(node.left != null){stack.push(node.left);}if(node.right != null){stack.push(node.right);}}Collections.reverse(result);//反转数组return result;}
}反转数组：Collections.reverse(result);
题目(学习)94：二叉树的中序遍历
访问顺序和处理顺序不同：先访问根节点，但是要从下面的子节点开始处理
//递归法
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();inorder(root,res);return res;}public void inorder(TreeNode root,List<Integer> list){if(root == null) return;inorder(root.left, list);list.add(root.val);inorder(root.right,list);}
}
//迭代法
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if(root == null) return result;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;//定义一个指针用来遍历二叉树的while(cur != null || !stack.isEmpty()){//遇到空节点 就从栈里弹出遍历的元素加入到数组if(cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}2023/9/1
题目(学习)102：二叉树的层序遍历
class Solution {public List<List<Integer>> resList = new ArrayList<List<Integer>>();//最后返回的是一个二维数组public List<List<Integer>> levelOrder(TreeNode root) {checkFun02(root);return resList;}public void checkFun02(TreeNode node){if(node == null) return;Queue<TreeNode> que = new LinkedList<TreeNode>();//队列的定义que.offer(node);while(!que.isEmpty()){List<Integer> itemList = new ArrayList<Integer>();//定义一个一维数组来存放每一层的结果int len = que.size();//记录当前层共有多少个元素while(len > 0){TreeNode tmpNode = que.poll();//从队列中取值itemList.add(tmpNode.val);//将取的值放在一维数组中if(tmpNode.left != null) que.offer(tmpNode.left);//左孩子不为空，添加if(tmpNode.right != null) que.offer(tmpNode.right);len--;}resList.add(itemList);//向一维数组中添加一维数组得二维数组}}
}2023/9/4
题目(学习)107：二叉树的层序遍历2
class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();//队列if(root == null) return list;que.offerLast(root);//根节点加入到队列while(!que.isEmpty()){List<Integer> levelList = new ArrayList<>();int levelSize = que.size();while(levelSize > 0){TreeNode peek = que.poll();levelList.add(peek.val);if(peek.left != null){que.offer(peek.left);}if(peek.right != null){que.offer(peek.right);}levelSize--;}// for(int i = 0;i < levelSize;i++){// TreeNode peek = que.peekFirst();// levelList.add(que.pollFirst().val);// if(peek.left != null){// que.offerLast(peek.left);// }// if(peek.right != null){// que.offerLast(peek.right);// }// }list.add(levelList);}List<List<Integer>> result = new ArrayList<>();for(int i = list.size() - 1;i >= 0;i--){result.add(list.get(i));}return result;}
}题目(未完成)199：二叉树的右视图
注释的部分是我想的，不得行，没有仔细审题，理解题目意思
class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> resList = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if(root == null) return resList;que.offer(root);while(!que.isEmpty()){int len = que.size();for(int i = 0;i < len;i++){TreeNode tmpNode = que.pollFirst();if(tmpNode.left != null) que.offer(tmpNode.left);if(tmpNode.right != null) que.offer(tmpNode.right);if(i == len - 1) resList.add(tmpNode.val);}// while(len > 0){// TreeNode tmpNode = que.poll();// resList.add(tmpNode.val);// // if(tmpNode.left != null) que.offer(tmpNode.left);// if(tmpNode.right != null) que.offer(tmpNode.right);// // if()// len--;// }} return resList;}
}2023/9/5
题目(完成)637：二叉树的层平均值
class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> resList = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if(root == null) return resList;que.offerLast(root);while(!que.isEmpty()){double temp = 0;int levelSize = que.size();int length = levelSize;while(levelSize > 0){TreeNode peek = que.poll();temp = temp + peek.val;if(peek.left != null){que.offer(peek.left);}if(peek.right != null){que.offer(peek.right);}levelSize--;}double res_temp = temp / length;resList.add(res_temp);}return resList;}
}2023/9/6
题目(学习)429：N叉树的层序遍历
class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> resList = new ArrayList<>();Deque<Node> que = new LinkedList<>();if(root == null) return resList;que.offerLast(root);while(!que.isEmpty()){List<Integer> levelList = new ArrayList<>();int levelSize = que.size();for(int i = 0;i < levelSize; i++){Node poll = que.pollFirst();levelList.add(poll.val);List<Node> children = poll.children;if(children == null || children.size() == 0){continue;}for(Node child : children){if(child != null){que.offerLast(child);}}}resList.add(levelList);} return resList;}
}题目(完成)515：在每个树行中找最大值
class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> resList = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if(root == null) return resList;que.offerLast(root);while(!que.isEmpty()){int levelSize = que.size();// int MAX_temp = -2147483648;int MAX_temp = Integer.MIN_VALUE;while(levelSize > 0){TreeNode peek = que.poll();if(peek.val >= MAX_temp) MAX_temp = peek.val;if(peek.left != null){que.offer(peek.left);}if(peek.right != null){que.offer(peek.right);}levelSize--;}resList.add(MAX_temp);}return resList;}
}题目(学习)116：填充每个节点的下一个右侧节点指针
题目(学习)117：填充每个节点的下一个右侧节点指针2
class Solution {public Node connect(Node root) {Queue<Node> tmpQueue = new LinkedList<Node>();if(root != null) tmpQueue.add(root);while(tmpQueue.size() != 0){int size = tmpQueue.size(); Node cur = tmpQueue.poll();//0 - size-1 if(cur.left != null) tmpQueue.add(cur.left);if(cur.right != null) tmpQueue.add(cur.right);for(int index = 1; index < size;index++){Node next = tmpQueue.poll();if(next.left != null) tmpQueue.add(next.left);if(next.right != null) tmpQueue.add(next.right);cur.next = next;cur = next;}}return root;}
}题目(完成)104：二叉树的最大深度
解题关键：根节点的高度就是这颗二叉树的最大深度
想不通的话就把代码写全，方便理解
//层序遍历
class Solution {public int maxDepth(TreeNode root) {Deque<TreeNode> que = new LinkedList<>();if(root != null) que.offer(root);int res = 0;while(!que.isEmpty()){int levelSize = que.size();while(levelSize > 0){TreeNode peek = que.poll();if(peek.left != null) que.offer(peek.left);if(peek.right != null) que.offer(peek.right);levelSize--;}res++;}return res;}
}
//后序遍历
class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;int leftDepth = maxDepth(root.left);//左int rightDepth = maxDepth(root.right);//右return Math.max(leftDepth,rightDepth) + 1;//中}
}
//前序遍历
class Solution {int maxnum = 0;public int maxDepth(TreeNode root) {ans(root,0);return maxnum;}void ans(TreeNode tr,int tmp){if(tr == null) return;tmp++;maxnum = maxnum < tmp ? tmp:maxnum;ans(tr.left,tmp);ans(tr.right,tmp);tmp--;}
}题目(完成)111：二叉树的最小深度
class Solution {public int minDepth(TreeNode root) {Deque<TreeNode> que = new LinkedList<>();if(root == null) return 0;int res = 0;if(root != null) que.offer(root);while(!que.isEmpty()){int levelSize = que.size();res++;while(levelSize > 0){TreeNode peek = que.poll();if(peek.left == null && peek.right == null) return res;if(peek.left != null) que.offer(peek.left);if(peek.right != null) que.offer(peek.right);levelSize--;}}return res;}
}根节点的最小高度正好符合该题目要求的最小深度
叶子节点:自己下面不再连接有节点的节点
//后序遍历
class Solution {public int minDepth(TreeNode root) {if(root == null) return 0;int leftDepth = minDepth(root.left);int rightDepth = minDepth(root.right);if(root.left == null){return rightDepth + 1;}if(root.right == null){return leftDepth + 1;}return Math.min(leftDepth,rightDepth) + 1;}
}2023/9/8
题目(学习)226：翻转二叉树
class Solution {public TreeNode invertTree(TreeNode root) {if(root == null) return null;//后序遍历inverTree(root.left);//左 反转左子树inverTree(root.right);//右 反转右子树swapChildren(root);//交换左右孩子节点 中return root;}private void swapChildren(TreeNode root){TreeNode tmp = root.left;root.left = root.right;root.right = tmp;}
}2023/9/8
什么样的题目只能采用后序遍历：需要收集左右孩子的信息向上一层返回
题目(学习)101：对称二叉树
class Solution {public boolean isSymmetric(TreeNode root) {return compare(root.left,root.right);}private boolean compare(TreeNode left,TreeNode right){if(left == null && right != null) return false;if(left != null && right == null) return false;if(left == null && right == null) return true;if(left.val != right.val) return false;//比较外侧boolean compareOutside = compare(left.left,right.right);//比较内侧boolean compareInside = compare(left.right,right.left);return compareInside && compareOutside;}
}题目(完成)559：N叉树的最大深度
class Solution {public int maxDepth(Node root) {if(root == null) return 0;int depth = 0;List<Node> children = root.children;// if(children == null || children.size() == 0) continue;for(Node child : children){if(child != null){int childDepth = maxDepth(child);depth = Math.max(depth,childDepth);}}return depth + 1;}
}题目(完成)222：完全二叉树的节点个数
//层序遍历
class Solution {public int countNodes(TreeNode root) {Deque<TreeNode> que = new LinkedList<>();int res = 0;if(root == null) return 0;que.offerLast(root);while(!que.isEmpty()){int levelSize = que.size();res = res + levelSize;while(levelSize > 0){TreeNode peek = que.poll();if(peek.left != null) que.offer(peek.left);if(peek.right != null) que.offer(peek.right);levelSize--;}}return res;}
}
//当作普通二叉树来处理
class Solution {public int countNodes(TreeNode root) {if(root == null) return 0;int leftnumber = countNodes(root.left);int rightnumber = countNodes(root.right);return leftnumber + rightnumber + 1;}
}
//针对完全二叉树的解法
class Solution {public int countNodes(TreeNode root) {if(root == null) return 0;TreeNode left = root.left;TreeNode right = root.right;int leftDepth = 0,rightDepth = 0;while(left != null){left = left.left;leftDepth++;}while(right != null){right = right.right;rightDepth++;}if(leftDepth == rightDepth){return (2 << leftDepth) - 1;}int rootleftnum = countNodes(root.left);int rootrightnum = countNodes(root.right);return rootleftnum + rootrightnum + 1;}
}2023/9/18
题目(学习)110：平衡二叉树
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}private int getHeight(TreeNode root){if(root == null) return 0;int leftHeight = getHeight(root.left);if(leftHeight == -1) return -1;int rightHeight = getHeight(root.right);if(rightHeight == -1) return -1;if(Math.abs(leftHeight - rightHeight) > 1) return -1;return Math.max(leftHeight,rightHeight) + 1;}
}2023/9/19
题目(学习)257：二叉树的所有路径
lass Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();if(root == null) return res;List<Integer> paths = new ArrayList<>();traversal(root,paths,res);return res;}private void traversal(TreeNode root,List<Integer>paths,List<String>res){paths.add(root.val);if(root.left == null && root.right == null){StringBuilder sb = new StringBuilder();for(int i = 0;i < paths.size() - 1;i++){sb.append(paths.get(i).append("->"));}sb.append(paths.get(paths.size() - 1));res.add(sb.toString());return;}if(root.left != null){traversal(root.left,paths,res);paths.remove(paths.size() - 1);//回溯}if(root.right != null){traversal(root.right,paths,res);paths.remove(paths.size() - 1);//回溯}}
}2023/9/20
题目(完成)100：相同的树
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {return compare(p,q);}public boolean compare(TreeNode left,TreeNode right){if(left == null && right != null) return false;if(left != null && right == null) return false;if(left == null && right == null) return true;if(left.val != right.val) return false;boolean compareLeft = compare(left.left,right.left);boolean compareRight =compare(left.right,right.right);return compareLeft && compareRight;}
}2023/9/21
题目(未解决) 572：另一颗树的子树
两个代码的逻辑一样，但是第一个不知道为什么有的题目通不过
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if (subRoot == null) return true;if (root == null) return false;return compare(root.left,subRoot) || compare(root.right,subRoot) || compare(root,subRoot);}public boolean compare(TreeNode left,TreeNode right){if(left == null && right != null) return false;if(left != null && right == null) return false;if(left == null && right == null) return true;if(left.val != right.val) return false;boolean compareLeft = compare(left.left,right.left);boolean compareRight = compare(left.right,right.right);return compareLeft && compareRight;}
}class Solution {public boolean isSubtree(TreeNode s, TreeNode t) {if (t == null) return true; // t 为 null 一定都是 trueif (s == null) return false; // 这里 t 一定不为 null, 只要 s 为 null，肯定是 falsereturn isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);}/*** 判断两棵树是否相同*/public boolean isSameTree(TreeNode s, TreeNode t){if (s == null && t == null) return true;if (s == null || t == null) return false;if (s.val != t.val) return false;return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);}
}2023/9/27
题目(未完成)1047：左叶子之和
class Solution {public int sumOfLeftLeaves(TreeNode root) {//终止条件if(root == null) return 0;if(root.left == null && root.right == null) return 0;int leftnum = sumOfLeftLeaves(root.left);if (root.left != null && root.left.left == null && root.left.right == null) { leftnum = root.left.val;}int rightnum = sumOfLeftLeaves(root.right);int sum = leftnum +rightnum;return sum;}
}class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum = 0;if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();while (size -- > 0) {TreeNode node = queue.poll();if (node.left != null) { // 左节点不为空if (node.left.left == null && node.left.right == null){ // 左叶子节点sum += node.left.val;}queue.offer(node.left);}if (node.right != null) queue.offer(node.right);}}return sum;}
}2023/9/28
题目(层序完成，递归不会)513：找树左下角的值
//迭代
class Solution {public int findBottomLeftValue(TreeNode root) {List<List<Integer>> list = new ArrayList<>();if(root == null) return 0;Deque<TreeNode> que = new LinkedList<>();que.offer(root);while(!que.isEmpty()){List<Integer> levelList = new ArrayList<>();int levelSize = que.size();while(levelSize > 0){TreeNode peek = que.poll();levelList.add(peek.val);if(peek.left != null){que.offer(peek.left);}if(peek.right != null){que.offer(peek.right);}levelSize--;}list.add(levelList);}return list.get(list.size() - 1).get(0);}
}//递归
class Solution {private int Deep = -1;private int value = 0;public int findBottomLeftValue(TreeNode root) {value = root.val;findLeftValue(root,0);return value;}private void findLeftValue(TreeNode root,int depth){if(root == null) return;if(root.left == null && root.right == null){if(depth > Deep){value = root.val;Deep = depth;}}if(root.left != null){depth++;findLeftValue(root.left,depth);depth--;//回溯}if(root.right != null){depth++;findLeftValue(root.right,depth);depth--;//回溯}}
}2023/10/8
题目(未完成)112：路径总和
//用累加再比的话，会比较麻烦//累减会好一些
class Solution {private int value = 0;public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null) return false;targetSum = targetSum - root.val;if(root.left == null && root.right == null) return targetSum == 0;if(root.left != null){// targetSum = targetSum - root.left.val;boolean left = hasPathSum(root.left,targetSum);if(left) return true;// targetSum = targetSum + root.left.val;}if(root.right != null){// targetSum = targetSum - root.right.val;boolean right = hasPathSum(root.right,targetSum);if(right) return true;// targetSum = targetSum + root.right.val;}return false;}
}题目(未完成)113：路径总和2
class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> res = new ArrayList<List<Integer>>();if(root == null) return res;List<Integer> path = new ArrayList<Integer>();preorderdfs(root,targetSum,res,path);return res;}public void preorderdfs(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path){path.add(root.val);if(root.left == null && root.right == null){if(targetSum - root.val == 0){res.add(new ArrayList<>(path));}return;}if(root.left != null){preorderdfs(root.left,targetSum - root.val,res,path);path.remove(path.size() - 1);}if(root.right != null){preorderdfs(root.right,targetSum - root.val,res,path);path.remove(path.size() - 1);}}
}题目(学习)106：从中序与后序遍历序列构造二叉树
class Solution {Map<Integer,Integer> map;public TreeNode buildTree(int[] inorder, int[] postorder) {map = new HashMap<>();for(int i = 0;i < inorder.length;i++){map.put(inorder[i],i);}return findNote(inorder,0,inorder.length,postorder,0,postorder.length); }public TreeNode findNote(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){if(inBegin >= inEnd || postBegin >= postEnd) return null;int rootIndex = map.get(postorder[postEnd - 1]);TreeNode root = new TreeNode(inorder[rootIndex]);int lenOfLeft = rootIndex - inBegin;root.left = findNote(inorder,inBegin,rootIndex,postorder,postBegin,postBegin + lenOfLeft);root.right = findNote(inorder,rootIndex + 1,inEnd,postorder,postBegin + lenOfLeft,postEnd - 1);return root;}
}2023/10/10
题目(完成)105:从前序与中序遍历序列构造二叉树
class Solution {Map<Integer,Integer> map;public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();for(int i = 0;i < inorder.length;i++){map.put(inorder[i],i);}return findNote(inorder,0,inorder.length,preorder,0,preorder.length);}public TreeNode findNote(int[] inorder,int inBegin,int inEnd,int[] preorder,int preBegin,int preEnd){if(inBegin >= inEnd || preBegin >= preEnd) return null;int rootIndex = map.get(preorder[preBegin]);TreeNode root = new TreeNode(inorder[rootIndex]);int lenOfLeft = rootIndex - inBegin;root.left = findNote(inorder,inBegin,rootIndex,preorder,preBegin + 1,preBegin + lenOfLeft + 1);root.right = findNote(inorder,rootIndex + 1,inEnd,preorder,preBegin + lenOfLeft + 1,preEnd);return root;}
}2023/10/10
题目(完成)654：最大二叉树
class Solution {Map<Integer,Integer> map;public TreeNode constructMaximumBinaryTree(int[] nums) {map = new HashMap<>();for(int i = 0;i < nums.length;i++){map.put(nums[i],i);}return findNote(nums,0,nums.length);}public TreeNode findNote(int[] nums,int numsBegin,int numsEnd){if(numsBegin >= numsEnd) return null;int max = 0;for(int i = numsBegin;i < numsEnd;i++){max = Math.max(max,nums[i]);}// int max = (int) Collections.max(Arrays.asList(nums));int rootIndex = map.get(max);int lenOfLeft = rootIndex - numsBegin;TreeNode root = new TreeNode(max);if(lenOfLeft != 0){root.left = findNote(nums,numsBegin,numsBegin + lenOfLeft);}if(rootIndex + 1 != numsEnd){root.right = findNote(nums,rootIndex + 1,numsEnd);}return root;}
}题目(完成)617：合并二叉树
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null && root2 == null) return null;if(root1 == null) return root2;if(root2 == null) return root1;TreeNode root = new TreeNode(root1.val + root2.val);if(root1.left != null || root2.left != null){root.left = mergeTrees(root1.left,root2.left);}if(root1.right != null || root2.right != null){root.right = mergeTrees(root1.right,root2.right);}return root;}
}题目(完成)700：二叉搜索树中的搜索
二叉搜索树：根节点的值比其左子树的都要大，比其右子树的都要小，子树也是这样
class Solution {public TreeNode searchBST(TreeNode root, int val) {//方法1if(root == null || root.val == val){return root;}TreeNode left = searchBST(root.left,val);if(left != null){return left;}return searchBST(root.right,val);//方法2 利用二叉搜索树的特性if(root == null || root.val == val){return root;}if(val < root.val){return searchBST(root.left,val);}else{return searchBST(root.right,val);}}
}题目(未完成)98：验证二叉搜索树
//二叉搜索树中序遍历是有序的
class Solution {TreeNode pre;public boolean isValidBST(TreeNode root) {// if(value == -1) value = root.val;//记录根节点的值if(root == null){return true;}boolean left = isValidBST(root.left);// if(pre != null && root.val > pre.val){// return true;// }if(pre != null && root.val <= pre.val){return false;}pre = root;boolean right = isValidBST(root.right);return left && right;}
}题目(完成) 530：二叉搜索树的最小绝对差
//因为按照中序遍历二叉搜索树是单调递增的
class Solution {TreeNode pre;private int res = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(root == null){return 0;}getMinimumDifference(root.left);if(pre != null){res = Math.min(res,Math.abs(root.val - pre.val));}pre = root;getMinimumDifference(root.right);return res;}
}题目(未完成)501：二叉搜索树中的众数 经典题目
lass Solution {ArrayList<Integer> resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {resList = new ArrayList<>();maxCount = 0;count = 0;pre = null;findMode(root);int[] res = new int[resList.size()];for(int i = 0;i < resList.size();i++){res[i] = resList.get(i);}return res;}public void findModel(TreeNode root){if(root == null){return;}findModel(root.left);int rootValue = root.val;if(pre == null || rootValue != pre.val){count = 1;}else{count++;}if(count > maxCount){resList.clear();resList.add(rootValue);maxCount = count;}else if(count == maxCount){resList.add(rootValue);}pre = root;findModel(root.right);}
}题目(未完成)236：二叉树的最近公共祖先
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;if(root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(left != null && right != null){return root;}else if(left == null && right != null){return right;}else if(left != null && right == null){return left;}else{return null;}}
}题目(未完成)235：二叉搜索树的最近公共祖先
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;if(root.val > p.val && root.val > q.val){TreeNode left = lowestCommonAncestor(root.left , p ,q);if(left != null){return left;}}else if(root.val < p.val && root.val < q.val){TreeNode right = lowestCommonAncestor(root.right , p ,q);if(right != null){return right;}}return root;}
}题目(完成一半)701：二叉搜索树中的插入操作
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root == null){TreeNode res = new TreeNode(val);return res;}if(root.val > val){root.left = insertIntoBST(root.left, val);}else{root.right = insertIntoBST(root.right, val);}return root; }
}题目(完成一半)450：删除二叉搜索树中的节点
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if(root == null) return null;if(root.val == key){if(root.left == null && root.right == null){return null;}else if(root.left == null && root.right != null){return root.right;}else if(root.left != null && root.right == null){return root.left;}else{TreeNode res = root.right;while(res.left != null){res = res.left;}res.left = root.left;root = root.right;return root;}}if(root.val > key){root.left = deleteNode(root.left,key);}else{root.right = deleteNode(root.right,key);}return root;}
}题目(完成一半)669：修剪二叉搜索树
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null) return null;if(root.val < low){TreeNode right = trimBST(root.right,low,high);return right;}if(root.val > high){TreeNode left = trimBST(root.left,low,high);return left;}root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);return root;}
}题目(完成)108：将有序数组转换成二叉搜索树
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return test(nums,0,nums.length);}public TreeNode test(int[] nums,int Begin,int End){if(Begin >= End) return null;if(End - Begin == 1) return new TreeNode(nums[Begin]);int mid = Begin + (End - Begin) / 2;int midroot = nums[mid];TreeNode root = new TreeNode(midroot);// int lenOfLeft = mid - Begin;root.left = test(nums,Begin,mid);root.right = test(nums,mid + 1,End);return root;}
}题目(完成一半)538：把二叉搜索树转换为累加树
class Solution {// TreeNode pre;private int sum = 0;public TreeNode convertBST(TreeNode root) {if(root == null) return null;TreeNode right = convertBST(root.right);// if(pre != null){// root = new TreeNode(pre.val + root.val);// }// pre = root;sum += root.val;root.val = sum;TreeNode left = convertBST(root.left);return root;}
}2023/8/28——栈
题目(完成一半)1047：删除字符串中的所有相邻重复项
lass Solution {public String removeDuplicates(String s) {// Map<Character,Integer> count = new HashMap<Character,Integer>();// for(int i = 0; i < s.length();i++){// char ch = s.charAt(i);// count.put(ch,count.getOrDefault(ch,0) + 1);// }//两个相邻且相同的字母StringBuffer res = new StringBuffer();int top = -1;for(int i = 0; i < s.length(); i++){char ch = s.charAt(i);if(top >= 0 && ch == res.charAt(top)){res.deleteCharAt(top);top--;}else{res.append(ch);top++;}}return res.toString();}
}2023/8/29
题目(未完成)150：逆波兰表达式求值 我写的虽然复杂，但是在idea是可以的
class Solution {public int evalRPN(String[] tokens) {//默认只能出现 1 2 + 而不会是1 + 2int i = 0;int Current_Location = 0;int res = 0;while(i < tokens.length){// if(Math.abs(Integer.parseInt(tokens[i])) >= 0){if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){tokens[Current_Location] = tokens[i];i++;Current_Location++;}else{if(tokens[i] == "+"){tokens[Current_Location - 2] = String.valueOf(Integer.parseInt(tokens[Current_Location - 2]) + Integer.parseInt(tokens[Current_Location - 1]));Current_Location = Current_Location - 1;}else if(tokens[i] == "-"){tokens[Current_Location - 2] = String.valueOf(Integer.parseInt(tokens[Current_Location - 2]) - Integer.parseInt(tokens[Current_Location - 1]));Current_Location = Current_Location - 1;}else if(tokens[i] == "*"){tokens[Current_Location - 2] = String.valueOf(Integer.parseInt(tokens[Current_Location - 2]) * Integer.parseInt(tokens[Current_Location - 1]));Current_Location = Current_Location - 1;}else if(tokens[i] == "/"){tokens[Current_Location - 2] = String.valueOf(Integer.parseInt(tokens[Current_Location - 2]) / Integer.parseInt(tokens[Current_Location - 1]));Current_Location = Current_Location - 1;}i++;}}res = Integer.parseInt(tokens[Current_Location - 1]);return res;}
}class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<Integer>();int n = tokens.length;for (int i = 0; i < n; i++) {String token = tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 = stack.pop();int num1 = stack.pop();switch (token) {case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;default:}}}return stack.pop();}public boolean isNumber(String token) {return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));}
}详解pop（）和push（）方法_对象池的方法pop、push_我要变成万人迷的博客-CSDN博客
【Java】Java双端队列Deque使用详解_java deque_devnn的博客-CSDN博客
题目(未完成)239：滑动窗口最大值 我自己写的思路差不多 就是不熟悉栈的语法
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length - k + 1];if(k == 1) return nums;int i = 0;int j = 0;int times = 1;int var = -Integer.MAX_VALUE;int p = 0;while(j <= nums.length - 1){if(times <= k){if(j <= nums.length - 1 && nums[j] >= var) var = nums[j];if(j == nums.length - 1) res[p] = var;j++;times++;}else{times = 1;i++;j = i;res[p] = var;p++;var = -Integer.MAX_VALUE;}}return res;}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums == null || nums.length < 2) return nums;// 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序LinkedList<Integer> queue = new LinkedList();// 结果数组int[] result = new int[nums.length-k+1];// 遍历nums数组for(int i = 0;i < nums.length;i++){// 保证从大到小 如果前面数小则需要依次弹出，直至满足要求while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){queue.pollLast();}// 添加当前值对应的数组下标queue.addLast(i);// 判断当前队列中队首的值是否有效//这里的目的就是为了维护窗口的大小合理if(queue.peek() <= i-k){queue.poll(); } // 当窗口长度为k时 保存当前窗口中最大值if(i+1 >= k){result[i+1-k] = nums[queue.peek()];}}return result;}
}pollFirst(),pollLast(),peekFirst(),peekLast()_记录菌的博客-CSDN博客
题目(完成)347：前K个高频元素
class Solution {public int[] topKFrequent(int[] nums, int k) {int lengths = 0;// int m = 0;if(nums == null) return nums;Map<Integer,Integer> count = new HashMap<Integer,Integer>();for(int i = 0;i < nums.length;i++){count.put(nums[i],count.getOrDefault(nums[i],0) + 1);// if(count.get(nums[i]) >= k) lengths++;}// List<Integer> list = new ArrayList<Integer>(map.keySet());List<Integer> list = new ArrayList<Integer>(count.keySet());// Collections.sort(list,(a,b))->(map.get(b) - map.get(a));Collections.sort(list, (a, b) -> count.get(b) - count.get(a));int[] res = new int[k];for(int m = 0;m < k;m++){int temp = list.get(m);res[m] = temp;}// for(Map.Entry<Integer,Integer> entry : count.entrySet()){// int key = entry.getKey();// int value = entry.getValue();// if(value >= k)// res[m] = key;// m++;// }// for(int i = 0;i < nums.length;i++){// if(count.get(nums[i]) >= k) res[m] = nums[i];// m++;// }return res;}
}哈希表及其基本操作：
Java数据结构---HashMap（哈希表及其基本操作）（含hashset）_Cloudeeeee的博客-CSDN博客
2023/10/31——回溯
题目(未完成)77：组合
class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1);return result;}public void backtracking(int n,int k,int startIndex){if(path.size == k){result.add(path);return;}for(int i = startIndex;i <= n;i++){path.add(i);backtracking(n,k,i + 1);path.removeLast();}}
}剪枝优化
class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return result;}/*** 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex* @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。*/private void combineHelper(int n, int k, int startIndex){//终止条件if (path.size() == k){result.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){path.add(i);combineHelper(n, k, i + 1);path.removeLast();}}
}题目(完成)216：组合总和3
class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();int res = 0;public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k,n,1);return result;}public void backtracking(int k,int n,int startIndex){if(res > n) return;if(path.size() == k){if(res == n){result.add(new LinkedList<>(path));}return;// res = res - path.getLast();}for(int i = startIndex; i <= 9;i++){path.add(i);res += i;backtracking(k,n,i + 1);path.removeLast();res -= i;}}
}题目(完成)17：电话号码的字母组合
class Solution {List<String> res = new ArrayList<>();String [] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0){return res;}// String [] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};backtracking(digits,0);return res;}StringBuilder sb = new StringBuilder();public void backtracking(String digits,int startIndex){if(sb.length() == digits.length()){res.add(sb.toString());return;}String str = numString[digits.charAt(startIndex) - '0'];// numString[temp] //"abc";for(int i = 0;i <= str.length() - 1;i++){sb.append(str.charAt(i));backtracking(digits,startIndex + 1);sb.deleteCharAt(sb.length() - 1);}}
}题目(完成一半)39:组合总和
组合是无序的
class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();int temp = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates , target,0);return res;}public void backtracking(int[] candidates,int target,int idx){if(temp > target){return;}else if(target == temp){res.add(new LinkedList<>(path));}for(int i = idx;i < candidates.length;i++){path.add(candidates[i]);temp += candidates[i];backtracking(candidates,target,i);temp -= candidates[i];path.removeLast();}}
}题目(未完成)40：组合总和2 树层剪枝，树枝剪枝
Arrays.fill(used_test,false);
class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();int temp = 0;boolean[] used_test;public List<List<Integer>> combinationSum2(int[] candidates, int target) {used_test = new boolean[candidates.length];Arrays.fill(used_test,false);Arrays.sort(candidates);backtracking(candidates , target,0);return res;}public void backtracking(int[] candidates,int target,int idx){if(temp > target){return;}else if(target == temp){res.add(new LinkedList<>(path));}for(int i = idx;i < candidates.length;i++){if(i > 0 && candidates[i] == candidates[i - 1] && !used_test[i - 1]){continue;}path.add(candidates[i]);used_test[i] = true;temp += candidates[i];backtracking(candidates,target,i + 1);used_test[i] = false;temp -= candidates[i];path.removeLast();}}
}题目 (未完成)131：分割回文串
class Solution {List<List<String>> lists = new ArrayList<>();Deque<String> deque = new LinkedList<>();public List<List<String>> partition(String s) {backtracking(s,0);return lists;}public void backtracking(String s,int startIndex){if(startIndex >= s.length){lists.add(new ArrayList(deque));return;}for(int i = startIndex;i < s.length(); i++){if(isPalindrome(s,startIndex,i)){String str = s.substring(startIndex,i + 1);deque.addLast(str);}else{continue;}backtracking(s,i + 1);deque.removeLast();}}private boolean isPalindrome(String s,int startIndex,int end){for(int i = startIndex,j = end; i < j;i++,j--){if(s.charAt(i) != s.charAt(j)){return false;}}return true;}
}题目(完成)78:子集
class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {backtracking(nums , 0);return res;}public void backtracking(int[] nums,int startIndex){res.add(new ArrayList<>(path));if(startIndex == nums.length){return;}for(int i = startIndex;i < nums.length;i++){path.add(nums[i]);backtracking(nums,i + 1);path.removeLast();}}
}题目(完成)90：子集2
class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used_test;public List<List<Integer>> subsetsWithDup(int[] nums) {used_test = new boolean[nums.length];Arrays.fill(used_test,false);Arrays.sort(nums);backtracking(nums , 0);return res;}public void backtracking(int[] nums,int startIndex){res.add(new ArrayList<>(path));if(startIndex == nums.length){return;}for(int i = startIndex;i < nums.length;i++){if(i > 0 && nums[i] == nums[i - 1] && !used_test[i - 1]){continue;}path.add(nums[i]);used_test[i] = true;backtracking(nums,i + 1);used_test[i] = false;path.removeLast();}}
}题目(未完成)491：递增子序列
class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums , 0);return res;}public void backtracking(int[] nums,int startIndex){if(path.size() >= 2) res.add(new ArrayList<>(path));HashSet<Integer> hs = new HashSet<>();for(int i = startIndex;i < nums.length;i++){if(!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i])) continue;hs.add(nums[i]);path.add(nums[i]);backtracking(nums.i + 1);path.remove(path.size() - 1);}}
}题目(完成)46：全排列
class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used_test;public List<List<Integer>> permute(int[] nums) {used_test = new boolean[nums.length];Arrays.fill(used_test,false);backtracking(nums,0);return res;}public void backtracking(int[] nums, int startIndex){if(path.size() == nums.length) res.add(new ArrayList<>(path));for(int i = startIndex;i < nums.length;i++){if(used_test[i]) continue;used_test[i] = true;path.add(nums[i]);backtracking(nums,0);used_test[i] = false;path.remove(path.size() - 1);}}
}题目(完成)47:全排列2
class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used_test;public List<List<Integer>> permuteUnique(int[] nums) {used_test = new boolean[nums.length];Arrays.sort(nums);Arrays.fill(used_test,false);backtracking(nums,0);return res;}public void backtracking(int[] nums, int startIndex){if(path.size() == nums.length) res.add(new ArrayList<>(path));for(int i = startIndex;i < nums.length;i++){if(i > 0 && nums[i] == nums[i - 1] && !used_test[i - 1] || used_test[i]) continue;// if() continue;used_test[i] = true;path.add(nums[i]);backtracking(nums,0);used_test[i] = false;path.remove(path.size() - 1);}}
}题目(未完成)51：N皇后
class Solution {List<List<String>> res = new ArrayList<>();// LinkedList<String>> path = new LinkedList<>();public List<List<String>> solveNQueens(int n) {char[][] chessboard = new char[n][n];for(char c : chessboard){Arrays.fill(c,'.');}backtracking(n,0,chessboard);return res;}public void backtracking(int n,int row,char[][] chessboard){if(row == n){res.add(Array2List(chessboard));return;}for(int col = 0;col < n;col++){if(isValid(row,col,n,chessboard)){chessboard[row][col] = 'Q';backtracking(n,row + 1;chessboard);chessboard[row][col] = '.';}}}public List Array2List(char[][] chessboard){List<String> list = new ArrayList<>();for(char[] c : chessboard){list.add(String.copyValueOf(c));}return list;}public boolean isValid(int row,int col,int n,char[][] chessboard){for(int i = 0;i < row;i++){if(chessboard[i][col] == 'Q'){return false;}}for(int i = row - 1,j = col - 1;i >= 0 && j >= 0;i--,j--){if(chessboard[i][j] == 'Q'){return false;}}for(int i = row - 1,j = col + 1;i >= 0 && j <= n - 1;i--,j++){if(chessboard[i][j] = 'Q'){return false;}}return true;}
}题目(未完成)37：解数独
class Solution {public void solveSudoku(char[][] board) {solveSudokuHelper(board);}private boolean solveSudokuHelper(char[][] board){//「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，// 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」for (int i = 0; i < 9; i++){ // 遍历行for (int j = 0; j < 9; j++){ // 遍历列if (board[i][j] != '.'){ // 跳过原始数字continue;}for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适if (isValidSudoku(i, j, k, board)){board[i][j] = k;if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回return true;}board[i][j] = '.';}}// 9个数都试完了，都不行，那么就返回falsereturn false;// 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！// 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」}}// 遍历完没有返回false，说明找到了合适棋盘位置了return true;}/*** 判断棋盘是否合法有如下三个维度:* 同行是否重复* 同列是否重复* 9宫格里是否重复*/private boolean isValidSudoku(int row, int col, char val, char[][] board){// 同行是否重复for (int i = 0; i < 9; i++){if (board[row][i] == val){return false;}}// 同列是否重复for (int j = 0; j < 9; j++){if (board[j][col] == val){return false;}}// 9宫格里是否重复int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++){for (int j = startCol; j < startCol + 3; j++){if (board[i][j] == val){return false;}}}return true;}
}更多推荐
力扣做题之旅
发布评论