当前位置:   article > 正文

力扣做题之旅_if(abs(d24)+abs(d25)+abs(d26)<1,true(),false()

if(abs(d24)+abs(d25)+abs(d26)<1,true(),false()

2022/12/4——数组专题

题目(完成):1.两数之和

  1. 我的解答:
  2. class Solution {
  3. public:
  4. vector<int> twoSum(vector<int>& nums, int target) {
  5. int nums_len=end(nums)-begin(nums);
  6. int i,j;
  7. int result_sum;
  8. int result_numpy[2];
  9. for(i=0;i<nums_len;i++)
  10. {
  11. for(j=0;j<nums_len;j++)
  12. {
  13. result_sum=nums[i]+nums[j];
  14. if(result_sum==target&&i!=j){
  15. result_numpy[0]=i;
  16. result_numpy[0]=j;
  17. return {i,j};
  18. }
  19. }
  20. }
  21. return {i,j};
  22. }
  23. };

经验:

1.求数组长度

int nums_len=end(nums)-begin(nums)

2.嵌套for循环

3.定义数组:

int numpy1[5] = { 0,1,2,3,4 } //注意数组的表达形式{}
  1. //java
  2. class Solution {
  3. public int[] twoSum(int[] nums, int target) {
  4. int sums = 0 ;
  5. int []result = new int[2];
  6. for(int i = 0;i<nums.length;i++){
  7. for(int j = 0;j<nums.length;j++){
  8. if(nums[i]+nums[j]==target && i!=j){
  9. result[0]=i;
  10. result[1]=j;
  11. break;
  12. }
  13. }
  14. }
  15. return result;
  16. }
  17. }

2022/12/5

题目(未做出)26:删除有序数组中的重复项

我的解答(二刷):

  1. class Solution {
  2. public:
  3. int removeDuplicates(vector<int>& nums) {
  4. int i=1;
  5. int j=1;
  6. while(i<nums.size()){
  7. if(nums[j]!=nums[i-1]){
  8. i++;
  9. j++;
  10. }
  11. else{
  12. j++;
  13. if(nums[i-1]!=nums[j]){
  14. nums[i]=nums[j];
  15. i++;
  16. j=i;
  17. }
  18. }
  19. }
  20. return i;
  21. }
  22. };

答案解答(思维有进步,但是还不够)

  1. class Solution {
  2. public:
  3. // j
  4. // i
  5. // 0 1 2 1 2 2 3 4
  6. int removeDuplicates(vector<int>& nums) {
  7. int i = 1, j = 1;
  8. while(j < nums.size())
  9. {
  10. if(nums[i - 1] != nums[j])
  11. {
  12. nums[i] = nums[j];
  13. ++i;
  14. }
  15. ++j;
  16. }
  17. return i;
  18. }
  19. };

三刷做的答案和第一次做的答案一模一样 真服了

  1. class Solution {
  2. public int removeDuplicates(int[] nums) {
  3. int i = 1;
  4. int j = 1;
  5. while(j<nums.length){
  6. if(nums[i-1]!=nums[j]){
  7. nums[i]=nums[j];
  8. i++;
  9. //j=i;
  10. }
  11. else{
  12. j++;
  13. }
  14. }
  15. return i;
  16. }
  17. }

2022/12/6

题目(做出一半):27.移除元素

我的解答:

  1. class Solution {
  2. public:
  3. int removeElement(vector<int>& nums, int val) {
  4. int i;
  5. int j;
  6. int k;
  7. for(i=0;i<(nums.size())/2;i++){
  8. if(nums[i]==val){
  9. for(j=nums.size()-1;j>=(nums.size())/2;j--){
  10. if(nums[j]!=val){
  11. k=nums[i];
  12. nums[i]=nums[j];
  13. nums[j]=k;
  14. break;
  15. }
  16. }
  17. }
  18. }
  19. return i;
  20. }
  21. };

经验:

我的思路是用双指针分别从左右遍历,答案有相同的思路,但是我写的不太好。

第二次解答 依托答辩

  1. class Solution {
  2. public:
  3. int removeElement(vector<int>& nums, int val) {
  4. int i,j=1;
  5. int a=0;
  6. while(j<nums.size()){
  7. if(nums[i-1]!=val){
  8. i++;
  9. j++;
  10. }
  11. else{
  12. j++;
  13. if(nums[j]!=val){
  14. a=nums[i-1];
  15. nums[i-1]=nums[j];
  16. nums[j]=a;
  17. i++;
  18. j=i;
  19. }
  20. }
  21. }
  22. return i;
  23. }
  24. };

非常简单直接的解题思路

  1. class Solution {
  2. public:
  3. int removeElement(vector<int>& nums, int val) {
  4. int i;
  5. int j=0;
  6. for(i=0;i<nums.size();i++){
  7. if(nums[i]!=val){
  8. nums[j]=nums[i];
  9. j++;
  10. }
  11. }
  12. return j;
  13. }
  14. };

2022/12/7

题目(未做出):35.搜索插入位置

题目中若要求算法的时间复杂度是O(logn),那么这个算法基本上就是二分法。

我的解答:超时 第二次

  1. 我的解答
  2. class Solution {
  3. public:
  4. int searchInsert(vector<int>& nums, int target) {
  5. int i=0;
  6. int a;
  7. while(i<nums.size()){
  8. if(nums[i]<=target&&target<=nums[i+1]){
  9. if(nums[i]==target){
  10. a=i;
  11. }
  12. else if(nums[i+1]==target){
  13. a=i+1;
  14. }
  15. else{
  16. a=i+1;
  17. }
  18. }
  19. else{
  20. i++;
  21. }
  22. }
  23. return a;
  24. }
  25. };
  26. 答案
  27. class Solution {
  28. public:
  29. int searchInsert(vector<int>& nums, int target) {
  30. int left = 0;
  31. int right = nums.size()-1;
  32. int mid = 0;
  33. while(left <= right){
  34. mid = left + (right - left)/2;
  35. if(nums[mid] == target){
  36. return mid;
  37. }
  38. if(nums[mid] >target){
  39. right = mid-1;
  40. }
  41. else{
  42. left = mid+1;
  43. }
  44. }
  45. return left;
  46. }
  47. };

2022/12/8

题目(基本完成):66.加一

  1. 我的解答
  2. class Solution {
  3. public:
  4. vector<int> plusOne(vector<int>& digits) {
  5. int length=digits.size()-1;
  6. digits[length]++;
  7. int i=digits.size()-1;
  8. while(i>0){
  9. if(digits[i]==10){
  10. digits[i]=0;
  11. digits[i-1]++;
  12. }
  13. i--;
  14. }
  15. if(digits[0]==10){
  16. vector<int>ans(digits.size()+1);
  17. ans[0]=1;
  18. return ans;
  19. }
  20. return digits;
  21. }
  22. };

经验:

可以自己定义一个新的数组并返回;定义一个全为0的数组:

vector<int>ans(digits.size()+1);

二刷 和第一遍做的一模一样 服了 一点进步没有啊

  1. class Solution {
  2. public:
  3. vector<int> plusOne(vector<int>& digits) {
  4. int i = digits.size() - 1;
  5. digits[i]++;
  6. while(i>=0){
  7. if(digits[i]==10){
  8. digits[i]=0;
  9. digits[i-1]++;
  10. }
  11. i--;
  12. }
  13. return digits;
  14. }
  15. };
  1. class Solution {
  2. public int[] plusOne(int[] digits) {
  3. int n = digits.length -1;
  4. digits[n]++;
  5. while(n>0){
  6. if(digits[n]==10){
  7. digits[n]=0;
  8. digits[n-1]++;
  9. }
  10. n--;
  11. }
  12. if(digits[0]==10){
  13. int []result = new int[digits.length+1];
  14. result[0]=1;
  15. for(int j=1;j<n+1;j++){
  16. result[j]=0;
  17. }
  18. return result;
  19. }
  20. return digits;
  21. }
  22. }
  23. 更简洁的思维
  24. public int[] plusOne(int[] digits) {
  25. for (int i = digits.length - 1; i >= 0; i--) {
  26. if (digits[i] == 9) {
  27. digits[i] = 0;
  28. } else {
  29. digits[i] += 1;
  30. return digits;
  31. }
  32. }
  33. //如果所有位都是进位,则长度+1
  34. digits= new int[digits.length + 1];
  35. digits[0] = 1;
  36. return digits;
  37. }

2022/12/9

题目(超时):88.合并两个有序数组

  1. 我的解答
  2. class Solution {
  3. public:
  4. void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
  5. int i;
  6. int j=0;
  7. for(i=m;i<m+n;i++){
  8. nums1[i]=nums2[j];
  9. j++;
  10. }
  11. int k=m+n;
  12. int i_1;
  13. int j_1;
  14. int test;
  15. int times=0;
  16. while(k>2){
  17. for(i_1=0;i_1<k;i_1++){
  18. for(j_1=0;j_1<k;j_1++){
  19. if(nums1[i_1]>=nums1[j_1]){
  20. times++;
  21. }
  22. if(times==k){
  23. test=nums1[i_1];
  24. nums1[i_1]=nums1[k-1];
  25. nums1[k-1]=test;
  26. k--;
  27. // i_1=0;
  28. // j_1=0;
  29. }
  30. }
  31. }
  32. }
  33. }
  34. };
  35. 答案
  36. class Solution {
  37. public:
  38. void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
  39. int r=nums1.size();
  40. while(n>0){
  41. if(m>0&&nums1[m-1]>nums2[n-1]){
  42. nums1[r-1]=nums1[m-1];
  43. m--;
  44. r--;
  45. }
  46. else{
  47. nums1[r-1]=nums2[n-1];
  48. n--;
  49. r--;
  50. }
  51. }
  52. }
  53. };

经验:

1.感觉自己写的逻辑上应该没问题,但是超时了。

2.因为两个数组都是非递减顺序的,所以从后往前比较两个数组的值大小然后插入。

二刷 未作出 还不如第一次 好歹还有点思路


2022/12/10

题目(未做出):118.杨辉三角

  1. 答案
  2. class Solution {
  3. public:
  4. vector<vector<int>> generate(int numRows) {
  5. vector<vector<int>>nums(numRows);
  6. int i;
  7. int j;
  8. int m;
  9. for(i=0;i<numRows;i++){
  10. nums[i].resize(i+1);
  11. nums[i][i]=1;
  12. nums[i][0]=1;
  13. }
  14. for(m=2;m<numRows;m++){
  15. for(j=1;j<m;j++){
  16. nums[m][j]=nums[m-1][j-1]+nums[m-1][j];
  17. }
  18. }
  19. return nums;
  20. }
  21. };

经验:

1.nums.resize()

2.nums[i][j]


2023/2/15

题目(我感觉没问题,但是答案也没有类似的解答):136.只出现一次的数字

  1. 我的解答
  2. class Solution {
  3. public:
  4. int singleNumber(vector<int>& nums) {
  5. int i,j;
  6. int times=0;
  7. int a=0;
  8. for(i=0;i<nums.size();i++){
  9. for(j=0;j<nums.size();j++){
  10. if(nums[i]==nums[j]){
  11. times++;
  12. }
  13. }
  14. if(times==1){
  15. return nums[i];
  16. }
  17. }
  18. return 0;
  19. }
  20. };

异或运算有两种特性:

  • x ^ x = 0,任意相同数字 x 异或的结果为 0;
  • x ^ 0 = x,任意非零数字与 0 异或的结果为其本身。
  • 异或运算满足交换律和结合律。
  1. class Solution {
  2. public int singleNumber(int[] nums) {
  3. int result = 0;
  4. for(int num:nums){
  5. result ^=num;
  6. }
  7. return result;
  8. }
  9. }

2023/3/27

题目(未做出)121:买卖股票的最佳时机

  1. 参考答案
  2. class Solution {
  3. public:
  4. int maxProfit(vector<int>& prices) {
  5. int cost=INT_MAX,profit=0;
  6. for(int price : prices){
  7. cost=min(cost,price);
  8. profit=max(profit,price-cost);
  9. }
  10. return profit;
  11. }
  12. };
  1. class Solution {
  2. public int maxProfit(int[] prices) {
  3. int cost = 100000;
  4. int profit = 0;
  5. for(int price:prices){
  6. cost=Math.min(cost,price);
  7. profit=Math.max(profit,price-cost);
  8. }
  9. return profit;
  10. }
  11. }
  12. //正无穷
  13. print(float("inf"))
  14. print(float("inf")+1)
  15. //负无穷
  16. print(float("-inf"))
  17. print(float("-inf")+1)

Java中最大值函数:Math.max

Java中最小值函数:Math.min


2023/3/29

题目(完成)169:多数元素

sort(nums.begin(),nums.end());
  1. class Solution {
  2. public int majorityElement(int[] nums) {
  3. Arrays.sort(nums);
  4. return(nums[(nums.length)/2]);
  5. }
  6. }

 Java中的排序函数:Arrays.sort(数组名)

题目(完成)217:存在重复元素

  1. 参考答案
  2. class Solution {
  3. public:
  4. bool containsDuplicate(vector<int>& nums) {
  5. sort(nums.begin(), nums.end());
  6. for (int i = 1; i < nums.size(); i++)
  7. if (nums[i-1] == nums[i]) return true;
  8. return false;
  9. }
  10. };
  11. class Solution {
  12. public:
  13. bool containsDuplicate(vector<int>& nums) {
  14. unordered_set<int> set;
  15. for (int num: nums) {
  16. if (set.find(num) != set.end()) return true;
  17. set.insert(num);
  18. }
  19. return false;
  20. }
  21. };
  22. class Solution {
  23. public:
  24. bool containsDuplicate(vector<int>& nums) {
  25. if(nums.size() <= 1) return false;
  26. unordered_map<int,int> map;
  27. for(int num : nums) {
  28. map[num]++;
  29. if(map[num] >= 2) return true;
  30. }
  31. return false;
  32. }
  33. };

unordered_set  find(key):查找以值为 key 的元素,如果找到,则返回一个指向该元素的正向迭代器;反之,则返回一个指向容器中最后一个元素之后位置的迭代器

Java哈希表:

  1. class Solution {
  2. public boolean containsDuplicate(int[] nums) {
  3. Set<Integer> set = new HashSet<Integer>();
  4. for (int x : nums) {
  5. if (!set.add(x)) {
  6. return true;
  7. }
  8. }
  9. return false;
  10. }
  11. }
  12. 个人感觉下面这个更好,能和C++版本对应上理解
  13. class Solution {
  14. public boolean containsDuplicate(int[] nums) {
  15. Set<Integer> set = new HashSet<>();
  16. for (int num: nums) {
  17. if (set.contains(num)) {
  18. return true;
  19. }
  20. set.add(num);
  21. }
  22. return false;
  23. }
  24. }

2023/3/30

题目(C++写未完成,用Java写的时候通过了)219:存在重复元素2

  1. class Solution {
  2. public:
  3. bool containsNearbyDuplicate(vector<int>& nums, int k) {
  4. unordered_map<int,int> map;
  5. for(int i=0;i<nums.size();i++){
  6. if(!map.empty() && map.count(nums[i])>0){
  7. if(i-map[nums[i]]<=k){
  8. return true;
  9. }
  10. }
  11. map[nums[i]]=i;
  12. }
  13. return false;
  14. }
  15. };

map和set两种容器的底层结构都是红黑树,所以容器中不会出现相同的元素,因此count()的结果只能为0和1,可以以此来判断键值元素是否存在(当然也可以使用find()方法判断键值是否存在)。

  1. Java
  2. class Solution {
  3. public boolean containsNearbyDuplicate(int[] nums, int k) {
  4. Set<Integer> set= new HashSet<>();
  5. for(int i=0;i<nums.length;i++){
  6. if(set.contains(nums[i])){
  7. // int k = 0;
  8. for(int j=0;j<nums.length;j++){
  9. if(nums[j]==nums[i]&&i!=j){
  10. if(Math.abs(i-j)<=k){
  11. return true;
  12. }
  13. }
  14. }
  15. }
  16. set.add(nums[i]);
  17. }
  18. return false;
  19. }
  20. }
  21. 答案
  22. class Solution {
  23. public boolean containsNearbyDuplicate(int[] nums, int k) {
  24. HashSet<Integer> set = new HashSet<>();
  25. for(int i = 0; i < nums.length; i++) {
  26. if(set.contains(nums[i])) {
  27. return true;
  28. }
  29. set.add(nums[i]);
  30. if(set.size() > k) {
  31. set.remove(nums[i - k]);
  32. }
  33. }
  34. return false;
  35. }
  36. }

答案采用的是是类似滑动窗口的一种方法 一直维护一个大小为K的滑动窗口一直往前走,判断窗口内是否有重复元素,所以与我考虑的存在哈希表内的数据是否有序无关,这里注意哈希表不保证集合中元素的顺序,在某些特定情况下可能是有序的。


2023/4/2

题目(思路正确,做出来一半)228:汇总区间

  1. 我的解答
  2. class Solution {
  3. public:
  4. vector<string> summaryRanges(vector<int>& nums) {
  5. vector<string>ans;
  6. int i=1;
  7. int j=1;
  8. string s;
  9. while(j<nums.size()){
  10. if(nums[j]-nums[i-1]>1){
  11. s = to_string(nums[i-1]);
  12. ans.push_back(s);
  13. i++;
  14. j++;
  15. }
  16. else{
  17. if(j==nums.size()-1){
  18. s=to_string(nums[i-1]) + "->" + to_string(nums[j]);
  19. ans.push_back(s);
  20. }
  21. int times = 1;
  22. j++;
  23. if(nums[j]-nums[i]==times){
  24. j++;
  25. times++;
  26. }
  27. if(nums[j]-nums[i]>times){
  28. // map[k]="nums[i-1],nums[j-1]]";
  29. // s += to_string(nums[l]) + "->" + to_string(nums[r - 1]);
  30. s=to_string(nums[i-1]) + "->" + to_string(nums[j-1]);
  31. ans.push_back(s);
  32. if(j==nums.size()-1){
  33. s=to_string(nums[j]);
  34. ans.push_back(s);
  35. }
  36. i=j+1;
  37. j=i;
  38. }
  39. }
  40. }
  41. return ans;
  42. }
  43. };
  44. // s = to_string(nums[l]);
  45. // ans.push_back(s);
  46. 答案
  47. class Solution {
  48. public:
  49. vector<string> summaryRanges(vector<int>& nums) {
  50. int n = nums.size();
  51. vector<string> ans;
  52. if(n == 0) {
  53. return {};
  54. }//nums是个空数组
  55. int l = 0;
  56. while(l < n) {
  57. string s;
  58. int r = l + 1;
  59. if(r == n) { //mums数组中只有一个元素
  60. s = to_string(nums[l]);
  61. ans.push_back(s);
  62. break;
  63. }
  64. while(r < n && nums[r] == nums[r - 1] + 1) {
  65. ++r;
  66. }
  67. if(r == l + 1) {
  68. s = to_string(nums[l]);
  69. }
  70. if(r > l + 1) {
  71. s += to_string(nums[l]) + "->" + to_string(nums[r - 1]);
  72. }
  73. l = r;
  74. ans.push_back(s);
  75. }
  76. return ans;
  77. }
  78. };

push_back()函数将一个新元素加到vector的最后,位置为当前最后一个元素的下一个元素

  1. Java
  2. class Solution {
  3. public List<String> summaryRanges(int[] nums) {
  4. List<String> res = new ArrayList<>();
  5. // i 初始指向第 1 个区间的起始位置
  6. int i = 0;
  7. for (int j = 0; j < nums.length; j++) {
  8. // j 向后遍历,直到不满足连续递增(即 nums[j] + 1 != nums[j + 1])
  9. // 或者 j 达到数组边界,则当前连续递增区间 [i, j] 遍历完毕,将其写入结果列表。
  10. if (j + 1 == nums.length || nums[j] + 1 != nums[j + 1]) {
  11. // 将当前区间 [i, j] 写入结果列表
  12. StringBuilder sb = new StringBuilder();
  13. sb.append(nums[i]);
  14. if (i != j) {
  15. sb.append("->").append(nums[j]);
  16. }
  17. res.add(sb.toString());
  18. // 将 i 指向更新为 j + 1,作为下一个区间的起始位置
  19. i = j + 1;
  20. }
  21. }
  22. return res;
  23. }
  24. }

List<String> res = new ArrayList<>();定义一个长度可变的数组

参考文章:(92条消息) Java如何向数组里添加元素_java数组添加元素的方法_zhangvalue的博客-CSDN博客

StringBuilder sb = new StringBuilder();可编辑的字符串

参考文章:

(92条消息) Java:StringBuilder的基本使用_java stringbuilder用法_Rex Chou的博客-CSDN博客


2023/4/3

题目(完成)268:消失的数字

我的解答

  1. 我的解答
  2. class Solution {
  3. public:
  4. int missingNumber(vector<int>& nums) {
  5. int n = nums.size();
  6. sort(nums.begin(),nums.end());
  7. int r = 0;
  8. if(nums[0]!=0){
  9. return r;
  10. }
  11. if(n == r + 1){
  12. return r+1;
  13. }
  14. while((r+1<n) && nums[r+1] == nums[r] + 1){
  15. r++;
  16. }
  17. return r+1;
  18. }
  19. };

2023/4/4

题目(完成)283:移动零

  1. 暴力解法
  2. class Solution {
  3. public:
  4. void moveZeroes(vector<int>& nums) {
  5. int times=0;
  6. int j = 0;
  7. // if(nums.size()==0){
  8. // return nums
  9. // }
  10. for(int i=0;i<nums.size();i++){
  11. if(nums[i]!=0){
  12. nums[j]=nums[i];
  13. j++;
  14. times++;
  15. }
  16. }
  17. for(times;times<nums.size();times++){
  18. nums[times]=0;
  19. }
  20. // return nums;
  21. }
  22. };
  23. 双指针
  24. class Solution {
  25. public:
  26. void moveZeroes(vector<int>& nums) {
  27. int left = 1;
  28. int right = 1;
  29. while(right<nums.size()){
  30. if(nums[left - 1]== 0){
  31. if(nums[right]!=0){
  32. nums[left-1]=nums[right];
  33. nums[right]=0;
  34. left++;
  35. right=left;
  36. }
  37. else{
  38. right++;
  39. }
  40. }
  41. else{
  42. left++;
  43. right++;
  44. }
  45. }
  46. }
  47. };
  48. 答案
  49. class Solution {
  50. public:
  51. void moveZeroes(vector<int>& nums) {
  52. int leftIndex = 0;
  53. int rightIndex = 0;
  54. /**
  55. * 还是两个指针,如果nums[rightIndex]不等于0的时候才交换,并且对left进行加
  56. */
  57. while(rightIndex < nums.size()){
  58. if(nums[rightIndex]){
  59. int t = nums[rightIndex];
  60. //很简洁 双指针自己和自己换的思想需要好好理解一下
  61. nums[rightIndex] = nums[leftIndex];
  62. nums[leftIndex] = t;
  63. ++leftIndex;
  64. }
  65. ++rightIndex;
  66. }
  67. }
  68. };

2023/4/5

题目(完成一半)303:区域和检索-数组不可变

对题目和函数的理解没到位

  1. class NumArray {
  2. vector<int>test;//全局变量
  3. public:
  4. NumArray(vector<int>& nums) {
  5. test.resize(nums.size()+1);
  6. for(int i=0;i<nums.size();i++){
  7. test[i+1]=test[i]+nums[i];
  8. }
  9. }
  10. int sumRange(int left, int right) {
  11. return test[right+1]-test[left];
  12. }
  13. };
  1. class NumArray {
  2. private int[] res;
  3. public NumArray(int[] nums) {
  4. res = new int[nums.length + 1];
  5. for(int i = 0;i < nums.length;i++){
  6. res[i+1] = res[i] + nums[i];
  7. }
  8. }
  9. public int sumRange(int left, int right) {
  10. return res[right + 1] - res[left];
  11. }
  12. }

为什么要这么写,而不是按照自己一开始比较直接的思路,需要好好理解,想不明白就看看解析


2023/4/6

题目(未完成)349:两个数组的交集

  1. class Solution {
  2. public:
  3. vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
  4. /* 存放结果,之所以用set是为了给结果集去重 */
  5. unordered_set<int> result;
  6. /* 由于输出的元素唯一不重复因此可以将nums1转化为unordered_set哈希表 */
  7. unordered_set<int> nums1_set(nums1.begin(),nums1.end());
  8. for(int i = 0; i < nums2.size(); i++){
  9. /* 判断nums1_set中是否有nums2的元素,若有将此值插入到result */
  10. if(nums1_set.find(nums2[i]) != nums1_set.end())
  11. result.insert(nums2[i]);
  12. }
  13. return vector<int> (result.begin(),result.end());
  14. }
  15. };

  1. 我的解答
  2. class Solution {
  3. public int[] intersection(int[] nums1, int[] nums2) {
  4. Set<Integer> hashset= new HashSet<Integer>();
  5. Set<Integer> hashset1= new HashSet<Integer>();
  6. for(int num1:nums1){
  7. hashset.add(num1);
  8. }
  9. for(int num2:nums2){
  10. if(hashset.contains(nums2)){
  11. hashset1.add(num2);
  12. }
  13. hashset.add(num2);
  14. }
  15. int [] resArr=new int[hashset1.size()];
  16. int index = 0;
  17. for(int i:hashset1){
  18. resArr[index++] = i;
  19. }
  20. return resArr;
  21. // int[] result = new int[hashset1.size()];
  22. // int i = 0;
  23. // for (int integer : hashset1) {
  24. // result[i++] = integer;
  25. // }
  26. // return result;
  27. // return int[] result = new int(hashset1);
  28. }
  29. }
  30. 答案
  31. class Solution {
  32. public int[] intersection(int[] nums1, int[] nums2) {
  33. if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
  34. return new int[0];
  35. }
  36. Set<Integer> set = new HashSet<Integer>();
  37. Set<Integer> result = new HashSet<Integer>(); // 结果哈希表
  38. // 遍历nums1加入set哈希表
  39. for ( int i : nums1) {
  40. set.add(i);
  41. }
  42. // 遍历nums2,如果set哈希表中存在就加入到结果哈希表中
  43. for ( int i : nums2) {
  44. if (set.contains(i)) {
  45. result.add(i);
  46. }
  47. set.add(i);
  48. }
  49. int[] resArr = new int[result.size()]; // 结果数组
  50. int index = 0;
  51. // 把哈希表的值传入数组
  52. for (int i : result) {
  53. resArr[index++] = i;
  54. }
  55. return resArr;
  56. }
  57. }

有运用哈希表的思维了,而且自己写的语言逻辑感觉和答案没差呀,不知道为什么就是不对(Java)


2023/4/7

题目(完成一半)350:两个数组的交集2

  1. class Solution {
  2. public:
  3. vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
  4. unordered_map<int,int>map1;
  5. unordered_map<int,int>map2;
  6. unordered_set<int>set;
  7. //vector是动态空间,随着新元素的加入,内部机制会自动扩充空间容纳新元素。
  8. vector<int>ans;
  9. for(int num1:nums1){
  10. map1[num1]++;
  11. }
  12. for(int num2:nums2){
  13. map2[num2]++;
  14. }
  15. for(int num3:nums1){
  16. if(map2.find(num3)!=map2.end()){
  17. int times = min(map1[num3],map2[num3]);
  18. for(int i=0;i<times/2;i++){
  19. ans.push_back(num3);
  20. }
  21. }
  22. }
  23. return ans;
  24. }
  25. };
  26. class Solution {
  27. public:
  28. vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
  29. unordered_map<int, int>Hash;
  30. vector<int> ans;
  31. for (auto &i : nums1){
  32. ++Hash[i];
  33. }
  34. for (auto &i : nums2){
  35. if (Hash.find(i) != Hash.end() && Hash[i] > 0){
  36. ans.emplace_back(i);
  37. --Hash[i];
  38. }
  39. }
  40. return ans;
  41. }
  42. };
  1. class Solution {
  2. public int[] intersect(int[] nums1, int[] nums2) {
  3. //总是让nums1指向短的呢个数组
  4. if(nums1.length > nums2.length){
  5. return intersect(nums2.nums1);
  6. }
  7. Map<Integer,Integer>map = new HashMap<Integer,Integer>();
  8. for(int num:nums1){
  9. int count = map.getOrDefault(num,0)+1;
  10. map.put(num,count);
  11. }
  12. int [] intersection = new int[nums1.length];
  13. int index = 0;
  14. for(int num:nums2){
  15. int count = map.getOrDefault(num,0);
  16. if(count >0){
  17. intersection[index++]=num;
  18. count--;
  19. if(count>0){
  20. map.put(num,count);
  21. }else{
  22. map.remove(num);
  23. }
  24. }
  25. }
  26. return Arrays.copyOfRange(intersection,0,index);
  27. }
  28. }


2023/4/7

题目(C++未完成,Java完成)414:第三大的数

  1. class Solution {
  2. public:
  3. int thirdMax(vector<int>&nums) {
  4. sort(nums.begin(),nums.end());
  5. set<int>st;
  6. int result=0;
  7. if(nums.size()<3){
  8. int n=nums.size()-1;
  9. return nums[n];
  10. }
  11. int times=0;
  12. for(int num:nums){
  13. st.insert(num);
  14. }
  15. for(auto it=st.end();it!=st.begin();it--){
  16. times++;
  17. if(times==3){
  18. result=*it;
  19. break;
  20. }
  21. }
  22. return result;
  23. }
  24. };
  25. class Solution {
  26. public:
  27. int thirdMax(vector<int> &nums) {
  28. set<int> s;
  29. for (int i = 0; i < nums.size(); i++) {
  30. s.insert(nums[i]);
  31. if (s.size() > 3) {
  32. s.erase(s.begin());
  33. }
  34. }
  35. if (s.size() == 3)
  36. return *s.begin();
  37. return *s.rbegin();
  38. }
  39. };
  1. class Solution {
  2. public int thirdMax(int[] nums) {
  3. Arrays.sort(nums);
  4. Map<Integer,Integer>map = new HashMap<Integer,Integer>();
  5. for(int num:nums){
  6. int count = map.getOrDefault(num,0)+1;
  7. map.put(num,count);
  8. }
  9. if(map.size()<3){
  10. return nums[nums.length-1];
  11. }else{
  12. int index = nums.length-1;
  13. int count_first=map.getOrDefault(nums[index],0);
  14. index=index-count_first;
  15. int count_second=map.getOrDefault(nums[index],0);
  16. index=index-count_second;
  17. return nums[index];
  18. }
  19. }
  20. }
  21. 这个解题思路不错
  22. class Solution {
  23. public int thirdMax(int[] nums) {
  24. Set<Integer> set = new HashSet<>();
  25. for (int x : nums) set.add(x);
  26. List<Integer> list = new ArrayList<>(set);
  27. Collections.sort(list);
  28. return list.size() < 3 ? list.get(list.size() - 1) : list.get(list.size() - 3);
  29. }
  30. }

对去重后的set数组进行了排序


2023/4/13

题目(未完成)34:在排序数组中查找元素的第一个和最后一个位置

  1. class Solution {
  2. public int[] searchRange(int[] nums, int target) {
  3. int x = Leftmost(nums,target);
  4. if(x == -1){
  5. return new int[]{-1,-1};
  6. }else{
  7. return new int[]{x,Rightmost(nums,target)};
  8. }
  9. }
  10. public int Leftmost(int[] nums, int target){
  11. int left = 0;
  12. int right = nums.length;
  13. int candidate = -1;
  14. // List<Integer> res = new ArrayList<Integer>();
  15. while(left <= right){
  16. int mid = (left+right) >>> 1;
  17. if(target < nums[mid]){
  18. right = mid - 1;
  19. }
  20. else if(target > nums[mid]){
  21. left = mid + 1;
  22. }
  23. else{
  24. candidate = mid;
  25. right = mid -1 ;
  26. }
  27. }
  28. return candidate;
  29. }
  30. public int Rightmost(int[] nums, int target){
  31. int left = 0;
  32. int right = nums.length;
  33. int candidate = -1;
  34. while(left <= right){
  35. int mid = (left+right) >>> 1;
  36. if(target < nums[mid]){
  37. right = mid - 1;
  38. }
  39. else if(target > nums[mid]){
  40. left = mid + 1;
  41. }
  42. else{
  43. candidate = mid;
  44. left = mid + 1 ;
  45. }
  46. }
  47. return candidate;
  48. }
  49. }

题目(完成)9:回文数

  1. class Solution {
  2. public boolean isPalindrome(int x) {
  3. int number = 0;
  4. int temp = x;
  5. //负数一定不是回文数
  6. if(x <0){
  7. return false;
  8. }
  9. while(x!=0){
  10. int unit = x % 10;
  11. x = x / 10;
  12. number = number * 10 + unit;
  13. }
  14. return (temp==number);
  15. }
  16. }

2023/4/14

题目(超时)448:找出所有数组中消失的数字

  1. class Solution {
  2. public List<Integer> findDisappearedNumbers(int[] nums) {
  3. Arrays.sort(nums);
  4. // Set<Integer> set = new Hashset<Integer>();
  5. Set<Integer> set = new HashSet<Integer>();
  6. //根据题意数组中第一个元素一定是1
  7. int i = 1;
  8. while(i<nums.length){
  9. if(nums[i]!=nums[i-1]+1){
  10. set.add(nums[i]);
  11. }
  12. }
  13. List<Integer> result = new ArrayList<>(set);
  14. for(int number : set){
  15. result.add(number);
  16. }
  17. return result;
  18. // int [] result = new int[set.size()];
  19. // int index = 0;
  20. // for (int j : set) {
  21. // result[index++] = j;
  22. // }
  23. // return result;
  24. }
  25. }
  26. 答案
  27. class Solution {
  28. public List<Integer> findDisappearedNumbers(int[] nums) {
  29. /*
  30. 原地哈希:
  31. 当看见数字范围为[1,n]恰好为等于数组索引长度时候,可以利用原数组压缩空间开销
  32. 常规做法是设置一个数目容器,然后找出出现个数为0的
  33. 但是这里可以利用原来数组作为数字容器,没枚举一共数字就将对应位置的数字变为对应的负数
  34. 最后找出所有还是正数的数字的位置就是答案
  35. 这样既能保留了原来的信息又可以进行标记
  36. 时间复杂度:O(N) 空间复杂度:O(1)
  37. */
  38. List<Integer> res = new ArrayList<>();
  39. int n = nums.length;
  40. for (int num : nums) {
  41. // 对应的索引
  42. int abs = Math.abs(num) - 1;
  43. nums[abs] = -Math.abs(nums[abs]);
  44. }
  45. for (int i = 0; i < n; i++) {
  46. if (nums[i] > 0) res.add(i + 1);
  47. }
  48. return res;
  49. }
  50. }
  51. class Solution {
  52. public List<Integer> findDisappearedNumbers(int[] nums) {
  53. List<Integer> res = new ArrayList<>();
  54. int i = 0;
  55. while (i < nums.length) {
  56. if (nums[i] == i + 1) {
  57. i++;
  58. continue;
  59. }
  60. int idealIdx = nums[i] - 1;
  61. if (nums[i] == nums[idealIdx]) {
  62. i++;
  63. continue;
  64. }
  65. int tmp = nums[i];
  66. nums[i] = nums[idealIdx];
  67. nums[idealIdx] = tmp;
  68. }
  69. for (int j = 0; j < nums.length; j++) {
  70. if (nums[j] != j + 1) {
  71. res.add(j + 1);
  72. }
  73. }
  74. return res;
  75. }
  76. }

答案的两种思维都需要好好学习一下

题目(未完成)455:分发饼干

  1. class Solution {
  2. public int findContentChildren(int[] g, int[] s) {
  3. int i = 0;
  4. int j = 0;
  5. int count = 0;
  6. Arrays.sort(g);
  7. Arrays.sort(s);
  8. if(s.length == 0 || g[0]>s[0]){
  9. return count;
  10. }
  11. else{
  12. while(i<g.length){
  13. if(g[i]<=s[j]){
  14. count++;
  15. i++;
  16. j++;
  17. }else{
  18. j++;
  19. if(j==s.length){
  20. break;
  21. }
  22. }
  23. }
  24. }
  25. return count;
  26. }
  27. }
  28. 答案
  29. class Solution {
  30. public int findContentChildren(int[] g, int[] s) {
  31. int cookie = 0;
  32. int child = 0;
  33. Arrays.sort(g);
  34. Arrays.sort(s);
  35. while(cookie < s.length && child < g.length){
  36. if(s[cookie] >= g[child]){
  37. child++;
  38. }
  39. cookie++;
  40. }
  41. return child;
  42. }
  43. }

思路是正确的,怎么写的就乱七八糟的,和老太太的臭裹脚布一样!!!!

  1. 10/27 已经完成80%了
  2. class Solution {
  3. public int findContentChildren(int[] g, int[] s) {
  4. Arrays.sort(g);
  5. Arrays.sort(s);
  6. // if(s[0] < g[0]) return 0;
  7. int i = 0;
  8. int j = 0;
  9. int res = 0;
  10. while(i < g.length){
  11. for(int k = j;k < s.length;k++){
  12. if(i < g.length && s[k] >= g[i]){
  13. j++;
  14. res++;
  15. break;
  16. }
  17. }
  18. i++;
  19. }
  20. return res;
  21. }
  22. }

2023/4/17

题目(完成)463:岛屿的周长

  1. 自己的思路
  2. class Solution {
  3. public int islandPerimeter(int[][] grid) {
  4. int Perimeter = 0;
  5. int times = 0;
  6. int redundant = 0;
  7. int result = 0;
  8. for(int i = 0;i<grid.length;i++){
  9. for(int j = 0;j<grid[i].length;j++){
  10. if(grid[i][j]==1){
  11. times++;
  12. if(i>=1&&grid[i-1][j]==grid[i][j]){
  13. redundant++;
  14. }
  15. if(j>=1&&grid[i][j-1]==grid[i][j]){
  16. redundant++;
  17. }
  18. }
  19. }
  20. }
  21. result = times * 4 - redundant *2;
  22. return result;
  23. }
  24. }

题目(已完成)485:最大连续1的个数

  1. class Solution {
  2. public int findMaxConsecutiveOnes(int[] nums) {
  3. int begin = 0;
  4. int times = 0;
  5. int temporary = 0;
  6. //还是卡在边界问题上了
  7. while(begin < nums.length){
  8. if(nums[begin]==1){
  9. begin++;
  10. times++;
  11. if(begin == nums.length){
  12. temporary = Math.max(temporary,times);
  13. break;
  14. }
  15. }else{
  16. temporary = Math.max(temporary,times);
  17. times=0;
  18. begin++;
  19. }
  20. }
  21. return temporary;
  22. }
  23. }

2023/4/18

题目(未完成)495:提莫攻击

  1. class Solution {
  2. public int findPoisonedDuration(int[] timeSeries, int duration) {
  3. int times = 0;
  4. int i = 0;
  5. while(i < timeSeries.length){
  6. if(i+1==timeSeries.length){
  7. times+=duration;
  8. break;
  9. }
  10. if(timeSeries[i]+duration-1 == timeSeries[i+1]){
  11. times+=(duration/2);
  12. i++;
  13. }else{
  14. times+=duration;
  15. i++;
  16. }
  17. }
  18. return times;
  19. }
  20. }
  21. 答案
  22. class Solution {
  23. public int findPoisonedDuration(int[] timeSeries, int duration) {
  24. int ans = 0;
  25. int expired = 0;
  26. for (int i = 0; i < timeSeries.length; ++i) {
  27. if (timeSeries[i] >= expired) {
  28. ans += duration;
  29. } else {
  30. //本次中毒增加的持续中毒时间
  31. ans += timeSeries[i] + duration - expired;
  32. }
  33. expired = timeSeries[i] + duration;
  34. }
  35. return ans;
  36. }
  37. }

2023/4/19

题目(完成)628:三个数的最大乘积

  1. class Solution {
  2. public int maximumProduct(int[] nums) {
  3. Arrays.sort(nums);
  4. int n = nums.length;
  5. int number1 = nums[n-1] * nums[n-2] * nums[n-3];
  6. int number2 = nums[0] * nums[1] *nums [n-1];
  7. return number1 > number2 ? number1:number2;
  8. }
  9. }

题目(未完成)645:错误的集合

  1. class Solution {
  2. public int[] findErrorNums(int[] nums) {
  3. Arrays.sort(nums);
  4. int [] result = new int[2];
  5. int i = 1;
  6. int n = nums.length;
  7. while(i<nums.length){
  8. if(nums[i]!=nums[i-1]){
  9. i++;
  10. }else{
  11. break;
  12. }
  13. }
  14. if(nums[i] == i+1){
  15. result[0]=nums[i];
  16. if(nums[0]!=1){
  17. result[1]=1;
  18. }else if(nums[n-1]!=n){
  19. result[1]=n;
  20. }else{
  21. result[1]=nums[i]-1;
  22. }
  23. }
  24. if(nums[i] != i+1){
  25. result[0]=nums[i];
  26. if(nums[0]!=1){
  27. result[1]=1;
  28. }else if(nums[n-1]!=n){
  29. result[1]=n;
  30. }else{
  31. result[1]=nums[i]+1;
  32. }
  33. }
  34. return result;
  35. }
  36. }
  37. 答案
  38. class Solution {
  39. public int[] findErrorNums(int[] nums) {
  40. int[] errorNums = new int[2];
  41. int n = nums.length;
  42. Arrays.sort(nums);
  43. int prev = 0;
  44. for (int i = 0; i < n; i++) {
  45. int curr = nums[i];
  46. if (curr == prev) {
  47. errorNums[0] = prev;
  48. } else if (curr - prev > 1) {
  49. errorNums[1] = prev + 1;
  50. }
  51. prev = curr;
  52. }
  53. if (nums[n - 1] != n) {
  54. errorNums[1] = n;
  55. }
  56. return errorNums;
  57. }
  58. }
  59. class Solution {
  60. public int[] findErrorNums(int[] nums) {
  61. int[] errorNums = new int[2];
  62. int n = nums.length;
  63. Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  64. for (int num : nums) {
  65. map.put(num, map.getOrDefault(num, 0) + 1);
  66. }
  67. for (int i = 1; i <= n; i++) {
  68. int count = map.getOrDefault(i, 0);
  69. if (count == 2) {
  70. errorNums[0] = i;
  71. } else if (count == 0) {
  72. errorNums[1] = i;
  73. }
  74. }
  75. return errorNums;
  76. }
  77. }


2023/4/20

题目(未完成)697:数组的度

  1. class Solution {
  2. public int findShortestSubArray(int[] nums) {
  3. Map<Integer,Integer> map = new HashMap<Integer,Integer>();
  4. //将元素都放入哈希表中统计每个数字出现的个数
  5. for(int num:nums){
  6. map.put(num,map.getOrDefault(num,0) + 1);
  7. }
  8. //找到度的大小
  9. int count = 0;
  10. for(int num:nums){
  11. count = Math.max(count,map.getOrDefault(num,0));
  12. }
  13. HashSet<
  14. }
  15. }
  16. 答案
  17. class Solution {
  18. public int findShortestSubArray(int[] nums) {
  19. Map<Integer, int[]> map = new HashMap<Integer, int[]>();
  20. int n = nums.length;
  21. for (int i = 0; i < n; i++) {
  22. if (map.containsKey(nums[i])) {
  23. map.get(nums[i])[0]++;
  24. map.get(nums[i])[2] = i;
  25. } else {
  26. map.put(nums[i], new int[]{1, i, i});
  27. }
  28. }
  29. int maxNum = 0, minLen = 0;
  30. for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
  31. int[] arr = entry.getValue();
  32. if (maxNum < arr[0]) {
  33. maxNum = arr[0];
  34. minLen = arr[2] - arr[1] + 1;
  35. } else if (maxNum == arr[0]) {
  36. if (minLen > arr[2] - arr[1] + 1) {
  37. minLen = arr[2] - arr[1] + 1;
  38. }
  39. }
  40. }
  41. return minLen;
  42. }
  43. }

哈希表的映射不一定是映射一个值,还可以是一个数组

Map<Integer,int[]> map = new HashMap<Integer, int[]>();

哈希表的定义方式中,Integer是key的数据类型,int[]是value的数据类型

题目(完成)442:数组中重复的数据

  1. //解法一 我的解答
  2. class Solution {
  3. public List<Integer> findDuplicates(int[] nums) {
  4. List<Integer> res = new ArrayList<Integer>();
  5. Arrays.sort(nums);
  6. if(nums.length == 1){
  7. return res;
  8. }else{
  9. for(int i = 1;i<nums.length;i++){
  10. if(nums[i]==nums[i-1]){
  11. res.add(nums[i]);
  12. }
  13. }
  14. }
  15. return res;
  16. }
  17. }
  18. //解法二 答案
  19. class Solution {
  20. public List<Integer> findDuplicates(int[] nums) {
  21. List<Integer> duplicates = new ArrayList<Integer>();
  22. int n = nums.length;
  23. for (int i = 0; i < n; i++) {
  24. int num = nums[i];
  25. int index = Math.abs(num) - 1;
  26. if (nums[index] > 0) {
  27. nums[index] = -nums[index];
  28. } else {
  29. duplicates.add(index + 1);
  30. }
  31. }
  32. return duplicates;
  33. }
  34. }

给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内

类似的题目已经出现第二次了,解题的思维也大同小异

题目(未完成)41:缺失的第一个正数

  1. 我的解答
  2. class Solution {
  3. public int firstMissingPositive(int[] nums) {
  4. //先找最小正整数1在不在
  5. Arrays.sort(nums);
  6. int result = 1;
  7. int index = 0;
  8. // if(nums.length == 1 && nums[0] != 1){
  9. // return result;
  10. // }else{
  11. // return nums[0]+1;
  12. // }
  13. for(int i = 0;i < nums.length;i++){
  14. if(nums[i] > 0 && nums[i] != 1){
  15. return result;
  16. }else if(nums.length == 1 && nums[nums.length-1]<=0){
  17. return result;
  18. }else if(nums[i] > 0 && nums[i] == 1){
  19. index = i;
  20. break;
  21. }
  22. }
  23. //index是1的下标
  24. if(index == nums.length -1){
  25. result = 2;
  26. return result;
  27. }
  28. while(index < nums.length){
  29. if(index + 1 == nums.length || nums[index+1] != nums[index] + 1){
  30. result = nums[index] + 1;
  31. break;
  32. }else{
  33. index++;
  34. }
  35. }
  36. return result;
  37. }
  38. }

这个题目的解题思维也挺类似>>>>>>给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内


2023/4/21

题目(未完成)274:H指数

  1. 我的解答
  2. class Solution {
  3. public int hIndex(int[] citations) {
  4. // Map<Integer,Integer> map = new HashMap<Integer,Integer>();
  5. // //将代表第几篇论文的索引值以及对应引用次数做成键值对送入哈希表
  6. // for(int i = 0;i<citations.length;i++){
  7. // map.put(i+1,citations[i]);
  8. // }
  9. int Threshold = 0;
  10. int result = 0;
  11. int i = 0;
  12. if(citations.length == 1 && citations[0]!=0){
  13. result = 1;
  14. return result;
  15. }
  16. if(citations.length == 1 && citations[0]==0){
  17. return result;
  18. }
  19. while(i<citations.length){
  20. while(i<citations.length){
  21. if(citations[i] > 0){
  22. Threshold = citations[i];
  23. break;
  24. }
  25. else{
  26. i++;
  27. }
  28. }
  29. int count = 0;
  30. for(int j = 0;j<citations.length;j++){
  31. if(citations[j] >= Threshold){
  32. count++;
  33. }
  34. }
  35. if(Threshold == count && citations.length - count <= Threshold){
  36. result = Math.max(result,Threshold);
  37. }
  38. i++;
  39. }
  40. if(result == 0){
  41. result = citations[0];
  42. for(int m = 0;m < citations.length;m++){
  43. result = Math.min(result,citations[m]);
  44. }
  45. }
  46. return result;
  47. }
  48. }
  49. --------------------------------------------------------------------------
  50. 答案
  51. class Solution {
  52. public int hIndex(int[] citations) {
  53. Arrays.sort(citations);
  54. int h = 0, i = citations.length - 1;
  55. while (i >= 0 && citations[i] > h) {
  56. h++;
  57. i--;
  58. }
  59. return h;
  60. }
  61. }
  62. class Solution {
  63. public int hIndex(int[] citations) {
  64. int n = citations.length;
  65. int left = 0;
  66. int right = n - 1;
  67. Arrays.sort(citations);
  68. while (left < right) {
  69. int mid = left + (right - left) / 2;
  70. if (citations[mid] < n - mid) {
  71. left = left + 1;
  72. } else {
  73. right = mid;
  74. }
  75. }
  76. return citations[left] == 0 ? 0 : n - left;
  77. }
  78. }
  79. public class Solution {
  80. public int hIndex(int[] citations) {
  81. int len = citations.length;
  82. int left = 0;
  83. int right = len;
  84. while (left < right) {
  85. // 猜论文篇数
  86. int mid = (left + right + 1) / 2;
  87. // 满足高引用的特点是:引用次数 >= 论文篇数
  88. // count 的含义是:大于等于 mid 的论文篇数
  89. int count = 0;
  90. for (int citation : citations) {
  91. if (citation >= mid) {
  92. count++;
  93. }
  94. }
  95. if (count >= mid) {
  96. left = mid;
  97. } else {
  98. right = mid - 1;
  99. }
  100. }
  101. return left;
  102. }
  103. }

二分查找没理解好

题目(未完成)453:最小操作次数使数组元素相等

求数组所有元素之和:Arrays.stream(arr1).sum();

求数组最大值/最小值:Arrays.stream(arr1).max.getAsInt();

Arrays.stream(arr1).min().getAsInt()

复制一个数组:int [] temparr = new int[n];

int [] resArr = Arrays.copyOf(temparr,temparr.length);

(101条消息) Arrays.stream()常用方法_now()的博客-CSDN博客

题目(完成)665:非递减数列

  1. class Solution {
  2. public boolean checkPossibility(int[] nums) {
  3. // int i = 1;
  4. // int count = 0;
  5. // int index = 0;
  6. // while(i<nums.length){
  7. // if(nums[i]<nums[i-1]){
  8. // count++;
  9. // index = i;
  10. // // if(i+1<nums.length && Math.abs(nums[i]-nums[i-1])>Math.abs(nums[i]-nums[i+1])){
  11. // // return false;
  12. // // }
  13. // if(count > 1){
  14. // return false;
  15. // }
  16. // }
  17. // i++;
  18. // }
  19. // return true;
  20. int i = 1;
  21. int count1 = 0;
  22. int count2 = 0;
  23. // int index = 0;
  24. int variable = 0;
  25. while(i<nums.length){
  26. if(nums[i]<nums[i-1]){
  27. variable = nums[i];
  28. nums[i]=nums[i-1];
  29. for(int j = 1;j < nums.length;j++){
  30. if(nums[j]<nums[j-1]){
  31. count1++;
  32. }
  33. }
  34. nums[i]=variable;
  35. nums[i-1]=variable;
  36. for(int k = 1;k < nums.length;k++){
  37. if(nums[k]<nums[k-1]){
  38. count2++;
  39. }
  40. }
  41. if(count1 > 0 && count2 >0){
  42. return false;
  43. }
  44. // count++;
  45. // index = i;
  46. // if(count > 1){
  47. // return false;
  48. // }
  49. }
  50. i++;
  51. }
  52. return true;
  53. }
  54. }
  55. 答案
  56. class Solution {
  57. public:
  58. bool checkPossibility(vector<int> &nums) {
  59. int n = nums.size();
  60. for (int i = 0; i < n - 1; ++i) {
  61. int x = nums[i], y = nums[i + 1];
  62. if (x > y) {
  63. nums[i] = y;
  64. if (is_sorted(nums.begin(), nums.end())) {
  65. return true;
  66. }
  67. nums[i] = x; // 复原
  68. nums[i + 1] = x;
  69. return is_sorted(nums.begin(), nums.end());
  70. }
  71. }
  72. return true;
  73. }
  74. };

答案和我的思路差不多,但是答案用了is_sorted函数(判断是否有序),代码更简洁一些。

(101条消息) is_sorted() 函数---一个判断数组和容器是否有序的函数_辉小歌的博客-CSDN博客


2023/4/23

题目(已完成)118.杨辉三角1

  1. class Solution {
  2. public List<List<Integer>> generate(int numRows) {
  3. List<List<Integer>> ret = new ArrayList<List<Integer>>();
  4. for(int i = 0;i < numRows; i++){
  5. List<Integer> row = new ArrayList<Integer>();
  6. for(int j = 0; j<=i; j++){
  7. if(i == j || j == 0){
  8. row.add(1);
  9. }else{
  10. row.add(ret.get(i - 1).get(j - 1) + ret.get(i-1).get(j));
  11. }
  12. }
  13. ret.add(row);
  14. }
  15. return ret;
  16. }
  17. }

二维List:(102条消息) 二维list的使用(java)_java 二维list_-Will-浩的博客-CSDN博客

ret.get(rowIndex);

题目(已完成)119.杨辉三角2

  1. class Solution {
  2. public List<Integer> getRow(int rowIndex) {
  3. List<List<Integer>> ret = new ArrayList<List<Integer>>();
  4. // List <Integer> res = new ArrayList<Integer>();
  5. for(int i = 0;i < rowIndex + 1; i++){
  6. List<Integer> row = new ArrayList<Integer>();
  7. for(int j = 0; j<=i; j++){
  8. if(i == j || j == 0){
  9. row.add(1);
  10. }else{
  11. row.add(ret.get(i - 1).get(j - 1) + ret.get(i-1).get(j));
  12. }
  13. // if(i == rowIndex){
  14. // if(i == j || j == 0){
  15. // res.add(1);
  16. // }else{
  17. // res.add(ret.get(i - 1).get(j - 1) + ret.get(i-1).get(j));
  18. // }
  19. // }
  20. }
  21. ret.add(row);
  22. }
  23. return ret.get(rowIndex);
  24. }
  25. }
  26. class Solution {
  27. public List<Integer> getRow(int rowIndex) {
  28. List<Integer> row = new ArrayList<Integer>();
  29. row.add(1);
  30. for (int i = 1; i <= rowIndex; ++i) {
  31. row.add(0);
  32. for (int j = i; j > 0; --j) {
  33. row.set(j, row.get(j) + row.get(j - 1));
  34. }
  35. }
  36. return row;
  37. }
  38. }

2023/4/24

题目(未完成)661:图片平滑器--------------------------------------------------------------------------------第37题

  1. //答案
  2. class Solution {
  3. public int[][] imageSmoother(int[][] img) {
  4. int m = img.length, n = img[0].length;
  5. int[][] ret = new int[m][n];
  6. for (int i = 0; i < m; i++) {
  7. for (int j = 0; j < n; j++) {
  8. int num = 0, sum = 0;
  9. for (int x = i - 1; x <= i + 1; x++) {
  10. for (int y = j - 1; y <= j + 1; y++) {
  11. if (x >= 0 && x < m && y >= 0 && y < n) {
  12. num++;
  13. sum += img[x][y];
  14. }
  15. }
  16. }
  17. ret[i][j] = sum / num;
  18. }
  19. }
  20. return ret;
  21. }
  22. }

 思维很简单,自己一开始想补一圈0,太复杂了,重新做的时候好好想一想,其实是可以想出来的

题目(完成一半)598:范围求和2

  1. class Solution {
  2. public int maxCount(int m, int n, int[][] ops) {
  3. for(int[]op : ops){
  4. m = Math.min(m,op[0]);
  5. n = Math.min(n,op[1]);
  6. }
  7. return m*n;
  8. }
  9. }

傻逼题目看都看不懂

题目(完成一半)419:甲板上的战舰

  1. 自己做的,有瑕疵
  2. class Solution {
  3. public int countBattleships(char[][] board) {
  4. int count = 0;
  5. int extra = 0;
  6. int x = 0;
  7. int y = 0;
  8. for(int i = 0;i < board.length;i++){
  9. for(int j = 0;j < board[i].length;j++){
  10. if(board[i][j] == 'X'){
  11. count++;
  12. if(x == i && Math.abs(j - y) == 1){
  13. extra++;
  14. }else if(y == j && Math.abs(x - i) == 1){
  15. extra++;
  16. }
  17. x = i;
  18. y = j;
  19. }
  20. }
  21. }
  22. return count - extra;
  23. }
  24. }
  25. 自己做的改进一下了,通过了
  26. class Solution {
  27. public int countBattleships(char[][] board) {
  28. int count = 0;
  29. int extra = 0;
  30. for(int i = 0;i < board.length;i++){
  31. for(int j = 0;j < board[i].length;j++){
  32. if(board[i][j] == 'X'){
  33. count++;
  34. if(i > 0 && board[i-1][j] == 'X'){
  35. extra++;
  36. }else if(j>0 &&board[i][j-1] == 'X'){
  37. extra++;
  38. }
  39. }
  40. }
  41. }
  42. return count - extra;
  43. }
  44. }
  45. 答案
  46. class Solution {
  47. public int countBattleships(char[][] board) {
  48. int count = 0;
  49. for(int i = 0;i<board.length;i++){
  50. for(int j =0;j<board[i].length;j++){
  51. if(board[i][j] == 'X'){
  52. if(i > 0 && board[i-1][j] == 'X'){
  53. //查找上一个是不是X
  54. continue;//强制进入下一次循环
  55. }else if(j>0 &&board[i][j-1] == 'X'){
  56. //查找左边一个是不是X
  57. continue;
  58. }else{
  59. count++;
  60. }
  61. }
  62. }
  63. }
  64. return count;
  65. }
  66. }

其实也不是做不出来,思维其实很像了,但是还是差一点


2023/4/25

题目(完成一半)189:轮转数组

  1. //我的解答
  2. class Solution {
  3. public void rotate(int[] nums, int k) {
  4. //k是几就循环几次 只把最后一位提出来,整体后移
  5. //超出时间限制
  6. // for(int i = 0;i < k; i++){
  7. // int target = nums[nums.length - 1];
  8. // for(int j = nums.length - 1;j > 0;j--){
  9. // nums[j] = nums[j - 1];
  10. // }
  11. // nums[0] = target;
  12. // }
  13. //arraycopy
  14. if(nums.length > 1){
  15. k %= nums.length;//关键
  16. int[] res = Arrays.copyOfRange(nums,nums.length - k,nums.length);
  17. System.arraycopy(nums,0,nums,k,nums.length-k);
  18. System.arraycopy(res,0,nums,0,k);
  19. }
  20. }
  21. }
  22. //答案
  23. class Solution {
  24. public void rotate(int[] nums, int k) {
  25. k %= nums.length;
  26. reverse(nums, 0, nums.length - 1);
  27. reverse(nums, 0, k - 1);
  28. reverse(nums, k, nums.length - 1);
  29. }
  30. public void reverse(int[] nums, int start, int end) {
  31. while (start < end) {
  32. int temp = nums[start];
  33. nums[start] = nums[end];
  34. nums[end] = temp;
  35. start += 1;
  36. end -= 1;
  37. }
  38. }
  39. }

Java复制(拷贝)数组的4种方法:arraycopy()方法、clone() 方法、copyOf()和copyOfRan (biancheng.net)


2023/4/27

题目(完成一半)396:旋转函数

  1. 我的解答
  2. class Solution {
  3. public int maxRotateFunction(int[] nums) {
  4. int res = 0;
  5. for(int i = 0;i < nums.length;i++){
  6. int target = nums[nums.length - 1];
  7. for(int j = nums.length - 1;j > 0;j--){
  8. nums[j] = nums[j - 1];
  9. }
  10. nums[0] = target;
  11. int temp = 0;
  12. for(int k = 0;k < nums.length;k++){
  13. temp +=k*nums[k];
  14. }
  15. res = Math.max(res,temp);
  16. }
  17. return res;
  18. }
  19. }

 题目(未完成)54:螺旋矩阵

  1. class Solution {
  2. public List<Integer> spiralOrder(int[][] matrix) {
  3. //仿照答案写的
  4. List<Integer> res = new ArrayList<Integer>();
  5. int top = 0;
  6. int bottom = matrix.length - 1;
  7. int left = 0;
  8. int right = matrix[0].length - 1;
  9. int count = matrix.length * matrix[0].length;
  10. while(count >= 1){
  11. for(int i = left;i <= right && count >= 1;i++){
  12. res.add(matrix[top][i]);
  13. count--;
  14. }
  15. top++;
  16. for(int i = top;i <= bottom && count >= 1;i++){
  17. res.add(matrix[i][right]);
  18. count--;
  19. }
  20. right--;
  21. for(int i = right;i >= left && count >= 1;i--){
  22. res.add(matrix[bottom][i]);
  23. count--;
  24. }
  25. bottom--;
  26. for(int i = bottom;i >= top && count >= 1;i--){
  27. res.add(matrix[i][left]);
  28. count--;
  29. }
  30. left++;
  31. }
  32. return res;
  33. //答案
  34. LinkedList<Integer> result = new LinkedList<>();
  35. if(matrix==null||matrix.length==0) return result;
  36. int left = 0;
  37. int right = matrix[0].length - 1;
  38. int top = 0;
  39. int bottom = matrix.length - 1;
  40. int numEle = matrix.length * matrix[0].length;
  41. while (numEle >= 1) {
  42. for (int i = left; i <= right && numEle >= 1; i++) {
  43. result.add(matrix[top][i]);
  44. numEle--;
  45. }
  46. top++;
  47. for (int i = top; i <= bottom && numEle >= 1; i++) {
  48. result.add(matrix[i][right]);
  49. numEle--;
  50. }
  51. right--;
  52. for (int i = right; i >= left && numEle >= 1; i--) {
  53. result.add(matrix[bottom][i]);
  54. numEle--;
  55. }
  56. bottom--;
  57. for (int i = bottom; i >= top && numEle >= 1; i--) {
  58. result.add(matrix[i][left]);
  59. numEle--;
  60. }
  61. left++;
  62. }
  63. return result;
  64. }
  65. }

2023/4/28

题目(完成一半,因为思路和昨天的一个题完全一样)59:螺旋矩阵2

  1. 我的解答
  2. class Solution {
  3. public int[][] generateMatrix(int n) {
  4. // int m = (int)Math.sqrt(n);
  5. int[][] res = new int[n][n];
  6. int top = 0;
  7. int bottom = res.length - 1;
  8. int left = 0;
  9. int right = res[0].length - 1;
  10. int count = 1;
  11. int numSum = n*n;
  12. while(count <= numSum){
  13. for(int i = left;i <= right;i++){
  14. res[top][i] = count;
  15. count++;
  16. }
  17. top++;
  18. for(int i = top;i <= bottom;i++){
  19. res[i][right] = count;
  20. count++;
  21. }
  22. right--;
  23. for(int i = right;i >= left;i--){
  24. res[bottom][i] = count;
  25. count++;
  26. }
  27. bottom--;
  28. for(int i = bottom;i >= top;i--){
  29. res[i][left] = count;
  30. count++;
  31. }
  32. left++;
  33. }
  34. return res;
  35. }
  36. }
  37. 答案
  38. class Solution {
  39. public int[][] generateMatrix(int n) {
  40. int l = 0, r = n - 1, t = 0, b = n - 1;
  41. int[][] mat = new int[n][n];
  42. int num = 1, tar = n * n;
  43. while(num <= tar){
  44. for(int i = l; i <= r; i++) mat[t][i] = num++; // left to right.
  45. t++;
  46. for(int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.
  47. r--;
  48. for(int i = r; i >= l; i--) mat[b][i] = num++; // right to left.
  49. b--;
  50. for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
  51. l++;
  52. }
  53. return mat;
  54. }
  55. }

题目(未完成)498:对角线的遍历

  1. 我的解答 思路想错了
  2. class Solution {
  3. public int[] findDiagonalOrder(int[][] mat) {
  4. //两个循环 一个从左下到右上,一个从右上到左下
  5. // int numSum = mat.length * mat[0].length;
  6. // int[] res = new int[numSum];
  7. // int count = 0;
  8. // int first = 0;
  9. // int second = 0;
  10. // while(count <= numSum){
  11. // //第一个循环,从左下到右上
  12. // res[count] = mat[first][second];
  13. // count++;
  14. // while(first - 1 >= 0 && second + 1 <= mat[0].length - 1){
  15. // res[count] = mat[first - 1][second + 1];
  16. // count++;
  17. // first--;
  18. // second++;
  19. // }
  20. // second++;
  21. // res[count] = mat[first][second];
  22. // count++;
  23. // while(first + 1 <= mat.length - 1 && second - 1 >= 0){
  24. // res[count] = mat[first + 1][second - 1];
  25. // count++;
  26. // first++;
  27. // second--;
  28. // }
  29. // first++;
  30. // }
  31. // return res;
  32. int top = 0;
  33. int bottom = mat.length - 1;
  34. int left = 0;
  35. int right = mat[0].length - 1;
  36. int numSum = mat.length * mat[0].length;
  37. int[] res = new int[numSum];
  38. int count = 0;
  39. for(int i = left;i <= right;i++){
  40. res[count] = mat[top][i];
  41. count++;
  42. int first = top;
  43. int second = i;
  44. while(first + 1 <= bottom && 0 <= second - 1){
  45. res[count] = mat[first + 1][second - 1];
  46. first++;
  47. second--;
  48. count++;
  49. }
  50. }
  51. top++;
  52. for(int i = top;i <= bottom;i++){
  53. res[count] = mat[i][right];
  54. int first = top;
  55. int second = i;
  56. while(first + 1 <= bottom && 0 <= second - 1){
  57. res[count] = mat[first + 1][second - 1];
  58. first++;
  59. second--;
  60. if(second != bottom){
  61. count++;
  62. }
  63. }
  64. }
  65. return res;
  66. }
  67. }


2023/4/30

题目(完成)566:重塑矩阵

  1. class Solution {
  2. public int[][] matrixReshape(int[][] mat, int r, int c) {
  3. if(r * c != mat.length * mat[0].length){
  4. return mat;
  5. }
  6. int left = 0;
  7. int right = 0;
  8. int[][] res = new int[r][c];
  9. for(int i = 0;i < mat.length;i++){
  10. for(int j = 0;j <mat[0].length;j++){
  11. res[left][right] = mat[i][j];
  12. right++;
  13. if(right == res[0].length){
  14. if(left < res.length){
  15. left++;
  16. right = 0;
  17. }
  18. }
  19. }
  20. }
  21. return res;
  22. }
  23. }

官方解答中的坐标映射似懂非懂


2023/4/30

题目(未完成) 48:旋转图像

只是看懂了答案,但是掌握的很不牢固


2023/5/1

题目(完成一半)73:矩阵置零

  1. 我的解答
  2. class Solution {
  3. public void setZeroes(int[][] matrix) {
  4. for(int i = 0;i<matrix.length;i++){
  5. for(int j = 0;j<matrix[i].length;j++){
  6. if(matrix[i][j] == 0){
  7. for(int k = 0;k < matrix[i].length;k++){
  8. if(matrix[i][k] != 0){
  9. matrix[i][k] = -100;
  10. }
  11. }
  12. for(int q = 0;q < matrix.length;q++){
  13. if(matrix[q][j] != 0){
  14. matrix[q][j] = -100;
  15. }
  16. }
  17. }
  18. }
  19. }
  20. for(int i = 0;i<matrix.length;i++){
  21. for(int j = 0;j<matrix[i].length;j++){
  22. if(matrix[i][j] == -100){
  23. matrix[i][j] = 0;
  24. }
  25. }
  26. }
  27. }
  28. }
  29. 答案
  30. class Solution {
  31. public void setZeroes(int[][] matrix) {
  32. int m = matrix.length, n = matrix[0].length;
  33. boolean flagCol0 = false, flagRow0 = false;
  34. for (int i = 0; i < m; i++) {
  35. if (matrix[i][0] == 0) {
  36. flagCol0 = true;
  37. }
  38. }
  39. for (int j = 0; j < n; j++) {
  40. if (matrix[0][j] == 0) {
  41. flagRow0 = true;
  42. }
  43. }
  44. for (int i = 1; i < m; i++) {
  45. for (int j = 1; j < n; j++) {
  46. if (matrix[i][j] == 0) {
  47. matrix[i][0] = matrix[0][j] = 0;
  48. }
  49. }
  50. }
  51. for (int i = 1; i < m; i++) {
  52. for (int j = 1; j < n; j++) {
  53. if (matrix[i][0] == 0 || matrix[0][j] == 0) {
  54. matrix[i][j] = 0;
  55. }
  56. }
  57. }
  58. if (flagCol0) {
  59. for (int i = 0; i < m; i++) {
  60. matrix[i][0] = 0;
  61. }
  62. }
  63. if (flagRow0) {
  64. for (int j = 0; j < n; j++) {
  65. matrix[0][j] = 0;
  66. }
  67. }
  68. }
  69. }

按照我的思路 百分之99的用例可以通过,但是总有百分之1的特殊情况通过不了

答案的复杂度分析


2023/5/6

题目(完成)289:生命游戏

  1. class Solution {
  2. public void gameOfLife(int[][] board) {
  3. int[][] res = new int[board.length][board[0].length];
  4. for(int i = 0;i < board.length;i++){
  5. for(int j = 0;j < board[0].length;j++){
  6. int count = 0;//统计活细胞的个数
  7. if(j - 1 >= 0){
  8. if(board[i][j-1] == 1){
  9. count++;
  10. }
  11. if(i - 1 >= 0 && board[i-1][j-1] == 1){
  12. count++;
  13. }
  14. if(i + 1 < board.length && board[i+1][j-1] == 1){
  15. count++;
  16. }
  17. }
  18. if(i - 1 >= 0 && board[i-1][j] == 1){
  19. count++;
  20. }
  21. if(i + 1 < board.length && board[i+1][j] == 1){
  22. count++;
  23. }
  24. if(j + 1 < board[0].length){
  25. if(board[i][j+1] == 1){
  26. count++;
  27. }
  28. if(i - 1 >= 0 && board[i-1][j+1] == 1){
  29. count++;
  30. }
  31. if(i + 1 < board.length && board[i+1][j+1] == 1){
  32. count++;
  33. }
  34. }
  35. if(board[i][j] == 1){
  36. if(count < 2 || 3 < count){
  37. res[i][j] = 0;
  38. }else{
  39. res[i][j] = 1;
  40. }
  41. }
  42. if(board[i][j] == 0){
  43. if(count == 3){
  44. res[i][j] = 1;
  45. }else{
  46. res[i][j] = 0;
  47. }
  48. }
  49. }
  50. }
  51. for(int i = 0;i < board.length;i++){
  52. for(int j = 0;j < board[0].length;j++){
  53. board[i][j] = res[i][j];
  54. }
  55. }
  56. }
  57. }

题目(完成)238:除自己以外数组的乘积

和官方的思路不一样

  1. class Solution {
  2. public int[] productExceptSelf(int[] nums) {
  3. //时间复杂度O(n) 不能使用嵌套循环
  4. int[] res = new int[nums.length];
  5. int count = 0;
  6. int temp = 1;
  7. for(int i = 0;i < nums.length;i++){
  8. if(nums[i] != 0){
  9. temp = temp * nums[i];
  10. }else{
  11. count++;
  12. }
  13. }
  14. for(int i = 0;i < res.length;i++){
  15. if(count >= 2){
  16. res[i] = 0;
  17. }else if(count == 1){
  18. if(nums[i] == 0){
  19. res[i] = temp;
  20. }else{
  21. res[i] = 0;
  22. }
  23. }else{
  24. res[i] = temp/nums[i];
  25. }
  26. }
  27. return res;
  28. }
  29. }

题目(未完成)304:二位区域检索-矩阵不可变

第二种解法更重要


2023/5/7——字符串专题

题目(完成)520:检测大写字母

  1. class Solution {
  2. public boolean detectCapitalUse(String word) {
  3. boolean res = true;
  4. int count = 0;
  5. for(int i = 0;i < word.length();i++){
  6. char str = word.charAt(i);
  7. if(Character.isUpperCase(str)){
  8. count++;
  9. }
  10. }
  11. if(count == word.length() || count == 0){
  12. res = true;
  13. }else if(count == 1 && word.length() > 1){
  14. char temp = word.charAt(0);
  15. if(Character.isUpperCase(temp)){
  16. res = true;
  17. }else{
  18. res = false;
  19. }
  20. }else{
  21. res = false;
  22. }
  23. return res;
  24. }
  25. }
  26. 宫水三叶
  27. class Solution {
  28. public boolean detectCapitalUse(String word) {
  29. if (word.toUpperCase().equals(word)) return true;
  30. if (word.toLowerCase().equals(word)) return true;
  31. int n = word.length(), idx = 1;
  32. if (Character.isUpperCase(word.charAt(0))) {
  33. while (idx < n && Character.isLowerCase(word.charAt(idx))) idx++;
  34. }
  35. return idx == n;
  36. }
  37. }

(111条消息) JAVA逻辑运算符示例详解:与、或、非、异或_java中或者_火石桥霍建华的博客-CSDN博客

.toUpperCase().equals() 先变成大写再比较

.equalsIgnoreCase() 忽略大小写


2023/5/7

题目(完成)125:验证回文串

  1. class Solution {
  2. public boolean isPalindrome(String s) {
  3. // boolean res = true;
  4. if(s.length() == 1){
  5. return true;
  6. }
  7. StringBuilder sb_1 = new StringBuilder();
  8. StringBuilder sb_2 = new StringBuilder();
  9. // s = Character.toLowerCase(s);
  10. for(int i = s.length() - 1;i >= 0;i--){
  11. char temp_1 = Character.toLowerCase(s.charAt(i));
  12. if(temp_1 >= 'a' && temp_1 <= 'z'){
  13. sb_1.append(temp_1);
  14. }
  15. if(temp_1 >= '0' && temp_1 <= '9'){
  16. sb_1.append(temp_1);
  17. }
  18. }
  19. for(int i = 0;i < s.length();i++){
  20. char temp_2 = Character.toLowerCase(s.charAt(i));
  21. if(temp_2 >= 'a' && temp_2 <= 'z'){
  22. sb_2.append(temp_2);
  23. }
  24. if(temp_2 >= '0' && temp_2 <= '9'){
  25. sb_2.append(temp_2);
  26. }
  27. }
  28. //return sb_1 == sb_2;
  29. return sb_1.toString().equals(sb_2.toString());
  30. }
  31. }

StringBuilder比较是否相等:sb_1.toString().equals(sb_2.toString());

  1. 答案
  2. class Solution {
  3. public boolean isPalindrome(String s) {
  4. StringBuffer sgood = new StringBuffer();
  5. int length = s.length();
  6. for (int i = 0; i < length; i++) {
  7. char ch = s.charAt(i);
  8. if (Character.isLetterOrDigit(ch)) {
  9. sgood.append(Character.toLowerCase(ch));
  10. }
  11. }
  12. StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
  13. return sgood.toString().equals(sgood_rev.toString());
  14. }
  15. }

.isLetterOrDigit():判断是否是字母或数字;

.reverse():反转字符串;


2023/5/8

题目(未完成)14:最长公共前缀

  1. class Solution {
  2. public String longestCommonPrefix(String[] strs) {
  3. if(strs.length == 0){
  4. return "";
  5. }
  6. StringBuilder res = new StringBuilder();
  7. String temp = strs[0];//数组中的第一个单词;
  8. boolean test = true;
  9. int i = 0;
  10. while(test){
  11. char temp_1 = temp.charAt(i); //取出来了f
  12. for(int j = 1;j < strs.length;j++){
  13. char temp_2 = strs[j].charAt(i);
  14. if(temp_1 != temp_2){
  15. test = false;
  16. }
  17. }
  18. if(test){
  19. res.append(temp_1);
  20. }
  21. i++;//这里存在隐患
  22. }
  23. return res.toString();
  24. }
  25. }
  26. 答案
  27. class Solution {
  28. public String longestCommonPrefix(String[] strs) {
  29. if(strs.length == 0) //特殊情况1
  30. return "";
  31. String ans = strs[0];
  32. for(int i =1;i < strs.length;i++) {
  33. int j=0;
  34. for(;j<ans.length() && j < strs[i].length();j++) {
  35. if(ans.charAt(j) != strs[i].charAt(j))
  36. break;
  37. }
  38. ans = ans.substring(0, j);
  39. if(ans.equals("")) //特殊情况2
  40. return ans;
  41. }
  42. return ans;
  43. }
  44. }

注意处理特殊情况

String[] strs = {}    strs.length() = 0;

String[] strs = {""}  strs.length() = 1;

题目(未完成)434:字符串中的单词数

  1. 我写的
  2. class Solution {
  3. public int countSegments(String s) {
  4. int i = 0;
  5. int count = 0;
  6. while(i < s.length()){
  7. if(Character.isLetter(s.charAt(i))){
  8. i++;
  9. if(i == s.length() && count == 0){
  10. count++;
  11. break;
  12. }
  13. }else{
  14. count++;
  15. i++;
  16. }
  17. }
  18. return count;
  19. }
  20. }
  21. 答案
  22. class Solution {
  23. public int countSegments(String s) {
  24. int n = s.length();
  25. int ans = 0;
  26. for (int i = 0; i < n; ) {
  27. if (s.charAt(i) == ' ' && i++ >= 0) continue;
  28. while (i < n && s.charAt(i) != ' ') i++;
  29. ans++;
  30. }
  31. return ans;
  32. }
  33. }
  34. 感觉答案写成这样更好理解一点
  35. class Solution {
  36. public int countSegments(String s) {
  37. int n = s.length();
  38. int ans = 0;
  39. for (int i = 0; i < n; ) {
  40. if (s.charAt(i) == ' '){
  41. i++;
  42. // System.out.println(i);
  43. continue;
  44. }
  45. while (i < n && s.charAt(i) != ' ') i++;
  46. ans++;
  47. }
  48. return ans;
  49. }
  50. }

continue只是跳过continue所在循环体中continue后的语句


2023/5/9

题目(完成)58:最后一个单词的长度

  1. class Solution {
  2. public int lengthOfLastWord(String s) {
  3. int count = 0;
  4. int i = s.length() - 1;
  5. while(s.charAt(i) == ' ' && i >= 0) i--;
  6. while(s.charAt(i) != ' ' && i >= 0){
  7. i--;
  8. if(i < 0){
  9. count++;
  10. break;
  11. }
  12. count++;
  13. }
  14. return count;
  15. }
  16. }

题目(完成)344:反转字符串

  1. //解法1
  2. class Solution {
  3. public void reverseString(char[] s) {
  4. StringBuilder res = new StringBuilder();
  5. for(int i = 0;i < s.length;i++){
  6. res.append(s[i]);
  7. }
  8. String res_1 = res.reverse().toString();
  9. for(int i = 0;i < res_1.length();i++){
  10. char c = res_1.charAt(i);
  11. s[i] = c;
  12. }
  13. }
  14. }
  15. //解法2
  16. class Solution {
  17. public void reverseString(char[] s) {
  18. int left = 0;
  19. int right = s.length - 1;
  20. while(left <= right){
  21. char c = s[left];
  22. s[left] = s[right];
  23. s[right] = c;
  24. left++;
  25. right--;
  26. }
  27. }
  28. }

题目(未完成)541:反转字符串2    写的又臭又长

  1. 我写的
  2. class Solution {
  3. public String reverseStr(String s, int k) {
  4. // String res = "";
  5. // if(s.length() - 2*k < k){
  6. // res = s.reverse();
  7. // return res;
  8. // }
  9. // if(s.length() - 2*k >= k && s.length() - 2*k < 2k){
  10. // }
  11. int i = 0;
  12. StringBuilder res = new StringBuilder();
  13. if(s.length() < 2*k && s.length() >= k){
  14. res.append(s.substring(0,k)).reverse();
  15. res.append(s.substring(k,s.length()));
  16. return res.toString();
  17. }
  18. // StringBuilder temp = new StringBuilder();
  19. while(i < s.length()){
  20. if(s.length() - (i + 2*k) >= 2*k){
  21. res.append(s.substring(i,i + k)).reverse();
  22. res.append(s.substring(i + k,i + 2*k));
  23. i = i + 2*k;
  24. }else if(s.length() - (i + 2*k) < k){
  25. StringBuilder temp = new StringBuilder();
  26. res.append(s.substring(i,i + k)).reverse();
  27. res.append(s.substring(i + k,i + 2*k));
  28. temp.append(s.substring(i + 2*k,s.length())).reverse();
  29. res.append(temp.toString());
  30. break;
  31. }else{
  32. StringBuilder temp = new StringBuilder();
  33. res.append(s.substring(i,i + k)).reverse();
  34. res.append(s.substring(i + k,i + 2*k));
  35. temp.append(s.substring(i + 2*k,i + 2*k + k)).reverse();
  36. res.append(temp.toString());
  37. res.append(s.substring(i + 2*k + k,s.length()));
  38. break;
  39. }
  40. }
  41. return res.toString();
  42. }
  43. }
  44. 答案
  45. class Solution {
  46. public String reverseStr(String s, int k) {
  47. int n = s.length();
  48. char[] arr = s.toCharArray();
  49. for (int i = 0; i < n; i += 2 * k) {
  50. reverse(arr, i, Math.min(i + k, n) - 1);
  51. }
  52. return new String(arr);
  53. }
  54. public void reverse(char[] arr, int left, int right) {
  55. while (left < right) {
  56. char temp = arr[left];
  57. arr[left] = arr[right];
  58. arr[right] = temp;
  59. left++;
  60. right--;
  61. }
  62. }
  63. }

(116条消息) toCharArray()_java tochararray()_Technology9997的博客-CSDN博客


2023/5/10

题目(完成)151:反转字符串中的单词        循环条件是有先后顺序的

  1. class Solution {
  2. public String reverseWords(String s) {
  3. StringBuilder res = new StringBuilder();
  4. int index = s.length() - 1;
  5. int left = 0;
  6. int right = 0;
  7. while(index >= 0 && left <= right){
  8. while(index >= 0 &&s.charAt(index) == ' '){
  9. index--;
  10. }
  11. right = index + 1;
  12. while(index >= 0 && s.charAt(index) != ' '){//这个循环条件有先后条件
  13. index--;
  14. }
  15. left = index + 1;
  16. if(right != left){
  17. res.append(s.substring(left,right));
  18. res.append(' ');
  19. }
  20. }
  21. res.deleteCharAt(res.length() - 1);//起作用了
  22. return res.toString();
  23. }
  24. }

.deleteCharAt():删除某个位置的字符

题目(完成)557:反转字符串中的单词3

  1. //有点像原地修改
  2. class Solution {
  3. public String reverseWords(String s) {
  4. int index = 0;
  5. int left = 0;
  6. int right = 0;
  7. char[] res = s.toCharArray();
  8. while(index < s.length()){
  9. while(s.charAt(index) == ' ')index++;
  10. left = index;
  11. while(index < s.length() && s.charAt(index) != ' ')index++;
  12. right = index - 1;
  13. reverse(res,left,right);
  14. }
  15. // String res_test = new String(res);
  16. return new String(res);
  17. }
  18. public void reverse(char[] res,int left,int right){
  19. while(left <= right){
  20. char c = res[left];
  21. res[left] = res[right];
  22. res[right]= c;
  23. left++;
  24. right--;
  25. }
  26. }
  27. }
  28. //第二种
  29. class Solution {
  30. public String reverseWords(String s) {
  31. StringBuilder res = new StringBuilder();
  32. int index = 0;
  33. int begin = 0;
  34. int end = 0;
  35. while(index < s.length()){
  36. while(index < s.length() && s.charAt(index) == ' ')index++;
  37. end = index;
  38. while(index < s.length() && s.charAt(index) != ' ')index++;
  39. begin = index - 1;
  40. for(int i = begin;i >= end;i--){
  41. res.append(s.charAt(i));
  42. }
  43. res.append(' ');
  44. }
  45. res.deleteCharAt(res.length() - 1);
  46. return res.toString();
  47. }
  48. }

char类型数组和String相互转化

(116条消息) Java char[]数组转成String类型(char to String)详细介绍_java char数组转string_Smile sea breeze的博客-CSDN博客

题目(已完成,但是是用笨办法完成的)387:字符串中的第一个唯一的字符

  1. 我写的
  2. class Solution {
  3. public int firstUniqChar(String s) {
  4. // int res = 0;
  5. int symbol = 0;
  6. for(int i = 0;i < s.length();i++){
  7. char temp = s.charAt(i);
  8. int j = 0;
  9. while(j < s.length()){
  10. if(temp == s.charAt(j) && i != j){
  11. break;
  12. }else{
  13. j++;
  14. if(j == s.length()){
  15. return i;
  16. }
  17. }
  18. }
  19. }
  20. return -1;
  21. }
  22. }
  23. 答案
  24. class Solution {
  25. public int firstUniqChar(String s) {
  26. int index = -1;
  27. int res = s.length();
  28. for(char ch = 'a'; ch<= 'z';ch++){
  29. index = s.indexOf(ch);//这个字符在字符串中第一次出现的位置 如果找不到 index = -1
  30. if(index != -1 && index == s.lastIndexOf(ch)){//这个字符在字符串中能找到 且第一次出现的位置和最后一次出现的位置相同
  31. res = Math.min(res,index);//找到第一个不重复的字符
  32. }
  33. }
  34. return res > s.length() - 1 ? -1 : res;
  35. }
  36. }
  37. 哈希表1
  38. class Solution {
  39. public int firstUniqChar(String s) {
  40. Map<Character,Integer> frequency = new HashMap<Character,Integer>();
  41. for(int i = 0;i < s.length();i++){
  42. char ch = s.charAt(i);
  43. frequency.put(ch,frequency.getOrDefault(ch,0) + 1);
  44. }
  45. for(int i = 0;i < s.length();i++){
  46. if(frequency.get(s.charAt(i)) == 1){
  47. return i;
  48. }
  49. }
  50. return -1;
  51. }
  52. }
  53. 哈希表2
  54. class Solution {
  55. public int firstUniqChar(String s) {
  56. Map<Character,Integer> position = new HashMap<Character,Integer>();
  57. int n = s.length();
  58. for(int i = 0;i < n;i++){
  59. char ch = s.charAt(i);
  60. if(position.containsKey(ch)){
  61. position.put(ch,-1);//覆盖
  62. }else{
  63. position.put(ch,i);
  64. }
  65. }
  66. int first = n;
  67. for(Map.Entry<Character,Integer> entry :position.entrySet()){//固定格式
  68. int pos = entry.getValue();
  69. if(pos != -1 && pos <first){
  70. first = pos;
  71. }
  72. }
  73. if(first == n){
  74. first = -1;
  75. }
  76. return first;
  77. }
  78. }

 indexOf():指定字符第一次出现的位置         lastIndexof():指定字符最后一次出现的位置

(116条消息) Java中indexOf() 方法 总计及其日常使用_你若不离不弃,我必生死相依的博客-CSDN博客

HashSet 不允许集合中出现重复的值。HashSet 底层其实就是 HashMap,所有对 HashSet 的操作其实就是对 HashMap 的操作。所以 HashSet 也不保证集合的顺序。

HashMap不保证插入顺序,但是循环遍历时,输出顺序是不会改变的。


2023/5/11

题目(完成)389:找不同            答案的ASCII和位运算很简便

  1. class Solution {
  2. public char findTheDifference(String s, String t) {
  3. if(s.length() == 0){
  4. return t.charAt(0);
  5. }
  6. Map<Character,Integer> res = new HashMap<Character,Integer>();
  7. char res_ch = ' ';
  8. for(int i = 0;i < s.length();i++){
  9. char ch = s.charAt(i);
  10. res.put(ch,res.getOrDefault(ch,0) + 1);
  11. }
  12. for(int j = 0;j < t.length();j++){
  13. char temp = t.charAt(j);
  14. if(!res.containsKey(temp)){
  15. res_ch = temp;
  16. break;
  17. }else{
  18. res.put(temp,res.get(temp) - 1);
  19. if(res.get(temp) == -1){
  20. res_ch = temp;
  21. break;
  22. }
  23. }
  24. }
  25. return res_ch;
  26. }
  27. }

 题目(完成)383:赎金信

  1. class Solution {
  2. public boolean canConstruct(String ransomNote, String magazine) {
  3. Map<Character,Integer> res = new HashMap<Character,Integer>();
  4. // char res_ch = ' ';
  5. for(int i = 0;i < magazine.length();i++){
  6. char ch = magazine.charAt(i);
  7. res.put(ch,res.getOrDefault(ch,0) + 1);
  8. }
  9. for(int j = 0;j < ransomNote.length();j++){
  10. char temp = ransomNote.charAt(j);
  11. if(!res.containsKey(temp)){
  12. return false;
  13. }else{
  14. res.put(temp,res.get(temp) - 1);
  15. if(res.get(temp) == -1){
  16. return false;
  17. }
  18. }
  19. }
  20. return true;
  21. }
  22. }

题目(完成)242:有效的字母异位词

  1. 我写的
  2. class Solution {
  3. public boolean isAnagram(String s, String t) {
  4. if(s.length() != t.length()) return false;
  5. Map<Character,Integer> res = new HashMap<Character,Integer>();
  6. // char res_ch = ' ';
  7. for(int i = 0;i < s.length();i++){
  8. char ch = s.charAt(i);
  9. res.put(ch,res.getOrDefault(ch,0) + 1);
  10. }
  11. for(int j = 0;j < t.length();j++){
  12. char temp = t.charAt(j);
  13. if(!res.containsKey(temp)){
  14. return false;
  15. }else{
  16. res.put(temp,res.get(temp) - 1);
  17. if(res.get(temp) == -1){
  18. return false;
  19. }
  20. }
  21. }
  22. return true;
  23. }
  24. }
  25. 答案
  26. class Solution {
  27. public boolean isAnagram(String s, String t) {
  28. if (s.length() != t.length()) {
  29. return false;
  30. }
  31. char[] str1 = s.toCharArray();
  32. char[] str2 = t.toCharArray();
  33. Arrays.sort(str1);
  34. Arrays.sort(str2);
  35. return Arrays.equals(str1, str2);
  36. }
  37. }

将字符串转换成字符数组,再排序


2023/5/12

题目(未完成)49:字母异位词分组

  1. class Solution {
  2. public List<List<String>> groupAnagrams(String[] strs) {
  3. Map<String, List<String>> map = new HashMao<String, List<String>>();
  4. for(String str : strs){
  5. char[] array = str.toCharArray();
  6. Arrays.sort(array);
  7. String key = new String(array);
  8. List<String> list = map.getOrDefault(key,new ArrayList<Sting>());
  9. list.add(str);
  10. map.put(key,list);
  11. }
  12. return new ArrayList<List<Sting>>(map.values());
  13. }
  14. }

List<String> list = new ArrayList<String>();

List<String> list = map.getOrDefault(key,new ArrayList<String>());

题目(完成)451:根据字符出现频率排序

  1. class Solution {
  2. public String frequencySort(String s) {
  3. Map<Character,Integer> res = new HashMap<Character,Integer>();
  4. for(int i = 0;i < s.length();i++){
  5. char ch = s.charAt(i);
  6. res.put(ch,res.getOrDefault(ch,0) + 1);
  7. }
  8. StringBuilder res_ch = new StringBuilder();
  9. char char_max = ' ';
  10. int char_max_times = 0;
  11. int count = s.length();
  12. while(count > 0){
  13. for(Map.Entry<Character,Integer> entry :res.entrySet()){
  14. char target = entry.getKey();
  15. int target_times = entry.getValue();
  16. if(target_times >= char_max_times){
  17. char_max = target;
  18. char_max_times = target_times;
  19. }
  20. }
  21. for(int i = 0;i < char_max_times;i++){
  22. res_ch.append(char_max);
  23. count--;
  24. }
  25. res.remove(char_max);
  26. char_max_times = 0;
  27. }
  28. return res_ch.toString();
  29. }
  30. }
  31. 唯一好理解的一个答案
  32. class Solution {
  33. public String frequencySort(String s) {
  34. Map<Character, Integer> map = new HashMap<Character, Integer>();
  35. int length = s.length();
  36. for (int i = 0; i < length; i++) {
  37. char c = s.charAt(i);
  38. int frequency = map.getOrDefault(c, 0) + 1;
  39. map.put(c, frequency);
  40. }
  41. List<Character> list = new ArrayList<Character>(map.keySet());
  42. Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
  43. StringBuffer sb = new StringBuffer();
  44. int size = list.size();
  45. for (int i = 0; i < size; i++) {
  46. char c = list.get(i);
  47. int frequency = map.get(c);
  48. for (int j = 0; j < frequency; j++) {
  49. sb.append(c);
  50. }
  51. }
  52. return sb.toString();
  53. }
  54. }

map.keySet(): 

将哈希表中的键按照其对应值的大小排序:


2023/5/14

题目(完成一半)423:从英文中重建数字                 我写的处理不了重复的情况

  1. class Solution {
  2. public String originalDigits(String s) {
  3. StringBuilder res = new StringBuilder();
  4. String[] Candidate_area = {"zero","one","two","three","four","five","six","seven","eight","nine"};
  5. for(int i = 0;i < Candidate_area.length;i++){
  6. char[] array = Candidate_area[i].toCharArray(); // zero
  7. int count = 0;//array.length();//one 3
  8. int times = 0;
  9. while(times < s.length()){
  10. char ch = s.charAt(times);
  11. //array[count];
  12. if(array[count] != ch){
  13. times++;
  14. }
  15. if(array[count] == ch){
  16. count++;
  17. times = 0;
  18. if(count == array.length){
  19. res.append(i);
  20. break;
  21. }
  22. }
  23. // times++;
  24. }
  25. }
  26. return res.toString();
  27. }
  28. }
  1. class Solution {
  2. static String[] ss = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
  3. static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
  4. public String originalDigits(String s) {
  5. int n = s.length();
  6. int[] cnts = new int[26];
  7. //将'a'放在cnts数组的第0个位置,记录26个字母在s字符串中的出现顺序
  8. for (int i = 0; i < n; i++) cnts[s.charAt(i) - 'a']++;
  9. StringBuilder sb = new StringBuilder();
  10. for (int i : priority) {
  11. int k = Integer.MAX_VALUE;
  12. //z e r o 找到ss[i]中在s字符串中出现频率最小的次数
  13. for (char c : ss[i].toCharArray()) k = Math.min(k, cnts[c - 'a']);
  14. for (char c : ss[i].toCharArray()) cnts[c - 'a'] -= k;
  15. while (k-- > 0) sb.append(i);
  16. }
  17. char[] cs = sb.toString().toCharArray();
  18. Arrays.sort(cs);
  19. return String.valueOf(cs);
  20. }
  21. }

说明:System.out.println(array);这样是不行的,这样打印是的是数组的首地址。

(117条消息) Java数组的三种打印方式_打印数组用百分号_chenkaibsw的博客-CSDN博客

char[]  和 String相互转化。

(117条消息) Java char[]数组转成String类型(char to String)详细介绍_java char数组转string_Smile sea breeze的博客-CSDN博客

被Static修饰的变量,其参数被该类所有的对象共享。

(117条消息) Java static关键字详解_Cappuccinooo的博客-CSDN博客


2023/5/16

题目(完成)657:机器人能否返回原点

  1. class Solution {
  2. public boolean judgeCircle(String moves) {
  3. // int left = 0;
  4. // int right = 0;
  5. // int up = 0;
  6. // int down = 0;
  7. // for(int i = 0;i < moves.length();i++){
  8. // char ch = moves.charAt(i);
  9. // if(ch == 'U') up++;
  10. // if(ch == 'D') down++;
  11. // if(ch == 'L') left++;
  12. // if(ch == 'R') right++;
  13. // }
  14. // if(up - down == 0 & left - right == 0){
  15. // return true;
  16. // }
  17. // return false;
  18. int left_right = 0;
  19. // int right = 0;
  20. int up_down = 0;
  21. // int down = 0;
  22. for(int i = 0;i < moves.length();i++){
  23. char ch = moves.charAt(i);
  24. if(ch == 'U') up_down++;
  25. if(ch == 'D') up_down--;
  26. if(ch == 'L') left_right++;
  27. if(ch == 'R') left_right--;
  28. }
  29. if(up_down == 0 & left_right == 0){
  30. return true;
  31. }
  32. return false;
  33. }
  34. }

题目(未完成)696:计数二进制子串            没抓住问题的关键

  1. 我写的
  2. class Solution {
  3. public int countBinarySubstrings(String s) {
  4. char[] res = s.toCharArray();
  5. int count = 0;
  6. int i = 1;
  7. int signal = 0;
  8. while(i < res.length){
  9. if(res[i] != res[i-1]){
  10. count++;
  11. i++;
  12. // if(signal > 0){
  13. // count++;
  14. // signal = 0;
  15. // }
  16. }else if(res[i] == res[i-1]){
  17. i++;
  18. signal++;
  19. if(signal == 2){
  20. count++;
  21. signal--;
  22. }
  23. }
  24. }
  25. return count;
  26. }
  27. }
  28. 答案
  29. class Solution {
  30. public int countBinarySubstrings(String s) {
  31. List<Integer> counts = new ArrayList<Integer>();
  32. int ptr = 0, n = s.length();
  33. while (ptr < n) {
  34. char c = s.charAt(ptr);
  35. int count = 0;
  36. while (ptr < n && s.charAt(ptr) == c) {
  37. ++ptr;
  38. ++count;
  39. }
  40. counts.add(count);
  41. }
  42. int ans = 0;
  43. for (int i = 1; i < counts.size(); ++i) {
  44. ans += Math.min(counts.get(i), counts.get(i - 1));
  45. }
  46. return ans;
  47. }
  48. }
  49. 答案改进
  50. class Solution {
  51. public int countBinarySubstrings(String s) {
  52. int ptr = 0, n = s.length(), last = 0, ans = 0;
  53. while (ptr < n) {
  54. char c = s.charAt(ptr);
  55. int count = 0;
  56. while (ptr < n && s.charAt(ptr) == c) {
  57. ++ptr;
  58. ++count;
  59. }
  60. ans += Math.min(count, last);
  61. last = count;
  62. }
  63. return ans;
  64. }
  65. }

 题目(完成)551:学生出勤记录1

  1. class Solution {
  2. public boolean checkRecord(String s) {
  3. int i = 0;
  4. int Absent = 0;
  5. int Late = 0;
  6. int temp = 0;
  7. char[] res = s.toCharArray();
  8. while(i < res.length){
  9. if(res[i] == 'A'){
  10. Absent++;
  11. i++;
  12. }else if(res[i] == 'L'){
  13. Late = 0;
  14. while(i < s.length() && res[i] == 'L'){
  15. Late++;
  16. i++;
  17. }
  18. temp = Math.max(temp,Late);
  19. }else{
  20. i++;
  21. }
  22. }
  23. if(Absent < 2 && temp < 3){
  24. return true;
  25. }else{
  26. return false;
  27. }
  28. }
  29. }

2023/5/18

题目(未完成)467:环绕字符串中唯一的子字符串       

这个题具体解析推导过程没理解,直接记高手答案

  1. 自己写的 垃圾
  2. class Solution {
  3. public int findSubstringInWraproundString(String s) {
  4. //只有z能和a挨着
  5. if(s.length() == 1 && s == " "){
  6. return 0;
  7. }
  8. if(s.length() == 1 && s != " "){
  9. return 1;
  10. }
  11. if(s.length() == 0){
  12. return 0;
  13. }
  14. char[] res = s.toCharArray();
  15. int i = 1;
  16. int j = 1;
  17. int count = 1;
  18. while(j < res.length){
  19. while(res[i] - res[i-1] == -25 || res[i] - res[i-1] == 1){
  20. i++;
  21. count++;
  22. if(i == res.length) break;
  23. }
  24. count++;
  25. j++;
  26. i = j;
  27. }
  28. return count;
  29. }
  30. }
  31. 高手
  32. class Solution {
  33. public int findSubstringInWraproundString(String _p) {
  34. char[] cs = _p.toCharArray();
  35. int n = cs.length, ans = 0;
  36. int[] max = new int[26];
  37. max[cs[0] - 'a']++;
  38. for (int i = 1, j = 1; i < n; i++) {
  39. int c = cs[i] - 'a', p = cs[i - 1] - 'a';
  40. if ((p == 25 && c == 0) || p + 1 == c) j++;
  41. else j = 1;
  42. max[c] = Math.max(max[c], j);
  43. }
  44. for (int i = 0; i < 26; i++) ans += max[i];
  45. return ans;
  46. }
  47. }

答案涉及一个专业词汇:线性DP


2023/5/22

题目(未完成)299:猜数字游戏           解题思路和上面呢个题很像

  1. 我写的
  2. class Solution {
  3. public String getHint(String secret, String guess) {
  4. StringBuilder sb = new StringBuilder();
  5. // Map<Character,Integer> map = new HashMap<Character,Integer>();
  6. Map<Character,Integer> count = new HashMap<Character,Integer>();
  7. for(int i = 0;i < secret.length();i++){
  8. char ch = secret.charAt(i);
  9. // map.put(ch,i);
  10. count.put(ch,count.getOrDefault(ch,0) + 1);
  11. }
  12. int Bulls = 0;
  13. int Cows = 0;
  14. for(int i = 0;i < guess.length();i++){
  15. char ch_secret = secret.charAt(i);
  16. char ch_guess = guess.charAt(i);
  17. if(ch_secret == ch_guess && count.get(ch_guess) > 0){
  18. Bulls++;
  19. count.put(ch_guess,count.get(ch_guess) - 1);
  20. }else{
  21. if(count.containsKey(ch_guess) && count.get(ch_guess) > 0){
  22. Cows++;
  23. count.put(ch_guess,count.get(ch_guess) - 1);
  24. }
  25. }
  26. }
  27. sb.append(Bulls);
  28. sb.append('A');
  29. sb.append(Cows);
  30. sb.append('B');
  31. return sb.toString();
  32. }
  33. }
  34. 宫水三叶
  35. class Solution {
  36. public String getHint(String secret, String guess) {
  37. int n = secret.length();
  38. int a = 0, b = 0;
  39. int[] cnt1 = new int[10], cnt2 = new int[10];
  40. for (int i = 0; i < n; i++) {
  41. int c1 = secret.charAt(i) - '0', c2= guess.charAt(i) - '0';
  42. if (c1 == c2) {
  43. a++;
  44. } else {
  45. cnt1[c1]++;
  46. cnt2[c2]++;
  47. }
  48. }
  49. for (int i = 0; i < 10; i++) b += Math.min(cnt1[i], cnt2[i]);
  50. return a + "A" + b + "B";
  51. }
  52. }

2023/5/29

题目(完成)412:Fizz Buzz

  1. class Solution {
  2. public List<String> fizzBuzz(int n) {
  3. List<String> res = new ArrayList<String>();
  4. for(int i = 1;i <= n;i++){
  5. if(i % 3 == 0 && i % 5 == 0){
  6. res.add("FizzBuzz");
  7. }else if(i % 3 == 0){
  8. res.add("Fizz");
  9. }else if(i % 5 == 0){
  10. res.add("Buzz");
  11. }else{
  12. res.add(String.valueOf(i));
  13. }
  14. }
  15. return res;
  16. }
  17. }
  18. 宫水三叶
  19. class Solution {
  20. public List<String> fizzBuzz(int n) {
  21. List<String> ans = new ArrayList<>();
  22. for (int i = 1; i <= n; i++) {
  23. String cur = "";
  24. if (i % 3 == 0) cur += "Fizz";
  25. if (i % 5 == 0) cur += "Buzz";
  26. if (cur.length() == 0) cur = i + "";
  27. ans.add(cur);
  28. }
  29. return ans;
  30. }
  31. }

将整数型转换成字符串

(125条消息) Java –将整数转换为字符串_cyan20115的博客-CSDN博客

题目(完成)506:相对名次

  1. class Solution {
  2. public String[] findRelativeRanks(int[] score) {
  3. String[] res = new String[score.length];
  4. int[] paixu = Arrays.copyOf(score,score.length);
  5. Arrays.sort(paixu);
  6. for(int i = 0;i < score.length;i++){
  7. int k = 0;
  8. for(int j = 0; j< paixu.length;j++){
  9. if(score[i] == paixu[j]){
  10. k = j;
  11. break;
  12. }
  13. }
  14. if(k == score.length - 1){
  15. res[i] = "Gold Medal";
  16. }else if(k == score.length - 2){
  17. res[i] = "Silver Medal";
  18. }else if(k == score.length - 3){
  19. res[i] = "Bronze Medal";
  20. }else{
  21. res[i] = score.length - k + "";
  22. // res[i] = String.valueOf(i + 1);
  23. }
  24. }
  25. return res;
  26. }
  27. }
  28. 宫水三叶
  29. class Solution {
  30. String[] ss = new String[]{"Gold Medal", "Silver Medal", "Bronze Medal"};
  31. public String[] findRelativeRanks(int[] score) {
  32. int n = score.length;
  33. String[] ans = new String[n];
  34. int[] clone = score.clone();
  35. Arrays.sort(clone);
  36. Map<Integer, Integer> map = new HashMap<>();
  37. for (int i = n - 1; i >= 0; i--) map.put(clone[i], n - 1 - i);
  38. for (int i = 0; i < n; i++) {
  39. int rank = map.get(score[i]);
  40. ans[i] = rank < 3 ? ss[rank] : String.valueOf(rank + 1);
  41. }
  42. return ans;
  43. }
  44. }

克隆数组:

int[] score = {1,2,3};
int[] clone = score.clone();


2023/5/31

题目(完成一半)539:最小时间差            我自己的思路和答案第一种解法相同,就是写法不同

  1. 我写的
  2. class Solution {
  3. public int findMinDifference(List<String> timePoints) {
  4. int[] res_res = new int[timePoints.size() * 2];
  5. int i = 0;
  6. for(String s : timePoints){
  7. char[] res = s.toCharArray();
  8. 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){
  9. res_res[i] = 23 * 60 + 60;
  10. res_res[i + timePoints.size()] = 0;
  11. }else if(Integer.parseInt(String.valueOf(res[0])) == 0 && Integer.parseInt(String.valueOf(res[1])) == 0){
  12. res_res[i] = 23 * 60 + (Integer.parseInt(String.valueOf(res[3])) *10 + Integer.parseInt(String.valueOf(res[4])));
  13. res_res[i + timePoints.size()] = (Integer.parseInt(String.valueOf(res[3])) *10 + Integer.parseInt(String.valueOf(res[4])));
  14. }else{
  15. 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])));
  16. }
  17. i++;
  18. }
  19. Arrays.sort(res_res);
  20. int res_min = Integer.MAX_VALUE;
  21. for(int k = 1; k < res_res.length;k++){
  22. res_min = Math.min(res_min,Math.abs(res_res[k] - res_res[k-1]));
  23. }
  24. return res_min;
  25. }
  26. }
  27. 宫水三叶
  28. class Solution {
  29. public int findMinDifference(List<String> timePoints) {
  30. int n = timePoints.size() * 2;
  31. int[] nums = new int[n];
  32. for (int i = 0, idx = 0; i < n / 2; i++, idx += 2) {
  33. String[] ss = timePoints.get(i).split(":");
  34. int h = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);
  35. nums[idx] = h * 60 + m;
  36. nums[idx + 1] = nums[idx] + 1440;
  37. }
  38. Arrays.sort(nums);
  39. int ans = nums[1] - nums[0];
  40. for (int i = 0; i < n - 1; i++) ans = Math.min(ans, nums[i + 1] - nums[i]);
  41. return ans;
  42. }
  43. }
  44. 宫水三叶
  45. class Solution {
  46. public int findMinDifference(List<String> timePoints) {
  47. int n = timePoints.size();
  48. if (n > 1440) return 0;
  49. int[] cnts = new int[1440 * 2 + 10];
  50. for (String s : timePoints) {
  51. String[] ss = s.split(":");
  52. int h = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);
  53. cnts[h * 60 + m]++;
  54. cnts[h * 60 + m + 1440]++;
  55. }
  56. int ans = 1440, last = -1;
  57. for (int i = 0; i <= 1440 * 2 && ans != 0; i++) {
  58. if (cnts[i] == 0) continue;
  59. if (cnts[i] > 1) ans = 0;
  60. else if (last != -1) ans = Math.min(ans, i - last);
  61. last = i;
  62. }
  63. return ans;
  64. }
  65. }

int的最大值:Integer.MAX_VALUE

数字,字符,字符串相互转化:(126条消息) Java数字、字符、字符串互相转换_java数字转字符串_有时候我也会的博客-CSDN博客

Java获取List元素:String s:timePoints

获取字符串中的数字(分割):String[] ss = timePoints.get(i).split(":");


2023/6/1

题目(未完成)533:最优除法           脑筋急转弯

  1. class Solution {
  2. public String optimalDivision(int[] nums) {
  3. StringBuilder res = new StringBuilder();
  4. for(int i = 0;i < nums.length;i++){
  5. if(nums.length >= 3){
  6. if(i < nums.length - 1){
  7. if(i == 1) res.append("(" + nums[i] + "/");
  8. else res.append(nums[i] + "/");
  9. }else{
  10. res.append(nums[i] + ")");
  11. }
  12. }else if(nums.length == 1){
  13. res.append(nums[i]);
  14. }else{
  15. if(i < nums.length - 1){
  16. res.append(nums[i] + "/");
  17. }else res.append(nums[i]);
  18. }
  19. }
  20. return res.toString();
  21. }
  22. }
  23. 宫水三叶
  24. class Solution {
  25. public String optimalDivision(int[] nums) {
  26. int n = nums.length;
  27. StringBuilder sb = new StringBuilder();
  28. for (int i = 0; i < n; i++) {
  29. sb.append(nums[i]);
  30. if (i + 1 < n) sb.append("/");
  31. }
  32. if (n > 2) {
  33. sb.insert(sb.indexOf("/") + 1, "(");
  34. sb.append(")");
  35. }
  36. return sb.toString();
  37. }
  38. }

indexOf:返回指定字符在字符串中第一次出现处的索引,如果此字符串中没有这样的字符,则返回 -1。


题目(未完成)537:复数乘法               思路是对的,就是处理过程有问题       java.split

  1. class Solution {
  2. public String complexNumberMultiply(String num1, String num2) {
  3. // a + bi c + di
  4. //(ac - bd) + (ad + bc)i
  5. StringBuilder res = new StringBuilder();
  6. char[] num1_char = num1.toCharArray();
  7. char[] num2_char = num2.toCharArray();
  8. int b,d = 0;
  9. int a = Integer.parseInt(String.valueOf(num1_char[0]));
  10. if(num1_char[2] == '-'){
  11. String temp = String.valueOf(num1_char[3]);
  12. b = -Integer.parseInt(temp);
  13. }else{
  14. b = Integer.parseInt(String.valueOf(num1_char[2]));
  15. }
  16. int c = Integer.parseInt(String.valueOf(num2_char[0]));
  17. if(num2_char[2] == '-'){
  18. String temp = String.valueOf(num2_char[3]);
  19. d = Integer.parseInt(temp);
  20. }else{
  21. d = Integer.parseInt(String.valueOf(num1_char[2]));
  22. }
  23. // int d = Integer.parseInt(String.valueOf(num2_char[2]));
  24. res.append(a*c - b*d);
  25. res.append('+');
  26. res.append(a*d + b*c);
  27. res.append('i');
  28. return res.toString();
  29. }
  30. }
  31. 宫水三叶
  32. class Solution {
  33. public String complexNumberMultiply(String num1, String num2) {
  34. String[] ss1 = num1.split("\\+|i"), ss2 = num2.split("\\+|i");
  35. int a = parse(ss1[0]), b = parse(ss1[1]);
  36. int c = parse(ss2[0]), d = parse(ss2[1]);
  37. int A = a * c - b * d, B = b * c + a * d;
  38. return A + "+" + B + "i";
  39. }
  40. int parse(String s) {
  41. return Integer.parseInt(s);
  42. }
  43. }

(126条消息) Java split方法详细讲解_一只光头猿的博客-CSDN博客


2023/6/7

题目(未完成)592:分数加减运算     我写的和答案思路是一样的 但是我处理方法想复杂了

  1. 我写的
  2. class Solution {
  3. public String fractionAddition(String expression) {
  4. String[] test_1 = expression.split("\\d/\\d");// + -
  5. String[] test_2 = expression.split("\\+|-");//1/3 2/3
  6. int fenzi = 0;
  7. int fenmu = 1;
  8. for(int i = 0;i < test_1.length;i++){
  9. char ch = test_1.charAt(i);//获取是正数还是负数
  10. char[] res = test_2[i].toCharArray();//将1/3中的分子和分母的数值提取出来
  11. int res_fenzi = Integer.parseInt(String.valueOf(res[0]));
  12. int res_fenmu = Integer.parseInt(String.valueOf(res[2]));
  13. if(ch == '-'){
  14. fenzi = (fenzi * res_fenmu) - (res_fenzi * fenmu);
  15. fenmu = fenmu * res_fenmu;
  16. }else{
  17. fenzi = (fenzi * res_fenmu) + (res_fenzi * fenmu);
  18. fenmu = fenmu * res_fenmu;
  19. }
  20. }
  21. }
  22. }
  23. 答案
  24. class Solution {
  25. public String fractionAddition(String expression) {
  26. long x = 0, y = 1; // 分子,分母
  27. int index = 0, n = expression.length();
  28. while (index < n) {
  29. // 读取分子
  30. long x1 = 0, sign = 1;
  31. if (expression.charAt(index) == '-' || expression.charAt(index) == '+') {
  32. sign = expression.charAt(index) == '-' ? -1 : 1;
  33. index++;
  34. }
  35. while (index < n && Character.isDigit(expression.charAt(index))) {
  36. x1 = x1 * 10 + expression.charAt(index) - '0';//处理32/65这种情况的
  37. index++;
  38. }
  39. x1 = sign * x1;
  40. index++;
  41. // 读取分母
  42. long y1 = 0;
  43. while (index < n && Character.isDigit(expression.charAt(index))) {
  44. y1 = y1 * 10 + expression.charAt(index) - '0';//处理32/65这种情况的
  45. index++;
  46. }
  47. x = x * y1 + x1 * y;
  48. y *= y1;
  49. }
  50. if (x == 0) {
  51. return "0/1";
  52. }
  53. long g = gcd(Math.abs(x), y); // 获取最大公约数
  54. return Long.toString(x / g) + "/" + Long.toString(y / g);
  55. }
  56. public long gcd(long a, long b) {
  57. long remainder = a % b;
  58. while (remainder != 0) {
  59. a = b;
  60. b = remainder;
  61. remainder = a % b;
  62. }
  63. return b;
  64. }
  65. }

long 数据类型用于保存 int 无法保存的较大整数

字符转数字的快捷办法:expression.charAt(index) - '0';

判断指定字符是否是数字:Character.isDigit(expression.charAt(index));


2023/6/8

题目(感觉就差最后一点了) 640:求解方程         我写的感觉就差个x前多位系数的处理了

  1. 我写的
  2. class Solution {
  3. public String solveEquation(String equation) {
  4. String[] res = equation.split("\\=");
  5. int left_x_final = 0;
  6. int left_num_final = 0;
  7. for(String s : res){
  8. int left_x = 0;
  9. int left_num = 0;
  10. int index = 0;
  11. int lengths = s.length();//x+5-3+x
  12. int sign = 1;
  13. while(index < lengths){
  14. if(index < lengths && s.charAt(index) == 'x'){
  15. if(index - 1 < 0){
  16. left_x++;
  17. }else if(index - 1 >= 0 && s.charAt(index - 1) == '+'){
  18. left_x++;
  19. }else if(index - 1 >= 0 && s.charAt(index - 1) == '-'){
  20. left_x--;
  21. }else if(index - 1 >= 0 && Character.isDigit(s.charAt(index - 1))){
  22. if(index - 2 < 0){
  23. left_x = left_x + (s.charAt(index - 1) - '0');
  24. }else if(index - 2 >= 0 && s.charAt(index - 2) == '+'){
  25. left_x = left_x + (s.charAt(index - 1) - '0');
  26. }else if(index - 2 >= 0 && s.charAt(index - 2) == '-'){
  27. left_x = left_x - (s.charAt(index - 1) - '0');
  28. }
  29. }
  30. index++;
  31. }
  32. if(index < lengths && (s.charAt(index) == '-' || s.charAt(index) == '+')){
  33. sign = s.charAt(index) == '-' ? -1 : 1;
  34. index++;
  35. }
  36. int temp = 0;
  37. while(index < lengths && Character.isDigit(s.charAt(index))){
  38. if(index + 1 < lengths && s.charAt(index + 1) == 'x'){
  39. index++;
  40. break;
  41. }else{
  42. temp = temp * 10 +(sign * (s.charAt(index) - '0'));
  43. // left_num += sign * (s.charAt(index) - '0');
  44. }
  45. index++;
  46. }
  47. left_num = left_num + temp;
  48. }
  49. if(left_x_final == 0 && left_num_final == 0){
  50. left_x_final = left_x;
  51. left_num_final = left_num;
  52. }else{
  53. if(left_x_final == left_x && left_num_final == left_num){
  54. return "Infinite solutions";
  55. }else{
  56. if(left_x_final > left_x){
  57. return "x=" + String.valueOf((left_num - left_num_final)/(left_x_final - left_x));
  58. }else if(left_x > left_x_final){
  59. return "x=" + String.valueOf((left_num_final - left_num)/(left_x - left_x_final));
  60. }
  61. }
  62. }
  63. }
  64. return "No solution";
  65. }
  66. }
  67. 答案
  68. class Solution {
  69. public String solveEquation(String equation) {
  70. int factor = 0, val = 0;
  71. int index = 0, n = equation.length(), sign1 = 1; // 等式左边默认系数为正
  72. while (index < n) {
  73. if (equation.charAt(index) == '=') {
  74. sign1 = -1; // 等式右边默认系数为负 相当于都移动到左边计算
  75. index++;
  76. continue;
  77. }
  78. int sign2 = sign1, number = 0;
  79. boolean valid = false; // 记录 number 是否有效
  80. if (equation.charAt(index) == '-' || equation.charAt(index) == '+') { // 去掉前面的符号
  81. sign2 = (equation.charAt(index) == '-') ? -sign1 : sign1;
  82. index++;
  83. }
  84. while (index < n && Character.isDigit(equation.charAt(index))) {
  85. number = number * 10 + (equation.charAt(index) - '0');
  86. index++;
  87. valid = true;
  88. }
  89. if (index < n && equation.charAt(index) == 'x') { // 变量
  90. factor += valid ? sign2 * number : sign2;//走这里说明是x的系数
  91. index++;
  92. } else { // 数值
  93. val += sign2 * number; //走这里说明是常量
  94. }
  95. }
  96. if (factor == 0) {
  97. return val == 0 ? "Infinite solutions" : "No solution";
  98. }
  99. return "x=" + (-val / factor); //再把常数项移回到右边 所以要再加负号
  100. }
  101. }

答案确实高明


2023/6/13

题目(完成)38:外观数列

  1. class Solution {
  2. public String countAndSay(int n) {
  3. String res = "1";
  4. for(int i = 0;i < n - 1;i++){
  5. StringBuilder res_test = new StringBuilder();
  6. String temp = res;
  7. int k = 0;
  8. while(k < temp.length()){
  9. int times = 0;
  10. char s = temp.charAt(k);
  11. while(k < temp.length() && temp.charAt(k) == s){
  12. k++;
  13. times++;
  14. }
  15. res_test.append(times);
  16. res_test.append(s);
  17. }
  18. res = res_test.toString();
  19. }
  20. return res;
  21. }
  22. }

2023/6/15

题目(我觉得没问题说实话,但是未通过)443:压缩字符串

我和三叶姐的思路是一模一样的

  1. 我写的
  2. class Solution {
  3. public int compress(char[] chars) {
  4. int k = 0;
  5. int res = 0;
  6. int pointer = 0;
  7. if(chars.length == 1){
  8. res = 1;
  9. return res;
  10. }
  11. while(k < chars.length){
  12. int times = 0;
  13. int times_copy = 0;
  14. char temp = chars[k];
  15. int times_times = 0;//统计一共有几位数
  16. int sentinel = 0;
  17. // pointer = k; //记录第一个字母的坐标
  18. while(k < chars.length && chars[k] == temp){
  19. k++;
  20. times++;
  21. }
  22. times_copy = times;
  23. //res负责记录整个数组最后的长度
  24. res++;
  25. res++;
  26. times_times++;
  27. while(times / 10 != 0){
  28. times = times / 10;
  29. res++;
  30. times_times++;
  31. }
  32. chars[pointer] = temp;
  33. pointer++;
  34. if(times_copy > 1){
  35. if(times_times == 1){
  36. chars[pointer] = Integer.toString(times_copy).charAt(0);
  37. pointer++;
  38. }else{
  39. sentinel = pointer + times_times - 1;
  40. chars[sentinel] = Integer.toString(times_copy % 10).charAt(0);//个位
  41. sentinel--;
  42. pointer++;
  43. while(times_copy / 10 != 0){
  44. chars[sentinel] = Integer.toString(times_copy / 10 % 10).charAt(0);
  45. times_copy = times_copy /10;
  46. sentinel--;
  47. pointer++;
  48. }
  49. }
  50. }
  51. }
  52. return res;
  53. }
  54. }
  55. 宫水三叶
  56. class Solution {
  57. public int compress(char[] cs) {
  58. int n = cs.length;
  59. int i = 0, j = 0;
  60. while (i < n) {
  61. int idx = i;
  62. while (idx < n && cs[idx] == cs[i]) idx++;
  63. int cnt = idx - i;
  64. cs[j++] = cs[i];
  65. if (cnt > 1) {
  66. int start = j, end = start;
  67. while (cnt != 0) {
  68. cs[end++] = (char)((cnt % 10) + '0');
  69. cnt /= 10;
  70. }
  71. reverse(cs, start, end - 1);
  72. j = end;
  73. }
  74. i = idx;
  75. }
  76. return j;
  77. }
  78. void reverse(char[] cs, int start, int end) {
  79. while (start < end) {
  80. char t = cs[start];
  81. cs[start] = cs[end];
  82. cs[end] = t;
  83. start++; end--;
  84. }
  85. }
  86. }

2023/6/20

题目(完成)13:罗马整数转数字

  1. class Solution {
  2. public int romanToInt(String s) {
  3. char[] res = s.toCharArray();
  4. int res_num = 0;
  5. int i = 0;
  6. while(i < res.length){
  7. if(res[i] == 'I'){
  8. if(i + 1 < res.length && res[i + 1] == 'V'){
  9. res_num = res_num + 4;
  10. i++;
  11. i++;
  12. if(i >= res.length) break;
  13. }else if(i + 1 < res.length && res[i + 1] == 'X'){
  14. res_num = res_num + 9;
  15. i++;
  16. i++;
  17. if(i >= res.length) break;
  18. }else{
  19. res_num = res_num + 1;
  20. i++;
  21. if(i >= res.length) break;
  22. }
  23. }
  24. if(res[i] == 'V'){
  25. res_num = res_num + 5;
  26. i++;
  27. if(i >= res.length) break;
  28. }
  29. if(res[i] == 'X'){
  30. if(i + 1 < res.length && res[i + 1] == 'L'){
  31. res_num = res_num + 40;
  32. i++;
  33. i++;
  34. if(i >= res.length) break;
  35. }else if(i + 1 < res.length && res[i + 1] == 'C'){
  36. res_num = res_num + 90;
  37. i++;
  38. i++;
  39. if(i >= res.length) break;
  40. }else{
  41. res_num = res_num + 10;
  42. i++;
  43. if(i >= res.length) break;
  44. }
  45. }
  46. if(res[i] == 'L'){
  47. res_num = res_num + 50;
  48. i++;
  49. if(i >= res.length) break;
  50. }
  51. if(res[i] == 'C'){
  52. if(i + 1 < res.length && res[i + 1] == 'D'){
  53. res_num = res_num + 400;
  54. i++;
  55. i++;
  56. if(i >= res.length) break;
  57. }else if(i + 1 < res.length && res[i + 1] == 'M'){
  58. res_num = res_num + 900;
  59. i++;
  60. i++;
  61. if(i >= res.length) break;
  62. }else{
  63. res_num = res_num + 100;
  64. i++;
  65. if(i >= res.length) break;
  66. }
  67. }
  68. if(res[i] == 'D'){
  69. res_num = res_num + 500;
  70. i++;
  71. if(i >= res.length) break;
  72. }
  73. if(res[i] == 'M'){
  74. res_num = res_num + 1000;
  75. i++;
  76. if(i >= res.length) break;
  77. }
  78. }
  79. return res_num;
  80. }
  81. }

题目(完成)12:整数转罗马数字

  1. class Solution {
  2. public String intToRoman(int num) {
  3. StringBuilder res = new StringBuilder();
  4. while(0 < num){
  5. //处理千位及以上
  6. while(1000 <= num){
  7. num = num - 1000;
  8. res.append("M");
  9. if(num <= 0) break;
  10. }
  11. //处理百位
  12. if(900 <= num && num < 1000){
  13. num = num - 900;
  14. res.append("CM");
  15. if(num <= 0) break;
  16. }else if(500 <= num && num < 900){
  17. num = num - 500;
  18. res.append("D");
  19. if(num <= 0) break;
  20. }else if(400 <= num && num < 500){
  21. num = num - 400;
  22. res.append("CD");
  23. if(num <= 0) break;
  24. }else if(100 <= num && num < 400){
  25. while(100 <= num){
  26. num = num - 100;
  27. res.append("C");
  28. if(num <= 0) break;
  29. }
  30. }
  31. //处理十位
  32. if(90 <= num && num < 100){
  33. num = num - 90;
  34. res.append("XC");
  35. if(num <= 0) break;
  36. }else if(50 <= num && num < 90){
  37. num = num - 50;
  38. res.append("L");
  39. if(num <= 0) break;
  40. }else if(40 <= num && num < 50){
  41. num = num - 40;
  42. res.append("XL");
  43. if(num <= 0) break;
  44. }else if(10 <= num && num < 40){
  45. while(10 <= num){
  46. num = num - 10;
  47. res.append("X");
  48. if(num <= 0) break;
  49. }
  50. }
  51. //处理个位
  52. if(9 <= num && num < 10){
  53. num = num - 9;
  54. res.append("IX");
  55. if(num <= 0) break;
  56. }else if(5 <= num && num < 9){
  57. num = num - 5;
  58. res.append("V");
  59. if(num <= 0) break;
  60. }else if(4 <= num && num < 5){
  61. num = num - 4;
  62. res.append("IV");
  63. if(num <= 0) break;
  64. }else if(1 <= num && num < 4){
  65. while(1 <= num){
  66. num = num - 1;
  67. res.append("I");
  68. if(num <= 0) break;
  69. }
  70. }
  71. }
  72. return res.toString();
  73. }
  74. }

2023/6/25

题目(我尽力了,未完成)273:整数转换英文表示

  1. 我写的 又臭又长
  2. class Solution {
  3. static String[] TheUnit = {"One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};
  4. static String[] TheTen = {"Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
  5. static String[] TheTen_Integer = {"Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
  6. public String numberToWords(int num) {
  7. StringBuilder res = new StringBuilder();
  8. String temp = String.valueOf(num);
  9. char[] res_ch = temp.toCharArray();
  10. if(0 <= res_ch.length && res_ch.length < 4){
  11. if(res_ch.length == 3){
  12. res.append(TheUnit[(res_ch[0] - '0') - 1]);
  13. res.append(" ");
  14. res.append("Hundred");
  15. res.append(" ");
  16. if(res_ch[1] == '1'){
  17. res.append(TheTen[res_ch[2] - '0']);
  18. // res.append(" ");
  19. }else if(res_ch[1] != '1' && res_ch[1] != '0'){
  20. res.append(TheTen_Integer[(res_ch[1] - '0') - 2]);
  21. res.append(" ");
  22. if(res_ch[2] != '0'){
  23. // res.appned(TheUnit[(res_ch[2] - '0') - 1]);
  24. res.append(TheUnit[(res_ch[2] - '0') - 1]);
  25. // res.append(" ");
  26. }
  27. }
  28. }else if(res_ch.length == 2){
  29. if(res_ch[0] == '1'){
  30. res.append(TheTen[res_ch[1] - '0']);
  31. // res.append(" ");
  32. }else{
  33. res.append(TheTen_Integer[(res_ch[0] - '0') - 2]);
  34. res.append(" ");
  35. if(res_ch[1] != '0'){
  36. res.append(TheUnit[(res_ch[1] - '0') - 1]);
  37. // res.append(" ");
  38. }
  39. }
  40. }else if(res_ch.length == 1){
  41. res.append(TheUnit[(res_ch[1] - '0') - 1]);
  42. // res.append(" ");
  43. }
  44. }else if(4 <= res_ch.length && res_ch.length < 7){
  45. int times = 0;
  46. if(res_ch.length == 6){
  47. times = 3;
  48. res.append(TheUnit[(res_ch[0] - '0') - 1]);
  49. res.append(" ");
  50. res.append("Hundred");
  51. res.append(" ");
  52. if(res_ch[1] == '1'){
  53. res.append(TheTen[res_ch[2] - '0']);
  54. res.append(" ");
  55. }else{
  56. res.append(TheTen_Integer[(res_ch[1] - '0') - 2]);
  57. res.append(" ");
  58. if(res_ch[2] != '0'){
  59. // res.appned(TheUnit[(res_ch[2] - '0') - 1]);
  60. res.append(TheUnit[(res_ch[2] - '0') - 1]);
  61. res.append(" ");
  62. }
  63. }
  64. }else if(res_ch.length == 5){
  65. times = 2;
  66. if(res_ch[0] == '1'){
  67. res.append(TheTen[res_ch[1] - '0']);
  68. res.append(" ");
  69. }else{
  70. res.append(TheTen_Integer[(res_ch[0] - '0') - 2]);
  71. res.append(" ");
  72. if(res_ch[1] != '0'){
  73. res.append(TheUnit[(res_ch[1] - '0') - 1]);
  74. res.append(" ");
  75. }
  76. }
  77. }else if(res_ch.length == 4){
  78. times = 1;
  79. res.append(TheUnit[(res_ch[0] - '0') - 1]);
  80. res.append(" ");
  81. }
  82. res.append("Thousand");
  83. res.append(" ");
  84. res.append(TheUnit[(res_ch[times] - '0') - 1]);
  85. res.append(" ");
  86. res.append("Hundred");
  87. res.append(" ");
  88. if(res_ch[times + 1] == '1'){
  89. res.append(TheTen[res_ch[times + 2] - '0']);
  90. // res.append(" ");
  91. }else{
  92. res.append(TheTen_Integer[(res_ch[times + 1] - '0') - 2]);
  93. res.append(" ");
  94. if(res_ch[times + 2] != '0'){
  95. // res.appned(TheUnit[(res_ch[2] - '0') - 1]);
  96. res.append(TheUnit[(res_ch[times + 2] - '0') - 1]);
  97. // res.append(" ");
  98. }
  99. }
  100. }else if(7 <= res_ch.length && res_ch.length < 10){
  101. if(res_ch.length == 9){
  102. res.append(TheUnit[(res_ch[0] - '0') - 1]);
  103. res.append(" ");
  104. res.append("Hundred");
  105. res.append(" ");
  106. if(res_ch[1] == '1'){
  107. res.append(TheTen[res_ch[2] - '0']);
  108. // res.append(" ");
  109. }else{
  110. res.append(TheTen_Integer[(res_ch[1] - '0') - 2]);
  111. // res.append(" ");
  112. if(res_ch[2] != '0'){
  113. // res.appned(TheUnit[(res_ch[2] - '0') - 1]);
  114. res.append(TheUnit[(res_ch[2] - '0') - 1]);
  115. // res.append(" ");
  116. }
  117. }
  118. }else if(res_ch.length == 8){
  119. if(res_ch[0] == '1'){
  120. res.append(TheTen[res_ch[1] - '0']);
  121. // res.append(" ");
  122. }else{
  123. res.append(TheTen_Integer[(res_ch[0] - '0') - 2]);
  124. res.append(" ");
  125. if(res_ch[1] != '0'){
  126. res.append(TheUnit[(res_ch[1] - '0') - 1]);
  127. // res.append(" ");
  128. }
  129. }
  130. }else if(res_ch.length == 7){
  131. res.append(TheUnit[(res_ch[1] - '0') - 1]);
  132. // res.append(" ");
  133. }
  134. res.append("Millon");
  135. res.append(" ");
  136. }else if(res_ch.length == 10){
  137. }
  138. return res.toString();
  139. }
  140. public void test(char[] res_ch){
  141. }
  142. }
  143. 宫水三叶
  144. class Solution {
  145. static String[] num2str_small = {
  146. "Zero",
  147. "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
  148. "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"
  149. };
  150. static String[] num2str_medium = {
  151. "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"
  152. };
  153. static String[] num2str_large = {
  154. "Billion", "Million", "Thousand", "",
  155. };
  156. String num2Str(int x) {
  157. String ans = "";
  158. if (x >= 100) {
  159. ans += num2str_small[x / 100] + " Hundred ";
  160. x %= 100;
  161. }
  162. if (x >= 20) {
  163. ans += num2str_medium[x / 10] + " ";
  164. x %= 10;
  165. }
  166. if (x != 0) ans += num2str_small[x] + " ";
  167. return ans;
  168. }
  169. public String numberToWords(int num) {
  170. if (num == 0) return num2str_small[0];
  171. StringBuilder sb = new StringBuilder();
  172. for (int i = (int)1e9, j = 0; i >= 1; i /= 1000, j++) {
  173. if (num < i) continue;
  174. sb.append(num2Str(num / i) + num2str_large[j] + " ");
  175. num %= i;
  176. }
  177. while (sb.charAt(sb.length() - 1) == ' ') sb.deleteCharAt(sb.length() - 1);
  178. return sb.toString();
  179. }
  180. }

while(sb.charAt(sb.length() - 1) == ' ') sb.deleteCharAt(sb.length() - 1);


2023/6/25

题目(我感觉我是完成了的,但是最后一个案例未通过,自己在idea试是可以的)165:比较版本号

  1. class Solution {
  2. public int compareVersion(String version1, String version2) {
  3. String[] vers1 = version1.split("\\.");
  4. String[] vers2 = version2.split("\\.");
  5. int length = Math.min(vers1.length,vers2.length);
  6. // int temp = 0;
  7. // int i = 0;
  8. for(int i = 0;i < length;i++){
  9. if(vers1[i] == vers2[i]) continue;
  10. else{
  11. int vers1_num = 0;
  12. if(vers1[i].length() != 1 && vers1[i].charAt(0) == '0'){
  13. int k = 0;
  14. while(k < vers1[i].length() && vers1[i].charAt(k) == '0') k++;
  15. while(k < vers1[i].length()){
  16. vers1_num = vers1_num * 10 + (vers1[i].charAt(k) + '0');
  17. k++;
  18. }
  19. }else if(vers1[i].length() != 1 && vers1[i].charAt(0) != '0'){
  20. int k = 0;
  21. while(k < vers1[i].length()){
  22. vers1_num = vers1_num * 10 + (vers1[i].charAt(k) + '0');
  23. k++;
  24. }
  25. }else if(vers1[i].length() == 1){
  26. vers1_num = vers1[i].charAt(0) + '0';
  27. }
  28. int vers2_num = 0;
  29. if(vers2[i].length() != 1 && vers2[i].charAt(0) == '0'){
  30. int k = 0;
  31. while(k < vers2[i].length() && vers2[i].charAt(k) == '0') k++;
  32. while(k < vers2[i].length()){
  33. vers2_num = vers2_num * 10 + (vers2[i].charAt(k) + '0');
  34. k++;
  35. }
  36. }else if(vers2[i].length() != 1 && vers2[i].charAt(0) != '0'){
  37. int k = 0;
  38. while(k < vers2[i].length()){
  39. vers2_num = vers2_num * 10 + (vers2[i].charAt(k) + '0');
  40. k++;
  41. }
  42. }else if(vers2[i].length() == 1){
  43. vers2_num = vers2[i].charAt(0) + '0';
  44. }
  45. if(vers1_num == vers2_num) continue;
  46. else if(vers1_num > vers2_num){
  47. return 1;
  48. }else if(vers1_num < vers2_num){
  49. return -1;
  50. }
  51. }
  52. }
  53. //走到这有两种情况 一种是真的是只能返回0 另一种是两个长度不一样
  54. if(vers1.length > vers2.length){
  55. for(int j = vers2.length;j < vers1.length;j++){
  56. if(vers1[j].length() == 1 && vers1[j].charAt(0) != '0') return 1;
  57. else if(vers1[j].length() > 1){
  58. for(int m = 0;m < vers1[j].length();m++){
  59. if(vers1[j].charAt(m) != '0') return 1;
  60. }
  61. }
  62. }
  63. return 0;
  64. }
  65. if(vers2.length > vers1.length){
  66. for(int j = vers1.length;j < vers2.length;j++){
  67. if(vers2[j].length() == 1 && vers2[j].charAt(0) != '0') return -1;
  68. else if(vers2[j].length() > 1){
  69. for(int m = 0;m < vers2[j].length();m++){
  70. if(vers2[j].charAt(m) != '0') return -1;
  71. }
  72. }
  73. // else return -1;
  74. }
  75. return 0;
  76. }
  77. return 0;
  78. }
  79. }
  80. 宫水三叶
  81. class Solution {
  82. public int compareVersion(String v1, String v2) {
  83. String[] ss1 = v1.split("\\."), ss2 = v2.split("\\.");
  84. int n = ss1.length, m = ss2.length;
  85. int i = 0, j = 0;
  86. while (i < n || j < m) {
  87. int a = 0, b = 0;
  88. if (i < n) a = Integer.parseInt(ss1[i++]);
  89. if (j < m) b = Integer.parseInt(ss2[j++]);
  90. if (a != b) return a > b ? 1 : -1;
  91. }
  92. return 0;
  93. }
  94. }

还得是三叶姐


2023/6/26

题目(完成)481:神奇字符串                         不知道为什么突然就成功了,本来还以为不行

  1. class Solution {
  2. public int magicalString(int n) {
  3. if(n <= 3) return 1;
  4. int res = 1;
  5. String s = "122";
  6. String s_guide = "122";
  7. int length = s.length(); //初始的长度
  8. // int s_pointer = 2;
  9. int s_guide_pointer = 2;
  10. char temp = '1';
  11. while(length < n){
  12. int times = s_guide.charAt(s_guide_pointer) - '0';
  13. for(int i = 0;i < times;i++){
  14. if(length < n){
  15. s += temp;
  16. if(temp == '1') res++;
  17. length++;
  18. }else{
  19. break;
  20. }
  21. }
  22. s_guide = s;
  23. s_guide_pointer++;
  24. if(s_guide_pointer % 2 == 0){
  25. temp = '1';
  26. }else{
  27. temp = '2';
  28. }
  29. }
  30. return res;
  31. }
  32. }

2023/6/27

题目(完成)392:判断子序列        第85道

  1. 我写的
  2. class Solution {
  3. public boolean isSubsequence(String s, String t) {
  4. //s是否为t的子序列
  5. int i = 0;
  6. int k = 0;
  7. int k_pointer = -1;
  8. while(i < s.length()){
  9. char temp = s.charAt(i);
  10. while(k < t.length() && t.charAt(k) != temp) k++;
  11. if(k == t.length()) return false;
  12. if(k > k_pointer){
  13. k_pointer = k;
  14. k++;//最后一个案例一直没通过的原因在于少了这行
  15. }else{
  16. return false;
  17. }
  18. i++;
  19. }
  20. return true;
  21. }
  22. }
  23. 答案
  24. class Solution {
  25. public boolean isSubsequence(String s, String t) {
  26. int n = s.length(), m = t.length();
  27. int i = 0, j = 0;
  28. while (i < n && j < m) {
  29. if (s.charAt(i) == t.charAt(j)) {
  30. i++;
  31. }
  32. j++;
  33. }
  34. return i == n;
  35. }
  36. }

题目(未完成)524:通过删除字母匹配到字典里最长单词      没有理解并处理好字典序

类似Map、Set、List等集合中元素排序,想想Collections.sort()

  1. 我写的
  2. class Solution {
  3. public String findLongestWord(String s, List<String> dictionary) {
  4. int length = 0;
  5. String res = "";
  6. int length_pointer = 0;
  7. // int Alphabetical_order_temp = 0;//存储上一个符合要求的字符序
  8. for(String str : dictionary){
  9. int i = 0 , j = 0;
  10. //str是短的 s是长的
  11. int Alphabetical_order = 0;//如果答案不止一个,返回长度最长且字母序最小
  12. while(i < str.length() && j < s.length()){
  13. if(str.charAt(i) == s.charAt(j)){
  14. if(Alphabetical_order == 0){
  15. char first_AlAlphabetical = str.charAt(i);
  16. }
  17. i++;
  18. // Alphabetical_order += j;
  19. }
  20. j++;
  21. if(i == str.length()){
  22. if(str.length() > length){
  23. //如果答案不止一个,返回长度最长且字母序最小
  24. length = str.length();
  25. res = str;
  26. }else if(str.length() == length){
  27. // if(Alphabetical_order < Alphabetical_order_temp){
  28. // res = str;
  29. // }
  30. }
  31. // Alphabetical_order_temp = Alphabetical_order;
  32. }
  33. }
  34. }
  35. return res;
  36. }
  37. }
  38. 最好理解的答案
  39. class Solution {
  40. public String findLongestWord(String s, List<String> dictionary) {
  41. String res = "";
  42. for (String t : dictionary) {
  43. int i = 0, j = 0;
  44. while (i < t.length() && j < s.length()) {
  45. if (t.charAt(i) == s.charAt(j)) {
  46. ++i;
  47. }
  48. ++j;
  49. }
  50. if (i == t.length()) {
  51. if (t.length() > res.length() || (t.length() == res.length() && t.compareTo(res) < 0)) {
  52. res = t;
  53. }
  54. }
  55. }
  56. return res;
  57. }
  58. }
  59. 宫水三叶
  60. class Solution {
  61. public String findLongestWord(String s, List<String> list) {
  62. Collections.sort(list, (a,b)->{
  63. if (a.length() != b.length()) return b.length() - a.length();
  64. return a.compareTo(b);
  65. });
  66. int n = s.length();
  67. for (String ss : list) {
  68. int m = ss.length();
  69. int i = 0, j = 0;
  70. while (i < n && j < m) {
  71. if (s.charAt(i) == ss.charAt(j)) j++;
  72. i++;
  73. }
  74. if (j == m) return ss;
  75. }
  76. return "";
  77. }
  78. }

什么是字典序:(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

题目(未完成)521:最长特殊序列1                       脑筋急转弯

  1. class Solution {
  2. public int findLUSlength(String a, String b) {
  3. return a.equals(b) ? -1 : Math.max(a.length(), b.length());
  4. }
  5. }

当两字符串不同时,我们总能选择长度不是最小的字符串作为答案,而当两字符串相同时,我们无法找到特殊序列。

题目(未完成)522:最长特殊序列2          答案想不到


2023/7/9

题目(完成)66:加一

  1. class Solution {
  2. public int[] plusOne(int[] digits) {
  3. int n = digits.length -1;
  4. digits[n]++;
  5. while(n>0){
  6. if(digits[n]==10){
  7. digits[n]=0;
  8. digits[n-1]++;
  9. }
  10. n--;
  11. }
  12. if(digits[0]==10){
  13. int []result = new int[digits.length+1];
  14. result[0]=1;
  15. for(int j=1;j<n+1;j++){
  16. result[j]=0;
  17. }
  18. return result;
  19. }
  20. return digits;
  21. }
  22. }
  23. public int[] plusOne(int[] digits) {
  24. for (int i = digits.length - 1; i >= 0; i--) {
  25. if (digits[i] == 9) {
  26. digits[i] = 0;
  27. } else {
  28. digits[i] += 1;
  29. return digits;
  30. }
  31. }
  32. //如果所有位都是进位,则长度+1
  33. digits= new int[digits.length + 1];
  34. digits[0] = 1;
  35. return digits;
  36. }

题目(完成)67:二进制求和

  1. class Solution {
  2. public String addBinary(String a, String b) {
  3. String res = "";
  4. String res_refer = "";
  5. if(a.length() >= b.length()){
  6. res = a;
  7. res_refer = b;
  8. }else{
  9. res = b;
  10. res_refer = a;
  11. }
  12. int length_res = res.length() - 1;
  13. int length = res_refer.length() - 1;
  14. int sign = 0;
  15. int length_Difference = res.length() - res_refer.length();
  16. while(length >= 0 || length_res >= 0){
  17. char[] res_char = res.toCharArray();
  18. int res_ch = res.charAt(length_res) - '0';
  19. int res_refer_ch = 0;
  20. if(length >= 0){
  21. res_refer_ch = res_refer.charAt(length) - '0';
  22. }
  23. if(res_ch + res_refer_ch + sign == 2){
  24. //res.charAt(length + length_Difference) = '0';
  25. res_char[length_res] = '0';
  26. }else if(res_ch + res_refer_ch + sign == 3){
  27. res_char[length_res] = '1';
  28. //res.charAt(length + length_Difference) = '1';
  29. }else if(res_ch + res_refer_ch + sign == 1){
  30. res_char[length_res] = '1';
  31. //res.charAt(length + length_Difference) = '1';
  32. sign = 0;
  33. }
  34. if(res_ch + res_refer_ch == 2){
  35. sign = 1;
  36. }
  37. length--;
  38. length_res--;
  39. res = String.valueOf(res_char);
  40. if(length_res < 0 && sign == 1){
  41. res = '1' + res;
  42. break;
  43. }
  44. }
  45. return res;
  46. }
  47. }

2023/7/10

题目(完成)415:字符串相加

  1. class Solution {
  2. public String addStrings(String a, String b) {
  3. String res = "";
  4. String res_refer = "";
  5. if(a.length() >= b.length()){
  6. res = a;
  7. res_refer = b;
  8. }else{
  9. res = b;
  10. res_refer = a;
  11. }
  12. int length_res = res.length() - 1;
  13. int length = res_refer.length() - 1;
  14. int sign = 0;
  15. while(length >= 0 || length_res >= 0){
  16. char[] res_char = res.toCharArray();
  17. int res_ch = res.charAt(length_res) - '0';
  18. int res_refer_ch = 0;
  19. if(length >= 0){
  20. res_refer_ch = res_refer.charAt(length) - '0';
  21. }
  22. if(res_ch + res_refer_ch + sign < 10){
  23. res_char[length_res] = Integer.toString(res_ch + res_refer_ch + sign).charAt(0);
  24. sign = 0;
  25. }else{
  26. res_char[length_res] = Integer.toString(res_ch + res_refer_ch + sign - 10).charAt(0);
  27. sign = 1;
  28. }
  29. length--;
  30. length_res--;
  31. res = String.valueOf(res_char);
  32. if(length_res < 0 && sign == 1){
  33. res = '1' + res;
  34. break;
  35. }
  36. }
  37. return res;
  38. }
  39. }

2023/7/14

题目(完成一半)43:字符串相乘                我写的直接将思路里每一步的结果相加,所以就处理不了太长的结果;答案是一步步往上加的,就很好的避免了我的问题。

  1. class Solution {
  2. public String multiply(String a, String b) {
  3. String res = "";
  4. String res_refer = "";
  5. if(a.length() >= b.length()){
  6. res = a;
  7. res_refer = b;
  8. }else{
  9. res = b;
  10. res_refer = a;
  11. }
  12. int length_res = res.length() - 1;
  13. int length = res_refer.length() - 1;
  14. long times = 0;
  15. long temp = 0;
  16. long res_num = 0;
  17. for(int i = length;i >= 0 ;i--){
  18. int sign = 0;
  19. int beishu = 1;
  20. int res_refer_ch = res_refer.charAt(i) - '0';
  21. int length_res_temp = length_res;
  22. // System.out.println("res_refer_ch:" + res_refer_ch);
  23. char[] res_char = res.toCharArray();
  24. while(length_res_temp >= 0){
  25. int res_ch = res.charAt(length_res_temp) - '0';
  26. // System.out.println("res_ch:" + res_ch);
  27. if(res_ch * res_refer_ch + sign < 10){
  28. res_char[length_res_temp] = Integer.toString(res_ch * res_refer_ch + sign).charAt(0);
  29. sign = 0;
  30. }else{
  31. res_char[length_res_temp] = Integer.toString(res_ch * res_refer_ch + sign).charAt(1);
  32. sign = Integer.toString(res_ch * res_refer_ch + sign).charAt(0) - '0';
  33. }
  34. // System.out.println("res_char[length_res_temp]:" + res_char[length_res_temp]);
  35. // System.out.println("sign:" + sign);
  36. length_res_temp--;
  37. }
  38. if(sign != 0){
  39. temp = Integer.parseInt(sign + String.valueOf(res_char));
  40. }else{
  41. temp = Integer.parseInt(String.valueOf(res_char));
  42. }
  43. // System.out.println("temp:" + temp);
  44. // System.out.println("temp:" + temp);
  45. // System.out.println("times:" + times);
  46. for(int k = 0;k < times;k++){
  47. beishu = beishu * 10;
  48. }
  49. // System.out.println("beishu:" + beishu);
  50. res_num = res_num + temp * beishu;
  51. // System.out.println("res_num:" + res_num);
  52. times++;
  53. }
  54. // if(sign != 0){
  55. // System.out.println(sign + "" + res_num + "");
  56. // }
  57. // System.out.println("sign2:" + sign);
  58. // System.out.println(res_num + "");
  59. return res_num + "";
  60. }
  61. }
  62. class Solution {
  63. /**
  64. * 计算形式
  65. * num1
  66. * x num2
  67. * ------
  68. * result
  69. */
  70. public String multiply(String num1, String num2) {
  71. if (num1.equals("0") || num2.equals("0")) {
  72. return "0";
  73. }
  74. // 保存计算结果
  75. String res = "0";
  76. // num2 逐位与 num1 相乘
  77. for (int i = num2.length() - 1; i >= 0; i--) {
  78. int carry = 0;
  79. // 保存 num2 第i位数字与 num1 相乘的结果
  80. StringBuilder temp = new StringBuilder();
  81. // 补 0
  82. for (int j = 0; j < num2.length() - 1 - i; j++) {
  83. temp.append(0);
  84. }
  85. int n2 = num2.charAt(i) - '0';
  86. // num2 的第 i 位数字 n2 与 num1 相乘
  87. for (int j = num1.length() - 1; j >= 0 || carry != 0; j--) {
  88. int n1 = j < 0 ? 0 : num1.charAt(j) - '0';
  89. int product = (n1 * n2 + carry) % 10;
  90. temp.append(product);
  91. carry = (n1 * n2 + carry) / 10;
  92. }
  93. // 将当前结果与新计算的结果求和作为新的结果
  94. res = addStrings(res, temp.reverse().toString());
  95. }
  96. return res;
  97. }
  98. /**
  99. * 对两个字符串数字进行相加,返回字符串形式的和
  100. */
  101. public String addStrings(String num1, String num2) {
  102. StringBuilder builder = new StringBuilder();
  103. int carry = 0;
  104. for (int i = num1.length() - 1, j = num2.length() - 1;
  105. i >= 0 || j >= 0 || carry != 0;
  106. i--, j--) {
  107. int x = i < 0 ? 0 : num1.charAt(i) - '0';
  108. int y = j < 0 ? 0 : num2.charAt(j) - '0';
  109. int sum = (x + y + carry) % 10;
  110. builder.append(sum);
  111. carry = (x + y + carry) / 10;
  112. }
  113. return builder.reverse().toString();
  114. }
  115. }

2023/7/19

题目(完成)482:密钥格式化

  1. class Solution {
  2. public String licenseKeyFormatting(String s, int k) {
  3. StringBuilder res = new StringBuilder();
  4. int length = s.length() - 1;
  5. int count = 0;
  6. while(length >= 0){
  7. if(length >= 0 && s.charAt(length) != '-'){
  8. res.append(s.charAt(length));
  9. count++;
  10. if(count == k){
  11. res.append('-');
  12. count = 0;
  13. }
  14. }
  15. length--;
  16. }
  17. if(res.length() - 1 >= 0 && res.charAt(res.length()- 1) == '-'){
  18. res.deleteCharAt(res.length() - 1);
  19. }
  20. return res.reverse().toString().toUpperCase();
  21. }
  22. }

题目(完成)6:N字形转换

  1. class Solution {
  2. public String convert(String s, int numRows) {
  3. StringBuilder res = new StringBuilder();
  4. if(numRows == 1) return s;
  5. int multiple = (numRows - 1) * 2;
  6. int rows = 0;
  7. int temp = 0;
  8. while(rows < numRows){
  9. temp = rows;
  10. if(rows == 0 || rows == numRows - 1){
  11. // res.append(s.charAt(temp));
  12. while(temp < s.length()){
  13. res.append(s.charAt(temp));
  14. temp = temp + multiple;
  15. }
  16. }else{
  17. // int temps = rows;
  18. int temp_extra = multiple - temp;
  19. while(temp< s.length()){
  20. res.append(s.charAt(temp));
  21. if(temp_extra < s.length()){
  22. res.append(s.charAt(temp_extra));
  23. }
  24. temp = temp + multiple;
  25. temp_extra = temp_extra + multiple;
  26. }
  27. }
  28. rows++;
  29. }
  30. return res.toString();
  31. }
  32. }

2023/7/20

题目(完成)28:找出字符串中第一个匹配的下标

  1. class Solution {
  2. public int strStr(String a, String b) {
  3. int a_length = a.length();
  4. int b_length = b.length();
  5. int a_pointer = 0;
  6. int b_pointer = 0;
  7. int a_pointer_replace = 0;
  8. int b_pointer_replace = 0;
  9. // int res = a_length;
  10. while(a_pointer < a_length){
  11. if(a.charAt(a_pointer) == b.charAt(b_pointer)){
  12. a_pointer_replace = a_pointer;
  13. b_pointer_replace = b_pointer;
  14. while(a_pointer_replace < a_length && b_pointer_replace < b_length && a.charAt(a_pointer_replace) == b.charAt(b_pointer_replace)){
  15. a_pointer_replace++;
  16. b_pointer_replace++;
  17. }
  18. if(b_pointer_replace == b_length) return a_pointer;
  19. }
  20. a_pointer++;
  21. }
  22. return -1;
  23. }
  24. }

2023/8/25——二叉树专题

二叉树基础知识

java中map的key是有序的,因为其底层实现逻辑是二叉平衡搜索树

深度优先法则:前中后序遍历

广度优先法则:层序遍历 

深度: 二叉树中任意一个节点到根节点的距离  从上往下计数  用前序遍历

高度:二叉树中任意一个节点到叶子节点的距离  从下往上计数  用后序遍历

叶子节点:自己下面不再连接有节点的节点 

二叉搜索树:根节点的值比其左子树的都要大,比其右子树的都要小,子树也是这样

二叉搜索树按照中序遍历的顺序得到的结果是单调递增的

题目(学习)144:二叉树的前序遍历

  1. //递归法
  2. class Solution {
  3. public List<Integer> preorderTraversal(TreeNode root) {
  4. List<Integer> result = new ArrayList<Integer>();
  5. preorder(root, result);//root:根节点 result:存储结果的数组
  6. return result;
  7. }
  8. public void preorder(TreeNode root,List<Integer> result){
  9. if(root == null) return;
  10. result.add(root.val); //中
  11. preorder(root.left,result); //左
  12. preorder(root.right,result); //右
  13. }
  14. }
  15. //迭代法
  16. class Solution {
  17. public List<Integer> preorderTraversal(TreeNode root) {
  18. List<Integer> result = new ArrayList<>();
  19. if(root == null) return result;
  20. Stack<TreeNode> stack = new Stack<>();//栈
  21. stack.push(root);
  22. while(!stack.isEmpty()){
  23. TreeNode node = stack.pop();
  24. result.add(node.val);
  25. //栈 先进后出 前序 中左右
  26. if(node.right != null){
  27. stack.push(node.right);
  28. }
  29. if(node.left != null){
  30. stack.push(node.left);
  31. }
  32. }
  33. return result;
  34. }
  35. }

题目(学习)145:二叉树的后序遍历

  1. //递归法
  2. class Solution {
  3. public List<Integer> postorderTraversal(TreeNode root) {
  4. List<Integer> result = new ArrayList<Integer>();
  5. postorder(root,result);
  6. return result;
  7. }
  8. public void postorder(TreeNode root,List<Integer> list){
  9. if(root == null) return;
  10. postorder(root.left, list);//左
  11. postorder(root.right,list);//右
  12. list.add(root.val);//中
  13. }
  14. }
  15. //迭代法
  16. class Solution {
  17. public List<Integer> postorderTraversal(TreeNode root) {
  18. List<Integer> result = new ArrayList<>();
  19. if(root == null){
  20. return result;
  21. }
  22. Stack<TreeNode> stack = new Stack<>();
  23. stack.push(root);
  24. while(!stack.isEmpty()){
  25. TreeNode node = stack.pop();
  26. result.add(node.val);
  27. if(node.left != null){
  28. stack.push(node.left);
  29. }
  30. if(node.right != null){
  31. stack.push(node.right);
  32. }
  33. }
  34. Collections.reverse(result);//反转数组
  35. return result;
  36. }
  37. }

 反转数组:Collections.reverse(result);

题目(学习)94:二叉树的中序遍历

访问顺序和处理顺序不同:先访问根节点,但是要从下面的子节点开始处理 

  1. //递归法
  2. class Solution {
  3. public List<Integer> inorderTraversal(TreeNode root) {
  4. List<Integer> res = new ArrayList<Integer>();
  5. inorder(root,res);
  6. return res;
  7. }
  8. public void inorder(TreeNode root,List<Integer> list){
  9. if(root == null) return;
  10. inorder(root.left, list);
  11. list.add(root.val);
  12. inorder(root.right,list);
  13. }
  14. }
  15. //迭代法
  16. class Solution {
  17. public List<Integer> inorderTraversal(TreeNode root) {
  18. List<Integer> result = new ArrayList<>();
  19. if(root == null) return result;
  20. Stack<TreeNode> stack = new Stack<>();
  21. TreeNode cur = root;//定义一个指针用来遍历二叉树的
  22. while(cur != null || !stack.isEmpty()){//遇到空节点 就从栈里弹出遍历的元素加入到数组
  23. if(cur != null){
  24. stack.push(cur);
  25. cur = cur.left;
  26. }else{
  27. cur = stack.pop();
  28. result.add(cur.val);
  29. cur = cur.right;
  30. }
  31. }
  32. return result;
  33. }
  34. }

 2023/9/1

题目(学习)102:二叉树的层序遍历 

  1. class Solution {
  2. public List<List<Integer>> resList = new ArrayList<List<Integer>>();//最后返回的是一个二维数组
  3. public List<List<Integer>> levelOrder(TreeNode root) {
  4. checkFun02(root);
  5. return resList;
  6. }
  7. public void checkFun02(TreeNode node){
  8. if(node == null) return;
  9. Queue<TreeNode> que = new LinkedList<TreeNode>();//队列的定义
  10. que.offer(node);
  11. while(!que.isEmpty()){
  12. List<Integer> itemList = new ArrayList<Integer>();//定义一个一维数组来存放每一层的结果
  13. int len = que.size();//记录当前层共有多少个元素
  14. while(len > 0){
  15. TreeNode tmpNode = que.poll();//从队列中取值
  16. itemList.add(tmpNode.val);//将取的值放在一维数组中
  17. if(tmpNode.left != null) que.offer(tmpNode.left);//左孩子不为空,添加
  18. if(tmpNode.right != null) que.offer(tmpNode.right);
  19. len--;
  20. }
  21. resList.add(itemList);//向一维数组中添加一维数组得二维数组
  22. }
  23. }
  24. }

2023/9/4

题目(学习)107:二叉树的层序遍历2

  1. class Solution {
  2. public List<List<Integer>> levelOrderBottom(TreeNode root) {
  3. List<List<Integer>> list = new ArrayList<>();
  4. Deque<TreeNode> que = new LinkedList<>();//队列
  5. if(root == null) return list;
  6. que.offerLast(root);//根节点加入到队列
  7. while(!que.isEmpty()){
  8. List<Integer> levelList = new ArrayList<>();
  9. int levelSize = que.size();
  10. while(levelSize > 0){
  11. TreeNode peek = que.poll();
  12. levelList.add(peek.val);
  13. if(peek.left != null){
  14. que.offer(peek.left);
  15. }
  16. if(peek.right != null){
  17. que.offer(peek.right);
  18. }
  19. levelSize--;
  20. }
  21. // for(int i = 0;i < levelSize;i++){
  22. // TreeNode peek = que.peekFirst();
  23. // levelList.add(que.pollFirst().val);
  24. // if(peek.left != null){
  25. // que.offerLast(peek.left);
  26. // }
  27. // if(peek.right != null){
  28. // que.offerLast(peek.right);
  29. // }
  30. // }
  31. list.add(levelList);
  32. }
  33. List<List<Integer>> result = new ArrayList<>();
  34. for(int i = list.size() - 1;i >= 0;i--){
  35. result.add(list.get(i));
  36. }
  37. return result;
  38. }
  39. }

 题目(未完成)199:二叉树的右视图

注释的部分是我想的,不得行,没有仔细审题,理解题目意思

  1. class Solution {
  2. public List<Integer> rightSideView(TreeNode root) {
  3. List<Integer> resList = new ArrayList<>();
  4. Deque<TreeNode> que = new LinkedList<>();
  5. if(root == null) return resList;
  6. que.offer(root);
  7. while(!que.isEmpty()){
  8. int len = que.size();
  9. for(int i = 0;i < len;i++){
  10. TreeNode tmpNode = que.pollFirst();
  11. if(tmpNode.left != null) que.offer(tmpNode.left);
  12. if(tmpNode.right != null) que.offer(tmpNode.right);
  13. if(i == len - 1) resList.add(tmpNode.val);
  14. }
  15. // while(len > 0){
  16. // TreeNode tmpNode = que.poll();
  17. // resList.add(tmpNode.val);
  18. // // if(tmpNode.left != null) que.offer(tmpNode.left);
  19. // if(tmpNode.right != null) que.offer(tmpNode.right);
  20. // // if()
  21. // len--;
  22. // }
  23. }
  24. return resList;
  25. }
  26. }

2023/9/5

 题目(完成)637:二叉树的层平均值

  1. class Solution {
  2. public List<Double> averageOfLevels(TreeNode root) {
  3. List<Double> resList = new ArrayList<>();
  4. Deque<TreeNode> que = new LinkedList<>();
  5. if(root == null) return resList;
  6. que.offerLast(root);
  7. while(!que.isEmpty()){
  8. double temp = 0;
  9. int levelSize = que.size();
  10. int length = levelSize;
  11. while(levelSize > 0){
  12. TreeNode peek = que.poll();
  13. temp = temp + peek.val;
  14. if(peek.left != null){
  15. que.offer(peek.left);
  16. }
  17. if(peek.right != null){
  18. que.offer(peek.right);
  19. }
  20. levelSize--;
  21. }
  22. double res_temp = temp / length;
  23. resList.add(res_temp);
  24. }
  25. return resList;
  26. }
  27. }

2023/9/6

题目(学习)429:N叉树的层序遍历 

  1. class Solution {
  2. public List<List<Integer>> levelOrder(Node root) {
  3. List<List<Integer>> resList = new ArrayList<>();
  4. Deque<Node> que = new LinkedList<>();
  5. if(root == null) return resList;
  6. que.offerLast(root);
  7. while(!que.isEmpty()){
  8. List<Integer> levelList = new ArrayList<>();
  9. int levelSize = que.size();
  10. for(int i = 0;i < levelSize; i++){
  11. Node poll = que.pollFirst();
  12. levelList.add(poll.val);
  13. List<Node> children = poll.children;
  14. if(children == null || children.size() == 0){
  15. continue;
  16. }
  17. for(Node child : children){
  18. if(child != null){
  19. que.offerLast(child);
  20. }
  21. }
  22. }
  23. resList.add(levelList);
  24. }
  25. return resList;
  26. }
  27. }

 题目(完成)515:在每个树行中找最大值

  1. class Solution {
  2. public List<Integer> largestValues(TreeNode root) {
  3. List<Integer> resList = new ArrayList<>();
  4. Deque<TreeNode> que = new LinkedList<>();
  5. if(root == null) return resList;
  6. que.offerLast(root);
  7. while(!que.isEmpty()){
  8. int levelSize = que.size();
  9. // int MAX_temp = -2147483648;
  10. int MAX_temp = Integer.MIN_VALUE;
  11. while(levelSize > 0){
  12. TreeNode peek = que.poll();
  13. if(peek.val >= MAX_temp) MAX_temp = peek.val;
  14. if(peek.left != null){
  15. que.offer(peek.left);
  16. }
  17. if(peek.right != null){
  18. que.offer(peek.right);
  19. }
  20. levelSize--;
  21. }
  22. resList.add(MAX_temp);
  23. }
  24. return resList;
  25. }
  26. }

 题目(学习)116:填充每个节点的下一个右侧节点指针

 题目(学习)117:填充每个节点的下一个右侧节点指针2

  1. class Solution {
  2. public Node connect(Node root) {
  3. Queue<Node> tmpQueue = new LinkedList<Node>();
  4. if(root != null) tmpQueue.add(root);
  5. while(tmpQueue.size() != 0){
  6. int size = tmpQueue.size();
  7. Node cur = tmpQueue.poll();//0 - size-1
  8. if(cur.left != null) tmpQueue.add(cur.left);
  9. if(cur.right != null) tmpQueue.add(cur.right);
  10. for(int index = 1; index < size;index++){
  11. Node next = tmpQueue.poll();
  12. if(next.left != null) tmpQueue.add(next.left);
  13. if(next.right != null) tmpQueue.add(next.right);
  14. cur.next = next;
  15. cur = next;
  16. }
  17. }
  18. return root;
  19. }
  20. }

题目(完成)104:二叉树的最大深度

 解题关键:根节点的高度就是这颗二叉树的最大深度

想不通的话就把代码写全,方便理解

  1. //层序遍历
  2. class Solution {
  3. public int maxDepth(TreeNode root) {
  4. Deque<TreeNode> que = new LinkedList<>();
  5. if(root != null) que.offer(root);
  6. int res = 0;
  7. while(!que.isEmpty()){
  8. int levelSize = que.size();
  9. while(levelSize > 0){
  10. TreeNode peek = que.poll();
  11. if(peek.left != null) que.offer(peek.left);
  12. if(peek.right != null) que.offer(peek.right);
  13. levelSize--;
  14. }
  15. res++;
  16. }
  17. return res;
  18. }
  19. }
  20. //后序遍历
  21. class Solution {
  22. public int maxDepth(TreeNode root) {
  23. if(root == null) return 0;
  24. int leftDepth = maxDepth(root.left);//左
  25. int rightDepth = maxDepth(root.right);//右
  26. return Math.max(leftDepth,rightDepth) + 1;//中
  27. }
  28. }
  29. //前序遍历
  30. class Solution {
  31. int maxnum = 0;
  32. public int maxDepth(TreeNode root) {
  33. ans(root,0);
  34. return maxnum;
  35. }
  36. void ans(TreeNode tr,int tmp){
  37. if(tr == null) return;
  38. tmp++;
  39. maxnum = maxnum < tmp ? tmp:maxnum;
  40. ans(tr.left,tmp);
  41. ans(tr.right,tmp);
  42. tmp--;
  43. }
  44. }

题目(完成)111:二叉树的最小深度

  1. class Solution {
  2. public int minDepth(TreeNode root) {
  3. Deque<TreeNode> que = new LinkedList<>();
  4. if(root == null) return 0;
  5. int res = 0;
  6. if(root != null) que.offer(root);
  7. while(!que.isEmpty()){
  8. int levelSize = que.size();
  9. res++;
  10. while(levelSize > 0){
  11. TreeNode peek = que.poll();
  12. if(peek.left == null && peek.right == null) return res;
  13. if(peek.left != null) que.offer(peek.left);
  14. if(peek.right != null) que.offer(peek.right);
  15. levelSize--;
  16. }
  17. }
  18. return res;
  19. }
  20. }

根节点的最小高度正好符合该题目要求的最小深度

叶子节点:自己下面不再连接有节点的节点

  1. //后序遍历
  2. class Solution {
  3. public int minDepth(TreeNode root) {
  4. if(root == null) return 0;
  5. int leftDepth = minDepth(root.left);
  6. int rightDepth = minDepth(root.right);
  7. if(root.left == null){
  8. return rightDepth + 1;
  9. }
  10. if(root.right == null){
  11. return leftDepth + 1;
  12. }
  13. return Math.min(leftDepth,rightDepth) + 1;
  14. }
  15. }

2023/9/8

题目(学习)226:翻转二叉树

  1. class Solution {
  2. public TreeNode invertTree(TreeNode root) {
  3. if(root == null) return null;
  4. //后序遍历
  5. inverTree(root.left);//左 反转左子树
  6. inverTree(root.right);//右 反转右子树
  7. swapChildren(root);//交换左右孩子节点 中
  8. return root;
  9. }
  10. private void swapChildren(TreeNode root){
  11. TreeNode tmp = root.left;
  12. root.left = root.right;
  13. root.right = tmp;
  14. }
  15. }

2023/9/8 

什么样的题目只能采用后序遍历:需要收集左右孩子的信息向上一层返回

题目(学习)101:对称二叉树

  1. class Solution {
  2. public boolean isSymmetric(TreeNode root) {
  3. return compare(root.left,root.right);
  4. }
  5. private boolean compare(TreeNode left,TreeNode right){
  6. if(left == null && right != null) return false;
  7. if(left != null && right == null) return false;
  8. if(left == null && right == null) return true;
  9. if(left.val != right.val) return false;
  10. //比较外侧
  11. boolean compareOutside = compare(left.left,right.right);
  12. //比较内侧
  13. boolean compareInside = compare(left.right,right.left);
  14. return compareInside && compareOutside;
  15. }
  16. }

题目(完成)559:N叉树的最大深度

  1. class Solution {
  2. public int maxDepth(Node root) {
  3. if(root == null) return 0;
  4. int depth = 0;
  5. List<Node> children = root.children;
  6. // if(children == null || children.size() == 0) continue;
  7. for(Node child : children){
  8. if(child != null){
  9. int childDepth = maxDepth(child);
  10. depth = Math.max(depth,childDepth);
  11. }
  12. }
  13. return depth + 1;
  14. }
  15. }

题目(完成)222:完全二叉树的节点个数

  1. //层序遍历
  2. class Solution {
  3. public int countNodes(TreeNode root) {
  4. Deque<TreeNode> que = new LinkedList<>();
  5. int res = 0;
  6. if(root == null) return 0;
  7. que.offerLast(root);
  8. while(!que.isEmpty()){
  9. int levelSize = que.size();
  10. res = res + levelSize;
  11. while(levelSize > 0){
  12. TreeNode peek = que.poll();
  13. if(peek.left != null) que.offer(peek.left);
  14. if(peek.right != null) que.offer(peek.right);
  15. levelSize--;
  16. }
  17. }
  18. return res;
  19. }
  20. }
  21. //当作普通二叉树来处理
  22. class Solution {
  23. public int countNodes(TreeNode root) {
  24. if(root == null) return 0;
  25. int leftnumber = countNodes(root.left);
  26. int rightnumber = countNodes(root.right);
  27. return leftnumber + rightnumber + 1;
  28. }
  29. }
  30. //针对完全二叉树的解法
  31. class Solution {
  32. public int countNodes(TreeNode root) {
  33. if(root == null) return 0;
  34. TreeNode left = root.left;
  35. TreeNode right = root.right;
  36. int leftDepth = 0,rightDepth = 0;
  37. while(left != null){
  38. left = left.left;
  39. leftDepth++;
  40. }
  41. while(right != null){
  42. right = right.right;
  43. rightDepth++;
  44. }
  45. if(leftDepth == rightDepth){
  46. return (2 << leftDepth) - 1;
  47. }
  48. int rootleftnum = countNodes(root.left);
  49. int rootrightnum = countNodes(root.right);
  50. return rootleftnum + rootrightnum + 1;
  51. }
  52. }

2023/9/18 

 题目(学习)110:平衡二叉树

  1. class Solution {
  2. public boolean isBalanced(TreeNode root) {
  3. return getHeight(root) != -1;
  4. }
  5. private int getHeight(TreeNode root){
  6. if(root == null) return 0;
  7. int leftHeight = getHeight(root.left);
  8. if(leftHeight == -1) return -1;
  9. int rightHeight = getHeight(root.right);
  10. if(rightHeight == -1) return -1;
  11. if(Math.abs(leftHeight - rightHeight) > 1) return -1;
  12. return Math.max(leftHeight,rightHeight) + 1;
  13. }
  14. }

 2023/9/19

题目(学习)257:二叉树的所有路径

  1. lass Solution {
  2. public List<String> binaryTreePaths(TreeNode root) {
  3. List<String> res = new ArrayList<>();
  4. if(root == null) return res;
  5. List<Integer> paths = new ArrayList<>();
  6. traversal(root,paths,res);
  7. return res;
  8. }
  9. private void traversal(TreeNode root,List<Integer>paths,List<String>res){
  10. paths.add(root.val);
  11. if(root.left == null && root.right == null){
  12. StringBuilder sb = new StringBuilder();
  13. for(int i = 0;i < paths.size() - 1;i++){
  14. sb.append(paths.get(i).append("->"));
  15. }
  16. sb.append(paths.get(paths.size() - 1));
  17. res.add(sb.toString());
  18. return;
  19. }
  20. if(root.left != null){
  21. traversal(root.left,paths,res);
  22. paths.remove(paths.size() - 1);//回溯
  23. }
  24. if(root.right != null){
  25. traversal(root.right,paths,res);
  26. paths.remove(paths.size() - 1);//回溯
  27. }
  28. }
  29. }

2023/9/20

题目(完成)100:相同的树

  1. class Solution {
  2. public boolean isSameTree(TreeNode p, TreeNode q) {
  3. return compare(p,q);
  4. }
  5. public boolean compare(TreeNode left,TreeNode right){
  6. if(left == null && right != null) return false;
  7. if(left != null && right == null) return false;
  8. if(left == null && right == null) return true;
  9. if(left.val != right.val) return false;
  10. boolean compareLeft = compare(left.left,right.left);
  11. boolean compareRight =compare(left.right,right.right);
  12. return compareLeft && compareRight;
  13. }
  14. }

2023/9/21

题目(未解决) 572:另一颗树的子树

两个代码的逻辑一样,但是第一个不知道为什么有的题目通不过 

  1. class Solution {
  2. public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  3. if (subRoot == null) return true;
  4. if (root == null) return false;
  5. return compare(root.left,subRoot) || compare(root.right,subRoot) || compare(root,subRoot);
  6. }
  7. public boolean compare(TreeNode left,TreeNode right){
  8. if(left == null && right != null) return false;
  9. if(left != null && right == null) return false;
  10. if(left == null && right == null) return true;
  11. if(left.val != right.val) return false;
  12. boolean compareLeft = compare(left.left,right.left);
  13. boolean compareRight = compare(left.right,right.right);
  14. return compareLeft && compareRight;
  15. }
  16. }
  17. class Solution {
  18. public boolean isSubtree(TreeNode s, TreeNode t) {
  19. if (t == null) return true; // t 为 null 一定都是 true
  20. if (s == null) return false; // 这里 t 一定不为 null, 只要 s 为 null,肯定是 false
  21. return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);
  22. }
  23. /**
  24. * 判断两棵树是否相同
  25. */
  26. public boolean isSameTree(TreeNode s, TreeNode t){
  27. if (s == null && t == null) return true;
  28. if (s == null || t == null) return false;
  29. if (s.val != t.val) return false;
  30. return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
  31. }
  32. }

2023/9/27

题目(未完成)1047:左叶子之和

  1. class Solution {
  2. public int sumOfLeftLeaves(TreeNode root) {
  3. //终止条件
  4. if(root == null) return 0;
  5. if(root.left == null && root.right == null) return 0;
  6. int leftnum = sumOfLeftLeaves(root.left);
  7. if (root.left != null && root.left.left == null && root.left.right == null) {
  8. leftnum = root.left.val;
  9. }
  10. int rightnum = sumOfLeftLeaves(root.right);
  11. int sum = leftnum +rightnum;
  12. return sum;
  13. }
  14. }
  15. class Solution {
  16. public int sumOfLeftLeaves(TreeNode root) {
  17. int sum = 0;
  18. if (root == null) return 0;
  19. Queue<TreeNode> queue = new LinkedList<>();
  20. queue.offer(root);
  21. while (!queue.isEmpty()) {
  22. int size = queue.size();
  23. while (size -- > 0) {
  24. TreeNode node = queue.poll();
  25. if (node.left != null) { // 左节点不为空
  26. if (node.left.left == null && node.left.right == null){ // 左叶子节点
  27. sum += node.left.val;
  28. }
  29. queue.offer(node.left);
  30. }
  31. if (node.right != null) queue.offer(node.right);
  32. }
  33. }
  34. return sum;
  35. }
  36. }

 2023/9/28

题目(层序完成,递归不会)513:找树左下角的值

  1. //迭代
  2. class Solution {
  3. public int findBottomLeftValue(TreeNode root) {
  4. List<List<Integer>> list = new ArrayList<>();
  5. if(root == null) return 0;
  6. Deque<TreeNode> que = new LinkedList<>();
  7. que.offer(root);
  8. while(!que.isEmpty()){
  9. List<Integer> levelList = new ArrayList<>();
  10. int levelSize = que.size();
  11. while(levelSize > 0){
  12. TreeNode peek = que.poll();
  13. levelList.add(peek.val);
  14. if(peek.left != null){
  15. que.offer(peek.left);
  16. }
  17. if(peek.right != null){
  18. que.offer(peek.right);
  19. }
  20. levelSize--;
  21. }
  22. list.add(levelList);
  23. }
  24. return list.get(list.size() - 1).get(0);
  25. }
  26. }
  27. //递归
  28. class Solution {
  29. private int Deep = -1;
  30. private int value = 0;
  31. public int findBottomLeftValue(TreeNode root) {
  32. value = root.val;
  33. findLeftValue(root,0);
  34. return value;
  35. }
  36. private void findLeftValue(TreeNode root,int depth){
  37. if(root == null) return;
  38. if(root.left == null && root.right == null){
  39. if(depth > Deep){
  40. value = root.val;
  41. Deep = depth;
  42. }
  43. }
  44. if(root.left != null){
  45. depth++;
  46. findLeftValue(root.left,depth);
  47. depth--;//回溯
  48. }
  49. if(root.right != null){
  50. depth++;
  51. findLeftValue(root.right,depth);
  52. depth--;//回溯
  53. }
  54. }
  55. }

2023/10/8

题目(未完成)112:路径总和

  1. //用累加再比的话,会比较麻烦
  2. //累减会好一些
  3. class Solution {
  4. private int value = 0;
  5. public boolean hasPathSum(TreeNode root, int targetSum) {
  6. if(root == null) return false;
  7. targetSum = targetSum - root.val;
  8. if(root.left == null && root.right == null) return targetSum == 0;
  9. if(root.left != null){
  10. // targetSum = targetSum - root.left.val;
  11. boolean left = hasPathSum(root.left,targetSum);
  12. if(left) return true;
  13. // targetSum = targetSum + root.left.val;
  14. }
  15. if(root.right != null){
  16. // targetSum = targetSum - root.right.val;
  17. boolean right = hasPathSum(root.right,targetSum);
  18. if(right) return true;
  19. // targetSum = targetSum + root.right.val;
  20. }
  21. return false;
  22. }
  23. }

 题目(未完成)113:路径总和2

  1. class Solution {
  2. public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  3. List<List<Integer>> res = new ArrayList<List<Integer>>();
  4. if(root == null) return res;
  5. List<Integer> path = new ArrayList<Integer>();
  6. preorderdfs(root,targetSum,res,path);
  7. return res;
  8. }
  9. public void preorderdfs(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path){
  10. path.add(root.val);
  11. if(root.left == null && root.right == null){
  12. if(targetSum - root.val == 0){
  13. res.add(new ArrayList<>(path));
  14. }
  15. return;
  16. }
  17. if(root.left != null){
  18. preorderdfs(root.left,targetSum - root.val,res,path);
  19. path.remove(path.size() - 1);
  20. }
  21. if(root.right != null){
  22. preorderdfs(root.right,targetSum - root.val,res,path);
  23. path.remove(path.size() - 1);
  24. }
  25. }
  26. }

题目(学习)106:从中序与后序遍历序列构造二叉树

  1. class Solution {
  2. Map<Integer,Integer> map;
  3. public TreeNode buildTree(int[] inorder, int[] postorder) {
  4. map = new HashMap<>();
  5. for(int i = 0;i < inorder.length;i++){
  6. map.put(inorder[i],i);
  7. }
  8. return findNote(inorder,0,inorder.length,postorder,0,postorder.length);
  9. }
  10. public TreeNode findNote(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
  11. if(inBegin >= inEnd || postBegin >= postEnd) return null;
  12. int rootIndex = map.get(postorder[postEnd - 1]);
  13. TreeNode root = new TreeNode(inorder[rootIndex]);
  14. int lenOfLeft = rootIndex - inBegin;
  15. root.left = findNote(inorder,inBegin,rootIndex,postorder,postBegin,postBegin + lenOfLeft);
  16. root.right = findNote(inorder,rootIndex + 1,inEnd,postorder,postBegin + lenOfLeft,postEnd - 1);
  17. return root;
  18. }
  19. }

2023/10/10

 题目(完成)105:从前序与中序遍历序列构造二叉树

  1. class Solution {
  2. Map<Integer,Integer> map;
  3. public TreeNode buildTree(int[] preorder, int[] inorder) {
  4. map = new HashMap<>();
  5. for(int i = 0;i < inorder.length;i++){
  6. map.put(inorder[i],i);
  7. }
  8. return findNote(inorder,0,inorder.length,preorder,0,preorder.length);
  9. }
  10. public TreeNode findNote(int[] inorder,int inBegin,int inEnd,int[] preorder,int preBegin,int preEnd){
  11. if(inBegin >= inEnd || preBegin >= preEnd) return null;
  12. int rootIndex = map.get(preorder[preBegin]);
  13. TreeNode root = new TreeNode(inorder[rootIndex]);
  14. int lenOfLeft = rootIndex - inBegin;
  15. root.left = findNote(inorder,inBegin,rootIndex,preorder,preBegin + 1,preBegin + lenOfLeft + 1);
  16. root.right = findNote(inorder,rootIndex + 1,inEnd,preorder,preBegin + lenOfLeft + 1,preEnd);
  17. return root;
  18. }
  19. }

2023/10/10

题目(完成)654:最大二叉树

  1. class Solution {
  2. Map<Integer,Integer> map;
  3. public TreeNode constructMaximumBinaryTree(int[] nums) {
  4. map = new HashMap<>();
  5. for(int i = 0;i < nums.length;i++){
  6. map.put(nums[i],i);
  7. }
  8. return findNote(nums,0,nums.length);
  9. }
  10. public TreeNode findNote(int[] nums,int numsBegin,int numsEnd){
  11. if(numsBegin >= numsEnd) return null;
  12. int max = 0;
  13. for(int i = numsBegin;i < numsEnd;i++){
  14. max = Math.max(max,nums[i]);
  15. }
  16. // int max = (int) Collections.max(Arrays.asList(nums));
  17. int rootIndex = map.get(max);
  18. int lenOfLeft = rootIndex - numsBegin;
  19. TreeNode root = new TreeNode(max);
  20. if(lenOfLeft != 0){
  21. root.left = findNote(nums,numsBegin,numsBegin + lenOfLeft);
  22. }
  23. if(rootIndex + 1 != numsEnd){
  24. root.right = findNote(nums,rootIndex + 1,numsEnd);
  25. }
  26. return root;
  27. }
  28. }

题目(完成)617:合并二叉树 

  1. class Solution {
  2. public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
  3. if(root1 == null && root2 == null) return null;
  4. if(root1 == null) return root2;
  5. if(root2 == null) return root1;
  6. TreeNode root = new TreeNode(root1.val + root2.val);
  7. if(root1.left != null || root2.left != null){
  8. root.left = mergeTrees(root1.left,root2.left);
  9. }
  10. if(root1.right != null || root2.right != null){
  11. root.right = mergeTrees(root1.right,root2.right);
  12. }
  13. return root;
  14. }
  15. }

题目(完成)700:二叉搜索树中的搜索 

二叉搜索树:根节点的值比其左子树的都要大,比其右子树的都要小,子树也是这样 

  1. class Solution {
  2. public TreeNode searchBST(TreeNode root, int val) {
  3. //方法1
  4. if(root == null || root.val == val){
  5. return root;
  6. }
  7. TreeNode left = searchBST(root.left,val);
  8. if(left != null){
  9. return left;
  10. }
  11. return searchBST(root.right,val);
  12. //方法2 利用二叉搜索树的特性
  13. if(root == null || root.val == val){
  14. return root;
  15. }
  16. if(val < root.val){
  17. return searchBST(root.left,val);
  18. }else{
  19. return searchBST(root.right,val);
  20. }
  21. }
  22. }

 题目(未完成)98:验证二叉搜索树

  1. //二叉搜索树中序遍历是有序的
  2. class Solution {
  3. TreeNode pre;
  4. public boolean isValidBST(TreeNode root) {
  5. // if(value == -1) value = root.val;//记录根节点的值
  6. if(root == null){
  7. return true;
  8. }
  9. boolean left = isValidBST(root.left);
  10. // if(pre != null && root.val > pre.val){
  11. // return true;
  12. // }
  13. if(pre != null && root.val <= pre.val){
  14. return false;
  15. }
  16. pre = root;
  17. boolean right = isValidBST(root.right);
  18. return left && right;
  19. }
  20. }

题目(完成) 530:二叉搜索树的最小绝对差

  1. //因为按照中序遍历二叉搜索树是单调递增的
  2. class Solution {
  3. TreeNode pre;
  4. private int res = Integer.MAX_VALUE;
  5. public int getMinimumDifference(TreeNode root) {
  6. if(root == null){
  7. return 0;
  8. }
  9. getMinimumDifference(root.left);
  10. if(pre != null){
  11. res = Math.min(res,Math.abs(root.val - pre.val));
  12. }
  13. pre = root;
  14. getMinimumDifference(root.right);
  15. return res;
  16. }
  17. }

题目(未完成)501:二叉搜索树中的众数  经典题目

  1. lass Solution {
  2. ArrayList<Integer> resList;
  3. int maxCount;
  4. int count;
  5. TreeNode pre;
  6. public int[] findMode(TreeNode root) {
  7. resList = new ArrayList<>();
  8. maxCount = 0;
  9. count = 0;
  10. pre = null;
  11. findMode(root);
  12. int[] res = new int[resList.size()];
  13. for(int i = 0;i < resList.size();i++){
  14. res[i] = resList.get(i);
  15. }
  16. return res;
  17. }
  18. public void findModel(TreeNode root){
  19. if(root == null){
  20. return;
  21. }
  22. findModel(root.left);
  23. int rootValue = root.val;
  24. if(pre == null || rootValue != pre.val){
  25. count = 1;
  26. }else{
  27. count++;
  28. }
  29. if(count > maxCount){
  30. resList.clear();
  31. resList.add(rootValue);
  32. maxCount = count;
  33. }else if(count == maxCount){
  34. resList.add(rootValue);
  35. }
  36. pre = root;
  37. findModel(root.right);
  38. }
  39. }

题目(未完成)236:二叉树的最近公共祖先

  1. class Solution {
  2. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3. if(root == null) return null;
  4. if(root == p || root == q) return root;
  5. TreeNode left = lowestCommonAncestor(root.left,p,q);
  6. TreeNode right = lowestCommonAncestor(root.right,p,q);
  7. if(left != null && right != null){
  8. return root;
  9. }else if(left == null && right != null){
  10. return right;
  11. }else if(left != null && right == null){
  12. return left;
  13. }else{
  14. return null;
  15. }
  16. }
  17. }

 题目(未完成)235:二叉搜索树的最近公共祖先

  1. class Solution {
  2. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3. if(root == null) return null;
  4. if(root.val > p.val && root.val > q.val){
  5. TreeNode left = lowestCommonAncestor(root.left , p ,q);
  6. if(left != null){
  7. return left;
  8. }
  9. }else if(root.val < p.val && root.val < q.val){
  10. TreeNode right = lowestCommonAncestor(root.right , p ,q);
  11. if(right != null){
  12. return right;
  13. }
  14. }
  15. return root;
  16. }
  17. }

题目(完成一半)701:二叉搜索树中的插入操作 

  1. class Solution {
  2. public TreeNode insertIntoBST(TreeNode root, int val) {
  3. if(root == null){
  4. TreeNode res = new TreeNode(val);
  5. return res;
  6. }
  7. if(root.val > val){
  8. root.left = insertIntoBST(root.left, val);
  9. }else{
  10. root.right = insertIntoBST(root.right, val);
  11. }
  12. return root;
  13. }
  14. }

 题目(完成一半)450:删除二叉搜索树中的节点

  1. class Solution {
  2. public TreeNode deleteNode(TreeNode root, int key) {
  3. if(root == null) return null;
  4. if(root.val == key){
  5. if(root.left == null && root.right == null){
  6. return null;
  7. }else if(root.left == null && root.right != null){
  8. return root.right;
  9. }else if(root.left != null && root.right == null){
  10. return root.left;
  11. }else{
  12. TreeNode res = root.right;
  13. while(res.left != null){
  14. res = res.left;
  15. }
  16. res.left = root.left;
  17. root = root.right;
  18. return root;
  19. }
  20. }
  21. if(root.val > key){
  22. root.left = deleteNode(root.left,key);
  23. }else{
  24. root.right = deleteNode(root.right,key);
  25. }
  26. return root;
  27. }
  28. }

 题目(完成一半)669:修剪二叉搜索树

  1. class Solution {
  2. public TreeNode trimBST(TreeNode root, int low, int high) {
  3. if(root == null) return null;
  4. if(root.val < low){
  5. TreeNode right = trimBST(root.right,low,high);
  6. return right;
  7. }
  8. if(root.val > high){
  9. TreeNode left = trimBST(root.left,low,high);
  10. return left;
  11. }
  12. root.left = trimBST(root.left,low,high);
  13. root.right = trimBST(root.right,low,high);
  14. return root;
  15. }
  16. }

 题目(完成)108:将有序数组转换成二叉搜索树

  1. class Solution {
  2. public TreeNode sortedArrayToBST(int[] nums) {
  3. return test(nums,0,nums.length);
  4. }
  5. public TreeNode test(int[] nums,int Begin,int End){
  6. if(Begin >= End) return null;
  7. if(End - Begin == 1) return new TreeNode(nums[Begin]);
  8. int mid = Begin + (End - Begin) / 2;
  9. int midroot = nums[mid];
  10. TreeNode root = new TreeNode(midroot);
  11. // int lenOfLeft = mid - Begin;
  12. root.left = test(nums,Begin,mid);
  13. root.right = test(nums,mid + 1,End);
  14. return root;
  15. }
  16. }

 题目(完成一半)538:把二叉搜索树转换为累加树

  1. class Solution {
  2. // TreeNode pre;
  3. private int sum = 0;
  4. public TreeNode convertBST(TreeNode root) {
  5. if(root == null) return null;
  6. TreeNode right = convertBST(root.right);
  7. // if(pre != null){
  8. // root = new TreeNode(pre.val + root.val);
  9. // }
  10. // pre = root;
  11. sum += root.val;
  12. root.val = sum;
  13. TreeNode left = convertBST(root.left);
  14. return root;
  15. }
  16. }

 2023/8/28——栈

题目(完成一半)1047:删除字符串中的所有相邻重复项

  1. lass Solution {
  2. public String removeDuplicates(String s) {
  3. // Map<Character,Integer> count = new HashMap<Character,Integer>();
  4. // for(int i = 0; i < s.length();i++){
  5. // char ch = s.charAt(i);
  6. // count.put(ch,count.getOrDefault(ch,0) + 1);
  7. // }
  8. //两个相邻且相同的字母
  9. StringBuffer res = new StringBuffer();
  10. int top = -1;
  11. for(int i = 0; i < s.length(); i++){
  12. char ch = s.charAt(i);
  13. if(top >= 0 && ch == res.charAt(top)){
  14. res.deleteCharAt(top);
  15. top--;
  16. }else{
  17. res.append(ch);
  18. top++;
  19. }
  20. }
  21. return res.toString();
  22. }
  23. }

2023/8/29

题目(未完成)150:逆波兰表达式求值      我写的虽然复杂,但是在idea是可以的

  1. class Solution {
  2. public int evalRPN(String[] tokens) {
  3. //默认只能出现 1 2 + 而不会是1 + 2
  4. int i = 0;
  5. int Current_Location = 0;
  6. int res = 0;
  7. while(i < tokens.length){
  8. // if(Math.abs(Integer.parseInt(tokens[i])) >= 0){
  9. if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){
  10. tokens[Current_Location] = tokens[i];
  11. i++;
  12. Current_Location++;
  13. }else{
  14. if(tokens[i] == "+"){
  15. tokens[Current_Location - 2] = String.valueOf(Integer.parseInt(tokens[Current_Location - 2]) + Integer.parseInt(tokens[Current_Location - 1]));
  16. Current_Location = Current_Location - 1;
  17. }else if(tokens[i] == "-"){
  18. tokens[Current_Location - 2] = String.valueOf(Integer.parseInt(tokens[Current_Location - 2]) - Integer.parseInt(tokens[Current_Location - 1]));
  19. Current_Location = Current_Location - 1;
  20. }else if(tokens[i] == "*"){
  21. tokens[Current_Location - 2] = String.valueOf(Integer.parseInt(tokens[Current_Location - 2]) * Integer.parseInt(tokens[Current_Location - 1]));
  22. Current_Location = Current_Location - 1;
  23. }else if(tokens[i] == "/"){
  24. tokens[Current_Location - 2] = String.valueOf(Integer.parseInt(tokens[Current_Location - 2]) / Integer.parseInt(tokens[Current_Location - 1]));
  25. Current_Location = Current_Location - 1;
  26. }
  27. i++;
  28. }
  29. }
  30. res = Integer.parseInt(tokens[Current_Location - 1]);
  31. return res;
  32. }
  33. }
  1. class Solution {
  2. public int evalRPN(String[] tokens) {
  3. Deque<Integer> stack = new LinkedList<Integer>();
  4. int n = tokens.length;
  5. for (int i = 0; i < n; i++) {
  6. String token = tokens[i];
  7. if (isNumber(token)) {
  8. stack.push(Integer.parseInt(token));
  9. } else {
  10. int num2 = stack.pop();
  11. int num1 = stack.pop();
  12. switch (token) {
  13. case "+":
  14. stack.push(num1 + num2);
  15. break;
  16. case "-":
  17. stack.push(num1 - num2);
  18. break;
  19. case "*":
  20. stack.push(num1 * num2);
  21. break;
  22. case "/":
  23. stack.push(num1 / num2);
  24. break;
  25. default:
  26. }
  27. }
  28. }
  29. return stack.pop();
  30. }
  31. public boolean isNumber(String token) {
  32. return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
  33. }
  34. }

详解pop()和push()方法_对象池的方法pop、push_我要变成万人迷的博客-CSDN博客

 【Java】Java双端队列Deque使用详解_java deque_devnn的博客-CSDN博客


题目(未完成)239:滑动窗口最大值      我自己写的思路差不多 就是不熟悉栈的语法

  1. class Solution {
  2. public int[] maxSlidingWindow(int[] nums, int k) {
  3. int[] res = new int[nums.length - k + 1];
  4. if(k == 1) return nums;
  5. int i = 0;
  6. int j = 0;
  7. int times = 1;
  8. int var = -Integer.MAX_VALUE;
  9. int p = 0;
  10. while(j <= nums.length - 1){
  11. if(times <= k){
  12. if(j <= nums.length - 1 && nums[j] >= var) var = nums[j];
  13. if(j == nums.length - 1) res[p] = var;
  14. j++;
  15. times++;
  16. }else{
  17. times = 1;
  18. i++;
  19. j = i;
  20. res[p] = var;
  21. p++;
  22. var = -Integer.MAX_VALUE;
  23. }
  24. }
  25. return res;
  26. }
  27. }
  1. class Solution {
  2. public int[] maxSlidingWindow(int[] nums, int k) {
  3. if(nums == null || nums.length < 2) return nums;
  4. // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
  5. LinkedList<Integer> queue = new LinkedList();
  6. // 结果数组
  7. int[] result = new int[nums.length-k+1];
  8. // 遍历nums数组
  9. for(int i = 0;i < nums.length;i++){
  10. // 保证从大到小 如果前面数小则需要依次弹出,直至满足要求
  11. while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
  12. queue.pollLast();
  13. }
  14. // 添加当前值对应的数组下标
  15. queue.addLast(i);
  16. // 判断当前队列中队首的值是否有效
  17. //这里的目的就是为了维护窗口的大小合理
  18. if(queue.peek() <= i-k){
  19. queue.poll();
  20. }
  21. // 当窗口长度为k时 保存当前窗口中最大值
  22. if(i+1 >= k){
  23. result[i+1-k] = nums[queue.peek()];
  24. }
  25. }
  26. return result;
  27. }
  28. }

pollFirst(),pollLast(),peekFirst(),peekLast()_记录菌的博客-CSDN博客


题目(完成)347:前K个高频元素

  1. class Solution {
  2. public int[] topKFrequent(int[] nums, int k) {
  3. int lengths = 0;
  4. // int m = 0;
  5. if(nums == null) return nums;
  6. Map<Integer,Integer> count = new HashMap<Integer,Integer>();
  7. for(int i = 0;i < nums.length;i++){
  8. count.put(nums[i],count.getOrDefault(nums[i],0) + 1);
  9. // if(count.get(nums[i]) >= k) lengths++;
  10. }
  11. // List<Integer> list = new ArrayList<Integer>(map.keySet());
  12. List<Integer> list = new ArrayList<Integer>(count.keySet());
  13. // Collections.sort(list,(a,b))->(map.get(b) - map.get(a));
  14. Collections.sort(list, (a, b) -> count.get(b) - count.get(a));
  15. int[] res = new int[k];
  16. for(int m = 0;m < k;m++){
  17. int temp = list.get(m);
  18. res[m] = temp;
  19. }
  20. // for(Map.Entry<Integer,Integer> entry : count.entrySet()){
  21. // int key = entry.getKey();
  22. // int value = entry.getValue();
  23. // if(value >= k)
  24. // res[m] = key;
  25. // m++;
  26. // }
  27. // for(int i = 0;i < nums.length;i++){
  28. // if(count.get(nums[i]) >= k) res[m] = nums[i];
  29. // m++;
  30. // }
  31. return res;
  32. }
  33. }

哈希表及其基本操作:

Java数据结构---HashMap(哈希表及其基本操作)(含hashset)_Cloudeeeee的博客-CSDN博客


2023/10/31——回溯 

题目(未完成)77:组合

  1. class Solution {
  2. List<List<Integer>> result = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. public List<List<Integer>> combine(int n, int k) {
  5. backtracking(n,k,1);
  6. return result;
  7. }
  8. public void backtracking(int n,int k,int startIndex){
  9. if(path.size == k){
  10. result.add(path);
  11. return;
  12. }
  13. for(int i = startIndex;i <= n;i++){
  14. path.add(i);
  15. backtracking(n,k,i + 1);
  16. path.removeLast();
  17. }
  18. }
  19. }
  1. 剪枝优化
  2. class Solution {
  3. List<List<Integer>> result = new ArrayList<>();
  4. LinkedList<Integer> path = new LinkedList<>();
  5. public List<List<Integer>> combine(int n, int k) {
  6. combineHelper(n, k, 1);
  7. return result;
  8. }
  9. /**
  10. * 每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围,就是要靠startIndex
  11. * @param startIndex 用来记录本层递归的中,集合从哪里开始遍历(集合就是[1,...,n] )。
  12. */
  13. private void combineHelper(int n, int k, int startIndex){
  14. //终止条件
  15. if (path.size() == k){
  16. result.add(new ArrayList<>(path));
  17. return;
  18. }
  19. for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
  20. path.add(i);
  21. combineHelper(n, k, i + 1);
  22. path.removeLast();
  23. }
  24. }
  25. }

题目(完成)216:组合总和3

  1. class Solution {
  2. List<List<Integer>> result = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. int res = 0;
  5. public List<List<Integer>> combinationSum3(int k, int n) {
  6. backtracking(k,n,1);
  7. return result;
  8. }
  9. public void backtracking(int k,int n,int startIndex){
  10. if(res > n) return;
  11. if(path.size() == k){
  12. if(res == n){
  13. result.add(new LinkedList<>(path));
  14. }
  15. return;
  16. // res = res - path.getLast();
  17. }
  18. for(int i = startIndex; i <= 9;i++){
  19. path.add(i);
  20. res += i;
  21. backtracking(k,n,i + 1);
  22. path.removeLast();
  23. res -= i;
  24. }
  25. }
  26. }

 题目(完成)17:电话号码的字母组合

  1. class Solution {
  2. List<String> res = new ArrayList<>();
  3. String [] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
  4. public List<String> letterCombinations(String digits) {
  5. if(digits == null || digits.length() == 0){
  6. return res;
  7. }
  8. // String [] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
  9. backtracking(digits,0);
  10. return res;
  11. }
  12. StringBuilder sb = new StringBuilder();
  13. public void backtracking(String digits,int startIndex){
  14. if(sb.length() == digits.length()){
  15. res.add(sb.toString());
  16. return;
  17. }
  18. String str = numString[digits.charAt(startIndex) - '0'];
  19. // numString[temp] //"abc";
  20. for(int i = 0;i <= str.length() - 1;i++){
  21. sb.append(str.charAt(i));
  22. backtracking(digits,startIndex + 1);
  23. sb.deleteCharAt(sb.length() - 1);
  24. }
  25. }
  26. }

题目(完成一半)39:组合总和

 组合是无序的

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. int temp = 0;
  5. public List<List<Integer>> combinationSum(int[] candidates, int target) {
  6. Arrays.sort(candidates);
  7. backtracking(candidates , target,0);
  8. return res;
  9. }
  10. public void backtracking(int[] candidates,int target,int idx){
  11. if(temp > target){
  12. return;
  13. }else if(target == temp){
  14. res.add(new LinkedList<>(path));
  15. }
  16. for(int i = idx;i < candidates.length;i++){
  17. path.add(candidates[i]);
  18. temp += candidates[i];
  19. backtracking(candidates,target,i);
  20. temp -= candidates[i];
  21. path.removeLast();
  22. }
  23. }
  24. }

题目(未完成)40:组合总和2  树层剪枝,树枝剪枝

  Arrays.fill(used_test,false);

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. int temp = 0;
  5. boolean[] used_test;
  6. public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  7. used_test = new boolean[candidates.length];
  8. Arrays.fill(used_test,false);
  9. Arrays.sort(candidates);
  10. backtracking(candidates , target,0);
  11. return res;
  12. }
  13. public void backtracking(int[] candidates,int target,int idx){
  14. if(temp > target){
  15. return;
  16. }else if(target == temp){
  17. res.add(new LinkedList<>(path));
  18. }
  19. for(int i = idx;i < candidates.length;i++){
  20. if(i > 0 && candidates[i] == candidates[i - 1] && !used_test[i - 1]){
  21. continue;
  22. }
  23. path.add(candidates[i]);
  24. used_test[i] = true;
  25. temp += candidates[i];
  26. backtracking(candidates,target,i + 1);
  27. used_test[i] = false;
  28. temp -= candidates[i];
  29. path.removeLast();
  30. }
  31. }
  32. }

题目 (未完成)131:分割回文串

  1. class Solution {
  2. List<List<String>> lists = new ArrayList<>();
  3. Deque<String> deque = new LinkedList<>();
  4. public List<List<String>> partition(String s) {
  5. backtracking(s,0);
  6. return lists;
  7. }
  8. public void backtracking(String s,int startIndex){
  9. if(startIndex >= s.length){
  10. lists.add(new ArrayList(deque));
  11. return;
  12. }
  13. for(int i = startIndex;i < s.length(); i++){
  14. if(isPalindrome(s,startIndex,i)){
  15. String str = s.substring(startIndex,i + 1);
  16. deque.addLast(str);
  17. }else{
  18. continue;
  19. }
  20. backtracking(s,i + 1);
  21. deque.removeLast();
  22. }
  23. }
  24. private boolean isPalindrome(String s,int startIndex,int end){
  25. for(int i = startIndex,j = end; i < j;i++,j--){
  26. if(s.charAt(i) != s.charAt(j)){
  27. return false;
  28. }
  29. }
  30. return true;
  31. }
  32. }

题目(完成)78:子集

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. public List<List<Integer>> subsets(int[] nums) {
  5. backtracking(nums , 0);
  6. return res;
  7. }
  8. public void backtracking(int[] nums,int startIndex){
  9. res.add(new ArrayList<>(path));
  10. if(startIndex == nums.length){
  11. return;
  12. }
  13. for(int i = startIndex;i < nums.length;i++){
  14. path.add(nums[i]);
  15. backtracking(nums,i + 1);
  16. path.removeLast();
  17. }
  18. }
  19. }

题目(完成)90:子集2

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. boolean[] used_test;
  5. public List<List<Integer>> subsetsWithDup(int[] nums) {
  6. used_test = new boolean[nums.length];
  7. Arrays.fill(used_test,false);
  8. Arrays.sort(nums);
  9. backtracking(nums , 0);
  10. return res;
  11. }
  12. public void backtracking(int[] nums,int startIndex){
  13. res.add(new ArrayList<>(path));
  14. if(startIndex == nums.length){
  15. return;
  16. }
  17. for(int i = startIndex;i < nums.length;i++){
  18. if(i > 0 && nums[i] == nums[i - 1] && !used_test[i - 1]){
  19. continue;
  20. }
  21. path.add(nums[i]);
  22. used_test[i] = true;
  23. backtracking(nums,i + 1);
  24. used_test[i] = false;
  25. path.removeLast();
  26. }
  27. }
  28. }

题目(未完成)491:递增子序列

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. public List<List<Integer>> findSubsequences(int[] nums) {
  5. backtracking(nums , 0);
  6. return res;
  7. }
  8. public void backtracking(int[] nums,int startIndex){
  9. if(path.size() >= 2) res.add(new ArrayList<>(path));
  10. HashSet<Integer> hs = new HashSet<>();
  11. for(int i = startIndex;i < nums.length;i++){
  12. if(!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i])) continue;
  13. hs.add(nums[i]);
  14. path.add(nums[i]);
  15. backtracking(nums.i + 1);
  16. path.remove(path.size() - 1);
  17. }
  18. }
  19. }

 题目(完成)46:全排列

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. boolean[] used_test;
  5. public List<List<Integer>> permute(int[] nums) {
  6. used_test = new boolean[nums.length];
  7. Arrays.fill(used_test,false);
  8. backtracking(nums,0);
  9. return res;
  10. }
  11. public void backtracking(int[] nums, int startIndex){
  12. if(path.size() == nums.length) res.add(new ArrayList<>(path));
  13. for(int i = startIndex;i < nums.length;i++){
  14. if(used_test[i]) continue;
  15. used_test[i] = true;
  16. path.add(nums[i]);
  17. backtracking(nums,0);
  18. used_test[i] = false;
  19. path.remove(path.size() - 1);
  20. }
  21. }
  22. }

题目(完成)47:全排列2

  1. class Solution {
  2. List<List<Integer>> res = new ArrayList<>();
  3. LinkedList<Integer> path = new LinkedList<>();
  4. boolean[] used_test;
  5. public List<List<Integer>> permuteUnique(int[] nums) {
  6. used_test = new boolean[nums.length];
  7. Arrays.sort(nums);
  8. Arrays.fill(used_test,false);
  9. backtracking(nums,0);
  10. return res;
  11. }
  12. public void backtracking(int[] nums, int startIndex){
  13. if(path.size() == nums.length) res.add(new ArrayList<>(path));
  14. for(int i = startIndex;i < nums.length;i++){
  15. if(i > 0 && nums[i] == nums[i - 1] && !used_test[i - 1] || used_test[i]) continue;
  16. // if() continue;
  17. used_test[i] = true;
  18. path.add(nums[i]);
  19. backtracking(nums,0);
  20. used_test[i] = false;
  21. path.remove(path.size() - 1);
  22. }
  23. }
  24. }

题目(未完成)51:N皇后

  1. class Solution {
  2. List<List<String>> res = new ArrayList<>();
  3. // LinkedList<String>> path = new LinkedList<>();
  4. public List<List<String>> solveNQueens(int n) {
  5. char[][] chessboard = new char[n][n];
  6. for(char c : chessboard){
  7. Arrays.fill(c,'.');
  8. }
  9. backtracking(n,0,chessboard);
  10. return res;
  11. }
  12. public void backtracking(int n,int row,char[][] chessboard){
  13. if(row == n){
  14. res.add(Array2List(chessboard));
  15. return;
  16. }
  17. for(int col = 0;col < n;col++){
  18. if(isValid(row,col,n,chessboard)){
  19. chessboard[row][col] = 'Q';
  20. backtracking(n,row + 1;chessboard);
  21. chessboard[row][col] = '.';
  22. }
  23. }
  24. }
  25. public List Array2List(char[][] chessboard){
  26. List<String> list = new ArrayList<>();
  27. for(char[] c : chessboard){
  28. list.add(String.copyValueOf(c));
  29. }
  30. return list;
  31. }
  32. public boolean isValid(int row,int col,int n,char[][] chessboard){
  33. for(int i = 0;i < row;i++){
  34. if(chessboard[i][col] == 'Q'){
  35. return false;
  36. }
  37. }
  38. for(int i = row - 1,j = col - 1;i >= 0 && j >= 0;i--,j--){
  39. if(chessboard[i][j] == 'Q'){
  40. return false;
  41. }
  42. }
  43. for(int i = row - 1,j = col + 1;i >= 0 && j <= n - 1;i--,j++){
  44. if(chessboard[i][j] = 'Q'){
  45. return false;
  46. }
  47. }
  48. return true;
  49. }
  50. }

 题目(未完成)37:解数独

  1. class Solution {
  2. public void solveSudoku(char[][] board) {
  3. solveSudokuHelper(board);
  4. }
  5. private boolean solveSudokuHelper(char[][] board){
  6. //「一个for循环遍历棋盘的行,一个for循环遍历棋盘的列,
  7. // 一行一列确定下来之后,递归遍历这个位置放9个数字的可能性!」
  8. for (int i = 0; i < 9; i++){ // 遍历行
  9. for (int j = 0; j < 9; j++){ // 遍历列
  10. if (board[i][j] != '.'){ // 跳过原始数字
  11. continue;
  12. }
  13. for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
  14. if (isValidSudoku(i, j, k, board)){
  15. board[i][j] = k;
  16. if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
  17. return true;
  18. }
  19. board[i][j] = '.';
  20. }
  21. }
  22. // 9个数都试完了,都不行,那么就返回false
  23. return false;
  24. // 因为如果一行一列确定下来了,这里尝试了9个数都不行,说明这个棋盘找不到解决数独问题的解!
  25. // 那么会直接返回, 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去!」
  26. }
  27. }
  28. // 遍历完没有返回false,说明找到了合适棋盘位置了
  29. return true;
  30. }
  31. /**
  32. * 判断棋盘是否合法有如下三个维度:
  33. * 同行是否重复
  34. * 同列是否重复
  35. * 9宫格里是否重复
  36. */
  37. private boolean isValidSudoku(int row, int col, char val, char[][] board){
  38. // 同行是否重复
  39. for (int i = 0; i < 9; i++){
  40. if (board[row][i] == val){
  41. return false;
  42. }
  43. }
  44. // 同列是否重复
  45. for (int j = 0; j < 9; j++){
  46. if (board[j][col] == val){
  47. return false;
  48. }
  49. }
  50. // 9宫格里是否重复
  51. int startRow = (row / 3) * 3;
  52. int startCol = (col / 3) * 3;
  53. for (int i = startRow; i < startRow + 3; i++){
  54. for (int j = startCol; j < startCol + 3; j++){
  55. if (board[i][j] == val){
  56. return false;
  57. }
  58. }
  59. }
  60. return true;
  61. }
  62. }

2023/11/15——贪心算法

题目(未完成)376:摆动序列

  1. class Solution {
  2. public int wiggleMaxLength(int[] nums) {
  3. if (nums.length <= 1) {
  4. return nums.length;
  5. }
  6. //当前差值
  7. int curDiff = 0;
  8. //上一个差值
  9. int preDiff = 0;
  10. int count = 1;
  11. for (int i = 1; i < nums.length; i++) {
  12. //得到当前差值
  13. curDiff = nums[i] - nums[i - 1];
  14. //如果当前差值和上一个差值为一正一负
  15. //等于0的情况表示初始时的preDiff
  16. if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
  17. count++;
  18. preDiff = curDiff;
  19. }
  20. }
  21. return count;
  22. }
  23. }

 题目(完成)53:最大子数组和

  1. class Solution {
  2. public int maxSubArray(int[] nums) {
  3. int res = - Integer.MAX_VALUE;
  4. int i = 0;
  5. int max_res = - Integer.MAX_VALUE;
  6. while(i < nums.length){
  7. if(res < 0 && nums[i] > 0){
  8. res = nums[i];
  9. }else if(res <= 0 && nums[i] <= 0){
  10. res = Math.max(res,nums[i]);
  11. }else{
  12. res = res + nums[i];
  13. }
  14. max_res = Math.max(max_res,res);
  15. i++;
  16. }
  17. return max_res;
  18. }
  19. }

 题目(完成)122:买卖股票的最佳时机2

  1. class Solution {
  2. public int maxProfit(int[] prices) {
  3. int i = 0;
  4. int Purchase = Integer.MAX_VALUE;
  5. int Selloff = 0;
  6. int res = 0;
  7. while(i < prices.length){
  8. if(prices[i] < Purchase){
  9. Purchase = prices[i];
  10. }
  11. if(prices[i] > Purchase){
  12. res += prices[i] - Purchase;
  13. Purchase = prices[i];
  14. }
  15. i++;
  16. }
  17. return res;
  18. }
  19. }

题目(未完成)55:跳跃游戏 

  1. class Solution {
  2. public boolean canJump(int[] nums) {
  3. if(nums.length == 1){
  4. return true;
  5. }
  6. int coverRange = 0;
  7. for(int i = 0;i <= coverRange;i++){
  8. coverRange = Math.max(coverRange,i + nums[i]);
  9. if(coverRange >= nums.length - 1){
  10. return true;
  11. }
  12. }
  13. return false;
  14. }
  15. }

题目(未完成)45:跳跃游戏2 

  1. class Solution {
  2. public int jump(int[] nums) {
  3. if (nums == null || nums.length == 0 || nums.length == 1) {
  4. return 0;
  5. }
  6. //记录跳跃的次数
  7. int count=0;
  8. //当前的覆盖最大区域
  9. int curDistance = 0;
  10. //最大的覆盖区域
  11. int maxDistance = 0;
  12. for (int i = 0; i < nums.length; i++) {
  13. //在可覆盖区域内更新最大的覆盖区域
  14. maxDistance = Math.max(maxDistance,i+nums[i]);
  15. //说明当前一步,再跳一步就到达了末尾
  16. if (maxDistance>=nums.length-1){
  17. count++;
  18. break;
  19. }
  20. //走到当前覆盖的最大区域时,更新下一步可达的最大区域
  21. if (i==curDistance){
  22. curDistance = maxDistance;
  23. count++;
  24. }
  25. }
  26. return count;
  27. }
  28. }

题目(完成)1005:K次取反后最大化的数组和

  1. class Solution {
  2. public int largestSumAfterKNegations(int[] nums, int k) {
  3. int count = 0;
  4. int sum = 0;
  5. while(count < k){
  6. Arrays.sort(nums);
  7. nums[0] = - nums[0];
  8. count++;
  9. }
  10. for(int res :nums){
  11. sum += res;
  12. }
  13. return sum;
  14. }
  15. }

题目(未完成)134:加油站

  1. class Solution {
  2. public int canCompleteCircuit(int[] gas, int[] cost) {
  3. int curSum = 0;
  4. int totalSum = 0;
  5. int index = 0;
  6. for (int i = 0; i < gas.length; i++) {
  7. curSum += gas[i] - cost[i];
  8. totalSum += gas[i] - cost[i];
  9. if (curSum < 0) {
  10. index = (i + 1) % gas.length ;
  11. curSum = 0;
  12. }
  13. }
  14. if (totalSum < 0) return -1;
  15. return index;
  16. }
  17. }

题目(未完成)135:分发糖果

  1. //我写的 思路不对
  2. class Solution {
  3. public int candy(int[] ratings) {
  4. int res = 0;
  5. int cur = 0;
  6. int bef = -1;
  7. for(int i = 0;i < ratings.length;i++){
  8. if(ratings[i] > bef){
  9. cur++;
  10. }else if(ratings[i] == bef){
  11. if(cur > 1){
  12. cur--;
  13. }
  14. }else{
  15. cur--;
  16. if(0 >= cur){
  17. cur = 1;
  18. res++;
  19. }
  20. }
  21. res += cur;
  22. bef = ratings[i];
  23. }
  24. return res;
  25. }
  26. }
  27. //答案
  28. class Solution {
  29. /**
  30. 分两个阶段
  31. 1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 1
  32. 2、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大
  33. */
  34. public int candy(int[] ratings) {
  35. int len = ratings.length;
  36. int[] candyVec = new int[len];
  37. candyVec[0] = 1;
  38. for (int i = 1; i < len; i++) {
  39. candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
  40. }
  41. for (int i = len - 2; i >= 0; i--) {
  42. if (ratings[i] > ratings[i + 1]) {
  43. candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
  44. }
  45. }
  46. int ans = 0;
  47. for (int num : candyVec) {
  48. ans += num;
  49. }
  50. return ans;
  51. }
  52. }

题目(完成)860:柠檬水找零

  1. class Solution {
  2. public boolean lemonadeChange(int[] bills) {
  3. if(bills[0] != 5) return false;
  4. int five_dollar = 0;
  5. int ten_dollar = 0;
  6. for(int i = 0;i < bills.length;i++){
  7. if(bills[i] == 5){
  8. five_dollar++;
  9. }else if(bills[i] == 10){
  10. ten_dollar++;
  11. five_dollar--;
  12. if(five_dollar < 0) return false;
  13. }else{
  14. if(ten_dollar > 0){
  15. ten_dollar--;
  16. five_dollar--;
  17. if(five_dollar < 0) return false;
  18. }else{
  19. if(five_dollar < 3){
  20. return false;
  21. }else{
  22. five_dollar = five_dollar - 3;
  23. }
  24. }
  25. }
  26. }
  27. return true;
  28. }
  29. }

题目(未完成)406:根据身高重建队列

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

二维数组排序

LinkedList.add()

Java LinkedList add()用法及代码示例 - 纯净天空 (vimsky.com)


题目(完成一半)452:用最少数量的箭引爆气球

  1. class Solution {
  2. public int findMinArrowShots(int[][] points) {
  3. int res = 1;
  4. // int Launch_position = 0;
  5. Arrays.sort(points,(a,b) -> Integer.compare(a[0],b[0]));
  6. for(int i = 1;i < points.length;i++){
  7. if(points[i][0] > points[i - 1][1]){
  8. res++;
  9. }else{
  10. points[i][1] = Math.min(points[i][1],points[i - 1][1]);
  11. }
  12. }
  13. // while(i < points.length){
  14. // Launch_position = points[i - 1][1];
  15. // if(Launch_position >= points[i][0] && points[i][1] >= Launch_position){
  16. // if(i + 1 < points.length){
  17. // i++;
  18. // }else{
  19. // res++;
  20. // i++;
  21. // }
  22. // }else{
  23. // res++;
  24. // i++;
  25. // }
  26. // }
  27. // res++;
  28. return res;
  29. }
  30. }

题目(完成)435:无重叠区间

  1. class Solution {
  2. public int eraseOverlapIntervals(int[][] intervals) {
  3. Arrays.sort(intervals,(a,b) -> {
  4. if(a[0] == b[0]) return a[1] - b[1];
  5. return a[0] - b[0];
  6. });
  7. int count = 0;
  8. for(int i = 1; i < intervals.length;i++){
  9. if(intervals[i][0] == intervals[i - 1][0]){
  10. intervals[i][1] = Math.min(intervals[i][1],intervals[i - 1][1]);
  11. count++;
  12. }else{
  13. if(intervals[i][0] > intervals[i - 1][0] && intervals[i][0] < intervals[i - 1][1]){
  14. count++;
  15. intervals[i][0] = Math.max(intervals[i][0],intervals[i - 1][0]);
  16. intervals[i][1] = Math.min(intervals[i][1],intervals[i - 1][1]);
  17. }
  18. }
  19. }
  20. return count;
  21. }
  22. }

题目(未完成且不是很理解答案)763:划分字母区间

  1. class Solution {
  2. public List<Integer> partitionLabels(String s) {
  3. List<Integer> list = new LinkedList<>();
  4. int[] edge = new int[26];
  5. char[] chars = S.toCharArray();
  6. for(int i = 0;i < chars.length;i++){
  7. edge[chars[i] - 'a'] = i;
  8. }
  9. int idx = 0;
  10. int last = -1;
  11. for(int i = 0;i < chars.length;i++){
  12. idx = Math.max(idx,edge[chars[i] - 'a']);
  13. if(i == idx){
  14. list.add(i - last);
  15. last = i;
  16. }
  17. }
  18. return list;
  19. }
  20. }

题目(完成)56:合并区间

  1. class Solution {
  2. public int[][] merge(int[][] intervals) {
  3. List<int[]> res = new LinkedList<>();
  4. Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
  5. // Arraysort(intervals,(a,b) -> {
  6. // if(a[0] == b[0]) return a[1] - b[1];
  7. // return a[0] - b[0];
  8. // });
  9. if(intervals.length == 1){
  10. res.add(intervals[0]);
  11. return res.toArray(new int[res.size()][]);
  12. }
  13. // if(intervals.length > 1 && intervals[1][0] > intervals[0][1]){
  14. // res.add(intervals[0]);
  15. // }
  16. for(int i = 1;i < intervals.length;i++){
  17. if(intervals[i][0] == intervals[i - 1][0]){
  18. intervals[i][1] = Math.max(intervals[i][1],intervals[i - 1][1]);
  19. // if(i == intervals.length - 1){
  20. // res.add(intervals[i]);
  21. // }
  22. }else if(intervals[i][0] > intervals[i - 1][0] && intervals[i - 1][1] >= intervals[i][0]){
  23. intervals[i][0] = Math.min(intervals[i][0],intervals[i - 1][0]);
  24. intervals[i][1] = Math.max(intervals[i][1],intervals[i - 1][1]);
  25. // if(i == intervals.length - 1){
  26. // res.add(intervals[i]);
  27. // }
  28. }else{
  29. res.add(intervals[i - 1]);
  30. }
  31. if(i == intervals.length - 1){
  32. res.add(intervals[i]);
  33. }
  34. }
  35. return res.toArray(new int[res.size()][]);
  36. // return res;
  37. }
  38. }

题目(未完成,好好审题)738:单调递增的数字

  1. class Solution {
  2. public int monotoneIncreasingDigits(int n) {
  3. String s = String.valueOf(n);
  4. char[] chars = s.toCharArray();
  5. int start = s.length();
  6. for (int i = s.length() - 2; i >= 0; i--) {
  7. if (chars[i] > chars[i + 1]) {
  8. chars[i]--;
  9. start = i+1;
  10. }
  11. }
  12. for (int i = start; i < s.length(); i++) {
  13. chars[i] = '9';
  14. }
  15. return Integer.parseInt(String.valueOf(chars));
  16. }
  17. }

2023/12/21——动态规划 

题目(完成)509:斐波那契数

  1. class Solution {
  2. public int fib(int n) {
  3. int a = 0;
  4. int b = 1;
  5. if(n == 0) return a;
  6. if(n == 1) return b;
  7. int temp = 0;
  8. for(int i = 0;i <= n - 2;i++){
  9. temp = b;
  10. b = a + b;
  11. a = temp;
  12. }
  13. return b;
  14. }
  15. }

题目(未完成)70:爬楼梯

  1. // 用变量记录代替数组
  2. class Solution {
  3. public int climbStairs(int n) {
  4. if(n <= 2) return n;
  5. int a = 1, b = 2, sum = 0;
  6. for(int i = 3; i <= n; i++){
  7. sum = a + b; // f(i - 1) + f(i - 2)
  8. a = b; // 记录f(i - 1),即下一轮的f(i - 2)
  9. b = sum; // 记录f(i),即下一轮的f(i - 1)
  10. }
  11. return b;
  12. }
  13. }

题目(未完成)746:使用最小花费爬楼梯

  1. class Solution {
  2. public int minCostClimbingStairs(int[] cost) {
  3. int len = cost.length;
  4. int[] dp = new int[len + 1];
  5. // 从下标为 0 或下标为 1 的台阶开始,因此支付费用为0
  6. dp[0] = 0;
  7. dp[1] = 0;
  8. // 计算到达每一层台阶的最小费用
  9. for (int i = 2; i <= len; i++) {
  10. dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  11. }
  12. return dp[len];
  13. }
  14. }

题目(临时,完成)27:移除元素

  1. class Solution {
  2. public int removeElement(int[] nums, int val) {
  3. int res = nums.length;
  4. int i = 0;
  5. int j = nums.length - 1;
  6. int temp = -1;
  7. while(i <= j){
  8. if(nums[i] == val){
  9. while(nums[j] == val){
  10. j--;
  11. res--;
  12. if(i > j || res <= 0){
  13. break;
  14. }
  15. }
  16. if(i > j || res <= 0){
  17. break;
  18. }else{
  19. temp = nums[i];
  20. nums[i] = nums[j];
  21. nums[j] = temp;
  22. j--;
  23. res--;
  24. }
  25. }
  26. i++;
  27. }
  28. return res;
  29. }
  30. }

题目(完成)62:不同路径

  1. class Solution {
  2. public int uniquePaths(int m, int n) {
  3. //确定dp数组及其下标的含义
  4. int[][] dp = new int[m][n];
  5. for(int i = 0; i < m;i++){
  6. dp[i][0] = 1;
  7. }
  8. for(int j = 0;j < n;j++){
  9. dp[0][j] = 1;
  10. }
  11. for(int i = 1;i < m;i++){
  12. for(int j = 1; j < n;j++){
  13. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  14. }
  15. }
  16. return dp[m - 1][n - 1];
  17. }
  18. }

题目(完成)63:不同路径2

  1. class Solution {
  2. public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3. int m = obstacleGrid.length;
  4. int n = obstacleGrid[0].length;
  5. int[][] dp = new int[m][n];
  6. for(int i = 0;i < m;i++){
  7. if(i > 0){
  8. if(obstacleGrid[i][0] == 1 || dp[i - 1][0] == 0){
  9. dp[i][0] = 0;
  10. }else{
  11. dp[i][0] = 1;
  12. }
  13. }else{
  14. if(obstacleGrid[i][0] == 1){
  15. dp[i][0] = 0;
  16. }else{
  17. dp[i][0] = 1;
  18. }
  19. }
  20. }
  21. for(int j = 0;j < n;j++){
  22. if(j > 0){
  23. if(obstacleGrid[0][j] == 1 || dp[0][j - 1] == 0){
  24. dp[0][j] = 0;
  25. }else{
  26. dp[0][j] = 1;
  27. }
  28. }else{
  29. if(obstacleGrid[0][j] == 1){
  30. dp[0][j] = 0;
  31. }else{
  32. dp[0][j] = 1;
  33. }
  34. }
  35. }
  36. for(int i = 1;i < m;i++){
  37. for(int j = 1;j < n;j++){
  38. if(obstacleGrid[i][j] == 1){
  39. dp[i][j] = 0;
  40. }else{
  41. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  42. }
  43. }
  44. }
  45. return dp[m - 1][n - 1];
  46. }
  47. }

 题目(未完成)343:整数拆分

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

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

 

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

题目(未完成)416:分割等和子集

  1. class Solution {
  2. public boolean canPartition(int[] nums) {
  3. if(nums == null || nums.length == 0) return false;
  4. int n = nums.length;
  5. int sum = 0;
  6. for(int num : nums){
  7. sum += num;
  8. }
  9. if(sum % 2 != 0) return false;
  10. int target = sum / 2;
  11. int[] dp = new int[target + 1];
  12. for(int i = 0; i < n;i++){
  13. for(int j = target;j >= nums[i];j--){
  14. dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
  15. }
  16. if(dp[target] == target) return true;
  17. }
  18. return dp[target] == target;
  19. }
  20. }

 题目(完成一半)1049:最后一块石头的重量2

  1. class Solution {
  2. public int lastStoneWeightII(int[] stones) {
  3. int sum = 0;
  4. for(int num : stones){
  5. sum += num;
  6. }
  7. int target = sum / 2;
  8. int[] dp = new int[target + 1];
  9. for(int i = 0; i < stones.length;i++){
  10. for(int j = target; j >= stones[i];j--){
  11. dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
  12. }
  13. }
  14. return sum - 2 * dp[target];
  15. }
  16. }

题目(未完成)494:目标和

  1. class Solution {
  2. public int findTargetSumWays(int[] nums, int target) {
  3. int sum = 0;
  4. for(int i = 0; i < nums.length;i++) sum += nums[i];
  5. if(target < 0 && sum < - target) return 0;
  6. if((target + sum) % 2 != 0) return 0;
  7. int size = (target + sum) / 2;
  8. if(size < 0) size = -size;
  9. int[] dp = new int[size + 1];
  10. dp[0] = 1;
  11. for(int i = 0;i < nums.length;i++){
  12. for(int j = size;j >= num[i];j--){
  13. dp[j] += dp[j - nums[i]];
  14. }
  15. }
  16. return dp[size];
  17. }
  18. }

题目(未完成)474:一和零

  1. class Solution {
  2. public int findMaxForm(String[] strs, int m, int n) {
  3. //dp[i][j]表示i个0和j个1时的最大子集
  4. int[][] dp = new int[m + 1][n + 1];
  5. int oneNum, zeroNum;
  6. for (String str : strs) {
  7. oneNum = 0;
  8. zeroNum = 0;
  9. for (char ch : str.toCharArray()) {
  10. if (ch == '0') {
  11. zeroNum++;
  12. } else {
  13. oneNum++;
  14. }
  15. }
  16. //倒序遍历
  17. for (int i = m; i >= zeroNum; i--) {
  18. for (int j = n; j >= oneNum; j--) {
  19. dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
  20. }
  21. }
  22. }
  23. return dp[m][n];
  24. }
  25. }

完全背包问题:求组合数,先遍历物品,再遍历背包;求排列数,先遍历背包,再遍历物品

题目(未完成)322:零钱兑换

  1. class Solution {
  2. public int coinChange(int[] coins, int amount) {
  3. //dp[j]数组的含义:装满容量大小为j的背包的最少物品为dp[j];
  4. int[] dp = new int[amount + 1];
  5. for(int k = 0;k < dp.length;k++){
  6. dp[k] = Integer.MAX_VALUE;
  7. }
  8. dp[0] = 0;
  9. for(int i = 0;i < coins.length;i++){
  10. for(int j = coins[i];j <= amount;j++){
  11. if(dp[j - coins[i]] != Integer.MAX_VALUE){
  12. dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
  13. }
  14. }
  15. }
  16. return dp[amount] == Integer.MAX_VALUE ? -1:dp[amount];
  17. }
  18. }

题目(完成一半)279:完全平方数

  1. class Solution {
  2. public int numSquares(int n) {
  3. //dp[i] 装满容量大小为i的背包,所需要的最少完全平方数的数量
  4. int[] dp = new int[n + 1];
  5. for(int k = 0;k < dp.length;k++){
  6. dp[k] = Integer.MAX_VALUE;
  7. }
  8. dp[0] = 0;
  9. for(int i = 1;i * i <= n;i++){
  10. for(int j = i * i;j <= n;j++){
  11. dp[j] = Math.min(dp[j],dp[j - i * i] + 1);
  12. }
  13. }
  14. return dp[n];
  15. }
  16. }

题目(未完成)139:单词划分

  1. class Solution {
  2. public boolean wordBreak(String s, List<String> wordDict) {
  3. HashSet<String> set = new HashSet<>(wordDict);
  4. boolean[] valid = new boolean[s.length() + 1];
  5. valid[0] = true;
  6. for (int i = 1; i <= s.length(); i++) {
  7. for (int j = 0; j < i && !valid[i]; j++) {
  8. if (set.contains(s.substring(j, i)) && valid[j]) {
  9. valid[i] = true;
  10. }
  11. }
  12. }
  13. return valid[s.length()];
  14. }
  15. }

题目(完成一半)198:打家劫舍

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

题目(未完成)213:打家劫舍2

  1. class Solution {
  2. public int rob(int[] nums) {
  3. if (nums == null || nums.length == 0)
  4. return 0;
  5. int len = nums.length;
  6. if (len == 1)
  7. return nums[0];
  8. return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
  9. }
  10. int robAction(int[] nums, int start, int end) {
  11. int x = 0, y = 0, z = 0;
  12. for (int i = start; i < end; i++) {
  13. y = z;
  14. z = Math.max(y, x + nums[i]);
  15. x = y;
  16. }
  17. return z;
  18. }
  19. }

 题目(未完成)121:买卖股票的最佳时机

  1. class Solution {
  2. public int maxProfit(int[] prices) {
  3. if (prices == null || prices.length == 0) return 0;
  4. int length = prices.length;
  5. // dp[i][0]代表第i天持有股票的最大收益
  6. // dp[i][1]代表第i天不持有股票的最大收益
  7. int[][] dp = new int[length][2];
  8. int result = 0;
  9. dp[0][0] = -prices[0];
  10. dp[0][1] = 0;
  11. for (int i = 1; i < length; i++) {
  12. dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
  13. dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
  14. }
  15. return dp[length - 1][1];
  16. }
  17. }

 题目(未完成)122:买卖股票的最佳时机2

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

  题目(未完成)123:买卖股票的最佳时机3

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

   题目(未完成)188:买卖股票的最佳时机4

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

  题目(未完成)309:买卖股票的最佳时机含冷冻期

  1. class Solution {
  2. public int maxProfit(int[] prices) {
  3. int len = prices.length;
  4. int dp[][] = new int[len][4];
  5. dp[0][0] = -prices[0];
  6. for(int i = 1;i < len; i++){
  7. dp[i][0] = Math.max(Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]),dp[i - 1][3] - prices[i]);
  8. dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][3]);
  9. dp[i][2] = dp[i - 1][0] + prices[i];
  10. dp[i][3] = dp[i - 1][2];
  11. }
  12. return Math.max(Math.max(dp[len - 1][1],dp[len - 1][2]),dp[len - 1][3]);
  13. }
  14. }

题目(完成一半)714:买卖股票的最佳时机含手续费

  1. class Solution {
  2. public int maxProfit(int[] prices, int fee) {
  3. int n = prices.length;
  4. int[][] dp = new int[n][2];
  5. // 0 不持股
  6. // 1 持股
  7. dp[0][0] = 0;
  8. dp[0][1] = -prices[0];
  9. for(int i = 1; i < n;i++){
  10. dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
  11. dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
  12. }
  13. return dp[n - 1][0];
  14. }
  15. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/article/detail/45317
推荐阅读
相关标签
  

闽ICP备14008679号