47. 全排列 II
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
List<Integer> track = new ArrayList<>();
backtrack(nums,track,0,used);
return res;
}
public void backtrack(int[] nums,List<Integer> track,int index,boolean[] used){
if(index==nums.length){
res.add(new ArrayList(track));
return;
}
for(int i = 0;i < nums.length;i++){
if(used[i]) continue;
if(i > 0 && nums[i]==nums[i-1] && !used[i-1]){
continue;
}
track.add(nums[i]);
used[i] = true;
backtrack(nums,track,index+1,used);
used[i] = false;
track.remove(track.size()-1);
}
}
}
234. 回文链表
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null || head.next == null) return true;
ListNode fast = head,slow = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
slow = reverse(slow.next);
while(slow != null){
if(head.val != slow.val){
return false;
}
head = head.next;
slow = slow.next;
}
return true;
}
private ListNode reverse(ListNode head){
// 递归到最后一个节点,返回新的新的头结点
if (head.next == null) {
return head;
}
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
62. 不同路径
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 1;
else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
你知道的越多,你不知道的越多。