赞
踩
- 我的解答:
- 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
我的解答(二刷):
- 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 4
- int 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
我的解答:
- 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
题目中若要求算法的时间复杂度是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
- 我的解答
- 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;
- }
-
- }
- //如果所有位都是进位,则长度+1
- digits= new int[digits.length + 1];
- digits[0] = 1;
- return digits;
- }

2022/12/9
- 我的解答
- 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
- 答案
- 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
- 我的解答
- 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;
- }
- };

异或运算有两种特性:
- class Solution {
- public int singleNumber(int[] nums) {
- int result = 0;
- for(int num:nums){
- result ^=num;
- }
- return result;
- }
- }
2023/3/27
- 参考答案
- 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
sort(nums.begin(),nums.end());
- class Solution {
- public int majorityElement(int[] nums) {
- Arrays.sort(nums);
- return(nums[(nums.length)/2]);
- }
- }
Java中的排序函数:Arrays.sort(数组名)
- 参考答案
- 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
- 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
- 我的解答
- 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
我的解答
- 我的解答
- 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
- 暴力解法
- 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
对题目和函数的理解没到位
- 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
- 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
- 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
- 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
- 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;
- }
-
- }

- 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
- class Solution {
- public List<Integer> findDisappearedNumbers(int[] nums) {
- Arrays.sort(nums);
- // Set<Integer> set = new Hashset<Integer>();
- Set<Integer> set = new HashSet<Integer>();
- //根据题意数组中第一个元素一定是1
- int 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;
- }
- }
-

答案的两种思维都需要好好学习一下
- 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
- 自己的思路
- 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;
-
-
- }
- }

- 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
- 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
- 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;
-
- }
- }
- 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
- 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的数据类型
- //解法一 我的解答
- 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
- 我的解答
- 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;
- }
- }
-
-

二分查找没理解好
求数组所有元素之和: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博客
- 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
- 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);
- 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
- //答案
- 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,太复杂了,重新做的时候好好想一想,其实是可以想出来的
- 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;
- }
- }
傻逼题目看都看不懂
- 自己做的,有瑕疵
- 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'){
- //查找上一个是不是X
- continue;//强制进入下一次循环
- }else if(j>0 &&board[i][j-1] == 'X'){
- //查找左边一个是不是X
- continue;
- }else{
- count++;
- }
- }
- }
- }
- return count;
- }
- }

其实也不是做不出来,思维其实很像了,但是还是差一点
2023/4/25
- //我的解答
- 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;
- // }
-
- //arraycopy
- if(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.net)
2023/4/27
- 我的解答
- 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;
-
- }
- }


- 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
- 我的解答
- 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;
- }
- }

- 我的解答 思路想错了
- 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
- 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
只是看懂了答案,但是掌握的很不牢固
2023/5/1
- 我的解答
- 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
- 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];
- }
- }
-
- }
- }


和官方的思路不一样
- 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;
- }
- }

第二种解法更重要
- 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
- 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
- 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); //取出来了f
- for(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) //特殊情况1
- return "";
- 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("")) //特殊情况2
- return ans;
- }
- return ans;
- }
- }

注意处理特殊情况
String[] strs = {} strs.length() = 0;
String[] strs = {""} strs.length() = 1;
- 我写的
- 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
- 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;
- }
- }

- //解法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--;
- }
- }
- }

- 我写的
- 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
- 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():删除某个位置的字符
- //有点像原地修改
- 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博客
- 我写的
- 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 = -1
- if(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
- 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;
- }
- }


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

- 我写的
- 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
- 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
- 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 3
- int 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
- 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;
- }
- }

- 我写的
- 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;
- }
- }

- 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
这个题具体解析推导过程没理解,直接记高手答案
- 自己写的 垃圾
- 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
- 我写的
- 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
- 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博客
- 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
- 我写的
- 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
- 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。
- class Solution {
- public String complexNumberMultiply(String num1, String num2) {
- // a + bi c + di
- //(ac - bd) + (ad + bc)i
- StringBuilder 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
- 我写的
- 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
- 我写的
- 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+x
- int 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
- 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
我和三叶姐的思路是一模一样的
- 我写的
- 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
- 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;
- }
- }

- 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
- 我写的 又臭又长
- 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
- 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
- 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
- 我写的
- 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;
- }
- }

类似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() && t.compareTo(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 a.compareTo(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.com)
Collections.sort(list, (a,b)->{
if (a.length() != b.length()) return b.length() - a.length();
return a.compareTo(b);
});
* 升序排的话就是第一个参数.compareTo(第二个参数);
* 降序排的话就是第二个参数.compareTo(第一个参数);
b.length() - a.length() 倒叙 a.length() - b.length() 正叙
2023/6/28
- class Solution {
- public int findLUSlength(String a, String b) {
- return a.equals(b) ? -1 : Math.max(a.length(), b.length());
- }
- }
当两字符串不同时,我们总能选择长度不是最小的字符串作为答案,而当两字符串相同时,我们无法找到特殊序列。
2023/7/9
- 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;
- }
-
- }
- //如果所有位都是进位,则长度+1
- digits= 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
- 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
- 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
- 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();
-
- }
- }

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

java中map的key是有序的,因为其底层实现逻辑是二叉平衡搜索树
深度优先法则:前中后序遍历
广度优先法则:层序遍历
深度: 二叉树中任意一个节点到根节点的距离 从上往下计数 用前序遍历
高度:二叉树中任意一个节点到叶子节点的距离 从下往上计数 用后序遍历
叶子节点:自己下面不再连接有节点的节点
二叉搜索树:根节点的值比其左子树的都要大,比其右子树的都要小,子树也是这样
二叉搜索树按照中序遍历的顺序得到的结果是单调递增的
- //递归法
- 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;
- }
- }

- //递归法
- 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);
访问顺序和处理顺序不同:先访问根节点,但是要从下面的子节点开始处理
- //递归法
- 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
- 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
- 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;
- }
- }

注释的部分是我想的,不得行,没有仔细审题,理解题目意思
- 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
- 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
- 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;
- }
- }

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

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

解题关键:根节点的高度就是这颗二叉树的最大深度
想不通的话就把代码写全,方便理解
- //层序遍历
- 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--;
- }
- }

- 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
- 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
什么样的题目只能采用后序遍历:需要收集左右孩子的信息向上一层返回
- 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;
- }
- }

- 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;
- }
- }
- //层序遍历
- 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
- 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
- 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
- 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
两个代码的逻辑一样,但是第一个不知道为什么有的题目通不过
- 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 一定都是 true
- if (s == null) return false; // 这里 t 一定不为 null, 只要 s 为 null,肯定是 false
- return 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
- 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
- //迭代
- 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
- //用累加再比的话,会比较麻烦
- //累减会好一些
- 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;
- }
- }

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

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

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

二叉搜索树:根节点的值比其左子树的都要大,比其右子树的都要小,子树也是这样
- class Solution {
- public TreeNode searchBST(TreeNode root, int val) {
- //方法1
- if(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);
- }
-
- }
- }

- //二叉搜索树中序遍历是有序的
- 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;
- }
- }

- //因为按照中序遍历二叉搜索树是单调递增的
- 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;
- }
- }

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

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

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

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

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

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

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

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

- 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
- class Solution {
- public int evalRPN(String[] tokens) {
- //默认只能出现 1 2 + 而不会是1 + 2
- int 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博客
- 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博客
- 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博客
- 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();
- }
- }
- }

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

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

组合是无序的
- 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();
- }
- }
- }

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

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

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

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

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

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

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

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

- 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个数都试完了,都不行,那么就返回false
- return 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;
- }
- }

- class Solution {
- public int wiggleMaxLength(int[] nums) {
- if (nums.length <= 1) {
- return nums.length;
- }
- //当前差值
- int curDiff = 0;
- //上一个差值
- int preDiff = 0;
- int count = 1;
- for (int i = 1; i < nums.length; i++) {
- //得到当前差值
- curDiff = nums[i] - nums[i - 1];
- //如果当前差值和上一个差值为一正一负
- //等于0的情况表示初始时的preDiff
- if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
- count++;
- preDiff = curDiff;
- }
- }
- return count;
- }
- }

- class Solution {
- public int maxSubArray(int[] nums) {
- int res = - Integer.MAX_VALUE;
- int i = 0;
- int max_res = - Integer.MAX_VALUE;
- while(i < nums.length){
- if(res < 0 && nums[i] > 0){
- res = nums[i];
- }else if(res <= 0 && nums[i] <= 0){
- res = Math.max(res,nums[i]);
- }else{
- res = res + nums[i];
- }
- max_res = Math.max(max_res,res);
- i++;
- }
- return max_res;
-
- }
- }

- class Solution {
- public int maxProfit(int[] prices) {
- int i = 0;
- int Purchase = Integer.MAX_VALUE;
- int Selloff = 0;
- int res = 0;
- while(i < prices.length){
- if(prices[i] < Purchase){
- Purchase = prices[i];
- }
- if(prices[i] > Purchase){
- res += prices[i] - Purchase;
- Purchase = prices[i];
- }
- i++;
- }
- return res;
- }
- }

- class Solution {
- public boolean canJump(int[] nums) {
- if(nums.length == 1){
- return true;
- }
-
- int coverRange = 0;
- for(int i = 0;i <= coverRange;i++){
- coverRange = Math.max(coverRange,i + nums[i]);
- if(coverRange >= nums.length - 1){
- return true;
- }
- }
- return false;
- }
- }

- class Solution {
- public int jump(int[] nums) {
- if (nums == null || nums.length == 0 || nums.length == 1) {
- return 0;
- }
- //记录跳跃的次数
- int count=0;
- //当前的覆盖最大区域
- int curDistance = 0;
- //最大的覆盖区域
- int maxDistance = 0;
- for (int i = 0; i < nums.length; i++) {
- //在可覆盖区域内更新最大的覆盖区域
- maxDistance = Math.max(maxDistance,i+nums[i]);
- //说明当前一步,再跳一步就到达了末尾
- if (maxDistance>=nums.length-1){
- count++;
- break;
- }
- //走到当前覆盖的最大区域时,更新下一步可达的最大区域
- if (i==curDistance){
- curDistance = maxDistance;
- count++;
- }
- }
- return count;
- }
- }

- class Solution {
- public int largestSumAfterKNegations(int[] nums, int k) {
- int count = 0;
- int sum = 0;
- while(count < k){
- Arrays.sort(nums);
- nums[0] = - nums[0];
- count++;
- }
-
- for(int res :nums){
- sum += res;
- }
-
- return sum;
- }
- }

- class Solution {
- public int canCompleteCircuit(int[] gas, int[] cost) {
- int curSum = 0;
- int totalSum = 0;
- int index = 0;
- for (int i = 0; i < gas.length; i++) {
- curSum += gas[i] - cost[i];
- totalSum += gas[i] - cost[i];
- if (curSum < 0) {
- index = (i + 1) % gas.length ;
- curSum = 0;
- }
- }
- if (totalSum < 0) return -1;
- return index;
- }
- }

- //我写的 思路不对
- class Solution {
- public int candy(int[] ratings) {
- int res = 0;
- int cur = 0;
- int bef = -1;
- for(int i = 0;i < ratings.length;i++){
- if(ratings[i] > bef){
- cur++;
- }else if(ratings[i] == bef){
- if(cur > 1){
- cur--;
- }
- }else{
- cur--;
- if(0 >= cur){
- cur = 1;
- res++;
- }
- }
- res += cur;
- bef = ratings[i];
- }
- return res;
- }
- }
- //答案
- class Solution {
- /**
- 分两个阶段
- 1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 1
- 2、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大
- */
- public int candy(int[] ratings) {
- int len = ratings.length;
- int[] candyVec = new int[len];
- candyVec[0] = 1;
- for (int i = 1; i < len; i++) {
- candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
- }
-
- for (int i = len - 2; i >= 0; i--) {
- if (ratings[i] > ratings[i + 1]) {
- candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
- }
- }
-
- int ans = 0;
- for (int num : candyVec) {
- ans += num;
- }
- return ans;
- }
- }

- class Solution {
- public boolean lemonadeChange(int[] bills) {
- if(bills[0] != 5) return false;
- int five_dollar = 0;
- int ten_dollar = 0;
- for(int i = 0;i < bills.length;i++){
- if(bills[i] == 5){
- five_dollar++;
- }else if(bills[i] == 10){
- ten_dollar++;
- five_dollar--;
- if(five_dollar < 0) return false;
- }else{
- if(ten_dollar > 0){
- ten_dollar--;
- five_dollar--;
- if(five_dollar < 0) return false;
- }else{
- if(five_dollar < 3){
- return false;
- }else{
- five_dollar = five_dollar - 3;
- }
- }
- }
-
- }
-
- return true;
- }
- }

- class Solution {
- public int[][] reconstructQueue(int[][] people) {
- // 身高从大到小排(身高相同k小的站前面)
- Arrays.sort(people, (a, b) -> {
- if (a[0] == b[0]) return a[1] - b[1]; // a - b 是升序排列,故在a[0] == b[0]的狀況下,會根據k值升序排列
- return b[0] - a[0]; //b - a 是降序排列,在a[0] != b[0],的狀況會根據h值降序排列
- });
-
- LinkedList<int[]> que = new LinkedList<>();
-
- for (int[] p : people) {
- que.add(p[1],p); //Linkedlist.add(index, value),會將value插入到指定index裡。
- }
-
- return que.toArray(new int[people.length][]);
- }
- }

二维数组排序
LinkedList.add()
Java LinkedList add()用法及代码示例 - 纯净天空 (vimsky.com)
- class Solution {
- public int findMinArrowShots(int[][] points) {
- int res = 1;
- // int Launch_position = 0;
- Arrays.sort(points,(a,b) -> Integer.compare(a[0],b[0]));
-
- for(int i = 1;i < points.length;i++){
- if(points[i][0] > points[i - 1][1]){
- res++;
- }else{
- points[i][1] = Math.min(points[i][1],points[i - 1][1]);
- }
- }
- // while(i < points.length){
- // Launch_position = points[i - 1][1];
- // if(Launch_position >= points[i][0] && points[i][1] >= Launch_position){
- // if(i + 1 < points.length){
- // i++;
- // }else{
- // res++;
- // i++;
- // }
-
- // }else{
- // res++;
- // i++;
- // }
- // }
- // res++;
- return res;
- }
- }

- class Solution {
- public int eraseOverlapIntervals(int[][] intervals) {
- Arrays.sort(intervals,(a,b) -> {
- if(a[0] == b[0]) return a[1] - b[1];
- return a[0] - b[0];
- });
- int count = 0;
- for(int i = 1; i < intervals.length;i++){
- if(intervals[i][0] == intervals[i - 1][0]){
- intervals[i][1] = Math.min(intervals[i][1],intervals[i - 1][1]);
- count++;
- }else{
- if(intervals[i][0] > intervals[i - 1][0] && intervals[i][0] < intervals[i - 1][1]){
- count++;
- intervals[i][0] = Math.max(intervals[i][0],intervals[i - 1][0]);
- intervals[i][1] = Math.min(intervals[i][1],intervals[i - 1][1]);
- }
- }
- }
- return count;
- }
- }

- class Solution {
- public List<Integer> partitionLabels(String s) {
- List<Integer> list = new LinkedList<>();
- int[] edge = new int[26];
- char[] chars = S.toCharArray();
- for(int i = 0;i < chars.length;i++){
- edge[chars[i] - 'a'] = i;
- }
- int idx = 0;
- int last = -1;
- for(int i = 0;i < chars.length;i++){
- idx = Math.max(idx,edge[chars[i] - 'a']);
- if(i == idx){
- list.add(i - last);
- last = i;
- }
- }
- return list;
- }
- }

- class Solution {
- public int[][] merge(int[][] intervals) {
- List<int[]> res = new LinkedList<>();
- Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
- // Arraysort(intervals,(a,b) -> {
- // if(a[0] == b[0]) return a[1] - b[1];
- // return a[0] - b[0];
- // });
- if(intervals.length == 1){
- res.add(intervals[0]);
- return res.toArray(new int[res.size()][]);
- }
- // if(intervals.length > 1 && intervals[1][0] > intervals[0][1]){
- // res.add(intervals[0]);
- // }
- for(int i = 1;i < intervals.length;i++){
- if(intervals[i][0] == intervals[i - 1][0]){
- intervals[i][1] = Math.max(intervals[i][1],intervals[i - 1][1]);
- // if(i == intervals.length - 1){
- // res.add(intervals[i]);
- // }
- }else if(intervals[i][0] > intervals[i - 1][0] && intervals[i - 1][1] >= intervals[i][0]){
- intervals[i][0] = Math.min(intervals[i][0],intervals[i - 1][0]);
- intervals[i][1] = Math.max(intervals[i][1],intervals[i - 1][1]);
- // if(i == intervals.length - 1){
- // res.add(intervals[i]);
- // }
- }else{
- res.add(intervals[i - 1]);
-
- }
- if(i == intervals.length - 1){
- res.add(intervals[i]);
- }
- }
- return res.toArray(new int[res.size()][]);
- // return res;
-
- }
- }

- class Solution {
- public int monotoneIncreasingDigits(int n) {
- String s = String.valueOf(n);
- char[] chars = s.toCharArray();
- int start = s.length();
- for (int i = s.length() - 2; i >= 0; i--) {
- if (chars[i] > chars[i + 1]) {
- chars[i]--;
- start = i+1;
- }
- }
- for (int i = start; i < s.length(); i++) {
- chars[i] = '9';
- }
- return Integer.parseInt(String.valueOf(chars));
- }
- }

- class Solution {
- public int fib(int n) {
- int a = 0;
- int b = 1;
- if(n == 0) return a;
- if(n == 1) return b;
- int temp = 0;
- for(int i = 0;i <= n - 2;i++){
- temp = b;
- b = a + b;
- a = temp;
- }
- return b;
- }
- }
- // 用变量记录代替数组
- class Solution {
- public int climbStairs(int n) {
- if(n <= 2) return n;
- int a = 1, b = 2, sum = 0;
-
- for(int i = 3; i <= n; i++){
- sum = a + b; // f(i - 1) + f(i - 2)
- a = b; // 记录f(i - 1),即下一轮的f(i - 2)
- b = sum; // 记录f(i),即下一轮的f(i - 1)
- }
- return b;
- }
- }
- class Solution {
- public int minCostClimbingStairs(int[] cost) {
- int len = cost.length;
- int[] dp = new int[len + 1];
-
- // 从下标为 0 或下标为 1 的台阶开始,因此支付费用为0
- dp[0] = 0;
- dp[1] = 0;
-
- // 计算到达每一层台阶的最小费用
- for (int i = 2; i <= len; i++) {
- dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
- }
-
- return dp[len];
- }
- }

- class Solution {
- public int removeElement(int[] nums, int val) {
- int res = nums.length;
- int i = 0;
- int j = nums.length - 1;
- int temp = -1;
-
-
- while(i <= j){
- if(nums[i] == val){
-
- while(nums[j] == val){
- j--;
- res--;
- if(i > j || res <= 0){
- break;
- }
- }
- if(i > j || res <= 0){
- break;
- }else{
- temp = nums[i];
- nums[i] = nums[j];
- nums[j] = temp;
- j--;
- res--;
-
- }
- }
- i++;
- }
- return res;
- }
- }

- class Solution {
- public int uniquePaths(int m, int n) {
- //确定dp数组及其下标的含义
- int[][] dp = new int[m][n];
-
- for(int i = 0; i < m;i++){
- dp[i][0] = 1;
- }
- for(int j = 0;j < n;j++){
- dp[0][j] = 1;
- }
- for(int i = 1;i < m;i++){
- for(int j = 1; j < n;j++){
- dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
- }
- }
-
- return dp[m - 1][n - 1];
- }
- }

- class Solution {
- public int uniquePathsWithObstacles(int[][] obstacleGrid) {
- int m = obstacleGrid.length;
- int n = obstacleGrid[0].length;
-
- int[][] dp = new int[m][n];
-
- for(int i = 0;i < m;i++){
- if(i > 0){
- if(obstacleGrid[i][0] == 1 || dp[i - 1][0] == 0){
- dp[i][0] = 0;
- }else{
- dp[i][0] = 1;
- }
- }else{
- if(obstacleGrid[i][0] == 1){
- dp[i][0] = 0;
- }else{
- dp[i][0] = 1;
- }
-
- }
-
- }
-
- for(int j = 0;j < n;j++){
- if(j > 0){
- if(obstacleGrid[0][j] == 1 || dp[0][j - 1] == 0){
- dp[0][j] = 0;
- }else{
- dp[0][j] = 1;
- }
- }else{
- if(obstacleGrid[0][j] == 1){
- dp[0][j] = 0;
- }else{
- dp[0][j] = 1;
- }
-
- }
- }
-
- for(int i = 1;i < m;i++){
- for(int j = 1;j < n;j++){
- if(obstacleGrid[i][j] == 1){
- dp[i][j] = 0;
- }else{
- dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
- }
-
- }
- }
-
- return dp[m - 1][n - 1];
-
- }
- }

- class Solution {
- public int integerBreak(int n) {
- //dp[i] 为正整数 i 拆分后的结果的最大乘积
- int[] dp = new int[n+1];
- dp[2] = 1;
- for(int i = 3; i <= n; i++) {
- for(int j = 1; j <= i-j; j++) {
- // 这里的 j 其实最大值为 i-j,再大只不过是重复而已,
- //并且,在本题中,我们分析 dp[0], dp[1]都是无意义的,
- //j 最大到 i-j,就不会用到 dp[0]与dp[1]
- dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
- // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ,再相乘
- //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
- }
- }
- return dp[n];
- }
- }

必须把dp定义为答案,然后找递推关系,反推到起点,然后双循环搞定


01背包问题本质还是需要通过最右下角的值求得最后的结果,如果是一维数组,就是最右边的值

- class Solution {
- public boolean canPartition(int[] nums) {
- if(nums == null || nums.length == 0) return false;
- int n = nums.length;
- int sum = 0;
- for(int num : nums){
- sum += num;
- }
-
- if(sum % 2 != 0) return false;
- int target = sum / 2;
- int[] dp = new int[target + 1];
-
- for(int i = 0; i < n;i++){
- for(int j = target;j >= nums[i];j--){
- dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
- }
-
- if(dp[target] == target) return true;
- }
- return dp[target] == target;
-
- }
- }

- class Solution {
- public int lastStoneWeightII(int[] stones) {
- int sum = 0;
- for(int num : stones){
- sum += num;
- }
-
- int target = sum / 2;
-
- int[] dp = new int[target + 1];
- for(int i = 0; i < stones.length;i++){
- for(int j = target; j >= stones[i];j--){
- dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
- }
- }
-
- return sum - 2 * dp[target];
-
- }
- }

- class Solution {
- public int findTargetSumWays(int[] nums, int target) {
- int sum = 0;
- for(int i = 0; i < nums.length;i++) sum += nums[i];
- if(target < 0 && sum < - target) return 0;
- if((target + sum) % 2 != 0) return 0;
- int size = (target + sum) / 2;
- if(size < 0) size = -size;
- int[] dp = new int[size + 1];
- dp[0] = 1;
- for(int i = 0;i < nums.length;i++){
- for(int j = size;j >= num[i];j--){
- dp[j] += dp[j - nums[i]];
- }
- }
- return dp[size];
- }
- }

- class Solution {
- public int findMaxForm(String[] strs, int m, int n) {
- //dp[i][j]表示i个0和j个1时的最大子集
- int[][] dp = new int[m + 1][n + 1];
- int oneNum, zeroNum;
- for (String str : strs) {
- oneNum = 0;
- zeroNum = 0;
- for (char ch : str.toCharArray()) {
- if (ch == '0') {
- zeroNum++;
- } else {
- oneNum++;
- }
- }
- //倒序遍历
- for (int i = m; i >= zeroNum; i--) {
- for (int j = n; j >= oneNum; j--) {
- dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
- }
- }
- }
- return dp[m][n];
- }
- }

完全背包问题:求组合数,先遍历物品,再遍历背包;求排列数,先遍历背包,再遍历物品
- class Solution {
- public int coinChange(int[] coins, int amount) {
- //dp[j]数组的含义:装满容量大小为j的背包的最少物品为dp[j];
-
- int[] dp = new int[amount + 1];
-
- for(int k = 0;k < dp.length;k++){
- dp[k] = Integer.MAX_VALUE;
- }
-
- dp[0] = 0;
-
- for(int i = 0;i < coins.length;i++){
- for(int j = coins[i];j <= amount;j++){
- if(dp[j - coins[i]] != Integer.MAX_VALUE){
- dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
- }
-
- }
- }
- return dp[amount] == Integer.MAX_VALUE ? -1:dp[amount];
- }
- }

- class Solution {
- public int numSquares(int n) {
- //dp[i] 装满容量大小为i的背包,所需要的最少完全平方数的数量
- int[] dp = new int[n + 1];
-
- for(int k = 0;k < dp.length;k++){
- dp[k] = Integer.MAX_VALUE;
- }
-
- dp[0] = 0;
-
-
- for(int i = 1;i * i <= n;i++){
- for(int j = i * i;j <= n;j++){
- dp[j] = Math.min(dp[j],dp[j - i * i] + 1);
- }
- }
- return dp[n];
- }
- }

- class Solution {
- public boolean wordBreak(String s, List<String> wordDict) {
- HashSet<String> set = new HashSet<>(wordDict);
- boolean[] valid = new boolean[s.length() + 1];
- valid[0] = true;
-
- for (int i = 1; i <= s.length(); i++) {
- for (int j = 0; j < i && !valid[i]; j++) {
- if (set.contains(s.substring(j, i)) && valid[j]) {
- valid[i] = true;
- }
- }
- }
- return valid[s.length()];
- }
- }

- class Solution {
- public int rob(int[] nums) {
- //dp数组的含义:考虑下表i(包括i)以内的房屋,最多可以偷窃的金额为dp[i];
- if(nums == null || nums.length == 0) return 0;
- if(nums.length == 1) return nums[0];
- int[] dp = new int[nums.length];
-
- dp[0] = nums[0];
- dp[1] = Math.max(nums[0],nums[1]);
-
-
- for(int i = 2;i < nums.length;i++){
- dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);
- }
-
- return dp[nums.length - 1];
- }
- }

- class Solution {
- public int rob(int[] nums) {
- if (nums == null || nums.length == 0)
- return 0;
- int len = nums.length;
- if (len == 1)
- return nums[0];
- return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
- }
-
- int robAction(int[] nums, int start, int end) {
- int x = 0, y = 0, z = 0;
- for (int i = start; i < end; i++) {
- y = z;
- z = Math.max(y, x + nums[i]);
- x = y;
- }
- return z;
- }
- }

- class Solution {
- public int maxProfit(int[] prices) {
- if (prices == null || prices.length == 0) return 0;
- int length = prices.length;
- // dp[i][0]代表第i天持有股票的最大收益
- // dp[i][1]代表第i天不持有股票的最大收益
- int[][] dp = new int[length][2];
- int result = 0;
- dp[0][0] = -prices[0];
- dp[0][1] = 0;
- for (int i = 1; i < length; i++) {
- dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
- dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
- }
- return dp[length - 1][1];
- }
- }

- // 动态规划
- class Solution
- // 实现1:二维数组存储
- // 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储
- // 时间复杂度:O(n),空间复杂度:O(n)
- public int maxProfit(int[] prices) {
- int n = prices.length;
- int[][] dp = new int[n][2]; // 创建二维数组存储状态
- dp[0][0] = 0; // 初始状态
- dp[0][1] = -prices[0];
- for (int i = 1; i < n; ++i) {
- dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 第 i 天,没有股票
- dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 第 i 天,持有股票
- }
- return dp[n - 1][0]; // 卖出股票收益高于持有股票收益,因此取[0]
- }
- }

- // 版本一
- class Solution {
- public int maxProfit(int[] prices) {
- int len = prices.length;
- // 边界判断, 题目中 length >= 1, 所以可省去
- if (prices.length == 0) return 0;
-
- /*
- * 定义 5 种状态:
- * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
- */
- int[][] dp = new int[len][5];
- dp[0][1] = -prices[0];
- // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
- dp[0][3] = -prices[0];
-
- for (int i = 1; i < len; i++) {
- dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
- dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
- dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
- dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
- }
-
- return dp[len - 1][4];
- }
- }

- class Solution {
- public int maxProfit(int k, int[] prices) {
- if (prices.length == 0) return 0;
-
- // [天数][股票状态]
- // 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
- int len = prices.length;
- int[][] dp = new int[len][k*2 + 1];
-
- // dp数组的初始化, 与版本一同理
- for (int i = 1; i < k*2; i += 2) {
- dp[0][i] = -prices[0];
- }
-
- for (int i = 1; i < len; i++) {
- for (int j = 0; j < k*2 - 1; j += 2) {
- dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
- dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
- }
- }
- return dp[len - 1][k*2];
- }
- }

- class Solution {
- public int maxProfit(int[] prices) {
- int len = prices.length;
- int dp[][] = new int[len][4];
- dp[0][0] = -prices[0];
-
- for(int i = 1;i < len; i++){
- dp[i][0] = Math.max(Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]),dp[i - 1][3] - prices[i]);
- dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][3]);
- dp[i][2] = dp[i - 1][0] + prices[i];
- dp[i][3] = dp[i - 1][2];
- }
-
-
- return Math.max(Math.max(dp[len - 1][1],dp[len - 1][2]),dp[len - 1][3]);
-
- }
- }

- class Solution {
- public int maxProfit(int[] prices, int fee) {
- int n = prices.length;
- int[][] dp = new int[n][2];
- // 0 不持股
- // 1 持股
- dp[0][0] = 0;
- dp[0][1] = -prices[0];
-
-
- for(int i = 1; i < n;i++){
- dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
- dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
- }
-
- return dp[n - 1][0];
- }
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。