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"
给定一个序号,返回该序号的规律字符串。
规律:
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;
};
输入一个32 位的整数[−2^31, 2^31 − 1], 输出它的反转后的值,如果溢出范围,则输出 0.
注意判断是否溢出。
使用 limit.h
中的 INT_MIN
INT_MAX
常量判断是否溢出。
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.
#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;
}
查找有序数组中目标值的索引:遍历排序好后的数组,找到值就返回下标;找不到但当前元素大于目标,则返回当前位置作为插入点。一般用二分查找可更快。
数数和说数(Count and Say):从第一个字符串“1”开始,依次根据上一个字符串描述其内容。例如“1”描述为“11”(一个1),“11”描述为“21”(两个1)等。代码实现需要循环生成每步结果。
反转整数:输入32位整数,输出其反转后的整数值。如果反转后溢出(超出32位带符号整数范围),则返回0。实现时要严格判断溢出。