Chinaunix首页 | 论坛 | 博客
  • 博客访问: 104525
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 407
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-27 13:42
文章分类

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: Java

2015-02-14 00:44:58

-- Minimum Path Sum ?
    >> 题目:从二维数组中找出从左上角到右下角的最短路径
    >> 解题思路:动态规划

-- Merge Sorted Array 
    >> 题目:将两个数组合并
    >> 解题思路:合并

-- Merge Intervals ?
    
-- Median of Two Sorted Arrays ?

-- Maximum Subarray 
     >> 题目:求子数组的最大和
     >> 解题思路:记录历史值,需要记录两个一个是以i结尾的子数组和的最大值,另一个是i以内的子数组最大值  。每一步都需要更新,注意后者更新需要比较三个数,所以先比较前者。

点击(此处)折叠或打开

  1.     public int maxSubArray(int[] A) {
  2.         int []all = new int[A.length];
  3.         int []end = new int[A.length];
  4.         all[0] = A[0];
  5.         end[0] = A[0];
  6.         for (int i = 1; i < A.length; i++) {
  7.             end[i] = Math.max(A[i], end[i - 1] + A[i]);
  8.             all[i] = Math.max(all[i - 1], end[i]); // 其实是需要比较三个数的,但是end已经计算了两个数
  9.         }
  10.         return all[A.length - 1];
  11.     }


-- Maximum Product Subarray  ?

-- Maximal Rectangle?

-- Majority Element ?

-- Longest Consecutive Sequence?

-- Largest Rectangle in Histogram ?

-- Jump Game ?

-- Jump Game II ?

-- Insert Interval ?

-- First Missing Positive 
    >> 题目:从无序数组中找到第一个没有出现的正数,要求试驾复杂度为n,空间为1
    >> 解题思路:排序(类似于桶排序,但是时间复杂度略高)。查找

-- Find Peak Element 
    >> 题目:查找数组中的峰值
    >> 解题思路:遍历,注意边界处理

点击(此处)折叠或打开

  1.     public int findPeakElement(int[] num) {
  2.         boolean increase_flag = false;
  3.         if (num.length == 0)
  4.             return -1;
  5.         if (num.length == 1)
  6.             return 0;
  7.         if (num[0] > num[1])
  8.             return 0;
  9.         for (int i = 1; i < num.length; i++) {
  10.             if (num[i] > num[i - 1]) {
  11.                 increase_flag = true;
  12.                 if (i == num.length - 1)
  13.                     return i;
  14.             }
  15.             if (increase_flag) {
  16.                 if (num[i] < num[i - 1])
  17.                     return i - 1;
  18.                 else {

  19.                 }
  20.             }
  21.         }
  22.         return -1;
  23.     }


-- Find Minimum in Rotated Sorted Array
    >> 题目:在循环右移后的数组中找最小值
    >> 解题思路:二分查找变种

点击(此处)折叠或打开

  1.     public int findMin(int[] num) {
  2.         if (num == null || num.length == 0)
  3.             return 0;
  4.         int l = 0;
  5.         int r = num.length - 1;
  6.         int min = num[0];
  7.         while (l < r - 1) {
  8.             int m = (l + r) / 2;
  9.             if (num[l] < num[m]) {
  10.                 min = Math.min(num[l], min);
  11.                 l = m + 1;
  12.             } else if (num[l] > num[m]) {
  13.                 min = Math.min(num[m], min);
  14.                 r = m - 1;
  15.             } else {
  16.                 l++;
  17.             }
  18.         }
  19.         min = Math.min(num[r], min);
  20.         min = Math.min(num[l], min);
  21.         return min;
  22.     }


-- Container With Most Water  
    >> 题目:在一个坐标系中,给出若干点,每个点做x轴的垂直线,然后求任何两条线形成的容器中能盛下最多水的情况
    >> 解题思路:刚开始看到这道题的时候有点不清楚题目的意思,以为中间部分也是需要计算的。原来是不需要啊,那就简单了

点击(此处)折叠或打开

  1.     public int maxArea(int[] height) {
  2.         if (height == null || height.length < 2) {
  3.             return 0;
  4.         }
  5.         int i = 0, j = height.length - 1;
  6.         int max = 0, temp = 0;
  7.         
  8.         while (i < j) {
  9.             temp = Math.min(height[j], height[i]) * (j - i);
  10.             max = Math.max(temp, max);
  11.             
  12.             if (height[i] < height[j]) {
  13.                 i++;
  14.             } else {
  15.                 j--;
  16.             }
  17.             
  18.         }
  19.         return max;
  20.     }





阅读(382) | 评论(0) | 转发(0) |
0

上一篇:LinkedList例题分析

下一篇:Math例题分析

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册