Leetcode 编程笔记

  1. 两数之和
  2. 无重复字符的最长子串
  3. 最长回文子串
  4. 整数反转
  5. 回文数
  6. 三数之和
  7. 最接近的三数之和

leetcode 算法题解法

持续更新

两数之和

  • 题目
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    # 将slice编程器数组,在进行求解
    func twoSum(nums []int, target int) []int {
    // turn slice to map
    numsMap := make(map[int][]int)
    for index, value := range nums {
    if numsMap[value] == nil {
    numsMap[value] = []int{}
    }
    numsMap[value] = append(numsMap[value], index)
    }

    for value, indexArr1 := range numsMap {
    indexArr2, isExist := numsMap[target-value]
    if isExist {
    if target == value*2 && len(indexArr1)>=2 {
    return []int{indexArr1[0], indexArr1[1]}
    } else if target == value*2 && len(indexArr1)<2 {
    return nil
    }
    return []int{indexArr1[0], indexArr2[0]}
    }
    }

    return nil
    }

无重复字符的最长子串

  • 题目
  • 滑动窗口详解
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # 使用滑动窗口
    func lengthOfLongestSubstring(s string) int {
    var i, j, max int

    for j < len(s) {
    if strings.Contains(s[i:j], string(s[j])) {
    // 遇到重复的
    if max < j-i {
    max = j-i
    }
    i++
    continue
    }
    j++
    }
    if max < j-i {
    return j-i
    }
    return max
    }

最长回文子串

  • 题目
  • 中心扩展法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 使用滑动窗口
    func longestPalindrome(s string) string {
    s = strings.Replace(s, "", "|", -1)
    retStr := ""
    length := len(s)

    for i:=0; i<length; i++ {
    left := i
    right := i
    for left-1>=0 && right+1<length {
    if s[left-1] != s[right+1] {
    break
    }
    left--
    right++
    }
    if len(retStr) < (right-left+1) {
    retStr = s[left:right+1]
    }
    }
    return strings.Replace(retStr, "|", "", -1)
    }

整数反转

  • 题目
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 这一题其实不难,主要为下一题作准备
    func reverse(x int) ( num int) {
    for x != 0 {
    num = num*10 + x%10
    x = x / 10
    }
    // 使用 math 包中定义好的最大最小值
    if num > math.MaxInt32 || num < math.MinInt32 {
    return 0
    }
    return
    }

回文数

  • 题目
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    # 判断一个数是不是回文数,可以先将其反转,然后在判断与原来的数是否相等
    func isPalindrome(x int) bool {
    if x < 0 {
    return false
    }

    reverseX := reverse(x)
    if reverseX == x {
    return true
    }
    return false
    }

    func reverse(x int) ( num int) {
    for x != 0 {
    num = num*10 + x%10
    x = x / 10
    }
    // 使用 math 包中定义好的最大最小值
    if num > math.MaxInt32 || num < math.MinInt32 {
    return 0
    }
    return
    }

三数之和

  • [题目](https://leetcode-cn.com/problems/3sum/)
  • 思路(双指针法思路)
    解题思路
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #include <iostream>
    #include <vector>
    #include <map>

    using namespace std;

    class Solution {
    public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ret;

    int size = nums.size();
    if (size < 3) {
    return ret;
    }

    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size()-2; ++i) {
    int r1 = i+1;
    int r2 = size-1;
    // 最小的数大于0
    if (nums[i] > 0) {
    continue;
    }

    if ( i != 0 && nums[i]==nums[i-1]) {
    continue;
    }

    while(r1 < r2) {
    int sum = nums[i] + nums[r1] + nums[r2];
    if (sum>0) {
    r2 = moveR2(nums, r2);
    } else if (sum<0) {
    r1 = moveR1(nums, r1);
    } else {
    ret.push_back(vector<int>{nums[i], nums[r1], nums[r2]});
    r1 = moveR1(nums, r1);
    r2 = moveR2(nums, r2);
    }
    }
    }
    return ret;
    }

    int moveR1(vector<int>& nums, int r1){
    int temp = nums[r1];
    r1++;
    while (r1 < nums.size()) {
    if (nums[r1] != temp) {
    break;
    }
    r1++;
    }
    return r1;
    }

    int moveR2(vector<int>& nums, int r2){
    int temp = nums[r2];
    r2--;
    while (r2 >= 0) {
    if (nums[r2] != temp) {
    break;
    }
    r2--;
    }
    return r2;
    }
    };


    int main() {
    vector<int> test = {-2,0,0,2,2};
    Solution s;
    auto result = s.threeSum(test);

    for (auto i : result){
    cout<< i[0] << i[1] << i[2] << endl;
    }
    }

最接近的三数之和

  • [题目](https://leetcode-cn.com/problems/3sum-closest/)
  • 思路(双指针法思路)
    • 这个题目和上个题目类似,都是先固定一个参数,再通过两个指针收尾移动的方法来确定
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      class Solution {
      public:
      int threeSumClosest(vector<int>& nums, int target) {
      sort(nums.begin(), nums.end());
      int size = nums.size();

      if (size < 3) {
      return 0;
      }

      int nearest = nums[0] + nums[1] + nums[size-1];
      int difference = abs(nums[0] + nums[1] + nums[size-1] - target);

      for (int i = 0; i < size-2; ++i) {
      int r1 = i+1;
      int r2 = size-1;

      int roundNearest = nums[i] + nums[r1] + nums[r2];
      int roundDifference = abs(nums[i] + nums[r1] + nums[r2] - target);

      while(r1 < r2) {

      int sum = nums[i] + nums[r1] + nums[r2];
      if (abs(sum-target) < roundDifference) {
      roundDifference = abs(sum-target);
      roundNearest = sum;
      }


      if (sum < target) {
      r1++;
      } else if (sum > target){
      r2--;
      } else {
      return target;
      }
      }

      if (difference > roundDifference) {
      nearest = roundNearest;
      difference = roundDifference;
      }
      }
      return nearest;
      }
      };

欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 qinhan_shu@163.com

文章标题:Leetcode 编程笔记

本文作者:QinHan

发布时间:2019-10-15, 08:24:17

最后更新:2020-02-20, 05:42:12

原始链接:https://qinhan.site/2019/10/15/leetcode/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏