专栏首页编程之禅算法训练营-第一周-数组链表

算法训练营-第一周-数组链表

一.时间复杂度&空间复杂度

常见的时间复杂度

  • 常量 O(1)
  • 对数 O(logn)
  • 线性 O(n)
  • 二维 O(n2)
  • 指数 O(2n)
  • 阶乘 O(n!)

常见的空间复杂度

  • 常量 O(1)
  • 线性 O(n)
  • 二维 O(n2)
  • 递归 O(n) n为递归深度

二.数组

定义

数组是相同变量组成的有序集合

图示

实战题目

283. 移动零

1.两次遍历 2.快慢指针

/*
    将数组中的0移动到最后,保持原来的非零数字的顺序。
        要求不能开辟新数组。
        方法一:
            两次遍历。第一次一边统计0的个数,一遍将非0数放在后面。index记录非0数索引位。
            第二次遍历将后面的数变为0。
            time:  O(n)
            space: O(1)
        方法二:背这个
            快慢指针。ab指针都从0出发,a先走,如果a不为0,就将ab交换。
            time:  O(n)
            space: O(1)
*/


// 方法1,两次遍历。
// class Solution {
//     public void moveZeroes(int[] nums) {
//       int index = 0;
//       for(int num:nums){
//           if(num!=0){
//               nums[index++]=num;
//           }
//       }
//       while(index<nums.length){
//           nums[index++] = 0;
//       }
//     }
// }


// 方法二,快慢指针。
// class Solution {
//     public void moveZeroes(int[] nums) {
//         for (int i = 0, j = 0; i < nums.length; i++) if (nums[i] != 0) nums[j] = nums[i] ^ nums[j] ^ (nums[i] = nums[j++]);
//     }
// }


// 将0移到最左边,一行代码
class Solution {
    public void moveZeroes(int[] a) {
        for (int i = 0, j = 0; i < a.length; i++) if (a[i] != 0) a[j] = a[i] ^ a[j] ^ (a[i] = a[j++]);
    }
}

11. 盛最多水的容器

左右双指针

// 双指针 时间复杂度O(n) 空间复杂度O(1)
class Solution {
    public int maxArea(int[] nums) {
        int maxArea = 0, left = 0, right = nums.length - 1;
        while(left < right) {
            int h = nums[left] < nums[right] ? nums[left++] : nums[right--];               
            maxArea = Math.max(maxArea, h * (right-left + 1)); // 因为上面向中间移动了一次,所以要加一
        }
        return maxArea;
    }
}

15. 三数之和

排序+双指针

// a + b = -c
// 方法一:暴力求解,三重循环 时间复杂度O(n3) 空间复杂度O(1)
// 方法二:两重循环 + hash。判断a+b的负值是否在哈希里面。 时间复杂度O(n2)
// 方法三:排序 + 双指针,排序后夹逼 时间复杂度 O(n2) 空间复杂度 O(logn) 


class Solution {
    public List<List<Integer>> threeSum(int[] a) {
        Arrays.sort(a);
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < a.length - 2; i++)
            if (i == 0 || (i > 0 && a[i] != a[i - 1])) {
                int x = i + 1, y = a.length - 1;
                while (x < y) {
                    int sum = a[i] + a[x] + a[y];
                    while (x < y && a[x] == a[x + 1]) x++;
                    while (x < y && a[y] == a[y - 1]) y--;
                    if (sum == 0) { res.add(Arrays.asList(a[i], a[x], a[y])); x++; y--; } 
                    else if (sum < 0) x++;
                    else y--;
                }
            }
        return res;
    }
}

26. 删除排序数组中的重复项

快慢指针

/*
    题目:在不创建新数组的条件下,在原数组中删除重复出现的数字。
    PS:数组是引用传递的,传递的是数组的头节点。对数组的修改会对调用者产生影响。
    !只修改前几个数就可以了
    方法一:快慢指针。题目中的数组是排序过了的,不需要单独排序。如果没排序过就Arrays.sort()
        left慢指针,right快指针。
        left左边是处理过的,right右边是未处理过的。
        由right遍历一遍数组。left记录下一个没有重复的数放置的位置。
    时间复杂度:O(n)
    空间复杂度:O(1)    
*/



// 两个关键点,有序,结果只要长度
class Solution {
    public int removeDuplicates(int[] a) {
        int i = 0;
        for (int j = 1; j < a.length; j++) if(a[i] != a[j]) a[++i] = a[j];
        return i + 1;
    }
}

941. 有效的山脉数组

一次遍历,模拟爬山

class Solution {
    public boolean validMountainArray(int[] a) {
        if(a.length < 3) return false;
        int i = 0;
        // 上山
        while(i < a.length - 1 && a[i+1] > a[i]) i++;
        if(i == 0 || i == a.length - 1) return false;
        while( i < a.length - 1 && a[i+1] < a[i]) i++;
        return i == a.length - 1;
    }
}

189. 旋转数组

三次反转

/*
    1.暴力遍历。
        时间复杂度O(n),空间复杂度O(1)
    2.公式法。 因子 是 a,b,c,根号n,k/c,k/b,k/a。
        只要遍历1-根号n。再从根号n遍历到1。       
        时间复杂度O(logn),空间复杂度O(1)
*/
// class Solution {
//     public int kthFactor(int n, int k) {
//         int cnt = 0;
//         for (int factor = 1; factor <= n; factor++) {
//             if (n % factor == 0) {
//                 cnt++;
//                 if (cnt == k) return factor;
//             }  
//         }
//         return -1;
//     }
// }
class Solution {
    public int kthFactor(int n, int k) {
        int cnt = 0, i;
        for (i = 1; i * i <= n; i++) { // 1 - 根号n
            if (n % i == 0) {
                cnt++;
                if (cnt == k) return i;
            }
        }
        i--;
        if (i * i == n) i--; // 重复计算情况需要减一个 根号n - 1。求他对应的因子
        while (i > 0) {
            if (n % i == 0) { //
                cnt++;
                if (cnt == k) return n / i;
            }
            i--;
        }
        return -1;
    }
}

三.链表

定义

单向链表包含两个部分,一是保存的数据data,一是指向下一个的指针next

图示

实战题目

160. 相交链表

双指针

public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

21. 合并两个有序链表

递归

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2; // 一个为空,另外一个接在最后
        if (l2 == null) return l1;
        if (l1.val < l2.val) { // 哪个值小,哪个作为头
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

数组VS链表

四.栈

定义

栈是一种线性逻辑结构,栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底,最后进入的元素存放的位置叫栈顶。

图示

栈的实现

数组实现:

链表实现:

实战题目

20. 有效的括号

// 方法一:暴力法。不断地replace匹配到的括号,直到替换为空String
// 死循环,找到能匹配的括号。一轮一轮的找。O(n^2)
// 方法二:用栈。如果是左括号,就压进去,如果是右括号,就匹配。正负抵消掉。把栈顶元素移出。
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            switch (c) {
                case '(': stack.push(')'); break;
                case '[': stack.push(']'); break;
                case '{': stack.push('}'); break; 
                default : if (stack.isEmpty() || stack.pop() != c) return false;
            }
        }
        return stack.isEmpty();
    }
}

155. 最小栈

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        //当前值更小
        if(x <= min){   
            //将之前的最小值保存
            stack.push(min);
            //更新最小值
            min=x;
        }
        stack.push(x);
    }


    public void pop() {
        //如果弹出的值是最小值,那么将下一个元素更新为最小值
        if(stack.pop() == min) {
            min=stack.pop();
        }
    }


    public int top() {
        return stack.peek();
    }


    public int getMin() {
        return min;
    }
}

84. 柱状图中最大的矩形

/* 
1.暴力
 for i -> 0, n-2
    for j -> i+1, n-1
        (i, j) -> 最小高度,area
        update max=area
 O(n^3)
2.暴力加速 O(n^2)
    for i -> 0, n-1:
        找到左边界,右边界。(保持高度的左右最大化边界
        area = height[i] * (right - left)
        update max=area                                                                      
3.用栈 O(n)
    维护一个栈,从小到大排列的。
    先放-1。放入一个值,第二个值比第一个值小,说明第一个值找到了边界,弹出。      
*/
class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int len = heights.length;
        for (int i = 0; i < len; i++) {
            int left = i, right = i;
            int count = 1;
            while (--left >= 0 && heights[left] >= heights[i]) {
                count++;
            }
            while (++right < len && heights[right] >= heights[i]) {
                count++;
            }
            max = Math.max(max, count * heights[i]);
        }
        return max;
    }
}

五.队列

定义

队列是线性逻辑结构,后进后出。出口叫队头,入口叫队尾。

图示

队列的实现

数组实现:

链表实现:

实战题目

239. 滑动窗口最大值

双端队列

/*
    有一个滑动窗口,每次向右启动,取出滑动窗口中的最大值,输出数组
        题目要求线性时间复杂度,只能用双端队列


    1.暴力。for i -> 0, n-3
                for j -> 0, 3
                    求出最大值
        时间复杂度O(n * k)
        空间复杂度O(n − k + 1)
    2.双端队列
        出入队列就可以了。
        新的元素进来,更大,其他的元素就可以出去了。
        时间复杂度O(n)
        空间复杂度O(n)
    3.维护一个最大堆
        会超时,不能使用    
*/


public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return nums;
        // 结果数组
        int[] res = new int[nums.length - k + 1];
        // 双端队列,维护一个左大右小,最多k个数的双端队列
        LinkedList<Integer> dq = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // 迭代器到达目标位置。移动一次,删一个左边元素。最左边的元素
            if (!dq.isEmpty() && dq.getFirst() <= i - k) {
                dq.pollFirst();
            }
            // 如果新元素比右边的大,删除右边的元素
            while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                dq.pollLast();
            }
            // 加入新元素
            dq.add(i);
            // 到达指定位置,将左边最大值放入数组中
            if (i + 1 >= k) {
                res[i +1 - k] = nums[dq.getFirst()];
            }
        }
        return res;
    }
}



/* 用最大堆会超时
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // assume nums is not null
        if (nums.length == 0 || k == 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] result = new int[n - k + 1]; // number of windows
        // 创建最大堆
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>((o1, o2) -> (o2 - o1));
        for (int i = 0; i < n; i++) {
            int start = i - k;
            if (start >= 0) {
                maxPQ.remove(nums[start]);
            }
            maxPQ.offer(nums[i]);
            // 当装满后,开始取值
            if (maxPQ.size() == k) {
                result[i - k + 1] = maxPQ.peek();
            }
        }
        return result;
    }
}
*/

[参考资料]

1.快速入门数据结构和算法

2.极客时间-算法训练营

3.极客时间-数据结构与算法之美

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 11. 盛最多水的容器

    https://frenxi.com/http-headers-you-dont-expect/

    编程之心
  • LeetCode 23. 移动零

    ​ 埃隆马斯克一天两本书。比尔盖茨一年五百本。扎克伯格两周一本。沃伦巴菲特每天5份报纸和500页企业报告。

    编程之心
  • 【网易云课堂】Java语言程序设计进阶----第一周编程作业

    编程之心
  • 数字问题-LeetCode 462、463、473、474、475、476、477、482(二分)

    LeetCode # 462 463 473 474 475 476 477 482

    算法工程师之路
  • LeetCode 324. 摆动排序 II

    给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

    Michael阿明
  • andriod游戏音效

    同学们在玩游戏的时候应该都会发现游戏中会有两种形式来播放音乐 ,一般设置选项中会明确标明 设置游戏音乐 与设置游戏音效。 客观的分析一下这两种形式的音乐,游戏背...

    xiangzhihong
  • 图的构建

    每天学Java
  • 从零打卡leetcode之day 1--两数之和

    不过心里才两个循环时间复杂度可是n的平方,心想肯定得超时,不过还是大胆提交一下提交,呵呵,居然通过了。。。。

    帅地
  • LeetCode 27 Remove Element

    ShenduCC
  • LeetCode 每日一题169: 求众数

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    benny

扫码关注云+社区

领取腾讯云代金券