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 语言实现。
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
给定一个序号,返回该序号的规律字符串。
规律:
11
21
,因为是 2 个 1.这里,我想的有点复杂了,所以时间和空间复杂度很高。
首先,他是从第一个开始到第 n 个的循环,每次算出上一个的结果。
n == 1, res = "1"
从第二个开始,每次循环中,提取出当前的 res 再来一个循环,记录 res 中前一个数字和当前遍历到的数字是否相同,bPostion == j ? count ++
。如果不相同,则把当前的记录的 count
和 bPostion
合并为字符串,push 到一个 临时数组中,当最外层循环结束后,把临时数组中的每一个字符串合并入 res,并且清空临时数组。对其他变量进行初始化。进行下一次循环。
使用坑爹的 JS 实现。
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.
注意判断是否溢出。
c
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
常量判断是否溢出。