链表问题
原创
链表问题
一、next指针的赋值方法
二、链表反转
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null ) return head;
ListNode cur = head;
ListNode next = null;
ListNode pre = null;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}三、链表的复制问题
public RandomListNode Clone(RandomListNode pHead)
{
if (pHead == null) return pHead;
RandomListNode cur = pHead;
RandomListNode next = null;
while( cur != null){
next = cur.next;
cur.next = new RandomListNode(cur.label);
cur.next.next = next;
cur = next;
}
cur = pHead;
RandomListNode copyNode = null;
while(cur != null){
next = cur.next.next;
copyNode = cur.next;
copyNode.random = cur.random != null ? cur.random.next : null;
cur = next;
}
cur = pHead;
RandomListNode res = cur.next;
copyNode = cur.next;
while(cur != null){
next = cur.next.next;
copyNode = cur.next;
copyNode.next = next!= null? next.next : null;
cur.next = next;
cur = next;
}
return res;
}24.Swap Nodes in Pairs
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode pre = new ListNode(0);
ListNode dummy = pre;
pre.next = head;
ListNode next1 = null;
ListNode next2 = null;
ListNode next3 = null;
while(pre.next != null && pre.next.next != null){
next1 = pre.next;
next2 = next1.next;
next3 = next2.next;
pre.next = next2;
next2.next = next1;
next1.next = next3;
pre = next1;
}
return dummy.next;
}贪心算法
455.Assign Cookies
public int findContentChildren(int[] g, int[] s) {
// [1,2,3], [1,1]
// child cookies
// [1,2], [1,2,3]
// child cookies
Arrays.sort(s);
Arrays.sort(g);
int res = 0;
int index = 0;
int i = 0;
while(i < g.length && index < s.length){
if(g[i] <= s[index]){
res++;
i++;
}
index++;
}
return res;
}435.Non-overlapping Intervals
class myComparator implements Comparator<Interval>{
@Override
public int compare(Interval arr1, Interval arr2){
return arr1.end - arr2.end;
}
}
public int eraseOverlapIntervals(Interval[] intervals) {
if(intervals == null || intervals.length < 2) return 0;
Arrays.sort(intervals, new myComparator());
int count = 1;
int preEnd = intervals[0].end;
for(int i = 1; i < intervals.length; i++){
if(intervals[i].start < preEnd){
continue;
}
preEnd = intervals[i].end;
count++;
}
return intervals.length - count;
}452.Minimum Number of Arrows to Burst Balloons
class myCom implements Comparator<int []>{
@Override
public int compare(int [] arr1, int[] arr2){
return arr1[1] - arr2[1];
}
}
public int findMinArrowShots(int[][] points) {
if(points == null || points.length == 0) return 0;
Arrays.sort(points, new myCom());
int count = 1;
int preEnd = points[0][1];
for(int i = 1; i < points.length; i++){
if(preEnd >= points[i][0]){
continue;
}
count++;
preEnd = points[i][1];
}
return count;
}406.Queue Reconstruction by Height(根据身高和序号重组队列)
身高降序，k增序
public int[][] reconstructQueue(int[][] people) {
if(people == null) return people;
Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
List<int[]> queue = new ArrayList<>();
for(int[] p : people){
queue.add(p[1],p); // add(index, object);
}
return queue.toArray(new int[queue.size()][]);
}763.Partition Labels（分隔字符串使同种字符出现在一起）
A stringSof lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
public List<Integer> partitionLabels(String S) {
List<Integer> list = new LinkedList<>();
char[] chars = S.toCharArray();
int[] index = new int[26];
for(int i = 0; i < chars.length; i++){
index[chars[i] - 'a'] = i;
}
int lastIndex = 0;
int j = 0;
for(int i = 0; i < chars.length; i++){
j = Math.max(index[chars[i] - 'a'], j);
if(i == j) {
list.add(j - lastIndex + 1);
j = j + 1;
lastIndex = j;
}
}
return list;
}605.Can Place Flowers
题目描述：花朵之间至少需要一个单位的间隔，求解是否能种下 n 朵花。
public boolean canPlaceFlowers(int[] arr, int n) {
int pre = 0;
int next = arr.length -1;
int count= 0;
for(int i = 0; i < arr.length; i++){
if(arr[i] == 1) continue;
pre = i == 0 ? 0 : arr[i - 1];
next = i == arr.length - 1 ? 0 : arr[i + 1];
if(pre == 0 && next == 0){
count++;
arr[i] = 1;
}
}
return count >= n;
}665.Non-decreasing Array
题目描述：判断一个数组能不能只修改一个数就成为非递减数组。
在出现 nums[i] < nums[i - 1] 时，需要考虑的是应该修改数组的哪个数，使得本次修改能使 i 之前的数组成为非递减数组，并且 不影响后续的操作 。优先考虑令 nums[i - 1] = nums[i]，因为如果修改 nums[i] = nums[i - 1] 的话，那么 nums[i] 这个数会变大，就有可能比 nums[i + 1] 大，从而影响了后续操作。还有一个比较特别的情况就是 nums[i] < nums[i - 2]，只修改 nums[i - 1] = nums[i] 不能使数组成为非递减数组，只能修改 nums[i] = nums[i - 1]。
public boolean checkPossibility(int[] nums) {
if(nums == null) return false;
int count = 0;
for(int i = 1; i < nums.length; i++){
if(nums[i] >= nums[i - 1]){
continue;
}
count++;
if( i - 2 >= 0 && nums[i - 2] > nums[i]){
nums[i] = nums[i -1];
}else{
nums[i -1] = nums[i];
}
}
return count <= 1;
}动态规划
198.House Robber
public int rob(int[] nums) {
if(nums == null || nums.length < 1) return 0;
// pre1 pre2 cur
int pre1 = 0;
int pre2 = 0;
int cur = 0;
for(int i = 0; i < nums.length; i++){
cur = Math.max(pre1 + nums[i], pre2);
pre1 = pre2;
pre2 = cur;
}
return cur;
} 213.House Robber II
public int rob(int[] nums) {
if(nums == null || nums.length < 1) return 0;
if(nums.length < 2) return nums[0];
return Math.max(rob(nums, 0, nums.length - 2) , rob(nums, 1, nums.length - 1));
}
private static int rob(int[] nums, int start, int end){
// pre1 pre2 cur
int pre1 = 0;
int pre2 = 0;
int cur = 0;
for(int i = start; i <= end; i++){
cur = Math.max(pre1 + nums[i], pre2);
pre1 = pre2;
pre2 = cur;
}
return cur;
}413.Arithmetic Slices
dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。
在 A[i] - A[i - 1] == A[i - 1] - A[i - 2] 的条件下，{A[i - 2], A[i - 1], A[i]} 是一个等差递增子区间。如果 {A[i - 3], A[i - 2], A[i - 1]} 是一个等差递增子区间，那么 {A[i - 3], A[i - 2], A[i - 1], A[i]} 也是等差递增子区间，dp[i] = dp[i-1] + 1。
public int numberOfArithmeticSlices(int[] A) {
if(A == null || A.length < 3) return 0;
int[] dp = new int[A.length];
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i < A.length; i++){
if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){
dp[i] = dp[i - 1] + 1;
}
}
int total = 0;
for(int i = 0; i < dp.length; i++){
total += dp[i];
}
return total;
}343.Integer Break
public int integerBreak(int n) {
if(n <= 0) return 0;
// dp[i] = max(dp[i], j * dp[i - j], j *(i - j))
int[] dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j < i; j++){
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j *(i - j)));
}
}
return dp[n];
}300.Longest Increasing Subsequence
dp[i] = dp[j] + 1 ( j < i && arr[j] < arr[i])
public int lengthOfLIS(int[] arr) {
if(arr == null || arr.length < 1) return 0;
// dp[i] = dp[j] + 1 ( j < i && arr[j] < arr[i])
int[] dp = new int[arr.length];
for(int i = 0; i < arr.length; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(arr[j] < arr[i]){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
}
int res = dp[0];
for(int i = 0; i < dp.length; i++){
if(res < dp[i]) res = dp[i];
}
return res;
}一组整数对能够构成的最长链
public int findLongestChain(int[][] pairs) {
if(pairs == null || pairs.length < 1 || pairs[0].length < 1) return 0;
Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
int n = pairs.length;
int [] dp = new int[n];
int res = 0;
for(int i = 0; i < pairs.length; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(pairs[i][0] > pairs[j][1]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}376.Wiggle Subsequence
public int wiggleMaxLength(int[] nums) {
if(nums == null || nums.length < 1) return 0;
int up = 1;
int down = 1;
for(int i = 1; i < nums.length; i++){
if(nums[i] > nums[i-1]){
up = down + 1;
}else if(nums[i] < nums[i - 1]){
down = up + 1;
}
}
return Math.max(up, down);
}0-1 背包
有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。
定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：
- 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
- 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。
第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
public int knapsack(int W, int N, int[] weights, int[] values) {
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = 1; j <= W; j++) {
if (j >= w) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}230.Kth Smallest Element in a BST
public int kthSmallest(TreeNode root, int k) {
int[] m = new int[2];
m[0] = k;
helper(root, m);
return m[1];
}
public void helper(TreeNode root, int[] k){
if(root == null || k[0] < 0) return;
helper(root.left, k);
k[0]--;
if(k[0] == 0) {
k[1] = root.val;
return;
}
helper(root.right, k);
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录