LeetCode日记

2022/04/27 LeetCode.26 简单

/// <summary>
      /// 2022/04/27 LeetCode.26 简单
      /// 执行用时：62.38% 内存消耗：59.40%
      /// </summary>
      public static int RemoveDuplicates(int[] nums)
      {
          int indexP = 0;
          int num = nums[0];

          for (int i = 1; i < nums.Length; i++)
          {
              if (nums[i] != num)
              {
                  num = nums[i];
                  nums[++indexP] = num;
              }
          }

          return indexP + 1;
      }

2022/04/28 LeetCode.27移除元素 简单

/// <summary>
      /// 2022/04/28 LeetCode.27移除元素 简单
      /// 执行用时：7.48% 内存消耗：10.92%
      /// </summary>
      public static int RemoveElement(int[] nums, int val)
      {
          int index = -1;
          for (int i = 0; i < nums.Length; i++)
          {
              if (nums[i] != val)
              {
                  index++;
                  if (i!=index)
                  {
                      nums[index] = nums[i];
                  }
              }
          }
          return index + 1;
      }

      /// <summary>
      /// 双指针优化 至多只需遍历一次
      /// 执行用时：75.13% 内存消耗：81.80%
      /// <returns></returns>
      public static int RemoveElement1(int[] nums, int val)
      {
          int left = 0;
          int right = nums.Length;
          while (left<right)
          {
              if (nums[left] == val)
              {
                  nums[left] = nums[right - 1];
                  right--;
              }
              else
              {
                  left++;
              }
          }

          return left;
      }

2022/04/29 LeetCode.35搜索插入位置 简单

/// <summary>
      /// 2022/04/29 LeetCode.35搜索插入位置 简单
      /// 双指针二分法
      /// 执行用时：20.49% 内存消耗：86.41%
      /// </summary>
      public static int SearchInsert(int[] nums, int target)
      {
          int left = 0;
          int right = nums.Length - 1;

          while (left <= right)
          {
              int middle = (left + right) / 2;

              if (nums[middle] == target)
              {
                  return middle;
              }
              else if (nums[middle] > target)
              {
                  right = middle - 1;
              }
              else if (nums[middle] < target)
              {
                  left = middle + 1;
              }
          }

          return left;
      }

2022/05/05 LeetCode.66加一 简单

/// <summary>
      /// 2022/05/05 LeetCode.66加一 简单
      /// 
      /// 执行用时：55.04% 内存消耗：63.67%
      /// </summary>
      public static int[] PlusOne(int[] digits)
      {
          for (int i = digits.Length - 1; i >= 0; i--)
          {
              if (digits[i] == 9)//需要进位
              {
                  if (i == 0)//需要扩充数组
                  {
                      int[] newdisgits = new int[digits.Length + 1];
                      newdisgits[0] = 1;
                      return newdisgits;
                  }
                  else
                  {
                      digits[i] = 0;
                  }          
              }
              else
              {
                  digits[i]++;
                  return digits;
              }
          }

          return digits;
      }

2022/05/06 LeetCode.70爬楼梯 简单

/// <summary>
      /// 2022/05/06 LeetCode.70爬楼梯 简单
      /// 到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法
      /// 执行用时：82.65% 内存消耗：43.42%
      /// </summary>
      public int ClimbStairs(int n)
      {
          if (n == 1) return 1;
          if (n == 2) return 2;

          int temp, a = 1, b = 2;
          for (int i = 3; i <= n; i++)
          {
              temp = a;//temp用于记录i-2的台阶方法数
              a = b;
              b = temp + a;
          }

          return b;
      }

2022/05/07 LeetCode.53最大子数组和 简单

/// <summary>
     /// 2022/05/07 LeetCode.53最大子数组和 简单
     /// 动态规划
     /// 执行用时：18.61% 内存消耗：36.78%
     /// </summary>
     public static int MaxSubArray(int[] nums)
     {
         int preAns = 0;//前置数组和
         int maxAns = nums[0];//最大数组和
         foreach (int num in nums)
         {
             preAns = Math.Max(preAns + num, num);//如果当前数+前置数组和  小于当前数 则舍弃前置数组
             maxAns = Math.Max(maxAns, preAns);
         }
         return maxAns;
     }

2022/05/09 LeetCode.1两数之和 简单

/// <summary>
     /// 2022/05/09 LeetCode.1两数之和 简单
     /// 双指针
     /// 执行用时：78.73% 内存消耗：83.46%
     /// </summary>
     public int[] TwoSum(int[] nums, int target)
     {
         Dictionary<int,int> targetDic = new Dictionary<int,int>();//对应值 索引位置 

         int left = 0, right = nums.Length - 1;

         while (left <= right)
         {
             int targetNum = target - nums[left];
             if (targetDic.ContainsKey(targetNum))
             {
                 return new int[] { left, targetDic[targetNum] };
             }
             else
             {
                 targetDic[nums[left]] = left;
             }

             targetNum = target - nums[right];
             if (targetDic.ContainsKey(targetNum))
             {
                 return new int[] { right, targetDic[targetNum] };
             }
             else
             {
                 targetDic[nums[right]] = right;
             }

             left++;
             right--;
         }

         return new int[] {0};//题意不会走到这步
     }

2022/05/10 LeetCode.58最后一个单词的长度 简单

/// <summary>
       /// 2022/05/10 LeetCode.58最后一个单词的长度 简单
       /// 
       /// 执行用时：97.08% 内存消耗：65.33%
       /// </summary>
       public int LengthOfLastWord(string s)
       {
           int length = 0;
           for (int i = s.Length - 1 ; i >= 0; i--)
           {
               if (s[i] != ' ')
               {
                   length++;
               }
               else if(length != 0)
               {
                   break;
               }
           }
           return length;
       }

2022/05/11 LeetCode.69x的平方根 简单

/// <summary>
      /// 2022/05/11 LeetCode.69x的平方根  简单
      /// 二分查找
      /// 执行用时：90.08% 内存消耗：37.81%
      /// </summary>
      public int MySqrt(int x)
      {
          if (x == 1) return 1;
          int min = 0;
          int max = x;
          while (max - min > 1)
          {
              int temp = (max + min) / 2;
              if (x/ temp < temp)
              {
                  max = temp;
              }
              else if (x/ temp > temp)
              {
                  min = temp;
              }
              else
              {
                  return temp;
              }
          }
          return min;
      }

2022/05/12 LeetCode 88. 合并两个有序数组 简单

/// <summary>
      /// 2022/05/12 LeetCode 88. 合并两个有序数组  简单
      /// 理解题意
      /// 执行用时：64.64% 内存消耗：16.85%
      /// </summary>
      public void Merge(int[] nums1, int m, int[] nums2, int n)
      {
          int one = m - 1;
          int two = n - 1;
          int newNode = m + n - 1;

          while (two >=0)
          {
              if (one < 0 || nums2[two] > nums1[one])
              {
                  nums1[newNode--] = nums2[two--];
              }
              else
              {
                  nums1[newNode--] = nums1[one--];
              }
          }
      }

2022/05/13 LeetCode 43. 字符串相乘 简单

/// <summary>
      /// 2022/05/13 LeetCode 43. 字符串相乘  简单
      /// 模拟竖式乘法
      /// 执行用时：46.71% 内存消耗：32.24%
      /// </summary>
      public static string Multiply(string num1, string num2)
      {
          if (num1 == "0" || num2 == "0")
          {
              return "0";
          }

          string result = "0";

          int lengthOne = num1.Length;
          int lengthTwo = num2.Length;

          Stack<int> addStack = new Stack<int>();//计数栈

          for (int i = lengthTwo - 1; i >= 0; i--)//以num2去乘num1
          {
              StringBuilder sb = new StringBuilder();
                            
              for (int j = lengthTwo - 1; j >i; j--)//高位相乘 需要添加对应的0
              {
                  addStack.Push(0);
              }
              int num = num2[i] - '0';//乘数

              int add = 0;//进位
              for (int k = lengthOne - 1; k >=0; k--)//乘法计算
              {
                  int singleNum = num1[k] - '0';
                  int ans = num * singleNum + add;
                  addStack.Push(ans % 10);
                  add = ans / 10;//进位
              }

              if (add != 0)
              {
                  addStack.Push(add % 10);
              }

              while (addStack.Count > 0)
              {
                  sb.Append(addStack.Pop());
              }

              //结果相加
              result = AddStr(result, sb.ToString());
          }

          return result;
      }

      public static String AddStr(string result,string addStr)
      {
          int lengthResult = result.Length - 1;
          int lengthAdd = addStr.Length - 1;
          int Add = 0;
          StringBuilder sb = new StringBuilder();
          Stack<int> addStack = new Stack<int>();//计数栈
          while (lengthResult >= 0 || lengthAdd >=0 || Add != 0)
          {
              int x = lengthResult >= 0 ? result[lengthResult] - '0' : 0;
              int y = lengthAdd >= 0 ? addStr[lengthAdd] - '0' : 0;
              int ans = x + y + Add;
              addStack.Push(ans % 10);
              Add = ans / 10;
              lengthResult--; lengthAdd--;
          }

          while (addStack.Count > 0)
          {
              sb.Append(addStack.Pop());
          }

          return sb.ToString();
      }