首页 > 其他分享 >23-05-20 刷题

23-05-20 刷题

时间:2023-05-20 23:13:43浏览次数:50  
标签:count use 20 05 int nums element array 刷题

练习英文描述算法

88. Merge Sorted Array - LeetCode 【easy】

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // two pointers, initially i,j points to the last number of the array (m-1, n-1)
        // use k to record the position of merged array, initially set to m+n-1
        // then compare i,j's element, put the larger one in the merged array,
        // and decrease the pointers of larger element index, and merged index
        // until either i or j reaches -1, if i = -1, copy remaining nums2 to merged array
        // if j = -1, no need to copy nums1 as it already in the right pos
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

LC 26. Remove Duplicates from Sorted Array - LeetCode 【easy】

class Solution {
    public int removeDuplicates(int[] nums) {
        // use two pointers i,j. use i to traverse the numbers, use j to track the
        // uniq number pos, initially set i = 1, j = 1.
        // when we found a uniq number, put it to j's position and move j forward
        int j = 1;
        for(int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                nums[++j] = nums[i];
            }
        }
        return j + 1;
    }
}

LC80. Remove Duplicates from Sorted Array II - LeetCode【Mid】

class Solution {
    public int removeDuplicates(int[] A) {
        // two pointers, use j to track the kept number's pos,
        // use i to enumerate each num from 2nd elem, init j to 0
        // if A[i] != A[j-1] || A[i] != A[j-2], kept A[i], copy A[i] to A[j] and move j forward
        if (A.length <= 2) return A.length;
        int j = 2;
        for (int i = 2; i < A.length; i++) {
            if (A[i] != A[j - 1] || A[i] != A[j - 2]) {
                A[j++] = A[i];
            }
        }
        return j;
    }
}

学习英文官方的描述:

Intuition 1: The input array is already sorted and hence, all the duplicates appear next to each other. The problem statement mentions that we are not allowed to use any additional space and we have to modify the array in-place. The easiest approach for in-place modifications would be to get rid of all the unwanted duplicates. For every number in the array, if we detect > 2 duplicates, we simply remove them from the list of elements and we do this for all the elements in the array.

Intuition 2

The second approach is really inspired by the fact that the problem statement asks us to return the new length of the array from the function. If all we had to do was remove elements, the function would not really ask us to return the updated length. However, in our scenario, this is really an indication that we don't need to actually remove elements from the array. Instead, we can do something better and simply overwrite the duplicate elements that are unwanted.

We won't be able to achieve this using a single pointer. We will be using a two-pointer approach where one pointer iterates over the original set of elements and another one that keeps track of the next "empty" location in the array or the next location that can be overwritten in the array.

Algorithm

  1. We define two pointers, i and j for our algorithm. The pointer i iterates of the array processing one element at a time and j keeps track of the next location in the array where we can overwrite an element.
  2. We also keep a variable count which keeps track of the count of a particular element in the array. Note that the minimum count would always be 1.
  3. We start with index 1 and process one element at a time in the array.
  4. If we find that the current element is the same as the previous element i.e. nums[i] == nums[i - 1], then we increment the count. If the value of count > 2, then we have encountered an unwanted duplicate element. In this case, we simply move forward i.e. we increment i but not j.
  5. However, if the count is <= 2, then we can move the element from index i to index j.
  6. If we encounter that the current element is not the same as the previous element i.e. nums[i] != nums[i - 1], then it means we have a new element at hand and so accordingly, we update count = 1 and also move this element to index j.
  7. It goes without saying that whenever we copy a new element to nums[j], we have to update the value of j as well since j always points to the location where the next element can be copied to in the array.

这个解法更容易懂一点,使用count来统计数字出现的数量,多用了一个变量而已。

class Solution {
    
    public int removeDuplicates(int[] nums) {        
        // Initialize the counter and the second pointer.
        int j = 1, count = 1;
        
        // Start from the second element of the array and process
        // elements one by one.
        for (int i = 1; i < nums.length; i++) {
            // If the current element is a duplicate, increment the count.
            if (nums[i] == nums[i - 1]) {
                count++;
            } else {
                // Reset the count since we encountered a different element
                // than the previous one.
                count = 1;
            }
            
            // For a count <= 2, we copy the element over thus
            // overwriting the element at index "j" in the array
            if (count <= 2) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }
}

另外一个精简的代码:

class Solution {
    public int removeDuplicates(int[] A) {
        // two pointers, use j to track the kept number's pos,
        // use i to enumerate each num from 2nd elem, init j to 0
        // if i <= 1 or A[i] != A[j-2], kept A[i], copy A[i] to A[j] and move j forward
        int j = 1;
        for (int i = 1; i < A.length; i++) {
            if (i <= 1 || A[i] != A[j - 2]) {
                A[j++] = A[i];
            }
        }
        return j;
    }
}

LC 169. Majority Element - LeetCode 【easy】

class Solution {
    public int majorityElement(int[] A) {
        // use a voting alg, each element vote for itself.
        
        // keep track of candidate and its voting count.
        // iterate each elem, first if count is 0, set current elem as candidate
        // update count, if current num is same as candidate vote 1, other decrease 1
        int candidate = 0, count = 0;
        for(int num : A) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate ? 1 : -1);
        }
        return candidate;
    }
}

这里比较巧妙的是,遍历所有元素,初始化时,count = 0. 循环里先更新candidate,再更新count,这样把第一个人的投票算进去了。

练习刷题思路

LC15. 3Sum - LeetCode

思路:

  • 如果暴力来做的话,使用三个指针i,j,k分别去找每一组的三个数,然后判断是否是答案,如果是加到结果List,注意需要使用Set去重,时间是O(n^3). 空间复杂度是O(n)
  • 优化的做法,使用排序+双指针。可以优化一维的空间,而且排序,可以很方便的去重。
class Solution {
    public List<List<Integer>> threeSum(int[] A) {        
        int n = A.length;
        List<List<Integer>> ans = new ArrayList<>();
        
        Arrays.sort(A);
        for (int i = 0; i < n; i++) {
            if (i > 0 && A[i] == A[i-1]) { // avoid duplicate a
                continue;
            }
            // find b + c = -A[i]
            for(int j = i + 1, k = n - 1; j < k;) {
                if (j > i + 1 && A[j] == A[j-1]) { // avoid duplicate b
                    j++;
                    continue;
                }
                if (A[j] + A[k] > -A[i]) {
                    k--;
                } else if (A[j] + A[k] < -A[i]) {
                    j++;
                } else {
                    ans.add(Arrays.asList(A[i], A[j], A[k]));
                    j++;
                    k--;
                }
            }
        }
        return ans;
    }
}

最容易犯错的两个点:

  • 首先要对输入数组进行排序,容易丢
  • 其次,在最里面的循环中,避免第二个数重复的时候,使用了continue,却忘记更新j索引。

复杂度分析:

  • 时间:排序数组 O(nlogn),枚举a, b, c两层循环,O(n^2). 所以总的时间复杂度是 O(n^2)
  • 空间:没有使用额外空间,O(1)

标签:count,use,20,05,int,nums,element,array,刷题
From: https://www.cnblogs.com/xianzhon/p/17417887.html

相关文章

  • 2023.5.20——软件工程日报
    所花时间(包括上课):6h代码量(行):0行博客量(篇):1篇今天,上午参观君乐宝企业,下午学习。我了解到的知识点:1.了解了一些数据库的知识;2.了解了一些python的知识;3.了解了一些英语知识;5.了解了一些Javaweb的知识;4.了解了一些数学建模的知识;6.了解了一些计算机网络的知识;......
  • 520-5 翻倒数
    一、问题描述:我们看到,把数字0-9翻倒,有的数字就认不出来了,比如2、3、4、5、7;有的数字看上去没什么大的变化,比如0、1、8;还有的数字变成了另一个数,比如6变成9,9变成6。给定一堆数字,请你判别每个数有没有可能是另一个数字翻倒形成的。输入格式:输入在第一行中给出一个正整......
  • 520就这样了
    520-3不要怕,爱!!!古代少女有了心上人时,会悄悄折一条树枝,揪那枝上的叶子,揪一片叶子念一句“爱我”,再揪一片念一句“不爱我”……这样揪落最后一片叶子的时候,看看是停在“爱”还是“不爱”。本题就请你根据枝条上叶子的片数,告诉你的用户应该从“爱”还是“不爱”开始,最后一定停......
  • C/C++程序设计课设题[2023-05-20]
    C/C++程序设计课设题[2023-05-20]ATM仿真系统-薛景背单词-叶水仙-理科实验班电信优惠套餐推荐系统的设计与实现-朱立华-通信工程多媒体文件管理及检索系统-刘林峰-广播电视工程公交路线自动化选择系统实现-张勤-测控技术与仪器基于朋友圈的商品推荐-汪云云-自动化基于数据......
  • day75(2023.5.20)
    1.通过Cookie实现客户端与服务端会话的维持 运行结果: 2.Cookie总结3.HttpSession对象的特点 4.HttpSession对象的创建 运行结果: 5.HttpSession对象的使用 运行结果:  6.HttpSession的销毁方式 运行结果: 在IE浏览器中......
  • 5.20
    代码时间:2h代码量(行):3百行相关事项:今天再次进行web实验四,通过使用JavaMVC模式设计简单的数据库管理系统,巩固使用JDBC技术访问数据库的方法,学习使用Java语言对服务器端进行编程,深入理解MVC网站设计模式的基本概念和框架结构。已经成功完成实验。。。。 今天的学校人格外的少......
  • 今天520,来个烟花吧
    '''name:圣诞树+烟火author:Babysen''' importturtleastimportrandomimportthreadingimporttimeimporttkinterastkimportmathfrommathimportcos,sin,atan,sqrtimportnumpyasnp t.screensize(bg='black')#定义背景颜色 #心......
  • 5.20打卡
      3.程序流程图4.代码实现#include<bits/stdc++.h>usingnamespacestd;intmain(){intt,a[5];longintk,i;for(i=95860;;i++){for(t=0,k=100000;k>=10;t++){a[t]=(i%k)/(k/10);k/=10;......
  • CCPC2023 河南省赛
    和零时加的队友打了一下,计算几何摆了,最优化摆了,adhoc摆了。A.小水獭游河南枚举前缀,是\(O(|\Sigma|)\)的,然后判断一下是不是回文串即可。B.ArtforRest昨天才做过这个套路的加强版。显然只用判断类似\(\max(a,b)<\min(b+1,c)\)的条件。暴力枚举是调和级数的。E.矩阵......
  • 2023年上海驾考科目三考试流程 All In One
    2023年上海驾考科目三考试流程AllInOne科目三考试一次通过秘籍demos(......