阿里面试算法题四

作者: Tim在路上 | 来源:发表于2020-07-12 20:15 被阅读0次

    最长不含有重复串的字符串

    请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

    示例 1:

    输入: "abcabcbb"
    输出: 3
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

    // 思路是使用 hashmap 进行存储,之前的位置
        public int lengthOfLongestSubstring(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            HashMap<Character,Integer> map = new HashMap<>();
            int max = 1;
            int left = 0;
            for(int i=0;i<s.length();i++){
                char c = s.charAt(i);
                if(map.containsKey(c) && map.get(c) > left){
                    max = Math.max(i-left,max);
                    left = map.get(c);
                }
                map.put(c,i+1);
            }
            return Math.max(s.length()-left,max);
        }
    
    

    315. 计算右侧小于当前元素的个数

    给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

    示例:

    输入: [5,2,6,1]
    输出: [2,1,1,0]

     // 计算右侧小于当前元素的个数, 
        // 可以从右边开始进行而进制的插入排序,插入的位置就是
    
        public List<Integer> countSmaller(int[] nums) {
            List<Integer> res = new ArrayList<>();
            if(nums == null || nums.length == 0){
                return res;
            }
            List<Integer> list = new ArrayList<>();
            for(int i = nums.length -1;i >= 0;i--){
                int left = 0, right = list.size();
                while(left < right){
                    int mid = left + (right - left)/2;
                    if(list.get(mid) >= nums[i]){
                        right = mid;
                    }else{
                        left = mid + 1;
                    }
                }
                list.add(left, nums[i]);
                res.add(left);
            }
            Collections.reverse(res);
            return res;
        }
    

    442. 数组中的重复数据

    给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

    找到所有出现两次的元素。

    你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?

    示例:

    输入:
    [4,3,2,7,8,2,3,1]

    输出:
    [2,3]

     // 这里因为 数值都是 1~n 可以将其散列在长度为n的数组中
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> res = new ArrayList<>();
            if(nums == null || nums.length == 0){
                return res;
            }
            int n = nums.length;
            // 可以将字符的添加增加到遍历中
            for(int x: nums){
                int index = Math.abs(x) - 1;
                nums[index] = -nums[index];
                if(nums[index] > 0){
                    res.add(Math.abs(x));
                }
            }
            return res;
        }
    

    189. 旋转数组

    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    示例 1:

    输入: [1,2,3,4,5,6,7] 和 k = 3
    输出: [5,6,7,1,2,3,4]

    // 将数组进行三次反转
        public void rotate(int[] nums, int k) {
            int n = nums.length;
            k = k % n;
            reserve(nums,0,nums.length-k-1);
            reserve(nums,nums.length-k,nums.length-1);
            reserve(nums,0,nums.length-1);
        }
    
        public void reserve(int[] nums, int left, int right){
            while(left < right){
                swap(nums,left,right);
                left++;
                right--;
            }
        }
    
        public void swap(int[] nums, int i, int j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    

    31. 下一次排列

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

    如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

    必须原地修改,只允许使用额外常数空间。

    以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
    1,2,3 → 1,3,2
    3,2,1 → 1,2,3
    1,1,5 → 1,5,1

     public  void nextPermutation(int[] nums) {
            nextPermutation(nums,0,nums.length);
        }
    
        private  void nextPermutation(int[] nums, int start, int end) {
            int p = end -2;
            while (p > -1 && nums[p] >= nums[p+1]){
                p--;
            }
            if (p == -1){
                reverse(nums,0,end);
                return;
            }
            int c = end - 1;
            while (c > p && nums[c] <= nums[p]){
                c--;
            }
            swap(nums,p,c);
            reverse(nums,p+1,end);
            return;
        }
    
        private  void swap(int[] nums, int p, int c) {
            int tmp = nums[c];
            nums[c] = nums[p];
            nums[p] = tmp;
        }
    
        private  void reverse(int[] nums, int start, int end) {
            for (int i = 0;i<(end - start)/2;i++){
                int tmp = nums[start + i];
                nums[start + i] = nums[end - i -1];
                nums[end - i - 1] = tmp;
            }
    

    915. 分割数组

    给定一个数组 A,将其划分为两个不相交(没有公共元素)的连续子数组 left 和 right, 使得:

    left 中的每个元素都小于或等于 right 中的每个元素。
    left 和 right 都是非空的。
    left 要尽可能小。
    在完成这样的分组后返回 left 的长度。可以保证存在这样的划分方法。

    示例 1:

    输入:[5,0,3,8,6]
    输出:3
    解释:left = [5,0,3],right = [8,6]

    // 因为数组的顺序是不能够改变的,所以思路是采用两个数组,将从左到右,从右到左的小数组
        public int partitionDisjoint(int[] A) {
            if(A == null || A.length == 0){
                return 0;
            }
            int[] leftMax = new int[A.length];
            int[] rightMin = new int[A.length];
            int max = A[0];
            for(int i=0;i<A.length;i++){
                max = Math.max(A[i], max);
                leftMax[i] = max;
            }
    
            int min = A[A.length-1];
            for(int i=A.length-1;i>=0;i--){
                min = Math.min(A[i],min);
                rightMin[i] = min;
            }
    
            for(int i=0;i<A.length-1;i++){
                if(leftMax[i] <= rightMin[i+1]){
                    return i+1;
                }
            }
            return -1;
        }
    

    54. 矩阵旋转

    给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

    示例 1:

    输入:
    [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
    ]
    输出: [1,2,3,6,9,8,7,4,5]

      // 思路是,定义左上角和右下角位置,每次进行缩减, 只需要多住一个一个情况柱状模式
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> res = new ArrayList<>();
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
                return res;
            }
            int leftUpRow = 0, leftUpCol = 0;
            int rightDownRow = matrix.length -1, rightDownCol = matrix[0].length - 1;
            int r = 0, c = 0;
            while(leftUpRow <= rightDownRow && leftUpCol <= rightDownCol){
                r = leftUpRow;
                c = leftUpCol;
                while(c <= rightDownCol){
                    res.add(matrix[leftUpRow][c]);
                    c++;
                }
                c--;
                r++;
                while(r <= rightDownRow){
                    res.add(matrix[r][rightDownCol]);
                    r++;
                }
                r--;
                c--;
                while(c >= leftUpCol && leftUpRow != rightDownRow){
                    res.add(matrix[rightDownRow][c]);
                    c--;
                }
                c++;
                r--;
                while(r > leftUpRow && leftUpCol != rightDownCol){
                    res.add(matrix[r][leftUpCol]);
                    r--;
                }
                leftUpCol++;
                leftUpRow++;
                rightDownCol--;
                rightDownRow--;
            }
            return res;
        }
    

    53. 最大子序和

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    示例:

    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

      // 使用dp
        public int maxSubArray(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            int maxSum = Integer.MIN_VALUE;
            int curSum = 0;
            for(int x : nums){
                if(curSum < 0){
                    curSum = x;
                }else{
                    curSum += x;
                }
                maxSum = Math.max(curSum, maxSum);
            }
            return maxSum;
        }
    

    152. 乘积最大子数组

    给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

    示例 1:

    输入: [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。

    // dp , 同时记录最大和最小,当前值为负数是交换
        public int maxProduct(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            int max = 1;
            int min = 1;
            int maxProduct = Integer.MIN_VALUE;
            for(int x : nums){
                if(x < 0){
                    int tmp = min;
                    min = max;
                    max = tmp;
                }
                min = Math.min(min * x,x);
                max = Math.max(max * x,x);
                maxProduct = Math.max(maxProduct,max);
            }
            return maxProduct;
        }
    

    138.复制带有随机指针的链表

    给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

    要求返回这个链表的 深拷贝。

    我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

    val:一个表示 Node.val 的整数。
    random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

     // 复制带有随机指针的链表
        // 使用hashmap 进行复制节点,同时按照链表顺序间next和随机节点连接起来
        public Node copyRandomList(Node head) {
            if(head == null){
                return head;
            }
            HashMap<Node, Node> map = new HashMap<>();
            Node p = head;
            while(p != null){
                map.put(p, new Node(p.val));
                p = p.next;
            }
            p = head;
            while(p != null){
                map.get(p).next = map.get(p.next);
                map.get(p).random = map.get(p.random);
                p = p.next;
            }
            return map.get(head);
        }
    

    136. 只出现一次的数字

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    说明:

    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

    示例 1:

    输入: [2,2,1]
    输出: 1

    // 异或将相同的数约掉
        public int singleNumber(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            int res = 0;
            for(int x: nums){
                res ^= x;
            }
            return res;
        }
    

    137. 只出现一次的数字2

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

    说明:

    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

    示例 1:

    输入: [2,2,3,2]
    输出: 3

    n 个 数 1 个 数,做加法,然后将数移到具体位置取模,不进位

     // 可以采用三进制加法,将数的每一位做,不进位的加法
        public int singleNumber(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            int res = 0;
            for(int i=0;i<32;i++){
                int sum = 0;
                for(int j=0;j<nums.length;j++){
                    sum += ((nums[j]>>i) & 1);
                }
                res |= (sum % 3) << i;
            }
            return res;
        }
    

    260. 只出现一次的数字3

    给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

    示例 :

    输入: [1,2,1,3,2,5]
    输出: [3,5]

     public int[] singleNumber(int[] nums) {
            // 两个数字出现,思路所有数字一起异或,就只剩下两个数字的异或,
            // res 与 相反数相与 
            int res = 0;
            for(int x : nums){
                res ^= x;
            }
            // 获得差异,只会保留位中出现最右边的第一个1,这个1 要么是来自x, 要么来自y
            int diff = res & -res;
            int x = 0;
            for(int i=0;i<nums.length;i++){
                if((diff & nums[i]) != 0){
                    x = x ^ nums[i];
                }
            }
            return new int[]{x,res^x};
        }
    

    263. 丑数

    编写一个程序判断给定的数是否为丑数。

    丑数就是只包含质因数 2, 3, 5 的正整数。

    示例 1:

    输入: 6
    输出: true
    解释: 6 = 2 × 3

     // 让 2,3,5
        public boolean isUgly(int num) {
            if(num == 0){
                return false;
            }
            if(num == 1){
                return true;
            }
            if(num % 2 == 0){
                return isUgly(num/2);
            }
            if(num % 3 == 0){
                return isUgly(num/3);
            }
            if(num % 5 == 0){
                return isUgly(num/5);
            }
            return false;
        }
    

    264. 丑数2

    编写一个程序,找出第 n 个丑数。

    丑数就是质因数只包含 2, 3, 5 的正整数。

    示例:

    输入: n = 10
    输出: 12
    解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

    // 依次进行2,3,5 找n个丑数
        public int nthUglyNumber(int n) {
            if(n == 1){
                return 1;
            }
            List<Integer> list = new ArrayList<>();
            list.add(1);
            // 这里采用,每一个数,2,3,5 都采用一个指针维护和上一个数的关系
            int s1 = 0, s2 = 0, s3 = 0;
            while(list.size() < n){
                int m1 = list.get(s1) * 2;
                int m2 = list.get(s2) * 3;
                int m3 = list.get(s3) * 5;
                int min = Math.min(m1, Math.min(m2, m3));
                list.add(min);
                if(min == m1){
                    s1++;
                }
                if(min == m2){
                    s2 ++;
                }
                if(min == m3){
                    s3 ++;
                }
            }
            return list.get(list.size()-1);
        }
    

    59. 滑动窗口的最大值

    给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

    示例:

    输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
    输出: [3,3,5,5,6,7]

      // 思路是: 维护一个双端队列,如果,队列头等于 数组第一个元素,当组数大于0 弹出
        //         队列为中元素小于当前元素时弹出,让队列中只维护大于改元素的元素
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums == null || nums.length == 0 || k == 0){
                return new int[0];
            }
            Deque<Integer> deque = new LinkedList<>();
            int[] res = new int[nums.length - k + 1];
            for(int j=0,i = 1 - k;j<nums.length;i++,j++){
                if(i > 0 && deque.peekFirst() == nums[i-1]) deque.removeFirst();
                while(!deque.isEmpty() && deque.peekLast() < nums[j]) deque.removeLast();
                deque.addLast(nums[j]);
                if(i >= 0) res[i] = deque.peekFirst();
            }
            return res;
        }
    

    128. 最长连续子序列

    给定一个未排序的整数数组,找出最长连续序列的长度。

    要求算法的时间复杂度为 O(n)。

    示例:

    输入: [100, 4, 200, 1, 3, 2]
    输出: 4

    思路是按顺序进行统计,跳过相等的数

    // 使用hashmap 进行每一个数的统计
        public int longestConsecutive(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            Arrays.sort(nums);
            int max = 1;
            for(int i =0;i<nums.length;i++){
                int curMax = 1;
                while(i+1 < nums.length && nums[i] + 1 >= nums[i+1]){
                    if(nums[i] + 1 == nums[i+1]) curMax++;
                    i++;
                }
                max = Math.max(max, curMax);
            }
            return max;
        }
    

    169. 多数元素

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

    你可以假设数组是非空的,并且给定的数组总是存在多数元素。

    示例 1:

    输入: [3,2,3]
    输出: 3

    // 超过半数的元素,统计个数,相同相加,不同相减
        public int majorityElement(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            int count = 1;
            int pre = nums[0];
            for(int i=1;i<nums.length;i++){
                if(pre == nums[i]){
                    count ++;
                }else if(count == 0){
                    count = 1;
                    pre = nums[i];
                }else{
                    count --;
                }
            }
            return pre;
        }
    

    392. 判断子序列

    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

    字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

    示例 1:
    s = "abc", t = "ahbgdc"

    返回 true.

    示例 2:
    s = "axc", t = "ahbgdc"

    返回 false.

        // 判断子序列
        public boolean isSubsequence(String s, String t) {
            if(t == null || s.length() > t.length()){
                return false;
            }
            int j = -1;
            for(int i=0;i<s.length();i++){
                char c = s.charAt(i);
                j = t.indexOf(c,j+1);
                if(j == -1){
                    return false;
                }
            }
            return true;
        }
    

    1. 两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

    示例:

    给定 nums = [2, 7, 11, 15], target = 9

     public int[] twoSum(int[] nums, int target) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i=0;i<nums.length;i++){
                int diff = target - nums[i];
                if(map.containsKey(diff)){
                    int j = map.get(diff);
                    return new int[]{j, i};
                }
                map.put(nums[i],i);
            }
            return new int[]{-1, -1};
        }
    

    153. 寻找旋转排序数组中的最小值

    假设按照升序排序的数组在预先未知的某个点上进行了旋转。

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    请找出其中最小的元素。

    你可以假设数组中不存在重复元素。

    示例 1:

    输入: [3,4,5,1,2]
    输出: 1

      // 直接使用二分查询进行查找
        public int findMin(int[] nums) {
            int left = 0, right = nums.length - 1;
            // 考虑不旋转的情况,考虑只有一个元素的情况
            if(nums[0] <= nums[nums.length-1]){
                return nums[0];
            }
            while(left < right){
                int mid = left + (right - left)/2;
                // 如果只有两个元素,那么mid元素可能就是第一个元素
                if(nums[mid] >= nums[0]){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
            return nums[left];
        }
    

    15. 三数之和

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

    注意:答案中不可以包含重复的三元组。

    示例:

    给定数组 nums = [-1, 0, 1, 2, -1, -4],

    满足要求的三元组集合为:
    [
    [-1, 0, 1],
    [-1, -1, 2]
    ]

    // 三数之和
        public List<List<Integer>> threeSum(int[] nums) {
           Set<List<Integer>> res = new LinkedHashSet<>();
            if(nums == null || nums.length == 0){
                return new ArrayList<>(res);
            }
            // 使用夹击的策略
            Arrays.sort(nums);
            // 使用hashmap 
            int left = 0, right = nums.length - 1;
            for(int i=0;i<nums.length-2;i++){
                left = i + 1;
                right = nums.length-1;
                while(left < right){
                    int sum = nums[left] + nums[right];
                    if(sum == -nums[i]){
                        res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    }
                    if(sum >= -nums[i]){
                        right--;
                    }else{
                        left++;
                    }
                }
            }
            return new ArrayList<>(res);
        }
    

    3. 无重复字符的最长子串

    给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

    示例 1:

    输入: "abcabcbb"
    输出: 3
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

    // 使用hashmap 位置每一个字符的位置,方便查询是否重复
        public int lengthOfLongestSubstring(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            int maxLen = 1;
            int left  = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            for(int i=0;i<s.length();i++){
                char c = s.charAt(i);
                if(map.containsKey(c)){
                    int j = map.get(c);
                    if(j >= left){
                    maxLen = Math.max(maxLen,i-left);
                    left = j;
                    }
                }
                map.put(c,i+1);
            }
            return Math.max(maxLen,s.length()-left);
        }
    

    插入括号

    有长度为length(0<length≤100000)的一个括号序列sequence,只有“(”或者“)”两种字符,每个括号的左右两边都能插一个括号,总共有length+1个位置可以插入括号,在第i个位置插入任意括号的代价是costi同一个位置只能插入一个括号,求使得括号序列合法的最小代价,并给出解法的时间复杂度和空间复杂度。
    例如输入

    length=6,sequence="()))((",cost=[1,2,5,5,3,4,1],输出8.

    思路是,遇到( 左括号压入栈,遇到右括号弹出栈,如果栈为空说明在当前位置前缺少左括号,然后找向前一个最小的数,并标记

    如果当前位置

    92. 反转链表

    反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

    说明:
    1 ≤ m ≤ n ≤ 链表长度。

    示例:

    输入: 1->2->3->4->5->NULL, m = 2, n = 4
    输出: 1->4->3->2->5->NULL

    思路,总共是两步,找到前驱和后记,以及要反转的的头和尾节点,同时将尾部断开,把器转化为普通结点进行旋转

     // 主要分为两步,找到前驱节点,以及首节点使用, n 来控制尾节点
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if(head == null){
                return null;
            }
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode pre = dummy;
            ListNode end = dummy;
            while(n-- > 0 && end != null){
                end = end.next;
            }
            while(m-- > 1 && pre != null){
                pre = pre.next;
            }
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            return dummy.next;
        }
    
        public ListNode reverse(ListNode head){
            if(head == null){
                return head;
            }
            ListNode pre = null, p = head;
            while(p != null){
                ListNode next = p.next;
                p.next = pre;
                pre = p ;
                p = next;
            }
            return pre;
        }
    

    86. 分割链表

    给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。

    你应当保留两个分区中每个节点的初始相对位置。

    示例:

    输入: head = 1->4->3->2->5->2, x = 3
    输出: 1->2->2->4->3->5

    // 思路是,将小于该元素的删除,并记录,再次遍历插入
        // 看懂题目,是小于X 的节点放在前面,可以将其拆分为两个队列进行合并
        public ListNode partition(ListNode head, int x) {
            ListNode left = new ListNode(-1);
            ListNode right = new ListNode(-1);
            ListNode cur = head, p = left, q = right;
            while(cur != null){
                if(cur.val < x){
                    p.next = new ListNode(cur.val);
                    p = p.next;
                }else {
                    q.next = new ListNode(cur.val);
                    q = q.next;
                }
                cur = cur.next;
            }
            p.next = right.next;
            return left.next;
        }
    

    83. 使用递归删除重复元素

    给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

    示例 1:

    输入: 1->1->2
    输出: 1->2

    // 使用递归删除重复元素
        public ListNode deleteDuplicates(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            if(head != null && head.next != null &&  head.val == head.next.val){
                return deleteDuplicates(head.next);
            }else{
                head.next = deleteDuplicates(head.next);
                return head;
            }
        }
    

    82. 删除链表中重复元素2

    给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

    示例 1:

    输入: 1->2->3->3->4->4->5
    输出: 1->2->5
    示例 2:

    输入: 1->1->1->2->3
    输出: 2->3

     // 使用递归删除
        public ListNode deleteDuplicates(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            if(head != null && head.next != null && head.val == head.next.val){
                // 这里进行迭代找的新的节点
                ListNode p = head.next;
               for(;p != null && p.val == head.val; p = p.next);
               return deleteDuplicates(p);
            }else{
                head.next = deleteDuplicates(head.next);
                return head;
            }
        }
    

    237. 删除链表中的节点

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

    现有一个链表 -- head = [4,5,1,9],它可以表示为:

    示例 1:

    输入: head = [4,5,1,9], node = 5
    输出: [4,1,9]
    解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

     // 思路很简单,就是讲当前节点和下一个节点互换,跳过下一个节点
        public void deleteNode(ListNode node) {
            if(node != null && node.next != null){
                node.val = node.next.val;
            }
            node.next = node.next.next;
        }
        
    ```
    
    #### 19. 删除链表的倒数第n个节点
    
    ```
    // 思路, 倒数第n个节点
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if(head == null){
                return head;
            }
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode fast = dummy, slow = dummy;
            while(n-- > 0){
                fast = fast.next;
            }
            while(fast != null && fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return dummy.next;
        }
        
    ```
    
    #### 203. 删除链表中等于给定值的所有节点
    
    删除链表中等于给定值 val 的所有节点。
    
    示例:
    
    输入: 1->2->6->3->4->5->6, val = 6
    输出: 1->2->3->4->5
    
    ```
     // 删除链表中等于给定值的所有节点,可以使用递归
        public ListNode removeElements(ListNode head, int val) {
            if(head == null){
                return head;
            }
            if(head.val == val){
                return removeElements(head.next, val);
            }else{
                head.next = removeElements(head.next,val);
                return head;
            }
        }
    ```
    
    #### 61.  旋转链表
    
    给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
    
    示例 1:
    
    输入: 1->2->3->4->5->NULL, k = 2
    输出: 4->5->1->2->3->NULL
    解释:
    向右旋转 1 步: 5->1->2->3->4->NULL
    向右旋转 2 步: 4->5->1->2->3->NULL
    
    注意k 为0 不进行旋转,和 k 取余为0 也是不旋转的的情况
    
    
    ```
     // 旋转链表
        // 思路将其断开,然后再拼接
        public ListNode rotateRight(ListNode head, int k) {
            if(head == null || head.next == null){
                return head;
            }
            ListNode p = head;
            int len = 0;
            while(p != null){
                len ++;
                p = p.next;
            }
            k = k % len;
            if(k == 0){
                return head;
            }
            // 快慢指针
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode fast = dummy, slow = dummy;
            while(k-- > 0){
                fast = fast.next;
            }
            while(fast != null && fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
            ListNode first = slow.next;
            slow.next = null;
            if(fast != null){
                fast.next = head;
            }
            return first;
        }
    ```
    
    #### 2. 两数相加
    
    给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
    
    如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
    
    您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
    
    示例:
    
    输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出:7 -> 0 -> 8
    原因:342 + 465 = 807
    
    
    ```
     // 两数相加,实质是链表的合并
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode cur = new ListNode(-1);
            ListNode p = l1, q = l2,r = cur;
            int c = 0;
            while(p != null || q != null || c != 0){
                int x = p != null ? p.val : 0;
                int y = q != null ? q.val : 0;
                int num = x +  y + c;
                r.next = new ListNode(num % 10);
                c = num / 10;
                r = r.next;
                p = p != null ? p.next:null;
                q = q != null ? q.next:null;
            }
            return cur.next;
        }
    ```
    
    #### 445. 两数相加
    
    ```
    
        // 要想递归,两个链表要同样的长度才行
        // 反转相加,效率高
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode p = reverse(l1);
            ListNode q = reverse(l2);
            ListNode head = new ListNode(-1);
            ListNode cur = head;
            int c = 0;
            while(p != null || q != null || c != 0){
                int x = p != null ? p.val : 0;
                int y = q != null ? q.val : 0;
                int num = x + y + c;
                cur.next = new ListNode(num % 10);
                c = num / 10;
                cur = cur.next;
                p = p != null ? p.next : null;
                q = q != null ? q.next : null;
            }
            return reverse(head.next);
        }
    
        public ListNode reverse(ListNode head){
            if(head == null || head.next == null){
                return head;
            }
            ListNode next = reverse(head.next);
            head.next.next = head;
            head.next = null;
            return next;
        }
    ```
    ```
     // 链表两数相加思路: 首先计算两个链表的长度,然后在短的前面补0,然后递归相加,注意在进行递归时创建好链表的节点,
        // 回溯时添加值,并判断返回的上一个节点是否大于 10 ,最终大于10 再添加个节点
        // 可不可以使用回溯进行两数相加
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int l1Size = listSize(l1);
            int l2Size = listSize(l2);
            if (l1Size - l2Size > 0) {
                l2 = headFillZero(l2, l1Size - l2Size);
            } else {
                l1 = headFillZero(l1, l2Size - l1Size);
            }
            ListNode node = addTwoNumbers(l1, l2, new ListNode(-1));
            if (node.val >= 10) {
                ListNode newNode = new ListNode(node.val % 10);
                node.val = node.val / 10;
                newNode.next = node.next;
                node.next = newNode;
            }
            return node;
        }
        public static ListNode addTwoNumbers(ListNode l1, ListNode l2, ListNode head) {
            if (l1.next == null && l2.next == null) {//遇见l1和l2的最后两个节点,相加返回
                head.next = new ListNode(l1.val + l2.val);
                return head.next;
            }
    
            head.next = new ListNode(-1);//先构建好一个节点追加在head后面,具体val在递归返回阶段依次计算填充.
            head = head.next;
            ListNode node = addTwoNumbers(l1.next == null ? l1 : l1.next, l2.next == null ? l2 : l2.next, head);
            int temp = l1.val + l2.val + node.val / 10;//计算当前节点的值,node.val是上一个节点的值,如果node.val大于10,则进位计算.
            node.val = node.val % 10;//重新计算上一个节点的值.
            head.val = temp;
            return head;
        }
    
        public static int listSize(ListNode listNode) {
            if (listNode == null) {
                return 0;
            }
            int size = 0;
            while (listNode != null) {
                size++;
                listNode = listNode.next;
            }
            return size;
        }
    
        public static ListNode headFillZero(ListNode node, int fillNum) {
            if (fillNum == 0) {
                return node;
            }
    
            ListNode head = node;
            for (int i = 0; i < fillNum; i++) {
                ListNode temp = head;
                head = new ListNode(0);
                head.next = temp;
            }
            return head;
        }
    ```
    
    #### 234. 回文链表
    
    请判断一个链表是否为回文链表。
    
    示例 1:
    
    输入: 1->2
    输出: false
    
    使用回溯判断回文链表
    
    ```
     // 使用回溯进行判断, 保存首节点
    
        ListNode first = null;
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null){
                return true;
            }
            first = head;
            return isPalindromeCore(head);
        }
    
        public boolean isPalindromeCore(ListNode head){
            if(head == null){
                return true;
            }
            if(!isPalindromeCore(head.next)) return false;
            if(first.val != head.val) return false;
            first = first.next;
            return true;
        }
    ```
    
    #### 24. 两两交换链表中的节点
    
    定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
    
    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
    
     
    
    示例:
    
    给定 1->2->3->4, 你应该返回 2->1->4->3.
    
    
    ```
     // 进行递归
        public ListNode swapPairs(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            ListNode first = head, second = head.next;
            ListNode next = swapPairs(second.next);
            second.next = first;
            first.next = next;
            return second;
        }
    ```
    
    #### 160. 橡胶链表的判断
    
    编写一个程序,找到两个单链表相交的起始节点。
    
    如下面的两个链表:
    
    
    ```
     // 找到相交节点的首节点, 思路将其两个进行拼接,遍历第一个相同的节点
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode p = headA, q = headB;
            while(p != q){
                p = p == null ? headB : p.next;
                q = q == null ? headA : q.next;
            }
            return p;
        }
    ```
    
    #### 141. 快慢指针判断是否有环
    
    给定一个链表,判断链表中是否有环。
    
    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
    
    
    ```
    // 快慢指针进行判断
        public boolean hasCycle(ListNode head) {
            if(head == null || head.next == null){
                return false;
            }
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode fast = dummy, slow = dummy;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
                    break;
                }
            }
            if(fast == null || fast.next == null){
                return false;
            }
            return true;
        }
    ```
    
    #### 142. 环形链表2
    
    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
    
    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
    
    说明:不允许修改给定的链表
    
    
    ```
     // 从相交节点走到 第一个节点 和 从起始节点走到第一个节点距离一样
        public ListNode detectCycle(ListNode head) {
            if(head == null || head.next == null){
                return null;
            }
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            // 注意从dummy 开始,在进行查找第一个节点的时候也得从dummy 开始
            ListNode fast = dummy, slow = dummy;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
                if(slow == fast){
                    break;
                }
            }
            if(fast == null || fast.next == null){
                return null;
            }
            fast = dummy;
            while(fast.val != slow.val){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    ```
    
    #### 21. 合并两个排序链表
    
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
    
     
    
    示例:
    
    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4
    
    

    21.合并两个有序的链表

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    示例:

    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4

    // 合并链表
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode head = new ListNode(-1);
            ListNode cur = head;
            while(l1 != null && l2 != null){
                if(l1.val < l2.val){
                    cur.next = new ListNode(l1.val);
                    l1 = l1.next;
                }else{
                    cur.next = new ListNode(l2.val);
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            if(l1 != null){
                cur.next = l1;
            }
            if(l2 != null){
                cur.next = l2;
            }
            return head.next;
        }
    

    相关文章

      网友评论

        本文标题:阿里面试算法题四

        本文链接:https://www.haomeiwen.com/subject/stuncktx.html