算法练习——搜索插入位置

2021年1月27日每日算法练习35. 搜索插入位置,这道题给出了一个排序数组和一个目标元素,需要返回将这个目标元素插入到排序数组的合适位置,那么很简单就可以得到当目标元素小于等于数组元素时就要插入,否则就是最大的那个数,应该放到数组的最后面,即array.length位置上。代码如下:

1
2
3
4
5
6
7
8
9
10
class Solution {
public int searchInsert(int[] nums, int target) {
for(int i = 0; i < nums.length; i++) {
if(nums[i] >= target) {
return i;
}
}
return nums.length;
}
}

第二道练习为38. 外观数列,这道题在题目上已经提醒了使用递归,每一次的返回值都是描述上一个返回值的读法,具体读法在题目上已经给出,因此我们只需要递归调用这个方法,并在n == 1的时候返回1,然后开始对返回的数字字符串进行描述,由于其只对连续的数字放在一起读几个x,因此循环遍历这个字符数组,当这个字符与pre指向的数组不一致的时候组合成nx字符串,其中n = i - pre,当遍历到最后一个字符的时候,需要对也进行操作,因此需要循环数组长度+1次操作。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public String countAndSay(int n) {
if (n == 1) return "1";
String s = countAndSay(n - 1);
char[] chars = s.toCharArray();
// 描述 n - 1 的字符串
StringBuilder builder = new StringBuilder();
int pre = 0;
for (int i = 0; i <= chars.length; i++) {
if (i == chars.length || chars[i] != chars[pre]) {
builder.append(i - pre).append(chars[pre]);
pre = i;
}
}
return builder.toString();
}
}