阿料

阿料 查看完整档案

西安编辑  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑

一个平凡的coder

个人动态

阿料 发布了文章 · 2月23日

19. 删除链表的倒数第 N 个结点(LeetCode)——C语言及JS实现

一、C语言实现

1. 先获取链表长度,再从正向遍历

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
// 比较朴素的算法
// 先求出链表长度,然后根据长度求出要删除的元素正向的位置
// 最后遍历到该元素前一元素进行删除操作

struct ListNode *removeNthFromEnd(struct ListNode *head, int n)
{
  int len = 0;
  struct ListNode *origin = head; 
  // 计算链表的长度
  while (head)
  {
    len++;
    head = head -> next;
  }
  // 将head重新指向头结点
  head = origin;
  // 计算是正向第几个节点
  int count = len - n;
  // 如果是正向第一个结点,则头结点被删除,只需要直接返回头结点的next即可
  if (count == 0) {
    return head -> next;
  } 
  // 如果不是正向第一个结点(即结点),则直接遍历到该结点的前一个结点
  for (int i = 0; i < count - 1; i++) {
    head = head -> next;
  }
  // 将该节点删除,然后返回头结点的指针
  head -> next = head -> next -> next;
  return origin;
}

2. 双指针法,只需要遍历一次

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//  双指针法,移动first指针使其到的链表末端,同时移动second指针
//  使其指向最终要删除的节点的前一个节点,此时即可删除节点并返回头结点
//  只需一轮循环即可完成
struct ListNode *removeNthFromEnd(struct ListNode *head, int n)
{
  // 创建一个哑结点,并将其指向头结点
  struct ListNode dumpy = {0, head};
  // 将first指针指向head头指针
  struct ListNode *first = head;
  // 将second指针指向哑结点,此处dumpy是结构体,因此需要取地址
  struct ListNode *second = &dumpy;
  for (int i = 0; i < n; i++)
  {
    first = first->next;
  }
  while (first)
  {
    first = first->next;
    second = second->next;
  }
  second->next = second->next->next;
  // first second和head都是结构体指针,因此可以使用 -> 访问成员
  // dumpy是结构体,可以直接用点号访问
  return dumpy.next;
}

二、JS实现

1. 先获取链表长度,再从正向遍历

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
// 比较朴素的算法
// 先求出链表长度,然后根据长度求出要删除的元素正向的位置
// 最后遍历到该元素前一元素进行删除操作
const removeNthFromEnd = function (head, n) {
  const origin = head
  if (!head) {
    return null
  }
  let count = 1
  while (head.next) {
    count++
    head = head.next
  }
  head = origin
  if (count <= n) {
    return origin.next
  } else {
    // 倒数第n个数,就是正数第count - n + 1个数,那么,只需要遍历到此数的前一个数,即可
    // 前一个数则是第count - n个数,从第一个数开始遍历,只需遍历count - n - 1次就可到达此数
    const index = count - n - 1
    for (let i = 0; i < index; i++) {
      head = head.next
    }
    head.next = head.next.next
  }
  return origin
}

2. 双指针法,只需要遍历一次

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */

//  双指针法,移动first指针使其到的链表末端,同时移动second指针
//  使其指向最终要删除的节点的前一个节点,此时即可删除节点并返回头结点
//  只需一轮循环即可完成
const removeNthFromEnd = function (head, n) {
  // 创建一个哑结点,并将它指向头结点
  const dumpy = new ListNode(0, head)
  // 将第二个指针指向哑结点,第一个指针指向头结点
  let second = dumpy
  let first = head
  // 将第一个指针往前移动n个位置
  for (let i = 0; i < n; i++) {
    first = first.next
  }
  // 移动第一个指针直到链表结尾,同时移动第二个指针
  while (first) {
    first = first.next
    second = second.next
  }
  // 此时第二个指针指向的是倒数第n个节点的前一个节点
  // 将倒数第n个节点删除即可
  second.next = second.next.next
  // 返回头结点,使用head会出错,为什么呢?因为如果要删除的节点是头结点,那么头结点被删除后,
  // 哑结点直接指向第二个结点,而head还是指向头结点,因此会报错。
  // 所以此时要么返回head.next,要么返回dumpy.next。
  // 而head.next的返回需要判断second.next是不是指向头结点
  // 而dumpy.next则直接使用
  return dumpy.next
}

三、算法时间及空间复杂度

1. 链表长度法的时间及空间复杂度

  • 时间复杂度:O(L),其中L是链表的长度。
  • 空间复杂度:O(1)。

2. 双指针法

  • 时间复杂度:O(L),其中L是链表的长度。
  • 空间复杂度:O(1)。
查看原文

赞 0 收藏 0 评论 0

阿料 发布了文章 · 2月23日

18. 四数之和(LeetCode)——C语言及JS

一、C语言实现

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int cmp(const void *a, const void *b)
{
  return *((int *)a) - *((int *)b);
}

int **fourSum(int *nums, int numsSize, int target, int *returnSize, int **returnColumnSizes)
{
  if (numsSize < 4)
  {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    return NULL;
  }
  // 先对数组进行排序
  qsort(nums, numsSize, sizeof(int), cmp);
  // 初始化*returnSize
  *returnSize = 0;
  // 分配存储四元组的数组
  int **returnArr = (int **)malloc(sizeof(int *) * (numsSize - 2) * (numsSize - 2));
  *returnColumnSizes = (int *)malloc(sizeof(int) * (numsSize - 2) * (numsSize - 2));
  // 开始进入循环
  // 由于进行了剪枝操作,因此,要用i < numsSize - 3作为终止循环的条件
  // 否则会导致数组访问越界
  for (int i = 0; i < numsSize - 3; i++)
  {
    // 剪枝操作
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
    {
      break;
    }
    if (nums[i] + nums[numsSize - 3] + nums[numsSize - 2] + nums[numsSize - 1] < target)
    {
      continue;
    }
    // 首元素去重
    if (i > 0 && nums[i] == nums[i - 1])
    {
      continue;
    }
    // 由于进行了剪枝操作,因此,要用j < numsSize - 2作为终止循环的条件
    // 否则会导致数组访问越界
    for (int j = i + 1; j < numsSize - 2; j++)
    {
      // 剪枝操作
      if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
      {
        break;
      }
      if (nums[i] + nums[j] + nums[numsSize - 2] + nums[numsSize - 1] < target)
      {
        continue;
      }
      // 第二个元素去重
      if (j > i + 1 && nums[j] == nums[j - 1])
      {
        continue;
      }
      int head = j + 1;
      int tail = numsSize - 1;
      while (head < tail)
      {
        // 左指针去重
        if (head > j + 1 && nums[head] == nums[head - 1])
        {
          head++;
          continue;
        }
        // 右指针去重
        if (tail < numsSize - 1 && nums[tail] == nums[tail + 1])
        {
          tail--;
          continue;
        }
        if (nums[i] + nums[j] + nums[head] + nums[tail] == target)
        {
          returnArr[*returnSize] = (int *)malloc(sizeof(int) * 4);
          returnArr[*returnSize][0] = nums[i];
          returnArr[*returnSize][1] = nums[j];
          returnArr[*returnSize][2] = nums[head];
          returnArr[*returnSize][3] = nums[tail];
          (*returnColumnSizes)[*returnSize] = 4;
          (*returnSize) += 1;
          head++;
          tail--;
        }
        else if (nums[i] + nums[j] + nums[head] + nums[tail] > target)
        {
          tail--;
        }
        else
        {
          head++;
        }
      }
    }
  }
  return returnArr;
}

二、JS实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
const fourSum = function (nums, target) {
  const len = nums.length
  if (len < 4) {
    return []
  }
  nums.sort((x, y) => { return x - y })
  const results = []
  for (let i = 0; i < len; i++) {
    if (i > 0 && nums[i - 1] === nums[i]) {
      continue
    }
    // 剪枝操作
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
      break
    }
    // 剪枝操作
    if (nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {
      continue
    }
    for (let j = i + 1; j < len; j++) {
      if (j > i + 1 && nums[j - 1] === nums[j]) {
        continue
      }
      // 剪枝操作
      if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
        break
      }
      // 剪枝操作
      if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {
        continue
      }
      let head = j + 1
      let tail = len - 1
      while (head < tail) {
        if (head > j + 1 && nums[head - 1] === nums[head]) {
          head++
          continue
        }
        if (tail < len - 1 && nums[tail + 1] === nums[tail]) {
          tail--
          continue
        }
        if (nums[i] + nums[j] + nums[head] + nums[tail] === target) {
          // 存储符合条件的四元组到结果数组
          results.push([nums[i], nums[j], nums[head], nums[tail]])
          // 将头指针右移,尾指针左移
          head++
          tail--
        } else if (nums[i] + nums[j] + nums[head] + nums[tail] > target) {
          tail--
        } else {
          head++
        }
      }
    }
  }
  return results
}
  • 时间复杂度:O(n^3),其中n是数组的长度。排序的时间复杂度是O(nlogn),枚举四元组的时间复杂度是 O(n^3),因此总时间复杂度为 O(n^3+nlogn)==O(n^3)。
  • 空间复杂度:O(logn),其中n是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组nums,实际情况中不一定允许,因此也可以看成使用了一个额外的数组存储了数组nums 的副本并排序,空间复杂度为 O(n)。
查看原文

赞 0 收藏 0 评论 0

阿料 发布了文章 · 2月23日

17. 电话号码的字母组合(LeetCode)——C语言和JS

一、C语言实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char *letterNumber[] = {"",
                        "",
                        "abc",
                        "def",
                        "ghi",
                        "jkl",
                        "mno",
                        "pqrs",
                        "tuv",
                        "wxyz"};
int len;
char *digitsBak;

char **res;
int resSize;

char *resItem;
int resItemSize;

void backTrack(int index)
{
  if (index == len)
  {
    // 给tmp分配空间
    char *tmp = malloc(sizeof(char) * (resItemSize + 1));
    memcpy(tmp, resItem, sizeof(char) * (resItemSize + 1));
    res[resSize++] = tmp;
  } else {
    // 取输入的字符串中的数字字符,将其转换为数字,作为下标获取数字对应的字符串
    int digitIndex = digitsBak[index] - '0';
    char *letters = letterNumber[digitIndex];
    int lettersLen = strlen(letters);
    for (int i = 0; i < lettersLen; i++)
    {
      resItem[resItemSize++] = letters[i];
      resItem[resItemSize] = 0;
      backTrack(index + 1);
      resItem[--resItemSize] = 0;
    }
  }
}

char **letterCombinations(char *digits, int *returnSize)
{
  len = strlen(digits);
  resSize = 0;
  resItemSize = 0;
  if (len == 0)
  {
    *returnSize = 0;
    return NULL;
  }
  int count = 1;
  digitsBak = digits; 
  for (int i = 0; i < len; i++)
  {
    count *= 4;
  }
  res = (char **)malloc(count * sizeof(char *));
  resItem = (char *)malloc(sizeof(char) * (len + 1));
  backTrack(0);
  *returnSize = resSize;
  return res;
}

二、JS实现

/**
 * @param {string} digits
 * @return {string[]}
 */
const letterCombinations = function (digits) {
  const len = typeof digits === 'string' && digits.length
  if (len === 0) {
    return []
  }
  // 声明一个对象,存储数字与字符串的对应关系
  const letterNumber = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' }
  const res = []
  const arr = []
  // 将与输入数字对应的字符串存储到一个数组中备用
  for (const digit of digits) {
    arr.push(letterNumber[digit])
  }
  const backTrack = function (str, index) {
    // 递归出口,当深度与输入的数字个数一致时,将获取的str存储,并不再递归调用
    // 此时程序进入下一次循环
    if (index === len) {
      res.push(str)
    } else {
      for (const letter of arr[index]) {
        // 此处必须用一个新的变量传递到递归调用的函数中
        // 不能直接修改str的值,当下面的递归结束,回溯到此循环时,
        // str需要的是本层循环开始时的初始值,因此不能直接str += letter
        const tmp = str + letter
        backTrack(tmp, index + 1)
      }
    }
  }
  backTrack('', 0)
  return res
}

时间复杂度:O(3^m4^n),其中m是输入中对应3个字母的数字个数(包括数字 22、33、44、55、66、88),n是输入中对应4个字母的数字个数(包括数字 77、99),m+n是输入数字的总个数。当输入包含m个对应3个字母的数字和n个对应4个字母的数字时,不同的字母组合一共有 3^m 4^n种,需要遍历每一种字母组合。

空间复杂度:O(m+n),其中m是输入中对应3个字母的数字个数,n是输入中对应4个字母的数字个数,m+n是输入数字的总个数。除了返回值以外,空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数,哈希表的大小与输入无关,可以看成常数,递归调用层数最大为 m+n。

查看原文

赞 0 收藏 0 评论 0

阿料 关注了用户 · 2月8日

Linus脱袜子 @qiuqi_turing

硕士研究生在读。

关注 20

阿料 关注了用户 · 2月7日

前端小智 @minnanitkong

我不是什么大牛,我其实想做的就是一个传播者。内容可能过于基础,但对于刚入门的人来说或许是一个窗口,一个解惑之窗。我要先坚持分享20年,大家来一起见证吧。

关注 9755

阿料 发布了文章 · 2月4日

16. 最接近是三数之和(LeetCode)——C语言及JS

一、双指针法——C语言实现

/**
 * 最接近的三数和 
 * LeetCode第16题
 * author: aliao   language: C
*/

#include <stdio.h>
#include <stdlib.h>

int compare (const void *a, const void *b) 
{
  return (*(int *)a) - (*(int *)b);
}
int threeSumClosest(int *nums, int numsSize, int target)
{
  // 先给数组升序排序
  qsort(nums, numsSize, sizeof(int), compare); 
  // 定义返回值
  int best;
  for (int i = 0; i < numsSize; i++)
  {
    if (i > 0 && nums[i] == nums[i - 1]) {
      continue;
    }
    int head = i + 1;
    int tail = numsSize - 1;
    while (head < tail)
    {
      // 求和
      int sum = nums[i] + nums[head] + nums[tail];
      // 将第一个三数之和存为最接近解best
      if (i == 0 && head == 1 && tail == numsSize - 1)
      {
        best = sum;
      }
      // 更新三元素之和
      if (abs(sum - target) < abs(best - target)) {
        best = sum; 
      }
      if (sum < target) {
        // 左指针左移
        head++;
        // 左指针去重
        while (nums[head] == nums[head - 1])
        {
          head++;
        }
      } else if (sum > target) {
        // 右指针左移
        tail--;
        // 右指针去重
        while (nums[tail] == nums[tail + 1])
        {
          tail--;
        }
      } else {
        return target;
      }
    }
  }
  return best;
}

int main (void)  {
  int nums[] = {-1, 2, 1, -4};
  int numsSize = 4;
  int target = 1;
  printf("%d\n", threeSumClosest(nums, numsSize, target));
}

image.png

二、双指针法——js实现

    /**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const threeSumClosest = function (nums, target) {
  const len = nums.length
  nums.sort((a, b) => { return a - b })
  let best = Infinity
  for (let i = 0; i < len; i++) {
    // 去除首层循环重复的元素
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue
    }
    let tail = len - 1
    let head = i + 1
    while (head < tail) {
      // 求和
      const sum = nums[i] + nums[head] + nums[tail]
      // 更新三元素之和
      if (Math.abs(sum - target) < Math.abs(best - target)) {
        best = sum
      }
      if (sum > target) {
        // 右指针左移1
        tail--
        // 左指针去重
        while (nums[tail] === nums[tail + 1]) {
          tail--
        }
      } else if (sum < target) {
        // 左指针右移
        head++
        // 右指针去重
        while (nums[head] === nums[head - 1]) {
          head++
        }
      } else {
        // sum与target相等时,直接返回target
        return target
      }
    }
  }
  return best
}
console.log(threeSumClosest([-1, 2, 1, -4], 1))

image.png

  • 时间复杂度:O(n^2),其中n是数组nums 的长度。我们首先需要O(nlogn)的时间对数组进行排序,随后在枚举的过程中,使用一重循环O(n)枚举a,双指针O(n)枚举b和c,故一共是O(n^2)。
  • 空间复杂度:O(logn)。排序需要使用O(logn)的空间。然而我们修改了输入的数组nums,在实际情况下不一定允许,因此最坏情况就是使用了一个额外的数组存储了nums的副本并进行排序,此时使用数组的空间复杂度为O(n)。排序空间复杂度为O(logn),额外的新数组空间复杂度是O(n),因此综合起来就是O(logn)。
查看原文

赞 0 收藏 0 评论 0

阿料 发布了文章 · 2月2日

15. 三数之和(leetcode)——C语言

一、双指针法——C语言实现

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

int compare(const void *a, const void *b)
{
  return *((int *)a) - *((int *)b);
}

int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes)
{
  // 数组长度小于3则直接返回空数组
  if (numsSize < 3)
  {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    return NULL;
  }
  // 先对数组进行排序,升序排列,qsort不返回任何值
  qsort(nums, numsSize, sizeof(int), compare);
  *returnSize = 0;
  // 分配存储空间
  int **returnArr = (int **)malloc(sizeof(int *) * (numsSize - 2) * (numsSize - 2));
  *returnColumnSizes = (int *)malloc(sizeof(int) * (numsSize - 2) * (numsSize - 2));
  // 开始二重循环,遍历数组nums
  for (int i = 0; i < numsSize; i++)
  {
    // 如果元素大于0,则其后的元素也大于0,那么三数之和肯定大于0
    // 所以到此时就可以直接退出遍历了
    if (nums[i] > 0)
    {
      break;
    }
    // 去除外层循环的重复值
    if (i > 0 && nums[i] == nums[i - 1])
    {
      continue;
    }
    // 记录右指针初始下标
    int third = numsSize - 1;
    // 记录外层循环下标对应的值,即三元组的第一个元素
    int oneNum = nums[i];
    for (int j = i + 1; j < numsSize; j++)
    {
      // 去除左指针指向的重复值
      if (j > i + 1 && nums[j] == nums[j - 1])
      {
        continue;
      }
      // 去除右指针指向的重复的值
      while (j < third && nums[j] + nums[third] > -oneNum)
      {
        third--;
      }
      // 左右指针重合时,退出内层循环
      if (j == third)
      {
        break;
      }
      // 将满足条件的三元组保存到结果数组
      if (nums[j] + nums[third] == -oneNum)
      {
        returnArr[*returnSize] = (int *)malloc(sizeof(int) * 3);
        returnArr[*returnSize][0] = oneNum;
        returnArr[*returnSize][1] = nums[j];
        returnArr[*returnSize][2] = nums[third];
        (*returnColumnSizes)[*returnSize] = 3;
        *returnSize += 1;
      }
    }
  }
  return returnArr;
}
int main(void) {
  int nums[] = {-1, 0, 1, 2, -1, -4};
  int numsSize = 6;
  int returnSize;
  int *returnColumnSizes = NULL;
  int **returnArr = threeSum(nums, numsSize, &returnSize, &returnColumnSizes);
  for (int i = 0; i < returnSize; i++) {
    printf("%d %d %d\n", returnArr[i][0], returnArr[i][1], returnArr[i][2]);
  }
  return 0;
}

image.png

二、双指针法——JavaScript实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = function (nums) {
  const len = nums.length
  // 数组长度小于3则直接返回空数组
  if (len < 3) {
    return []
  }
  // 对数组进行排序
  nums.sort(function (a, b) { return a - b })
  // 定义一个空数组作为返回数组
  const returnArr = []
  for (let i = 0; i < len; i++) {
    // 如果元素大于0,则其后的元素也大于0,那么三数之和肯定大于0
    // 所以到此时就可以直接退出遍历了
    if (nums[i] > 0) {
      break
    }
    // 去除外层循环的重复值
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue
    }
    // 记录右指针初始下标
    let third = len - 1
    // 记录外层循环下标对应的值,即三元组的第一个元素
    const oneNum = nums[i]
    for (let j = i + 1; j < len; j++) {
      // 去除左指针指向的重复值
      if (j > i + 1 && nums[j] === nums[j - 1]) {
        continue
      }
      // 去除右指针指向的重复的值
      while (j < third && nums[j] + nums[third] > -oneNum) {
        third--
      }
      // 左右指针重合时,退出内层循环
      if (j === third) {
        break
      }
      // 将满足条件的三元组push到结果数组
      if (nums[j] + nums[third] === -oneNum) {
        returnArr.push([oneNum, nums[j], nums[third]])
      }
    }
  }
  return returnArr
}

image.png

  • 时间复杂度:O(N^2),其中 NN 是数组nums的长度。
  • 空间复杂度:O(logN)。我们忽略存储答案的空间,额外的排序的空间复杂度为O(logN)。然而我们修改了输入的数组nums,在实际情况下不一定允许,因此也可以看成使用了一个额外的数组存储了nums 的副本并进行排序,空间复杂度为 O(N)。
查看原文

赞 0 收藏 0 评论 0

阿料 发布了文章 · 1月22日

14.最长公共前缀(LeetCode)——C语言

方法一、横向遍历法

// 横向遍历法
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int getCommonPrefix(char *prev, char *next) {
  int len = strlen(prev) < strlen(next) ? strlen(prev) : strlen(next);
  int k = 0;
  while (k < len) {
    if (prev[k] != next[k]) {
      return k;
    }
    k++;
  }
  return k;
}

char *longestCommonPrefix(char **strs, int strsSize) {
  if (strsSize <= 0) {
    return "";
  }
  int commonPrefixLen = strlen(strs[0]);
  char *commonPrefix = (char *)malloc((commonPrefixLen + 1) * sizeof(char));
  strncpy(commonPrefix, *strs, commonPrefixLen);
  // 给字符串结尾加上空字符,否则会数组访问出错,导致堆溢出
  // 这个问题找了好久,最后发现strncpy只是复制字符,并不会自动在字符串结尾添加空字符
  *(commonPrefix + commonPrefixLen) = '\0';
  for (int i = 1; i < strsSize; i++)
  {
    int len = getCommonPrefix(commonPrefix, *(strs + i));
    // 将字符串初始化为全空,此后复制字符不用担心结尾添加空字符的问题
    memset(commonPrefix, '\0', commonPrefixLen + 1);
    if (len <= 0) {
      return commonPrefix;
    }
    strncpy(commonPrefix, *(strs + i), len);
  }
  return commonPrefix;
}

int main(void) {
  char *strs[] = {"flower", "flow", "flight"};
  printf("%s\n", longestCommonPrefix(strs, 3));
}

image.png

  • 时间复杂度:O(mn),其中m是字符串数组中的字符串的平均长度,n 是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次。
  • 空间复杂度:O(1)。使用的额外空间复杂度为常数。

方法二、纵向遍历法

// 纵向遍历法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *longestCommonPrefix(char **strs, int strsSize)
{
  if (strsSize <= 0) {
    return "";
  }
  int len = strlen(strs[0]);
  char *commonPrefix = (char *)malloc((len + 1) * sizeof(char));
  memset(commonPrefix, '\0', len + 1);
  for (int i = 0; i < len; i++)
  {
    for (int j = 0; j < strsSize - 1; j++) {
      // i == strlen(strs[j])用来防止数组访问越界
      if (i == strlen(strs[j]) || strs[j][i] != strs[j + 1][i])
      {
        strncpy(commonPrefix, strs[0], i);
        return commonPrefix;
      }
    }
  }
  return strs[0];
}

int main(void) {
  char *strs[] = {"flower","flow","flight"};
  printf("%s\n", longestCommonPrefix(strs, 3));
}

image.png

  • 时间复杂度:O(mn),m是字符串数组中的字符串的平均长度,n是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次。
  • 空间复杂度:O(1)。使用的额外空间复杂度为常数。

方法三、分治法

// 分治法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *commonPrefix(char *leftStr, char *rightStr)
{
  int len = strlen(leftStr) < strlen(rightStr) ? strlen(leftStr) : strlen(rightStr);
  char *str = (char *)malloc((len + 1) * sizeof(char));
  memset(str, '\0', len + 1);
  for (int i = 0; i < len; i++)
  {
    if (leftStr[i] != rightStr[i])
    {
      strncpy(str, leftStr, i);
      return str;
    }
  }
  strncpy(str, leftStr, len);
  return str;
}

char *recurse(char **strs, int start, int end)
{
  
  if (start == end)
  {
    return strs[start];
  }
  int mid = (end - start) / 2 + start;
  char *leftStr = recurse(strs, start, mid);
  char *rightStr = recurse(strs, mid + 1, end);
  
  return commonPrefix(leftStr, rightStr);
}

char *longestCommonPrefix(char **strs, int strsSize)
{
  if (strsSize <= 0)
  {
    return "";
  }
  return recurse(strs, 0, strsSize - 1);
}

int main(void)
{
  char *strs[] = {"dog", "racecar", "car"};
  printf("%s\n", longestCommonPrefix(strs, 3));
}

image.png

  • 时间复杂度:O(mn),其中m是字符串数组中的字符串的平均长度,n是字符串的数量。时间复杂度的递推式是T(n)=2⋅T(2n)+O(m),通过计算可得T(n)=O(mn)。
  • 空间复杂度:O(mlogn),其中m是字符串数组中的字符串的平均长度,n是字符串的数量。空间复杂度主要取决于递归调用的层数,层数最大为logn,每层需要m的空间存储返回结果。

方法四、二分查找

// 二分查找
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int getMinLen(char **strs, int strsSize) 
{
  int minLen = strlen(strs[0]);
  for (int i = 1; i < strsSize; i++) {
    if (strlen(strs[i]) < minLen)
    {
      minLen = strlen(strs[i]);
    }
  }
  return minLen;
}

int isCommonPrefix(char **strs, int strsSize, int mid) {
  for (int i = 0; i < strsSize - 1; i++) {
    if (strncmp(strs[i], strs[i + 1], mid) != 0) {
      return 0;
    }
  }
  return 1;
}

char *longestCommonPrefix(char **strs, int strsSize)
{
  if (strsSize <= 0) {
    return "";
  }
  int minLen = getMinLen(strs, strsSize);
  char *commonPrefix = (char *)malloc((minLen + 1) * sizeof(char)); 
  memset(commonPrefix, '\0', minLen + 1);
  int left = 1;
  int right = minLen;
  while (left <= right) {
    int mid = (left + right) / 2;
    if (isCommonPrefix(strs, strsSize, mid))
    {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  strncpy(commonPrefix, strs[0], right);
  return commonPrefix;
}

int main(void)
{
  char *strs[] = {"flower", "flow", "flight"};
  printf("%s\n", longestCommonPrefix(strs, 3));
}

image.png

  • 时间复杂度:O(mnlogm),其中m是字符串数组中的字符串的最小长度,n是字符串的数量。二分查找的迭代执行次数是O(logm),每次迭代最多需要比较mn个字符,因此总时间复杂度是O(mnlogm)。
  • 空间复杂度:O(1)。使用的额外空间复杂度为常数。
查看原文

赞 0 收藏 0 评论 0

阿料 发布了文章 · 1月20日

几天一个Linux命令——wc

wc: 打印文件的行数、字数(Word数)和字节数。

word指的是被空白字符分隔的长度不为0的字符序列。

具体用法:
wc [option] [file]

常用的[option]:

  • -c: 打印字节数
  • -m: 打印字符数
  • -l: 打印行数
  • -w: 打印字数
  • -L: 打印最长的行的长度(以字符个数计数)

[file]可以是一个或者多个文件名,也可以是-(即标准输入)

不加任何option时,默认显示的是行数、字数及字节数,如果是多个文件,则会进行汇总,在最后一行显示总的行数、总的字数及总的字节数。

查看原文

赞 0 收藏 0 评论 0

阿料 发布了文章 · 1月20日

13. 罗马数字转整数(leetcode)——C语言

思路:
遍历字符串,比较当前罗马字符与后一个罗马字符对应的十进制数字的大小。
如果大于,则将该数字累加到num,如果小于,则求出他们的差值,并将其累加到num。
遍历结束,将num返回即可。

第一版、没有使用哈希表,使用数组模拟

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int getIndex(char *str, char c) 
{
  int k = 0;
  while (str[k] != '\0')
  {
    if (str[k] == c) 
    {
      return k;
    }
    k++;
  }
  return -1;
}

int romanToInt(char *str)
{
  int numArr[] = {1000, 500, 100, 50, 10, 5, 1};
  char roman[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
  int k = 0;
  int num = 0;
  while (str[k] != '\0') {
    int indexCurt = getIndex(roman, str[k]);
    // 判断下一个字符是否是空字符,防止字符串越界
    // 如果是空字符,就将其下标与前一个字符的下标置为一样
    int indexNext = str[k + 1] != '\0' ? getIndex(roman, str[k + 1]) : indexCurt;
    if (numArr[indexCurt] < numArr[indexNext])
    {
      num += numArr[indexNext] - numArr[indexCurt];
      k += 2;
    } else {
      num += numArr[indexCurt];
      k++;
    }
  }
  return num;
}

int main(void) {
  char *str = "MCMXCIV";
  printf("%d\n", romanToInt(str));
}

image.png

时间复杂度: O(1)
空间复杂度: O(1)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int getValue(char c)
{
  switch (c)
  {
  case 'M':
    return 1000;
    break;
  case 'D':
    return 500;
    break;
  case 'C':
    return 100;
    break;
  case 'L':
    return 50;
    break;
  case 'X':
    return 10;
    break;
  case 'V':
    return 5;
    break;
  case 'I':
    return 1;
    break;
  default:
    return -1;
    break;
  }
}

int romanToInt(char *str)
{
  int k = 0;
  int num = 0;
  while (str[k] != '\0')
  {
    int numCurt = getValue(str[k]);
    // 判断下一个字符是否是空字符,防止字符串越界
    // 如果是空字符,就将其下标与前一个字符的下标置为一样
    int numNext = str[k + 1] != '\0' ? getValue(str[k + 1]) : numCurt;
    if (numCurt < numNext)
    {
      num += numNext - numCurt;
      k += 2;
    }
    else
    {
      num += numCurt;
      k++;
    }
  }
  return num;
}

int main(void)
{
  char *str = "MCMXCIV";
  printf("%d\n", romanToInt(str));
}

方法二、将罗马数字与十进制数字作为键值对存储在哈希表中,然后其他步骤和方法一一样。

js实现

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let intRoman = {
        "M": 1000,
        "D": 500,
        "C": 100,
        "L": 50,
        "X": 10,
        "V": 5,
        "I": 1
    };
    let len = s.length;
    let i = 0; 
    let num = 0;
    while (i < len) {
        let numCurt = intRoman[s[i]]
        let numNext = i + 1 < len ? intRoman[s[i + 1]] : intRoman[s[i]]
        if (numCurt < numNext) {
            num += numNext - numCurt;
            i += 2;
        } else {
            num += numCurt;
            i++;
        }
    }
    return num;
};

image.png

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 0 次点赞
  • 获得 0 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 0 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2020-12-11
个人主页被 922 人浏览