文章目录
面试经典150题【11-20】
388.O(1) 时间插入、删除和获取随机元素
用一个哈希表和一个变长数组组成一个新的数据类型。
获取随机元素的话，直接random一个数然后从数组里取就行。
插入和删除的话，先判断有没有这个数，哈希表里存的是{ 数据：在变长数组中的索引}
插入的话直接插变长数组末尾，然后再在哈希表里插
删除的话，把最后一个元素放到要删除的位置，然后删除最后一个元素即可。哈希里的也要set一下然后删一下。
238.除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
以【1,2，3,4，5】来举例，对于3来说，可以让前面×1×后面
创建一个全为1的数组来代替1
双指针遍历两次，i指针代表前缀和，J指针代表后缀和
class Solution {
public int[] productExceptSelf(int[] nums) {
int n=nums.length;
int[] ans=new int[n];
Arrays.fill(ans,1);
int beforesum=1,aftersum=1;
for(int i=0,j=n-1;i<n;i++,j--){
ans[i] *=beforesum;
ans[j] *=aftersum;
beforesum *=nums[i];
aftersum *=nums[j];
}
return ans;
}
}
134加油站
先建立一个差分数组，从头开始累加，累加失败后从失败数的后一位累加。累加N次成功即可。
时间复杂度O（2N）
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n=gas.length;
int []diff=new int[n];
for(int i=0;i<n;i++){
diff[i]=gas[i]-cost[i];
}
int ans=0,i=0;
while(i<n){
int sum=0,cnt=0;
//cnt计数，cnt循环一圈应该是n
while(cnt<n){
sum+=diff[(i+cnt)%n];
if(sum<0){
break;
}
cnt++;
}
if(cnt==n){
return i;
}else{
//跳到负数之后的一位
i+=cnt+1;
}
}
return -1;
}
}
135.分发糖果
先从左往右遍历一遍，再从右往左遍历（赋值的时候应该赋值Max）
class Solution {
public int candy(int[] ratings) {
int []ans=new int[ratings.length];
ans[0]=1;
for(int i=1;i<ratings.length;i++){
if(ratings[i]>ratings[i-1]){
ans[i]=ans[i-1]+1;
}else{
ans[i]=1;
}
}
for(int i=ratings.length-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
ans[i]=Math.max(ans[i],ans[i+1]+1);
}
}
int sum=0;
for(int i=0;i<ratings.length;i++){
sum+=ans[i];
}
return sum;
}
}
或者用left[] 和right[] 两个数组来分别遍历两次
然后ans[]= Max(left,right)
这样也是满足从左到右和从右到左两个规则的最小值。
42. 接雨水
方法一：先算一个leftMax数组，再算一个rightMax数组。然后每个格子的存储水的量就等于
min(leftMax,rightMax) - height
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
如果是想调整为0（1）的空间复杂度的话,也是记录leftMax和rightMax两个变量。
当左边最高比右边最高低的时候，利用漏桶效应，是左边最高减去本地的height。
右边同理。
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
13.罗马数字
IV是15，所以是5-1，则后一个比前一个数字大，则前一个数字是减法。
否则就是加法，最后一个数字肯定是加法。
class Solution {
public int romanToInt(String s) {
int sum = 0;
int preNum = symbolValues.get(s.charAt(0));
for(int i = 1;i < s.length(); i ++) {
int num = symbolValues.get(s.charAt(i));
if(preNum < num) {
sum -= preNum;
} else {
sum += preNum;
}
preNum = num;
}
sum += preNum;
return sum;
}
Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {
{
put('I', 1);
put('V', 5);
put('X', 10);
put('L', 50);
put('C', 100);
put('D', 500);
put('M', 1000);
}};
}
12.整数 转 罗马数字
硬编码没意义
58.最后一个单词的长度
没意思，注意一下最后可能有空格，先写个while循环把空格排除掉就行
14.最长公共前缀
无论是什么算法，肯定是O（MN）的复杂度。
依次遍历所有的字符串，选择求取公共字符串函数（目前的公共字符串，下一个普通字符串）即可
class Solution {
public String longestCommonPrefix(String[] strs) {
// 如果字符串数组为空，直接返回空字符串
if (strs == null || strs.length == 0) {
return "";
}
// 初始公共前缀为第一个字符串
String commonPrefix = strs[0];
// 遍历剩余的字符串
for (int i = 1; i < strs.length; i++) {
// 比较当前字符串与当前最长公共前缀，更新最长公共前缀
commonPrefix = getCommonPrefix(commonPrefix, strs[i]);
// 如果最长公共前缀已经为空，直接返回
if (commonPrefix.equals("")) {
return "";
}
}
// 返回最长公共前缀
return commonPrefix;
}
// 辅助函数，用于获取两个字符串的公共前缀
private String getCommonPrefix(String str1, String str2) {
int index = 0;
// 找到两个字符串的公共前缀的长度
while (index < str1.length() && index < str2.length() && str1.charAt(index) == str2.charAt(index)) {
index++;
}
// 返回公共前缀
return str1.substring(0, index);
}
}
151.反转字符串中的单词
先把前后的空格删了，再从后到前提取每一个单词，再拼接所有的单词。
“ hello world ”–>“world hello”
class Solution {
public static String reverseWords(String s) {
StringBuilder ans = new StringBuilder();
s = s.trim(); // 删除首尾的空格
int j = s.length() - 1, i = j; // 开始的时候ij两个指针都在最右边
while (i >= 0) {
while (i >= 0 && s.charAt(i) != ' ')
i--; // 搜索单词的最前面
ans.append(s.substring(i + 1, j + 1) + " "); // 把新单词添加上
while (i >= 0 && s.charAt(i) == ' ')
i--; // 搜索单词的最后面
j = i;
}
return ans.toString().trim();
}
}
