精华内容
下载资源
问答
  • 数组一分为二,和相等

    千次阅读 2018-03-31 15:56:33
    题目描述编写一个函数,传入一个int型数组,返回该数组能否分成两组,使得两组中各元素加起来的和相等,并且,所有5的倍数必须在其中一个组中,所有3的倍数在另一个组中(不包括5的倍数),能满足以上条件,返回true...
    题目描述
    编写一个函数,传入一个int型数组,返回该数组能否分成两组,使得两组中各元素加起来的和相等,并且,所有5的倍数必须在其中一个组中,所有3的倍数在另一个组中(不包括5的倍数),能满足以上条件,返回true;不满足时返回false。 
    输入描述:
    第一行是数据个数,第二行是输入的数据
    输出描述:

    返回true或者false

    思路:

    将能整除3或者5的各自分为一组,记为sum1和sum2,剩余的保存在数组others里
    剩余others里的数要么在sum1里要么在sum2里,利用递归依次放在sum1和sum2中
    最终others里的数字全部放进去,若sum1 == sum2,则返回true,否则,返回false

    import java.util.Scanner;
    
    public class Main
    {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext())
            {
                int n = scanner.nextInt();
                int[] arr = new int[n];
                int sum1 = 0;
                int sum2 = 0;
                int[] others = new int[n];
                int index = 0;
                for (int i = 0; i < n; i++)
                {
                    arr[i] = scanner.nextInt();
                    if (arr[i] % 5 == 0)
                        sum1 += arr[i];
                    else if (arr[i] % 3 == 0)
                        sum2 += arr[i];
                    else
                        others[index++] = arr[i];
                }
                System.out.println(isExist(sum1, sum2, others, 0));
            }
        }
        public static boolean isExist(int sum1, int sum2, int[] others, int index)
        {
            if (index == others.length && sum1 != sum2)
                return false;
            if (index == others.length && sum1 == sum2)
                return true;
            if (index < others.length)
                return isExist(sum1 + others[index], sum2, others, index + 1) || isExist(sum1, sum2 + others[index], others, index + 1);
            return false;
        }
    }

    展开全文
  • 与其把PHP中的数组理解为我们狭义上的“数组”,我觉得还不妨把这个数组一分为二,一者为我们常规上的数组,一者为我们的Dictionary。
  • 旋转数组专题

    2021-04-09 09:40:14
      将数组一分为二,其中一定有一个是有序的,另一个可能是有序,也能是部分有序。 此时有序部分用二分法查找。无序部分再一分为二,其中一个一定有序,另一个可能有序,可能无序。就这样循环。 旋转排序数组153. ...

    旋转数组思路:
      将数组一分为二,其中一定有一个是有序的,另一个可能是有序,也能是部分有序。
    此时有序部分用二分法查找。无序部分再一分为二,其中一个一定有序,另一个可能有序,可能无序。就这样循环。

    153. 寻找旋转排序数组中的最小值(无重复值)

    在这里插入图片描述
    思路:
    在这里插入图片描述

    class Solution {
        public int findMin(int[] nums) {
            int left = 0, right = nums.length - 1;
            while(left < right){
                int mid = left + (right - left) / 2;
                if(nums[mid] < nums[right]){
                    right = mid;
                }else if(nums[mid] > nums[right]){
                    left = mid + 1;
                }
            }
            return nums[left];
        }
    }
    

    154. 寻找旋转排序数组中的最小值 II(有重复值)

    思路:当nums[mid] == nums[r]时,无论nums[r] 是不是最小值,都有一个它的「替代品」num[mid],因此我们可以忽略二分查找区间的右端点。

    class Solution {
        public int findMin(int[] nums) {
            if(nums.length == 1){
                return nums[0];
            }
            int l = 0, r = nums.length - 1;
            while(l < r){
                int mid = l + (r - l) / 2;
                if(nums[mid] > nums[r]){
                    l = mid + 1;
                }else if(nums[mid] < nums[r]){
                    r = mid;
                }else{
                    r--;
                }
            }
            return nums[l];
        }
    }
    

    33. 搜索旋转排序数组(无重复值)

    在这里插入图片描述

    class Solution {
        public int search(int[] nums, int target) {
            if (nums.length == 0) return -1;
            if (nums.length == 1) {
                return nums[0] == target ? 0 : -1;
            }
            int l = 0, r = nums.length - 1;
            while(l <= r){
                int mid = l + (r - l) / 2;
                if(nums[mid] == target){
                    return mid;
                }
                // 先根据 nums[mid] 与 nums[l] 的关系判断 mid 是在左段还是右段
                // 在左段
                if(nums[l] <= nums[mid]){
                    // 再判断 target 是在 mid 的左边还是右边,从而调整左右边界 lo 和 hi
                    // target在mid左边
                    if(nums[l] <= target && target < nums[mid]){
                        r = mid - 1;
                    // target在mid右边
                    }else{
                        l = mid + 1;
                    }
                // 在右段
                }else{
                    if(nums[mid] < target && target <= nums[r]){
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
            }
            return -1;
        }
    }
    

    81. 搜索旋转排序数组(有重复值)

    class Solution {
        public boolean search(int[] nums, int target) {
            if(nums.length == 0)    return false;
            if(nums.length == 1){
                return nums[0] == target ? true : false;
            }
            int left = 0, right = nums.length - 1;
            while(left <= right){
                int mid = left + (right - left) / 2;
                if(nums[mid] == target) return true;
                // 如果有重复值,10111 和 11101这种,start++相当于去掉一个重复的干扰项。
                if (nums[left] == nums[mid]) {
                    left++;
                    continue;
                }
                // mid在左段
                if(nums[mid] > nums[left]){
                    if(nums[left] <= target && target < nums[mid]){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                // mid在右段
                }else{
                    if(nums[mid] < target && target <= nums[right]){
                        left = mid + 1;
                    }else{
                        right = mid - 1;
                    }
                }
            }
            return false;
        }
    }
    
    展开全文
  • 1.分析  首先,这样的数组一定是有正...我们知道,通过将数组一分为二后,最大子数组有以下三种位置: 存在于左子数组中 存在于右子数组中 跨越中点,存在于左右两个子数组中 2.使用递归进行求解 ...

    1.分析

      首先,这样的数组一定是有正负数组成的,这样问题才有意义。要求解这个问题,可以使用分治思想将所求问题的规模变小,通过求解子问题的解来最终得到所求问题的解,显然每个子问题和原问题相同,可以用递归来进行求解。

    我们知道,通过将数组一分为二后,最大子数组有以下三种位置:

    • 存在于左子数组中
    • 存在于右子数组中
    • 跨越中点,存在于左右两个子数组中

    2.使用递归进行求解

     1 def findMaxCrossSubarray(L,low,mid,high):
     2     left_sum = -float("inf")
     3     Sum = 0
     4     for i in range(mid,low -1,-1):
     5         Sum = Sum + L[i]
     6         if Sum > left_sum:
     7             left_sum = Sum
     8             left_max = i
     9 
    10     right_sum = -float("inf")
    11     Sum = 0
    12     for j in range(mid+1,high+1):
    13         Sum = Sum + L[j]
    14         if Sum > right_sum:
    15             right_sum = Sum
    16             right_max = j
    17 
    18     return (left_max,right_max,left_sum + right_sum)
    19 
    20 
    21 
    22 def findMaxSubarray(L,low,high):
    23     if low == high:
    24         return (low,high,L[low])
    25     else:
    26         mid = (low + high) / 2
    27         (left_i,left_j,left_sum) = findMaxSubarray(L,low,mid)
    28         (right_i,right_j,right_sum) = findMaxSubarray(L,mid+1,high)
    29         (cross_i,cross_j,cross_sum) = findMaxCrossSubarray(L,low,mid,high)
    30 
    31         if left_sum >= right_sum and left_sum >= cross_sum:
    32             return (left_i,left_j,left_sum)
    33         elif right_sum >= left_sum and right_sum >= cross_sum:
    34             return (right_i,right_j,right_sum)
    35         else:
    36             return (cross_i,cross_j,cross_sum)
    37 
    38 if __name__ == "__main__":
    39     L = [3,-2,8,-3,-5,3]
    40     low = 0
    41     high = len(L) - 1
    42     print findMaxSubarray(L,low,high)

    参考:算法导论(p40)



    3. 最优解法

      要求最大连续和最大的子数组和,我们的第一个元素必须要大于0

    def FindMaxSubarray(L):
        lenght = len(L)
        Max_subarray_value = 0
        current = 0
        for item in L:
            current += item
            if current > 0:
    
                if current > Max_subarray_value:
    
                    Max_subarray_value = current
            else:
                current = 0
    
        return Max_subarray_value
    
    if __name__ == "__main__":
        L = [-1,2,-1,3]
        print FindMaxSubarray(L)

     

    转载于:https://www.cnblogs.com/lpworkstudyspace1992/p/7743405.html

    展开全文
  • 题目超链接 搜索旋转排序数组 搜索旋转排序数组II 寻找旋转排序数组的最小值 寻找旋转数组的最小值II 均为二分查找 搜索旋转排序数组 ... def search(self, nums: List[int], target: ... # 将数组一分为二,肯定为一.

    题目超链接

    1. 搜索旋转排序数组
    2. 搜索旋转排序数组II
    3. 寻找旋转排序数组的最小值
    4. 寻找旋转数组的最小值II
      均为二分查找

    1. 搜索旋转排序数组
    class Solution:
        def search(self, nums: List[int], target: int) -> int:
            if not nums: return -1
            n = len(nums)
            left, right = 0, n-1
            # 将数组一分为二,肯定为一部分有序,一部分无序,在有序部分进行查找target,没有的话则进行下一次二分
            while left <= right:
                mid = (left + right) // 2
                if nums[left] <= nums[mid]: # 有序部分为left-mid区间
                    if nums[left] <= target <= nums[mid]: # target在有序部分
                        return self.binarysearch(nums, left, mid+1, target)
                    else:
                        left = mid + 1
                else: # 有序部分为mid - right 区间
                    if nums[mid] <= target <= nums[right]:
                        return self.binarysearch(nums, mid, right+1, target)
                    else:
                        right = mid - 1
            return -1
    
        def binarysearch(self, nums, left, right, target):
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target: return mid
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1
    
    1. 搜索旋转排序数组II
    class Solution:
        def search(self, nums: List[int], target: int) -> int:
            if not nums: return False
            n = len(nums)
            left, right = 0, n-1
            # 将数组一分为二,肯定为一部分有序,一部分无序,在有序部分进行查找target,没有的话则进行下一次二分
            while left <= right:
                while left < right and nums[left] == nums[left+1]: left += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                mid = (left + right) // 2
                if nums[mid] == target: return True
                if nums[left] <= nums[mid]: # 有序部分为left-mid区间
                    if nums[left] <= target < nums[mid]: # target在有序部分
                        return self.binarysearch(nums, left, mid, target)
                    else:
                        left = mid + 1
                else: # 有序部分为mid - right 区间
                    if nums[mid] < target <= nums[right]:
                        return self.binarysearch(nums, mid, right+1, target)
                    else:
                        right = mid - 1
            return False
    
        def binarysearch(self, nums, left, right, target):
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target: return True
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return False
    

    1 2解法补充:写法相对简单一些,思想一样,较之上面写法多了几次判断

    class Solution:
        def search(self, nums: List[int], target: int) -> int:
            if not nums: return False
            n = len(nums)
            left, right = 0, n-1
            # 将数组一分为二,肯定为一部分有序,一部分无序,在有序部分进行查找target,没有的话则进行下一次二分
            while left <= right:
                while left < right and nums[left] == nums[left+1]: left += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                mid = (left + right) // 2
                if nums[mid] == target: return True
                if nums[left] <= nums[mid]: # 有序部分为left-mid区间
                    if nums[left] <= target < nums[mid]: # target在有序部分
                        right = mid - 1
                    else:
                        left = mid + 1
                else: # 有序部分为mid - right 区间
                    if nums[mid] < target <= nums[right]:
                        left = mid + 1
                    else:
                        right = mid - 1
            return False
    
    1. 寻找旋转排序数组的最小值
    class Solution:
        def findMin(self, nums: List[int]) -> int:
            if not nums: return False
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) // 2
                if nums[mid] < nums[right]:
                     right = mid
                else:
                    left = mid + 1
            return nums[left]
    
    1. 寻找旋转数组的最小值II
    class Solution:
        def findMin(self, nums: List[int]) -> int:
            if not nums: return False
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) // 2
                if nums[mid] < nums[right]:
                     right = mid
                elif nums[mid] > nums[right]:
                    left = mid + 1
                else:
                    right -= 1
            return nums[left]
    
    展开全文
  • 搜索旋转排序数组

    2021-03-16 10:38:16
      二分查找只能用于有序序列,旋转后的序列不是有序序列,但是用二分查找中的mid将数组一分为二后,总有一半的数组是有序的 (可用反证法证明)。可以在这部分有序数组中使用二分查找 代码: class Solution { ...
  • 数组中的逆序对

    2019-08-11 14:33:27
    思路:实际上是一个分治问题,不断将数组一分为二,直到数组中只有两个元素,统计逆序对个数,分别排序后进行合并,merge的时候计算合并的两个数组间的逆序对个数。类似归并排序的过程。 def ...
  • 这个题其实比较有意思,因为题目给出了...仔细去想一下的话,对于旋转排序数组,如果将这个数组一分为二,一定有一半是有序的,对于有序的这部分,判断一个target是否在有序数组中是非常容易的,如果在的话,那就...
  • 分治 将数组一分为二,则该最长数组有三种情况:1.在左子数组中,2.在右子数组中 3.跨越中间节点的子数组 递归地解决该问题,代码如下: int add(int a[],int fro,int re){ if(fro==re) return a[fro]; int ...
  • 通过一个数组实现两个栈(C语言)

    千次阅读 2018-04-17 20:06:01
    我们可以将一个数组一分为二,供两个栈使用。 也有另外一种虽然也是讲一个数组一分为二供两个栈使用,但在具体实现上有所不同。 牢记栈1的区间是[0,top1)的左闭右开区间,栈2的区间是[top2,max_size)的左闭右...
  • 二分法 在数组中寻找某一个值,通过将数组区间一分为二的方法,不断逼近目标值。 例 在一维有序数组中,查找与key值相等的元素,返回此元素是数组中的第几个元素。...//得到中间值,将数组一分为二
  • 二分法主要思想是将一个数组一分为二,每次查询都能将查询范围在上一次的基础上缩小一半。所以效率非常高。 下面是Java代码实现: import java.util.*; public class Main { public static void main...
  • 33. 搜索旋转排序数组

    2020-03-19 15:11:26
    数组一分为二,则一定有 一部分是有序的,一部分是无序的 4 5 6 7 0 1 2 如果nums[r] > nums[mid] 则右边一定有序 0 1 2 (7_mid 0 1 2_r) 如果 nums[l] < nums[mid] 则左边一定有序 4 5 6 7 4_l 5 6 7 0_...
  • 连续子数组最大和

    2018-09-10 20:53:24
    分治法Divide and Conquer Approach来解,这个分治法的思想就类似于二分搜索法,我们需要把数组一分为二,分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,求出的最大值分别和左右两边得出...
  • 分治法求数组的最大最小值

    千次阅读 2015-01-18 15:05:37
    分治法的思想就是每次将数组一分为二,分别求两部分的最大值与最小值,然后比较哪部分的更大和更小,最后得出整个数组的最大最小值。 源代码如下: /************************************************************...
  • 循环有序数组的查找笔记

    千次阅读 2016-02-22 22:03:21
    将一个循环有序数组一分为二,一定得到一个有序数组和另一个循环有序数组 2.长度不超过2的循环有序数组其实就是有序数组。 解答思路: 我们要先弄清楚这个循环有序数组的原数组是单调减的还是单调增。 http
  • 通过死循环不断地将数组一分为二,得到中间元素,然后目标元素与中间元素进行比对,当出位置等于末位置时,退出。 缺点:局限性很大,只能用于排好序了地数组 public class Search{ public static void main(String...
  • 前言:搜索是很多软件不可或缺的功能...思路:将原来的数组按照线程数进行分割,当有两个线程搜索元素时,可以将数组一分为二,让每个线程在指定的角标范围内搜索元素,当其中有一个线程搜索到元素则,立即将结果返回。
  • 1. PHP中的数组与其把PHP中的数组理解为我们狭义上的“数组”,我觉得还不妨把这个数组一分为二,一者为我们常规上的数组,一者为我们的Dictionary。2. 创建数组如果数组不存在,那么向数组中存放值将会创建数组。...
  • 思路:分治策略,将数组一分为二,最大子数组可能在左半,或右半,或横跨中间。不断分割,直到子问题可解,求出子数组,再逐步合并。 def Max_subarray(a,low,high): #初始输入的low和high应为0,len(a)-1 if ...
  • 数组中Arrays.sort的排序方法是什么?

    千次阅读 2018-06-15 17:41:16
    算法的思想:选择基准将数组一分为二,基准前面的比基准小,基准后面的比基准大,之后分别对这两部分继续之前的操作,已达到整个数组有序的目的。算法内容描述:先选择一个基准,指向数组开始的指针start和指向数组...
  • 021.数组的二分查找

    2015-11-02 17:16:48
    二分,顾名思义,就是在数组有序的前提下,将整个数组一分为二,从中间的数字开始比较。 比较无非就是三种情况: 1.中间数恰好等于比较数,这是运气最好的 一种情况,可以直接将中间数的下标返回。 2.中间数小于...
  • 题目描述:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中...优化方法是分治法,把数组一分为二子数组,再分为子数组,直到为一个数字是一个数组的...
  • 如果数组是排序比较平稳的话,那么不一定把数组一分为二来比较,可以按照图上分数来确定中间值再比较
  • 归并排序 首先我们来回忆一下归并排序的主要思想: 首先考虑如何让将两个有序子...通过不断将数组一分为二,直到每个子序列只剩一个元素的时候,子序列就是有序的了,这样一来,我们就可以实现子有序序列的合...
  • 可以根据这种想法,把数组一分为二,左边的子数组异或得到一个数,右边的子数组 异或得到一个数,左右子树组的划分,首先把数组异或得到两个不同数的异或结果,找到他们最右边的1出现的位置,根据对应为为1,来划分...
  • 方法2:从中间开始将数组一分为二,左边为栈1,右边为栈2; 方法3:栈1从头开始增长,栈2从尾向头进行增长,相遇后,增容; 优劣分析:***建议:*** 如果要快速实现逻辑,可以不用实现成动态增长内存的版本,直接...
  • 1. PHP中的数组 与其把PHP中的数组理解为我们狭义上的“数组”,我觉得还不妨把这个数组一分为二,一者为我们常规上的数组,一者为我们的Dictionary。 2. 创建数组 如果数组不存在,那么向数组中存放值将会创建数组...
  • 数组的左边,比分割值大的数值放在数组的右边,这样分割值的位置就被确定了,数组一分为二,我们只需要排序 前一半数组和后一半数组即可,复杂度直接减半,采用这种思想不断递归,最终分割的只剩下一个元素,整个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 438
精华内容 175
关键字:

数组一分为二