0715学习

面试 leetcode学习
  • 剑指 Offer 20. 表示数值的字符串
    请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：
若干空格
一个 小数 或者 整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
若干空格

小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（’+’ 或 ‘-‘）
下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
至少一位数字

部分数值列举如下：
[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]
部分非数值列举如下：
[“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]

提示：
1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 ‘+’ ，减号 ‘-’ ，空格 ’ ’ 或者点 ‘.’ 。

  1. private enum InputState
  2. {
  3.     Default,
  4.     Symbol,
  5.     Dot,
  6.     Int,
  7.     Decimal,
  8.     E,
  9.     ESymbol,
  10.     EInt,
  11. }
  12. 

  13. private string _symbols = "+-";
  14. private string _numbers = "0987654321";
  15. private string _dot = ".";
  16. private string _e = "Ee";
  17. 

  18. public bool IsNumber(string s)
  19. {
  20.     s = s.Trim();
  21.     if (s.Length <= 0)
  22.     {
  23.         return false;
  24.     }
  25. 

  26.     var state = __Help(s);
  27. 

  28.     return state is InputState.Decimal or InputState.Int or InputState.EInt;
  29. }
  30. 

  31. private InputState __Help(string s)
  32. {
  33.     var state = InputState.Default;
  34.     var i = 0;
  35.     while (i < s.Length)
  36.     {
  37.         var c = s[i];
  38.         switch (state)
  39.         {
  40.             case InputState.Default:
  41.                 if (_symbols.Contains(c))
  42.                 {
  43.                     state = InputState.Symbol;
  44.                 }
  45.                 else if (_numbers.Contains(c))
  46.                 {
  47.                     state = InputState.Int;
  48.                 }
  49.                 else if (_dot.Contains(c))
  50.                 {
  51.                     state = InputState.Dot;
  52.                 }
  53.                 else
  54.                 {
  55.                     return InputState.Default;
  56.                 }
  57. 

  58.                 break;
  59.             case InputState.Symbol:
  60.                 if (_numbers.Contains(c))
  61.                 {
  62.                     state = InputState.Int;
  63.                 }
  64.                 else if (_dot.Contains(c))
  65.                 {
  66.                     state = InputState.Dot;
  67.                 }
  68.                 else
  69.                 {
  70.                     return InputState.Default;
  71.                 }
  72. 

  73.                 break;
  74.             case InputState.Dot:
  75.                 if (_numbers.Contains(c))
  76.                 {
  77.                     state = InputState.Decimal;
  78.                 }
  79.                 else
  80.                 {
  81.                     return InputState.Default;
  82.                 }
  83. 

  84.                 break;
  85.             case InputState.Int:
  86.                 if (_numbers.Contains(c))
  87.                 {
  88.                     i++;
  89.                     continue;
  90.                 }
  91. 

  92.                 if (_dot.Contains(c))
  93.                 {
  94.                     state = InputState.Decimal;
  95.                 }
  96.                 else if (_e.Contains(c))
  97.                 {
  98.                     state = InputState.E;
  99.                 }
  100.                 else
  101.                 {
  102.                     return InputState.Default;
  103.                 }
  104. 

  105.                 break;
  106.             case InputState.Decimal:
  107.                 if (_numbers.Contains(c))
  108.                 {
  109.                     i++;
  110.                     continue;
  111.                 }
  112. 

  113.                 if (_e.Contains(c))
  114.                 {
  115.                     state = InputState.E;
  116.                 }
  117.                 else
  118.                 {
  119.                     return InputState.Default;
  120.                 }
  121. 

  122.                 break;
  123.             case InputState.E:
  124.                 if (_numbers.Contains(c))
  125.                 {
  126.                     state = InputState.EInt;
  127.                 }
  128.                 else if (_symbols.Contains(c))
  129.                 {
  130.                     state = InputState.ESymbol;
  131.                 }
  132.                 else
  133.                 {
  134.                     return InputState.Default;
  135.                 }
  136. 

  137.                 break;
  138.             case InputState.ESymbol:
  139.                 if (_numbers.Contains(c))
  140.                 {
  141.                     state = InputState.EInt;
  142.                 }
  143.                 else
  144.                 {
  145.                     return InputState.Default;
  146.                 }
  147. 

  148.                 break;
  149.             case InputState.EInt:
  150.                 if (_numbers.Contains(c))
  151.                 {
  152.                     i++;
  153.                     continue;
  154.                 }
  155. 

  156.                 return InputState.Default;
  157.         }
  158. 

  159.         i++;
  160.     }
  161. 

  162.     return state;
  163. }
  • 剑指 Offer 67. 把字符串转换成整数
    写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
    首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
    当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
    该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
    注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
    在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

WX20230714-1513252x.png

  1. private string _symbol = "+-";
  2. private string _number = "0987654321";
  3. 

  4. public int StrToInt(string str)
  5. {
  6.     str = str.Trim();
  7.     var num = 0;
  8.     var i = 0;
  9.     var symbol = 1;
  10.     var bndry = Int32.MaxValue / 10;
  11.     while (i < str.Length)
  12.     {
  13.         var c = str[i];
  14.         if (i == 0)
  15.         {
  16.             if (_symbol.Contains(c))
  17.             {
  18.                 symbol = c == '+' ? 1 : -1;
  19.             }
  20.             else if (_number.Contains(c))
  21.             {
  22.                 num = (c - '0');
  23.             }
  24.             else
  25.             {
  26.                 return 0;
  27.             }
  28.         }
  29.         else
  30.         {
  31.             if (_number.Contains(c))
  32.             {
  33.                 if (num > bndry || num == bndry && (c - '0') > 7)
  34.                 {
  35.                     return symbol == 1 ? int.MaxValue : int.MinValue;
  36.                 }
  37. 

  38.                 num = num * 10 + (c - '0');
  39. 

  40.                 // var temp = ((long)num) * 10 + (c - '0');
  41.                 // var tempSymbol = temp * symbol;
  42.                 // switch (tempSymbol)
  43.                 // {
  44.                 //     case >= int.MaxValue:
  45.                 //         return int.MaxValue;
  46.                 //     case <= int.MinValue:
  47.                 //         return int.MinValue;
  48.                 //     default:
  49.                 //         num = (int)temp;
  50.                 //         break;
  51.                 // }
  52.             }
  53.             else
  54.             {
  55.                 return symbol * num;
  56.             }
  57.         }
  58. 

  59.         i++;
  60.     }
  61. 

  62.     return num * symbol;
  63. }
  • 滑动窗口最大值
    给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
    返回 滑动窗口中的最大值 。
    示例 1：
    输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
    输出：[3,3,5,5,6,7]
    解释：
    滑动窗口的位置 最大值
    ————— —–
    [1 3 -1] -3 5 3 6 7 3
    1 [3 -1 -3] 5 3 6 7 3
    1 3 [-1 -3 5] 3 6 7 5
    1 3 -1 [-3 5 3] 6 7 5
    1 3 -1 -3 [5 3 6] 7 6
    1 3 -1 -3 5 [3 6 7] 7

主要考察的是实现单调队列,保证队列头最大，新添加的数据如果发现队尾比添加数据下，这将队尾数据弹出，再添加数据

  1. public int[] MaxSlidingWindow(int[] nums, int k)
  2. {
  3.     var length = nums.Length;
  4.     if (length <= 0 || k == 0)
  5.     {
  6.         return Array.Empty<int>();
  7.     }
  8. 

  9.     var result = new int[length - k + 1];
  10.     var queue = new LinkedList<int>();
  11.     for (int i = 0; i < k; i++)
  12.     {
  13.         while (queue.Count > 0 && queue.Last.Value < nums[i])
  14.         {
  15.             queue.RemoveLast();
  16.         }
  17. 

  18.         queue.AddLast(nums[i]);
  19.     }
  20. 

  21.     result[0] = queue.First.Value;
  22. 

  23.     for (var i = k; i < length; i++)
  24.     {
  25.         if (queue.First.Value == nums[i - k])
  26.         {
  27.             queue.RemoveFirst();
  28.         }
  29. 

  30.         while (queue.Count > 0 && queue.Last.Value < nums[i])
  31.         {
  32.             queue.RemoveLast();
  33.         }
  34. 

  35.         queue.AddLast(nums[i]);
  36.         result[i - k + 1] = queue.First.Value;
  37.     }
  38. 

  39.     return result;
  40. }
  • 剑指 Offer 59 - II. 队列的最大值
    请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
    若队列为空，pop_front 和 max_value 需要返回 -1
    示例 1：
    输入:
    [“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
    [[],[1],[2],[],[],[]]
    输出: [null,null,null,2,1,2]
    示例 2：
    输入:
    [“MaxQueue”,”pop_front”,”max_value”]
    [[],[],[]]
    输出: [null,-1,-1]
    限制：
    1 <= push_back,pop_front,max_value的总操作数 <= 10000
    1 <= value <= 10^5
  1. public class MaxQueue
  2. {
  3.     private Queue<int> _queueLink;
  4.     //双端队列
  5.     private LinkedList<int> _maxQueue;
  6.     public MaxQueue()
  7.     {
  8.         _queueLink = new Queue<int>();
  9.         _maxQueue = new LinkedList<int>();
  10.     }
  11. 

  12.     public int Max_value()
  13.     {
  14.         if (_maxQueue.Count <= 0)
  15.         {
  16.             return -1;
  17.         }
  18. 

  19.         return _maxQueue.First.Value;
  20.     }
  21. 

  22.     public void Push_back(int value)
  23.     {
  24.         while (_maxQueue.Count > 0 && _maxQueue.Last.Value < value)
  25.         {
  26.             _maxQueue.RemoveLast();
  27.         }
  28. 

  29.         _queueLink.Enqueue(value);
  30.         _maxQueue.AddLast(value);
  31.     }
  32. 

  33.     public int Pop_front()
  34.     {
  35.         if (_queueLink.Count <= 0)
  36.         {
  37.             return -1;
  38.         }
  39. 

  40. 

  41.         var v = _queueLink.Dequeue();
  42.         if (v == _maxQueue.First.Value)
  43.         {
  44.             _maxQueue.RemoveFirst();
  45.         }
  46. 

  47.         return v;
  48.     }
  49. }
0718学习
0714学习