1. 数组的全排列：
回溯法
class Solution {
public List<List<Integer>> permute(int[] nums) {
LinkedList<List<Integer>> res = new LinkedList<List<Integer>>();
if (nums == null || nums.length == 0)
return res;
Helper(res, new LinkedList<Integer>(), nums, new HashSet<Integer>());
return res;
}
private void Helper(List<List<Integer>> res, List<Integer> curlist, int[] nums,
HashSet<Integer> set){
if (curlist.size() == nums.length)
res.add(new LinkedList<Integer>(curlist));
else{
for (int i = 0; i < nums.length; i++){ //对每个数而言
if (set.contains(nums[i]))
continue;
//加数
curlist.add(nums[i]);
set.add(nums[i]);
Helper(res, curlist, nums, set); //下层的执行完，要把刚刚加进的数字弹出
//删数
set.remove(nums[i]);
int last = curlist.size() - 1;
curlist.remove(last);
}
}
}
}
class Solution {
public List<List<Integer>> permute(int[] nums) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0)
return res;
Helper(nums, res, new ArrayList<Integer>(), new HashSet<Integer>());
return res;
}
private void Helper(int[] nums, ArrayList<List<Integer>> res, ArrayList<Integer> curlist,
HashSet<Integer> set){
if (nums.length == curlist.size())
res.add(new ArrayList<Integer>(curlist));
else{
for (int i = 0; i < nums.length; i++){
if (set.contains(nums[i]))
continue;
set.add(nums[i]);
curlist.add(nums[i]);
Helper(nums, res, curlist, set);
set.remove(nums[i]);
curlist.remove(curlist.size() - 1);
}
}
}
}
2. 去重的全排列：
先排序 然后只需要在每个元素入数组之前判断：这个索引之前没用过&&这个数和上个数不一样
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0)
return null;
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<List<Integer>>();
Helper(nums, new boolean[nums.length], new LinkedList<Integer>(), res);
return res;
}
private void Helper(int[] nums, boolean[] used, List<Integer> curlist, List<List<Integer>> res){
if (curlist.size() == nums.length)
res.add(new ArrayList<Integer>(curlist));
else{
int pre = nums[0] - 1; //这个目的： 记录前一个数
for (int idx = 0; idx < nums.length; idx ++){
if (used[idx] == false && (nums[idx] != pre)) {
//索引没被用过，而且索引上的数字和前一个数不一样
pre = nums[idx];
curlist.add(nums[idx]);
used[idx] = true;
Helper(nums, used, curlist, res);
curlist.remove(curlist.size() - 1);
used[idx] = false;
}
}
}
}
}
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0)
return null;
Arrays.sort(nums);
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
Helper(res, nums, new boolean[nums.length], new ArrayList<Integer>());
return res;
}
private void Helper(ArrayList<List<Integer>> res, int[] nums, boolean[] use,
ArrayList<Integer> curlist){
if (curlist.size() == nums.length)
res.add(new ArrayList<Integer>(curlist));
else{
int pre = nums[0] - 1;
for (int i = 0; i < nums.length; i++){
if (use[i] == false && pre != nums[i]){
pre = nums[i];
use[i] = true;
curlist.add(nums[i]);
Helper(res, nums, use, curlist);
curlist.remove(curlist.size() - 1); //往上回溯时候 去掉后面的尾巴
use[i] = false;
}
}
}
}
}
3. 最长回文串：
class Solution {
public int longestPalindrome(String s) {
if(s == null || s.length() == 0)
return 0;
int[] count = new int[128];
int res = 0;
for (char c : s.toCharArray()){
count[c] ++;
}
for (int val : count){
res += val/2 *2;
if (val%2 == 1 && res%2 == 0) //如果想当中心
res++;
}
return res;
}
}
4. 最长回文子串：
中心拓展法，对每个字母进行中心拓展。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1)
return "";
int start = 0, end = 0;
int len = 0;
for(int i = 0; i < s.length(); i++){
int len1 = expand(s, i, i);
int len2 = expand(s, i, i+1);
len = Math.max(len1, len2);
if (len > (end - start)){
start = i - (len - 1)/2;
end = i + (len/2);
}
}
return s.substring(start,end + 1);
}
private int expand(String s, int l, int r){
int i = l, j = r;
while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
i --;
j ++;
}
return j - i - 1;
}
}
5. 二叉树展开为链表
后序递归，先右后左。
class Solution {
TreeNode pre = null;
public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = pre;
root.left = null;
pre = root;
}
}
6. 最长递增子序列：
动态规划，
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) { //对i之前的数遍历：如果i比j上的数大，那就看maxval能不能取更大的
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = Math.max(maxans, dp[i]); //每个i结束，都看看能不能当最大的
}
return maxans;
}
}
//我的方法：
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int[] dp = new int[nums.length];
dp[0] = 1;
int res = 1;
for (int i = 1; i < nums.length; i++){
int maxFori = 0;
for (int j = 0; j < i; j++){
if(nums[i] > nums[j])
maxFori = Math.max(maxFori, dp[j]);
}
dp[i] = maxFori + 1;
res = Math.max(res, dp[i]);
}
return res;
}
}
7. 最长公共子数组：
从后往前
class Solution {
public int findLength(int[] A, int[] B) {
int ans = 0;
int[][] memo = new int[A.length + 1][B.length + 1];
//从后往前
for (int i = A.length - 1; i >= 0; --i) {
for (int j = B.length - 1; j >= 0; --j) {
if (A[i] == B[j]) {
memo[i][j] = memo[i+1][j+1] + 1;
if (ans < memo[i][j])
ans = memo[i][j];
}
}
}
return ans;
}
}
8. 快速幂：
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
double current_product = x;
for (long i = N; i > 0; i /= 2) {
if ((i % 2) == 1) {
ans = ans * current_product; //注意这里：不管n是奇数还是偶数，都会走这一步，因为最后i都是1，如果n是奇数，那么就在第一步时候多乘个自己
}
current_product = current_product * current_product;
}
return ans;
}
};
9. 合并k个有序链表
使用优先队列
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
PriorityQueue<ListNode> qu = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
if (o1.val < o2.val) return -1;
else if (o1.val == o2.val) return 0;
else return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode p = dummy;
for (ListNode node: lists){ //先把头放进去
if (node != null)
qu.add(node);
}
//出队 下一个不空入队
while(!qu.isEmpty()){
p.next = qu.poll();
p = p.next;
if (p.next != null) qu.add(p.next);
}
return dummy.next;
}
} 
京公网安备 11010502036488号