Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
The value k is positive and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 104
Absolute value of elements in the array and x will not exceed 104
public List<Integer> findClosestElements(int[] arr, int k, int x){ int upperIdx = firstEqualOrGreater(arr, x); int lowerIdx = upperIdx-1; List result = new ArrayList(); for(int i=k;i>0;i--){ if(lowerIdx<0) result.add(arr[upperIdx++]); elseif(upperIdx>=arr.length) result.add(arr[lowerIdx--]); elseif(x-arr[lowerIdx]<=arr[upperIdx]-x) result.add(arr[lowerIdx--]); else result.add(arr[upperIdx++]); } Collections.sort(result); return result; }
publicintfirstEqualOrGreater(int[] a, int key){ int lo = 0, hi = a.length-1; while(lo<=hi){ int mid = lo + (hi - lo) / 2; if(a[mid]<key) lo = mid+1; else hi = mid-1; } return lo; }
Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4 The longest increasing path is [1, 2, 6, 9].
Example 2:
nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
deflongestIncreasingPath(self, matrix: List[List[int]]) -> int: ary = [] for i in range(len(matrix)): for j in range(len(matrix[0])): ary.append((matrix[i][j], i, j)) ary.sort() dp = [[1for _ in range(len(matrix[0]))] for _ in range(len(matrix))] for val, _x, _y in ary: for _dx, _dy in OFFSETS: x, y = _x + _dx, _y + _dy if x < 0or x >= len(matrix) or y < 0or y >= len(matrix[0]): continue if matrix[x][y] > matrix[_x][_y]: dp[x][y] = max(dp[x][y], dp[_x][_y] + 1) return max(map(max, dp))
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
Example 2: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Return ["JFK","ATL","JFK","SFO","ATL","SFO"]. Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
deffindItinerary2(self, tickets: List[List[str]]) -> List[str]: graph = collections.defaultdict(list) for li in tickets: graph[li[0]].append(li[1]) for li in graph.values(): li.sort() path, res = ['JFK'], [] self.dfs2(graph, 'JFK', len(tickets), path, res) return res[0]
defdfs2(self, graph, start, ticket_left, path, res): if ticket_left == 0: res.append(list(path)) # remember returnTrue for i, neighbor in enumerate(graph[start]): path.append(neighbor) graph[start].pop(i) # remember if self.dfs2(graph, neighbor, ticket_left - 1, path, res): returnTrue graph[start].insert(i, neighbor) path.pop() returnFalse
