首页 > 代码库 > 学习真的使我快乐~

学习真的使我快乐~

2024-08-25 03:49:58   218人阅读

（1）Remove Element

技术分享

正常思路代码如下：

技术分享 
 1 public class Solution {
 2     public int removeElement(int[] nums, int val) {
 3         int count = 0;
 4         for (int i = 0; i < nums.length; i++) {
 5             if(nums[i] != val) {
 6                 nums[count++] = nums[i];
 7             }
 8         }
 9         return count;
10     }
11 }
View Code

学习使我快乐的来源，最优解题思路真的好机智！！！代码如下：

技术分享 
 1 public class Solution {
 2     public int removeElement(int[] nums, int val) {
 3         int i = 0;
 4         int index = nums.length - 1;
 5         while (i <= index ) {
 6             if(nums[i] == val) {
 7                 nums[i] = nums[index--];
 8             }
 9             else {
10                 i++;
11             }
12         }
13         return index + 1;
14     }
15 }
View Code

解题思路:从第一个元素开始，如果该元素与指定元素相同，则替换为最后一个元素（为防止[3,2,2,3]这种情况出现错误，不能用for循坏每次i都加一），然后最后一个元素位置减1 ，如果该元素与指定元素不同，就加1。

（2）Majority Element

技术分享

最优解题思路如下：用一个变量记录主要元素，初始化为第一个元素，一个变量记录出现次数，初始化为1，遍历数组中的元素，与当前记录的主要元素相同的话，次数就加1，不同就减1，如果次数减到0，那就将主要元素换成新遍历到的元素，这样遍历完一轮得到最后记录的主要元素，就是我们要的结果。因为主要元素出现的次数大于n/2，所以可以想见最后留下来的一定会是主要元素。别的元素即使记录过也会因为次数归零抛弃掉的。这个方法只需要遍历一次数组就可以了，时间复杂度为0(n),空间复杂度为0(1).

代码如下：

技术分享 
 1 public class Solution {
 2     public int majorityElement(int[] nums) {
 3         int count = 0;
 4         int majorty = -1;
 5         for (int i = 0; i < nums.length; i++) {
 6             if (count == 0) {
 7                 majorty = nums[i];
 8                 count = 1;
 9             }
10             else if (majorty == nums[i]) {
11                 count++;
12             }
13             else {
14                 count--;
15             }
16         }
17         return majorty;
18     }
19 }
View Code

（3）Best Time to Buy and Sell Stock

 技术分享

题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。 如果只允许进行一次交易，也就是说只允许买一支股票并卖掉，求最大的收益。

解题思路：动态规划法。从前向后遍历数组，记录当前出现过的最低价格，作为买入价格，并计算以当天价格出售的收益，作为可能的最大收益，整个遍历过程中，出现过的最大收益就是所求。

代码：

技术分享 
 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         if (prices.length < 2) {
 4             return 0;
 5         }
 6         int maxProfit = 0;
 7         int curMin = prices[0];
 8         for (int i = 1; i < prices.length; i++) {
 9             curMin = Math.min(curMin, prices[i]);
10             maxProfit = Math.max(maxProfit, prices[i] - curMin);
11         }
12         return maxProfit;
13     }
14 }
View Code

时间复杂度为O(n)时间，空间复杂度为O(1)。

最优解思路相通，代码略有差别，如下：

技术分享 
 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         if (prices.length == 0 || prices == null) {
 4             return 0;
 5         }
 6         int maxProfit = 0;
 7         int curMin = Integer.MAX_VALUE;
 8        // int curMin = prices[0];(也可)
 9         for (int i : prices) {
10             curMin = i > curMin ? curMin : i;
11             maxProfit = maxProfit > (i - curMin) ? maxProfit : i - curMin;
12         }
13         return maxProfit;
14     }
15 }
View Code

使用了foreach循环遍历。

 

学习真的使我快乐~


联系
我们