刷题目标：
刷题计划：
- 前TOP100，学习java解题，每天2道题，先刷2遍，和小姐妹互相监督（自己刚搭建好的博客）。
- 数组-> 链表-> 哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构，从简单刷起，再慢慢做中等、困难题目。
- 尽量不要用暴力！！！
内容：
数组
1. 两数之和
class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) return new int[0];
// 数据预处理
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// O(n)
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
// O(n)
int x = nums[i];
// 哈希查找 - O(1)
if (map.containsKey(target - x)) {
int index = map.get(target - x);
// i 和 index 不是同一个元素，同一个元素不能使用两次
if (i != index) return new int[]{
i, index};
}
}
return new int[0];
}
}
53. 最大子序和
解题思路
对于含有正数的序列而言，最大子序列和肯定是正数，所以头尾肯定都是正数；
我们可以从第一个正数开始算起，每往后加一个数便更新一次和的最大值；
当前子序列和为负数时，则表明此前序列无法为后面提供最大子序列和，因此必须重新确定序列首项。
class Solution {
public int maxSubArray(int[] nums) {
int sum=0;
int ans=nums[0];
for(int i=0;i<nums.length;i++){
if(sum>0){
sum+=nums[i];
}else{
sum=nums[i];//记录前一个数
}
if(ans<=sum){
ans=sum;
}
}
return ans;
}
}
121. 买卖股票的最佳时机
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];//历史最低点
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
169. 多数元素
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
283. 移动零
先统计非零元素个数，再将非零的紧凑的重新分配到数组，剩下的直接赋值0。
class Solution {
public void moveZeroes(int[] nums) {
int cnt=0;//记录非零元素个数
for(int i=0;i<nums.length;i++){
if(nums[i]!=0) cnt++;
}
int index=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=0) {
nums[index]=nums[i];
index++;
}
}
for(int i=index;i<nums.length;i++){
nums[i]=0;
}
}
}
448. 找到所有数组中消失的数字
遍历数组，将每个数字交换到它理应出现的位置上，下面情况不用换：
当前数字本就出现在理应的位置上，跳过，不用换。
当前数字理应出现的位置上，已经存在当前数字，跳过，不用换。
再次遍历，如果当前位置没对应正确的数。
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
//利用数组与索引建立关系
List<Integer> res = new ArrayList<>();
int num;//记录索引下的值
for(int i = 0 ; i < nums.length ; i++){
num = Math.abs(nums[i])-1;
if(nums[num] > 0){
//索引下的值在理应位置是一个其余大于0的值，变为负数
nums[num] *= -1;
}
}
for(int i=0 ; i < nums.length ; i++){
if(nums[i] > 0){
//若最后在理应位置不是负数，说明这个数在其他位置重复，理应的数又没出现
res.add(i+1);//不存在的存入
}
}
return res;
}
}
总结：
- 复习了java一些语法，忘性太快了。
- 在做题时，总是用暴力简单思维，以后多学习题解中动规，dp，容器巧妙解决的思路吧。
- 自律不行他律！
转载：https://blog.csdn.net/Action_now_zj/article/details/116274899
查看评论