文章目录
构建乘积数组
题目
描述
给定一个数组 A[0,1,…,n-1] ,请构建一个数组 B[0,1,…,n-1] ,其中 B 的元素 B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1](除 A[i] 以外的全部元素的的乘积)。程序中不能使用除法。(注意:规定 B[0] = A[1] * A[2] * … * A[n-1],B[n-1] = A[0] * A[1] * … * A[n-2])
对于 A 长度为 1 的情况,B 无意义,故而无法构建,用例中不包括这种情况。
数据范围:1≤n≤10 ,数组中元素满足 ∣val∣≤10
示例1
输入:
[1,2,3,4,5]
返回值:
[120,60,40,30,24]
示例2
输入:
[100,50]
返回值:
[50,100]
牛客题目链接
思路
采用双重for循环,外循环i倒序遍历数组,内循环j顺序遍历数组,内循环中当i!=j时,乘上当前A[j](除 A[i] 以外的全部元素的的乘积),同时每次内循环遍历一遍后,需要将临时数据重置,结果在外循环中存储;
代码实现
public int[] multiply (int[] A) {
if(A == null || A.length < 2){
return new int[0];
}
int[] res = new int[A.length];
int sum = 0;
for(int i = A.length - 1;i>=0;i--){
sum = 1;
for(int j = 0; j < A.length;j++){
if(i != j){
sum *= A[j];
}
}
res[i] = sum;
}
return res;
}
第一个只出现一次的字符
题目
描述
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)
数据范围:0≤n≤10000,且字符串只有字母组成。
要求:空间复杂度 O(n),时间复杂度 O(n)
示例1
输入:
“google”
返回值:
4
示例2
输入:
“aa”
返回值:
-1
牛客题目链接
思路
采用HashMap + 两次for循环处理,第一次for循环记录每个字符出现的次数,第二次for循环找出第一个出现一次的字符。
代码实现
public int FirstNotRepeatingChar (String str) {
if(str == null){
return -1;
}
HashMap<Character,Integer> hash = new HashMap();
for(int i = 0; i<str.length();i++){
char a = str.charAt(i);
if(hash.containsKey(a)){
hash.put(a,2);//没必要统计字符出现的次数,不要设置不为1即可。
}else{
hash.put(a,1);
}
}
for(int i = 0; i < str.length();i++){
char a = str.charAt(i);
if(hash.get(a) == 1){
return i;
}
}
return -1;
}
替换空格
题目
描述
请实现一个函数,将一个字符串s中的每个空格替换成“%20”。
例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
数据范围:0≤len(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。
示例1
输入:
“We Are Happy”
返回值:
“We%20Are%20Happy”
示例2
输入:
" "
返回值:
“%20”
牛客题目链接
思路
直接for循环判断拼接;
代码实现
public String replaceSpace (String s) {
if(s == null || s.length() == 0){
return s;
}
StringBuilder res = new StringBuilder();
for(int i = 0; i < s.length();i++){
char c = s.charAt(i);
if(' ' == c){
res.append("%20");
}else{
res.append(c);
}
}
return res.toString();
}
调整数组顺序使奇数位于偶数前面(一)
题目
描述
输入一个长度为 n 整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前面部分,所有的偶数位于数组的后面部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
数据范围:0≤n≤5000,数组中每个数的值 0≤val≤10000
要求:时间复杂度 O(n),空间复杂度 O(n)
进阶:时间复杂度 O(n/2),空间复杂度 O(1)
示例1
输入:
[1,2,3,4]
返回值:
[1,3,2,4]
示例2
输入:
[2,4,6,5,7]
返回值:
[5,7,2,4,6]
思路
采用双指针思路,一个指针用于记录奇数从前往后遍历,则结果数组前部分记录的都是奇数,一个指针用于记录偶数从后往前遍历,则结果数组后部分记录的都是偶数,直到都遍历完整个数组为止;
代码实现
public int[] reOrderArray(int[] array) {
if (array == null || array.length == 0) {
return array;
}
int[] res = new int[array.length];
int l = 0;
int li = l;
int r = array.length - 1;
int ri = r;
while (l < array.length && r >= 0) {
if (array[l] % 2 == 1) {
//当前是奇数
res[li++] = array[l];
}
l++;
if (array[r] % 2 == 0) {
//当前是偶数
res[ri--] = array[r];
}
r--;
}
return res;
}
数组中出现次数超过一半的数字
题目
描述
给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。
数据范围:n≤50000,数组中元素的值 0≤val≤10000
要求:空间复杂度:O(1),时间复杂度 O(n)
输入描述:
保证数组输入非空,且保证有解
示例1
输入:
[1,2,3,2,2,2,5,4,2]
返回值:
2
示例2
输入:
[3,3,3,3,2,2,2]
返回值:
牛客题目链接
思路
使用哈希表统计数组中数字出现的次数,然后判断即可;
代码实现
public int MoreThanHalfNum_Solution (int[] numbers) {
HashMap<Integer,Integer> hash = new HashMap();
for(int num : numbers){
if(hash.containsKey(num)){
hash.put(num,hash.get(num)+1);
} else{
hash.put(num,1);
}
if(hash.get(num) > numbers.length /2){
return num;
}
}
return numbers[0];
}
整数中1出现的次数(从1到n整数中1出现的次数)
题目
描述
输入一个整数 n ,求 1~n 这 n 个整数的十进制表示中 1 出现的次数
例如, 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次
注意:11 这种情况算两次
数据范围: 1≤n≤30000
进阶:空间复杂度 O(1) ,时间复杂度 O(lognn)
示例1
输入:
13
返回值:
6
示例2
输入:
0
返回值:
0
思路
直接遍历每一个数字的每一位是否为1进行累加;
代码实现
public int NumberOf1Between1AndN_Solution(int n) {
int res = 0;
for(int i = 1; i <= n;i++){
for(int j = i;j>0;j=j/10){
if(j % 10 == 1){
res++;
}
}
}
return res;
}
把数组排成最小的数
题目
描述
输入一个非负整数数组numbers,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
例如输入数组[3,32,321],则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大,所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
数据范围:
0<=len(numbers)<=100
示例1
输入:
[11,3]
返回值:
“113”
示例2
输入:
[]
返回值:
“”
牛客题目链接
思路
利用贪心算法,每次拼接字符串的时候判断是否为最小字典序,则最终拼接结果一定也为最小值;
代码实现
public String PrintMinNumber (int[] numbers) {
if(numbers == null || numbers.length == 0){
return "";
}
String[] strs = new String[numbers.length];
for(int i =0 ;i<numbers.length;i++){
strs[i] = numbers[i] + "";
}
//利用字典序对strs数组进行排序
Arrays.sort(strs,(Comparator<String>) (o1, o2) -> (o1 + o2).compareTo(o2+o1));
StringBuilder res = new StringBuilder();
for(String str:strs ){
res.append(str);
}
return res.toString();
}
丑数
题目
描述
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围:0≤n≤2000
要求:空间复杂度 O(n) , 时间复杂度 O(n)
示例1
输入:
7
返回值:
8
思路
从题目可以知道,对应丑数的定义,当a为丑数时,则2a,3a,5a都是丑数,则我们利用小顶堆性质,依次计算n范围内的所有丑数放入小顶堆中,然后取出n对应的丑数即可;
代码实现
public int GetUglyNumber_Solution (int index) {
if(index == 0){
return 0;
}
PriorityQueue<Long> pq = new PriorityQueue();
HashMap<Long,Integer> hashMap = new HashMap();
int[] specials = new int[]{
2,3,5};
pq.offer(1L);
hashMap.put(1L,1);
long res = 0;
for(int i = 0;i<index;i++){
res = pq.poll();
for(int j = 0 ;j<specials.length;j++){
long num = res*specials[j];
if(!hashMap.containsKey(num)){
pq.offer(num);
hashMap.put(num,1);
}
}
}
return (int)res;
}
和为S的连续正数序列
题目
描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
数据范围:0<n≤100
进阶:时间复杂度 O(n)
返回值描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序
示例1
输入:
9
返回值:
[[2,3,4],[4,5]]
示例2
输入:
0
返回值:
[]
牛客题目链接
思路
采用穷举的思路,不断找到满足之和 == sum的数字添加到集合中,又因为两个大于sum一半的数肯定大于sum,所以只需要穷举sum一半的数即可;
代码实现
public ArrayList<ArrayList<Integer>> FindContinuousSequence (int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList();
int len = sum /2 ;
for(int i = 1;i <= len;i++){
int num = 0;
int j = i;
ArrayList<Integer> array = new ArrayList();
while(num < sum){
num += j;
array.add(j);
j++;
}
if(num == sum){
res.add(array);
}
}
return res;
}
和为S的两个数字
题目
描述
输入一个升序数组 array 和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,返回任意一组即可,如果无法找出这样的数字,返回一个空数组即可。
数据范围: 0≤len(array)≤10 1≤array[i]≤10
示例1
输入:
[1,2,4,7,11,15],15
返回值:
[4,11]
说明:
返回[4,11]或者[11,4]都是可以的
示例2
输入:
[1,5,11],10
返回值:
[]
说明:
不存在,返回空数组
牛客题目链接
思路
使用哈希表处理,遍历数组,如果temp = sum-array[i]在hashmap中能否查找到,则说明temp之前已存储到hashmap中,则可以直接返回{temp,array[i]},否则没找到则只需要讲当前array[i]存储到hashmap中即可;
代码实现
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList();
if(array == null || array.length < 2){
return res;
}
HashMap<Integer,Integer> hash = new HashMap();
for(int i = 0;i< array.length;i++){
int temp = sum - array[i];
if(hash.containsKey(temp)){
res.add(temp);
res.add(array[i]);
return res;
}else{
hash.put(array[i],i);
}
}
return res;
}
左旋转字符串
题目
描述
汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S ,请你把其循环左移 K 位后的序列输出。例如,字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果,即 “XYZdefabc”
数据范围:输入的字符串长度满足 0≤len≤100 , 0≤n≤100
进阶:空间复杂度 O(n) ,时间复杂度 O(n)
示例1
输入:
“abcXYZdef”,3
返回值:
“XYZdefabc”
示例2
输入:
“aab”,10
返回值:
“aba”
思路
根据题目描述,我们可以得知,只需要对字符串分割反向拼接即可,如 S = ”abcXYZdef” , 要求输出循环左移 3 位,实际上就是将S分割成"abc"和"XYZdef"后,然后重新拼接成"XYZdefabc"即可,只是需要注意输入的参数n可能大于字符串的长度,由于当n == 字符串的长度时,相当于没旋转,因此我们需要对n进行取余操作即可;
代码实现
public String LeftRotateString (String str, int n) {
if(str == null || str.length() == 0){
return str;
}
int len = n % str.length();
String first = str.substring(0,len);
String end = str.substring(len);
return end + first;
}
孩子们的游戏(圆圈中最后剩下的数)
题目
描述
每年六一儿童节,牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中,有个游戏是这样的:首先,让 n 个小朋友们围成一个大圈,小朋友们的编号是0~n-1。然后,随机指定一个数 m ,让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0… m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客礼品,请你试着想下,哪个小朋友会得到这份礼品呢?
数据范围:1≤n≤5000,1≤m≤10000
要求:空间复杂度 O(1),时间复杂度 O(n)
示例1
输入:
5,3
返回值:
3
示例2
输入:
2,3
返回值:
1
说明:
有2个小朋友编号为0,1,第一次报数报到3的是0号小朋友,0号小朋友出圈,1号小朋友得到礼物
牛客题目链接
思路
采用递归思路,求(n,m)的结果,可以先求(n-1,m)的结果 ,若(n-1,m)结果为x,则(n,m)的结果即为(x+m)%n,而中止条件也很明确,即当n=1时,x=0,由此可以使用递归解决;
代码实现
public int LastRemaining_Solution (int n, int m) {
if(n == 0 || m == 0){
return -1;
}
return fuction(n,m);
}
private int fuction(int n,int m){
if(n == 1){
return 0;
}
int x = fuction(n-1,m);
return (x+m)%n;
}