Here is my email : [email protected]
Weclome to Yvonne's Leetcode's Link.
My NoteBook for the Basic Knowledge
11. Container With Most Water
15. 3Sum.
56. Merge Intervals.
704. Binary Search
509. Fibonacci Number.
70. Climbing Stairs.
746. Min Cost Climbing Stairs.
5. Longest Palindromic Substring
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
g =[[float('inf')] * n for _ in range(n)]
for x, y, time in times:
g[x-1][y-1] = time
dist = [float('inf')] * n
dist[ k - 1] = 0
used = [False] * n
for _ in range(n):
x = -1
# 0:T 1:F 2:F 3:F
for y, u in enumerate(used):
if not u and (x == -1 or dist[y] < dist[x]):
x = y
used[x] = True
for y, time in enumerate(g[x]):
dist[y] = min(dist[y], dist[x] + time)
ans = max(dist)
return ans if ans < float('inf') else -1class Solution {
public boolean isValid(String s) {
if(s.length()%2!=0) return false;
Stack<Character> st = new Stack<>();
for(int i = 0; i < s.length(); i ++){
Character word = s.charAt(i);
if(word == '{' ||word == '(' || word == '[' ){
st.push(word);
}else{
if(st.isEmpty()) return false;
Character word2 = st.pop();
if((word=='}' && word2!='{') || (word==']' && word2 != '[') || (word==')' && word2 != '(')){
return false;
}
}
}
if(st.isEmpty()) return true;
else return false;
}
} class Solution {
public int fib(int n) {
int dp [] = new int[n+1];
if (n<=1) return n;
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++){
//System.out.print(dp[i]);
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = nums.length - 1;
int num1 = nums[i];
while(left < right){
int num2 = nums[left], num3 = nums[right];
int sum = num1 + num2 + num3;
if(left -1 > i && nums[left -1] == nums[left]){
left++;
continue;
}
if(sum == 0) {
ans.add(Arrays.asList(num1, num2, num3));
left++;
}
else if(sum > 0) right--;
else if(sum < 0) left++;
}
}
return ans;
}
}/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dammy = new ListNode(0);
ListNode cur = dammy;
while (list1!= null|| list2!=null){
if(list1 == null){
cur.next = list2;
break;
}else if(list2 == null){
cur.next = list1;
break;
}
if(list1.val <= list2.val){
cur.next = list1;
list1 = list1.next;
}else{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
return dammy.next;
}
}class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length -1, sum = 0;
while(left < right){
sum = Math.max(sum, (right - left) * Math.min(height[right], height[left]));
if(height[right] < height[left]){
right--;
}else{
left++;
}
}
return sum;
}
}TreeMap is a class in Java that implements the Map interface and is backed by a red-black tree data structure. It is used to store key-value pairs, where the keys must be unique and are sorted in ascending order. The keys are used to access the values stored in the map.
In other words, a TreeMap is a type of map that stores key-value pairs and allows you to perform operations such as insertion, deletion, and retrieval of values based on the keys. It provides an efficient way to store data in a key-value format, while maintaining the order of the keys.
Some of the features of a TreeMap in Java include:
class Solution {
public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int[] a : items1){
if(map.containsKey(a[0])){
map.put(a[0],map.get(a[0])+a[1]);
}else{
map.put(a[0],a[1]);
}
}
for(int[] b : items2){
if(map.containsKey(b[0])){
map.put(b[0],map.get(b[0])+b[1]);
}else{
map.put(b[0],b[1]);
}
}
List<List<Integer>> ans = new ArrayList<>();
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
List<Integer> list = new ArrayList<>();
list.add(entry.getKey());
list.add(entry.getValue());
ans.add(list);
}
return ans;
}
}Cleaner Code
class Solution {
public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int[] item : items1) {
map.put(item[0], map.getOrDefault(item[0], 0) + item[1]);
}
for (int[] item : items2) {
map.put(item[0], map.getOrDefault(item[0], 0) + item[1]);
}
List<List<Integer>> ans = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
ans.add(new ArrayList<>(Arrays.asList(entry.getKey(), entry.getValue())));
}
return ans;
}
}class Solution {
public String longestCommonPrefix(String[] strs) {
char[] com = strs[0].toCharArray();
for(int i = 1; i < strs.length; i++){
char[] str = strs[i].toCharArray();
int len = Math.min(str.length, com.length);
if (len == 0) return new String("");
for(int j = 0; j < len; j++){
if(str[j] != com[j]){
//System.out.println(j);
com = Arrays.copyOf(com, j);
break;
}else if(j== len -1){
com = Arrays.copyOf(com, j+1);
}
}
}
return new String(com);
}
}class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if(len < 2) return s;
int maxLen = 1;
int begin = 0;
//dp[i][j] 表示s[i..j]是否是回文串
boolean[][] dp = new boolean[len][len];
for(int i = 0; i < len; i++) dp[i][i] = true;
char[] charArray = s.toCharArray();
for( int L = 2; L <= len; L++){
for(int i = 0; i < len; i++){
int j = L + i - 1;
if(j >= len){
break;
}
if(charArray[i] != charArray[j]){
dp[i][j] = false;
}else{
if(j - i < 3){
dp[i][j] = true;
}else{
dp[i][j] = dp[i+1][j-1];
}
}
if(dp[i][j] && j - i+ 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left, right = 0, len(nums) -1
while left <= right:
mid = left + (right - left)// 2
num = nums[mid]
if num == target:
return mid
elif num > target:
right = mid - 1
else:
left = mid + 1
return -1class Solution {
public int climbStairs(int n) {
if(n <= 2) return n;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}class Solution {
public boolean isValid(String s) {
Stack<Character> memo = new Stack<>();
for(char cur : s.toCharArray()){
if(cur=='(' || cur =='[' || cur == '{') memo.push(cur);
else if(cur ==')'){
if(memo.isEmpty() || memo.pop() != '(') return false;
}
else if(cur ==']'){
if(memo.isEmpty() || memo.pop() != '[') return false;
}
else if(cur =='}'){
if(memo.isEmpty() || memo.pop() != '{') return false;
}
}
return memo.isEmpty();
}
}
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[][] dp = new int[cost.length+1][2];
dp[0][0] = 0;
dp[1][0] = cost[0];
dp[0][1] = 0;
dp[1][1] = 0;
for(int i = 2; i <= cost.length; i++){
dp[i][0] = Math.min(dp[i-1][0]+cost[i-1],dp[i-2][0]+cost[i-2]);
dp[i][1] = Math.min(dp[i-1][1]+cost[i-1],dp[i-2][1]+cost[i-2]);
}
return Math.min(dp[cost.length][0],dp[cost.length][1]);
}
}Backtracking is a general algorithm for finding all (or some) solutions to a problem incrementally by trying out potential solutions, and abandoning a potential solution as soon as it proves to be unfeasible. It is typically used for problems that can be broken down into smaller subproblems, where the problem is to find a solution among all possible combinations of the subproblems.
Backtracking is commonly used to solve several types of problems, including:
Combination problems: finding all possible combinations of N elements, subject to certain rules
77. Combinations
Cutting problems: finding all possible ways of cutting a string, subject to certain rules.
Subset problems: finding all possible subsets of N elements that meet certain conditions
Permutation problems: finding all possible permutations of N elements, subject to certain rules
Chessboard problems: solving problems like the N-Queens problem, where the goal is to place N queens on a chessboard so that no two queens attack each other.
These problems can all be solved using backtracking by incrementally constructing a solution, and checking the feasibility of each partial solution before proceeding to the next step.
Public void backtracking(){
}Public void backtracking(){
if( Termination condition ){
Store the Result
return;
}Public void backtracking(){
if( Termination condition ){
Store the Result
return;
}
for ( The same layer in the tree) {
Process the node;
Backtracking (path) //Recursion
backtracking
}
} Design patterns are reusable solutions to common problems that arise in software development. They provide a way to organize and structure code in a way that makes it more maintainable, scalable, and reusable.
Design patterns are not specific to any programming language, and they can be applied to a wide range of software development projects. They provide a common vocabulary and a shared understanding among developers, making it easier for teams to work together on complex projects.
Design patterns are categorized into several groups, including creational patterns, structural patterns, and behavioral patterns. Creational patterns focus on object creation, structural patterns focus on object composition, and behavioral patterns focus on communication between objects.
Design patterns are useful for several reasons:
The MVC pattern provides several benefits, including:
Separation of concerns: The MVC pattern separates the application into different components, each with a specific responsibility. This makes the application easier to understand, develop, and maintain.
Reusability: The components of the MVC pattern can be reused in other applications, reducing the amount of code that needs to be written.
Flexibility: The MVC pattern allows for changes to be made to one component without affecting the other components, making the application more flexible and adaptable.
In conclusion, MVC is a design pattern used in software development to separate an application into three interconnected components: the model, the view, and the controller. It provides several benefits, including separation of concerns, reusability, and flexibility.
Singleton:
The Singleton pattern is a creational pattern that ensures a class has only one instance, while providing a global point of access to this instance. This pattern is useful in situations where you need to ensure that only one instance of a class exists, such as when managing resources that are shared across the entire application.
Factory Method:
The Factory Method is a creational pattern that provides an interface for creating objects in a superclass, but allows subclasses to alter the type of objects that will be created. This pattern is useful in situations where you want to delegate the creation of objects to subclasses, and you want to ensure that the correct type of object is created for a given use case.
[121. Best Time to Buy and Sell Stock][https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/]
class Solution {
public int maxProfit(int[] prices) {
int min = prices[0], maxPro = 0;
for(int price : prices){
min = Math.min(min, price);
maxPro = Math.max(maxPro, price - min);
}
return maxPro;
}
}class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
Arrays.sort(intervals, Comparator.comparingInt(a ->a[0]));
int[] subRes =intervals[0];
for(int i = 1; i < intervals.length; i++){
int[] cur = intervals[i];
if(cur[0] <= subRes[1]){
subRes[1] = Math.max(subRes[1], cur[1]);
}else{
res.add(subRes);
subRes = cur;
}
}
res.add(subRes);
return res.toArray(new int[res.size()][]);
}
}class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
List<int[]> merged = new ArrayList<int[]>();
for (int i = 0; i < intervals.length; ++i) {
int L = intervals[i][0], R = intervals[i][1];
System.out.println("L = " + L + " R = "+ R);
System.out.println("merged.size = " + merged.size() );
if(merged.size() >0){
System.out.println("merged.get(merged.size() - 1)[1] = " + merged.get(merged.size() - 1)[1] );
}
if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
return merged.toArray(new int[merged.size()][]);
}
}class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
intervals.sort(key = lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(interval[1], merged[-1][1])
return mergedclass Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
Arrays.sort(intervals, Comparator.comparingInt(a ->a[0]));
int[] subRes =intervals[0];
for(int i = 1; i < intervals.length; i++){
int[] cur = intervals[i];
if(cur[0] <= subRes[1]){
subRes[1] = Math.max(subRes[1], cur[1]);
}else{
res.add(subRes);
subRes = cur;
}
}
res.add(subRes);
return res.toArray(new int[res.size()][]);
}
}class Solution {
private List<List<Integer>> result;
private List<Integer> path;
public List<List<Integer>> combine(int n, int k) {
result = new ArrayList<>();
path = new ArrayList<>();
backtracking(n, k, 1);
return result;
}
private void backtracking (int n, int k, int start){
if(path.size() == k){
result.add(new ArrayList<>(path));
return;
}
for (int i = start ; i <= n; i++){
path.add(i);
System.out.println(i);
backtracking(n, k, i+1);
path.remove(path.size() - 1); //backtracking : return to the last step
}
}
}class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> valueMap = new HashMap<>();
for(int i = 0; i < nums.length; i++)
valueMap.put(nums[i], i);
for(int i = 0; i < nums.length; i++)
if(valueMap.containsKey(target - nums[i]) &&valueMap.get(target - nums[i]) != i) return new int[]{i, valueMap.get(target - nums[i])};
return new int[]{0, 0};
}
}Introduction:
Character encoding is the process of converting a sequence of characters into a sequence of bytes that can be stored or transmitted over a network. Character encoding is necessary because computers use binary data to represent information, but characters are not naturally represented in binary form.
Character Sets:
A character set is a collection of characters and symbols used by a particular writing system or language. Character sets typically include the letters of the alphabet, numbers, punctuation marks, and other symbols.
Character Encoding Standards:
A character encoding standard is a standardized method of mapping characters from a character set to binary data. Some of the most widely used character encoding standards include ASCII, ISO-8859, GB2312, Big5, and Unicode.
Character Encoding Schemes:
A character encoding scheme is a specific implementation of a character encoding standard. For example, UTF-8 is a character encoding scheme that implements the Unicode character encoding standard.
Character Encoding in Web Applications:
In web applications, character encoding is used to encode text data that is transmitted over the Internet. The default character encoding for web pages is UTF-8, but other character encoding standards can be used if specified in the HTML document.
Character Encoding in File Formats:
Character encoding is also used in file formats, such as text files, XML files, and CSV files. The character encoding used in a file is typically specified in the file header or specified when the file is opened.
Character Encoding in Databases:
In databases, character encoding is used to store text data in a way that can be retrieved and used by applications. The character encoding used in a database is typically specified when the database is created, and it can be different for different columns or tables within the same database.
In conclusion, character encoding is an important aspect of working with text data, and it is used in a variety of applications and file formats. Understanding character encoding standards, schemes, and character sets is essential for working with text data in a consistent and interoperable way.
XML (Extensible Markup Language) is a markup language used for encoding and storing data in a structured format. It is a text-based format that uses tags to describe the structure of the data, making it human-readable and easy to parse.
XML files are commonly used for a variety of purposes, including:
Data storage: XML is often used as a data storage format, as it provides a way to store structured data that can be easily read and written by both humans and computers.
Data exchange: XML is widely used for exchanging data between different systems, as it provides a common format that can be understood by a variety of platforms and technologies.
Configuration files: XML is often used as a format for configuration files, as it provides a way to store configuration data in a structured and easily readable format.
Document markup: XML is used in many document markup languages, including XHTML and Office Open XML, to define the structure and content of documents.
In conclusion, XML is a versatile and widely-used markup language that is used for a variety of purposes, including data storage, data exchange, configuration files, and document markup. It provides a structured format for encoding and storing data that can be easily read and written by both humans and computers.
class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length()-1;
while(left <= right){
while(left < s.length() &&! Character.isLetterOrDigit(s.charAt(left))){
left++;
}
while(right >= 0 && ! Character.isLetterOrDigit(s.charAt(right))){
right--;
}
if(left >= right) break;
// System.out.println(s.charAt(left)+" "+s.charAt(right));
if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
left++;
right--;
}
return true;
//24min
}
}There are m jobs to schedule on n processors.
A schedule is balanced if the difference between the number of jobs scheduled on any two neighboring processors does not exceed 1.
The k th processor is the most efficient, and thus, the maximum number of jobs should be scheduled on that processor.
Find the maximum number of jobs that can be scheduled on the k th processor, such that the overall schedule remains balanced.
Note: Each processor must have at least one job scheduled Example Consider n=5, m=11, k=3.
package org.example;
public class weRideOA1 {
public static void main(String[] args) {
//int a = getMaximumJobs(5, 14, 2);
System.out.println(getMaximumJobs(5, 11, 5));
//4
}
static int getMaximumJobs (int n, int m, int k){
// : number of processor
// Visualization of how array builds up (for k = 2, n = 5, m = 16) in the above code
// 1 1 1 1 1 --> Sum is less than m = 16 - OK
// 1 2 1 1 1 --> Sum is less than m = 16 - OK
// 2 3 2 1 1 --> Sum is less than m = 16 - OK
// 3 4 3 2 1 --> Sum is less than m = 16 - OK
// 4 5 4 3 2 ---> sum is 18, greater than m. Hence answer is previous value for kth element, which is 4
k--;
int arr [] = new int[n];
for(int i = 0; i < n; i++ ) arr[i] = 1;
int sum = n, maxjob = 1;
while( ++sum <= m){
maxjob = ++arr[k];
System.out.print("pre");
for(int i : arr){
System.out.print(i+" ");
}
System.out.println(" ");
for(int i = k - 1; i >= 0; i--){
if((arr[i + 1] - arr[i] ) > 1){
arr[i] ++;
sum ++;
}
}
for(int i = k + 1; i < n; i++){
if((arr[i -1] - arr[i]) > 1){
arr[i] ++;
sum ++;
}
}
for(int i : arr){
System.out.print(i+" ");
}
System.out.println("sum = " +sum);
System.out.println(" ");
}
return maxjob;
}
}
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> ans = new ArrayList<>();
HashMap<String, List> map = new HashMap<>();
for(String subStr : strs){
char[] charArr = subStr.toCharArray();
Arrays.sort(charArr);
String sortedStr = new String(charArr);
if(!map.containsKey(sortedStr)){
map.put(sortedStr,new ArrayList<String>());
}
map.get(sortedStr).add(subStr);
}
for(List a : map.values()){
ans.add(a);
}
return ans;
}
}
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.