LeetCode初尝
387.First Unique Character in a String
Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.
example:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
给定一个字符串,从左到右找出整个字符串第一个没有重复的字符,返回下标,题目提示仅考虑全是小写字母的情况。
思路:因为只有小写字母组成的字符串,考虑用到数组配合下标的形式来记录字符出现的次数以及位置
定义一个长度为26的整数数组,下标表示字符,值表示出现的次数,若值为1,就返回当前下标为问题所要求的下标
public class Solution {
public int firstUniqChar(String s) {
int[] m = new int[26];
int length = s.length();
// 字符之间的减法是根据字符的ASCII码的值做减法
for(int i = 0; i < length; i++){
// 记录字符串每个位置在数组中的出现次数
m[s.charAt(i) - 'a']++;
}
for(int i = 0; i < length; i++){
if(m[s.charAt(i) - 'a'] == 1)
return i;
}
return -1;
}
}
390.Elimination Game
There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.
We keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Find the last number that remains starting with a list of length n.
example:
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6
给定一个整数n,生成一串从1到n的整数,第一次从左到右开始移除奇数位元素,然后第二次从右到左移除上一次剩下的元素奇数位元素,以此类推,直到最后剩下一个元素的时候返回
思路(参考):不同于一般的二分查找,这是隔了一位的移除法。使用标记头部的方式,每次移除元素的时候都重新标记一下头部,移除到最后的时候,只剩下一个元素,head也刚好标记到这个元素,返回即可
public int elimationEliment(int n) {
int remaining = n;
boolean left = true;
int head = 1;
int step = 1;
while(remaining > 1) {
// 从做到右清除或者剩余元素为奇数个时移动head
if(left || remaining % 2 ==1) {
head = head + step;
}
// 因为是隔位清除,所以step需要乘以2(见下面分析)
step = step * 2;
// 剩余的数的个数
remaining = remaining / 2;
// 清除开始方向
left = !left;
}
}
举个例子:n = 14
1,2,3,4,5,6,7,8,9,10,11,12,13,14
初始值:head=1,left=true,step=1,remaining=14;从左到右筛选后
2,4,6,8,10,12,14
第一次筛选后:head=2,left=false,step=2,remaining=7;从右到左再次筛选后
4,8,12
第二次筛选后:head=4,left=true,step=4,remaining=3;从做到右再次筛选后
8
第三次筛选后:head=8,left=false,step=8,remainging=1;此时remaining为1,返回的即筛选最后的结果。
感觉白白学了多年编程了,随便找两道题就很启发思维,能保持个习惯就好,这是非技术文,是学习笔记,自己写的代码就不贴了,逻辑很硬板,没有这么灵活。