查找一个值的索引

题目描述

1Given 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.
2
3You may assume no duplicates in the array.
4
5Example 1:
6
7Input: [1,3,5,6], 5
8Output: 2
9Example 2:
10
11Input: [1,3,5,6], 2
12Output: 1
13Example 3:
14
15Input: [1,3,5,6], 7
16Output: 4
17Example 4:
18
19Input: [1,3,5,6], 0
20Output: 0
Copy

简要说明

给定一个排序过后的数组和一个目标值,查找给定目标值在数组中的索引值,若不存在这个值,则返回如果该值存在时的索引值。(注意是,排序过的数组)
思想:
因为是排序过的数组,所以只要一次遍历就可以了。
如果找到该值,则返回当前下标;如果该值在比较时,数组中的值已经大于目标值,则只可能在当前位置上可以按照当前的顺序插入该值,所以也应该返回当前下标。

实现

算法比较简单,故使用速度更快的 C 语言实现。
1int searchInsert(int* nums, int numsSize, int target){
2    for(int i = 0; i < numsSize; i++) {
3        if(*(nums+i) == target)
4            return i;
5        else if(*(nums + i) > target)
6            return i;
7        else {
8            continue;
9        }
10    }
11   return numsSize;
12}
Copy
运行时间: 4ms。内存使用: 7.3 MB

数数和说数

题目描述

1The count-and-say sequence is the sequence of integers with the first five terms as following:
2
31.     1
42.     11
53.     21
64.     1211
75.     111221
81 is read off as "one 1" or 11.
911 is read off as "two 1s" or 21.
1021 is read off as "one 2, then one 1" or 1211.
11
12Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.
13
14Note: Each term of the sequence of integers will be represented as a string.
15
16 
17
18Example 1:
19
20Input: 1
21Output: "1"
22Example 2:
23
24Input: 4
25Output: "1211"
Copy

简要描述

给定一个序号,返回该序号的规律字符串。
规律:
  1. 第一个永远是 "1"
  2. 第二个是第一个的描述后的数字,例如第一个的"1", 可以这么说,一个 1,所以一个表示成 1, 1 表示成 1,所以结果是11
  3. 那么第三个就是在第二个的基础上,也就是21,因为是 2 个 1.

思想

这里,我想的有点复杂了,所以时间和空间复杂度很高。
首先,他是从第一个开始到第 n 个的循环,每次算出上一个的结果。
n == 1, res = "1"
从第二个开始,每次循环中,提取出当前的 res 再来一个循环,记录 res 中前一个数字和当前遍历到的数字是否相同,bPostion == j ? count ++。如果不相同,则把当前的记录的 countbPostion 合并为字符串,push 到一个 临时数组中,当最外层循环结束后,把临时数组中的每一个字符串合并入 res,并且清空临时数组。对其他变量进行初始化。进行下一次循环。

实现

使用坑爹的 JS 实现。
1var countAndSay = function(n) {
2  let res = "1"
3  let bPostion = ''
4  let count = 0
5  let temp = []
6  for (let i = 2; i <= n ; i++ ){
7    rt = res + '!'
8    for(let j of rt) {
9      if ((bPostion || j) == j) {
10        count++;
11      }
12      else {
13        temp.push(String(count || 1) + (bPostion || j))
14        count = 1
15      }
16      bPostion = j
17    }
18    if(temp.length) {
19      res = ''
20      for (let i of temp){
21        res += i
22      }
23    }
24    bPostion = ''
25    temp = []
26    count = 0
27  }
28
29  return res;
30};
Copy

反转整数

题目描述

1Given a 32-bit signed integer, reverse digits of an integer.
2
3Example 1:
4
5Input: 123
6Output: 321
7Example 2:
8
9Input: -123
10Output: -321
11Example 3:
12
13Input: 120
14Output: 21
15Note:
16Assume 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.
Copy

简要描述

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

思路

注意判断是否溢出。

实现

1#include <limits.h>
2int reverse(int x){
3    long long temp, res = 0;
4    while(x) {
5        temp = x % 10;
6        x /= 10;
7        res = (res * 10) + temp;
8    }
9    return (res < INT_MIN || res > INT_MAX) ? 0 : res;
10}
Copy
使用 limit.h 中的 INT_MIN INT_MAX常量判断是否溢出。

亲亲留个评论再走呗

正在加载评论区...