贪婪算法的小例子记录

电玩女神 2022-05-18 23:35 131阅读 0赞

一 定义

贪心算法（又称贪婪算法）是指，在对[问题求解][Link 1]时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部[最优解][Link 2]。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关

二 例子

(1)求字符串中最大长度的回文串

这是在leetcode上面看到的题目，里面有个大神使用的贪婪算法解决，很厉害，这里记录一下

原题：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 长度最长为1000。  
    输入: "babad"  
    输出: "bab"  
    注意: "aba"也是有效答案

贪婪算法解答：

/**
    	 * 求最大回文串的贪婪算法（每次判断，获取最优解）
    	 * 思想：
    	 * 比如在字符串中，有某个回文串x，长度为max
    	 * 那么，在读入一个字符时，最优解应该是x的前一个字符和
    	 * 后一个字符和x一起组成回文串，就是i-max-1到i，如果
    	 * 是的话，max的值要加2
    	 * 如果上一步不是回文串，就判断x和x的下一个字符是不是回文
    	 * 串，如果是，max的值要加1
    	 * 如果上述两个条件都不满足，则继续读入字符，且判断字符串
    	 * 的长度最少也要是max+1的，因为已经有一个max长度的
    	 * 回文了，判断字符串的长度小于或等于max的话，没有意义
    	 * 每一步判断，都要把回文串的开始和结束位置记下，以便后面
    	 * 进行切割
    	 */
    	public static String longestPalindrome2(String s) {
    	    char[] ca = s.toCharArray();
    	    int rs = 0, re = 0;
    	    //已经获取到的最大回文串的长度
    	    int max = 0;
    	    for(int i = 0; i < ca.length; i++) {
    	    	//注意的i-max-1到i,是比当前max值大2的长度。如果有这样的回文串，max直接加2
    	        if(isPalindrome(ca, i - max - 1, i)) {
    	            rs = i - max - 1; re = i;
    	            max += 2;
    	        } 
    	        //注意的i-max到i,是比当前max值大1的长度。如果有这样的回文串，max直接加1
    	        else if(isPalindrome(ca, i - max, i)) {
    	            rs = i - max; re = i;
    	            max += 1;
    	        }
    	    }
    	    return s.substring(rs, re + 1);
    	}
    
    	//判断是否是回文串
    	private static boolean isPalindrome(char[] ca, int s, int e) {
    	    if(s < 0) return false;
    	    
    	    while(s < e) {
    	        if(ca[s++] != ca[e--]) return false;
    	    }
    	    return true;
    	}

[Link 1]: https://baike.baidu.com/item/%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3
[Link 2]: https://baike.baidu.com/item/%E6%9C%80%E4%BC%98%E8%A7%A3