leetcode刷题总结451-500

451. 根据字符出现频率排序

  描述:

    

   思路:通过hashmap存储,然后对List<enttry>排序。

452. 用最少数量的箭引爆气球

  描述:

    

   思路:按照第一个维度进行排序,采取贪婪策略。获取最大的结束节点(这样箭的数量才最少)

453. 最小移动次数使数组元素相等

  描述:

    

   思路:题目可等于找到最大的数使其减1,不断循环,-1的次数。

454. 四数相加 II

  描述:

    

   思路:将4数相加看为 2个  两数相加。时间复杂度为n^2.   (我认为还可以通过动态规划。在n的时间复杂下完成)

455. 分发饼干

  描述:

    

   思路:贪心

456. 132模式‘ 

  描述:

      

   思路:从后往前,当元素比栈顶大的时候,栈弹出,找到了次大的元素。然后继续遍历找比次大元素小的元素即可。

457. 环形数组循环

  描述:

    

   思路:快指针慢指针。

459. 重复的子字符串

  描述:

    

   思路:源字符串s至少是子串的2倍,那么S=s+s,去除首尾之后,看s是否在S中。

460. LFU缓存

  描述:LRU:最近最少使用;LFU:最不经常使用

  思路:LRU是按照时间来进行的,LFU是按照次数,需要对node对象增加一个频率字段

462. 最少移动次数使数组元素相等 II

  描述:

    

   思路:找到中位数(快排的思想),然后其余每个数-中位数的和。

463. 岛屿的周长

466. 统计重复个数

  描述:

    

   思路:先不用去组装S1,S2。判断一个s1包含多少个s2,或者多少s1包含一个s2.。然后按照倍数的关系进行计算。

472. 连接词

  描述:

    

   思路:前缀树即可。

473. 火柴拼正方形

  描述:

    

   思路:先计算出正方形的边长。然后递归

474. 一和零

  描述:

    

   思路:动态规划 01背包问题。dp[i][m][n]表示对于0-i区间的字符串集合的所能拼出的最大次数。==dp[i-1][m][n]或者dp[i-1][m-000][n-1111]+1

475. 供暖器

  描述:

    

   思路:计算每个房子到每个供暖期距离最大值。二分。对于每个房子来说,先找到供暖期的中间,通过判断中间不断缩小二分。

476. 数字的补数

  描述:

    

   思路:和1异或。

477. 汉明距离总和

  描述:

    

   思路:按照位计算。然后每个位进累加。某一个位的汉明距离之和为  0的个数*1的个数。

479. 最大回文数乘积

  描述:

    

   思路:可以从这个例子出发,从99*99逐渐减少1判断。

480. 滑动窗口中位数

  描述:

    

   思路:参考 之前的 数据流的滑动窗口,此题无非就增加了一个删除。

485. 最大连续1的个数

  描述:

    

   思路:双指针。

486. 预测赢家

  描述:

    

   思路:动态规划。dp[i][j]表示最大的差值分数,dp[0][leng-1]大于0表示itrue.

491. 递增子序列

  描述:

    

  思路:递归。set

492. 构造矩形

  描述:

    

   思路:从正方正边上逐渐缩小。

493. 翻转对

   描述:

    

   思路:分治。思想和剑指offer中的逆序对 相同。

494. 目标和

  描述:

    

   思路:动态规划。[-5,5]进行填充。

495. 提莫攻击

  描述:

    

   思路:线性时间就可以。判断。

496. 下一个更大元素 I

  描述:

    

   思路:单调栈。将nums2的元素压栈。当栈顶元素小于准备压入栈的,那么弹出[1,3]的hash。然后num1去查找hash。

498. 对角线遍历

  描述:

    

   思路:找到遍历的点.1,2,7,6,9.

500. 键盘行

   描述:

      

     思路:判断即可。

原文地址:https://www.cnblogs.com/dhName/p/13288682.html