LeetCode 刷题第一天

查找一个值的索引

题目描述

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

简要说明

给定一个排序过后的数组和一个目标值，查找给定目标值在数组中的索引值，若不存在这个值，则返回如果该值存在时的索引值。（注意是，排序过的数组）

思想：

因为是排序过的数组，所以只要一次遍历就可以了。

如果找到该值，则返回当前下标；如果该值在比较时，数组中的值已经大于目标值，则只可能在当前位置上可以按照当前的顺序插入该值，所以也应该返回当前下标。

实现

算法比较简单，故使用速度更快的 C 语言实现。

int searchInsert(int* nums, int numsSize, int target){
    for(int i = 0; i < numsSize; i++) {
        if(*(nums+i) == target)
            return i;
        else if(*(nums + i) > target)
            return i;
        else {
            continue;
        }
    }
   return numsSize;
}

运行时间： 4ms。内存使用： 7.3 MB

数数和说数

题目描述

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

 

Example 1:

Input: 1
Output: "1"
Example 2:

Input: 4
Output: "1211"

简要描述

给定一个序号，返回该序号的规律字符串。

规律：

第一个永远是 "1"
第二个是第一个的描述后的数字，例如第一个的"1", 可以这么说，一个 1，所以一个表示成 1, 1 表示成 1，所以结果是11
那么第三个就是在第二个的基础上，也就是21，因为是 2 个 1.

思想

这里，我想的有点复杂了，所以时间和空间复杂度很高。

首先，他是从第一个开始到第 n 个的循环，每次算出上一个的结果。

n == 1, res = "1"

从第二个开始，每次循环中，提取出当前的 res 再来一个循环，记录 res 中前一个数字和当前遍历到的数字是否相同，bPostion == j ? count ++。如果不相同，则把当前的记录的 count 和 bPostion 合并为字符串，push 到一个临时数组中，当最外层循环结束后，把临时数组中的每一个字符串合并入 res，并且清空临时数组。对其他变量进行初始化。进行下一次循环。

实现

使用坑爹的 JS 实现。

var countAndSay = function(n) {
  let res = "1"
  let bPostion = ''
  let count = 0
  let temp = []
  for (let i = 2; i <= n ; i++ ){
    rt = res + '!'
    for(let j of rt) {
      if ((bPostion || j) == j) {
        count++;
      }
      else {
        temp.push(String(count || 1) + (bPostion || j))
        count = 1
      }
      bPostion = j
    }
    if(temp.length) {
      res = ''
      for (let i of temp){
        res += i
      }
    }
    bPostion = ''
    temp = []
    count = 0
  }

  return res;
};

反转整数

题目描述

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321
Example 2:

Input: -123
Output: -321
Example 3:

Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

简要描述

输入一个32 位的整数[−2^31, 2^31 − 1], 输出它的反转后的值，如果溢出范围，则输出 0.

思路

注意判断是否溢出。

实现


#include <limits.h>
int reverse(int x){
    long long temp, res = 0;
    while(x) {
        temp = x % 10;
        x /= 10;
        res = (res * 10) + temp;
    }
    return (res < INT_MIN || res > INT_MAX) ? 0 : res;
}

使用 limit.h 中的 INT_MIN INT_MAX常量判断是否溢出。

查找一个值的索引

题目描述

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

简要说明

思想：

因为是排序过的数组，所以只要一次遍历就可以了。

实现

算法比较简单，故使用速度更快的 C 语言实现。

int searchInsert(int* nums, int numsSize, int target){
    for(int i = 0; i < numsSize; i++) {
        if(*(nums+i) == target)
            return i;
        else if(*(nums + i) > target)
            return i;
        else {
            continue;
        }
    }
   return numsSize;
}

运行时间： 4ms。内存使用： 7.3 MB

数数和说数

题目描述

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

 

Example 1:

Input: 1
Output: "1"
Example 2:

Input: 4
Output: "1211"

简要描述

给定一个序号，返回该序号的规律字符串。

规律：

第一个永远是 "1"
第二个是第一个的描述后的数字，例如第一个的"1", 可以这么说，一个 1，所以一个表示成 1, 1 表示成 1，所以结果是11
那么第三个就是在第二个的基础上，也就是21，因为是 2 个 1.

思想

这里，我想的有点复杂了，所以时间和空间复杂度很高。

首先，他是从第一个开始到第 n 个的循环，每次算出上一个的结果。

n == 1, res = "1"

实现

使用坑爹的 JS 实现。

var countAndSay = function(n) {
  let res = "1"
  let bPostion = ''
  let count = 0
  let temp = []
  for (let i = 2; i <= n ; i++ ){
    rt = res + '!'
    for(let j of rt) {
      if ((bPostion || j) == j) {
        count++;
      }
      else {
        temp.push(String(count || 1) + (bPostion || j))
        count = 1
      }
      bPostion = j
    }
    if(temp.length) {
      res = ''
      for (let i of temp){
        res += i
      }
    }
    bPostion = ''
    temp = []
    count = 0
  }

  return res;
};

反转整数

题目描述

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321
Example 2:

Input: -123
Output: -321
Example 3:

Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

简要描述

输入一个32 位的整数[−2^31, 2^31 − 1], 输出它的反转后的值，如果溢出范围，则输出 0.

思路

注意判断是否溢出。

实现


#include <limits.h>
int reverse(int x){
    long long temp, res = 0;
    while(x) {
        temp = x % 10;
        x /= 10;
        res = (res * 10) + temp;
    }
    return (res < INT_MIN || res > INT_MAX) ? 0 : res;
}

使用 limit.h 中的 INT_MIN INT_MAX常量判断是否溢出。