小精灵儿童网站免费做踢,企业推广,jsp 网站连接数据库,长春盛网网站建设今天回顾一下下面三个算法#xff0c;涉及到了动态规划、合并链表、位运算#xff0c;好吧#xff0c;让我们再次手敲一遍
//乘积最大子数组//思路: 维护三个变量#xff0c;imax最大前缀乘积 imin最小前缀乘积 max最大连续乘积//由于元素有正负#xff0c;imax和imin需…今天回顾一下下面三个算法涉及到了动态规划、合并链表、位运算好吧让我们再次手敲一遍
//乘积最大子数组//思路: 维护三个变量imax最大前缀乘积 imin最小前缀乘积 max最大连续乘积//由于元素有正负imax和imin需要互换所以需要单独维护一个max用于记录最大连续乘积public int maxProduct(int[] nums) {if (nums null || nums.length 0) {return -1;}if (nums.length 1) {return nums[0];}int imax 1, imin 1, max Integer.MIN_VALUE;for (int i 0; i nums.length; i) {if (nums[i] 0) {int temp imax;imax imin;imin temp;}imax Math.max(nums[i], imax * nums[i]);imin Math.min(nums[i], imin * nums[i]);max Math.max(max, imax);}return max;}//排序链表//思路: 先将链表分成多条长度为1length的子链表然后合并两条长度为1的有序子链表//接着把链表分为多条长度为2length的子链表然后合并两条长度为2的有序子链表//重复以上步骤直到length大于等于链表的长度结束public ListNode sortList(ListNode head) {if (head null) {return null;}int length 0;ListNode curr head;while (curr ! null) {length;curr curr.next;}ListNode dummyHead new ListNode(0, head);for (int subLength 1; subLength length; subLength subLength * 2) {ListNode prev dummyHead;curr dummyHead.next;while (curr ! null) {ListNode head1 curr, head2;for (int i 1; i subLength curr ! null curr.next ! null; i) {curr curr.next;}head2 curr.next;curr.next null;curr head2;for (int i 1; i subLength curr ! null curr.next ! null; i) {curr curr.next;}ListNode dailyListHead null;if (curr ! null) {dailyListHead curr.next;curr.next null;}prev.next merged(head1, head2);while (prev.next ! null) {prev prev.next;}curr dailyListHead;}}return dummyHead.next;}private ListNode merged(ListNode head1, ListNode head2) {ListNode dummyHead new ListNode(0);ListNode temp dummyHead, temp1 head1, temp2 head2;while (temp1 ! null temp2 ! null) {if (temp1.val temp2.val) {temp.next temp2;temp2 temp2.next;} else {temp.next temp1;temp1 temp1.next;}temp temp.next;}if (temp1 ! null) {temp.next temp1;} else if (temp2 ! null) {temp.next temp2;}return dummyHead.next;}//只出现一次的数字//思路: 利用异或运算进行求解异或运算性质0异或任何数都等于本身任何数与本身异或都等于0public int singleNumber(int[] nums) {int single 0;for (int i 0; i nums.length; i) {single ^ nums[i];}return single;}
